ברוכים הבאים לשיעור בנושא בקרת מקביליות, יחידה קריטית בקורס מערכות נתונים. בעולם שבו מספר רב של משתמשים ויישומים ניגשים ומשנים נתונים במקביל, שמירה על עקביות ושלמות הנתונים היא אתגר מהותי. שיעור זה יתמקד בפתרון בעיות מקביליות באמצעות פרוטוקולי נעילה וחותמות זמן, שהם אבני יסוד בתכנון מערכות בסיסי נתונים. נבין את העקרונות, המנגנונים וההשלכות של גישות אלו, תוך התייחסות לאופן שבו הן מבטיחות את תכונת ה-Isolation (בידוד) של טרנזקציות.
מבוא לבקרת מקביליות ואנומליות
טרנזקציה היא יחידת עבודה לוגית אחת, המכילה סדרה של פעולות על בסיס הנתונים (קריאה, כתיבה). כדי להבטיח את שלמות הנתונים, טרנזקציות צריכות לקיים את תכונות ה-ACID. בקרת מקביליות עוסקת בעיקר בתכונת ה-Isolation, ומבטיחה שביצוע מקבילי של טרנזקציות יפיק תוצאות זהות לביצוע סדרתי כלשהו שלהן (Serializability).
אנומליות נפוצות בביצוע מקבילי
כאשר טרנזקציות מתבצעות במקביל ללא בקרת מקביליות מתאימה, עלולות להיווצר אנומליות הפוגעות בעקביות הנתונים:
- עדכון אבוד (Lost Update): טרנזקציה אחת מבצעת עדכון, וטרנזקציה אחרת דורסת אותו מבלי שהטרנזקציה הראשונה סיימה את פעולתה.
- קריאה מלוכלכת (Dirty Read): טרנזקציה קוראת נתון שטרנזקציה אחרת כתבה, אך טרנזקציה זו טרם ביצעה Commit (ולאחר מכן היא מבצעת Rollback).
- קריאה לא חוזרת (Unrepeatable Read): טרנזקציה קוראת נתון פעמיים, ובין שתי הקריאות טרנזקציה אחרת משנה את הנתון ומבצעת Commit.
- קריאת רפאים (Phantom Read): טרנזקציה מבצעת שאילתת טווח פעמיים, ובין שתי הקריאות טרנזקציה אחרת מוסיפה או מוחקת רשומות בטווח.
פרוטוקולי נעילה
פרוטוקולי נעילה הם הגישה הנפוצה ביותר לבקרת מקביליות. הם מבוססים על הרעיון שטרנזקציה חייבת לרכוש נעילה על פריט נתונים לפני שהיא יכולה לגשת אליו. קיימים שני סוגי נעילות עיקריים:
- נעילה משותפת (Shared Lock - S): מאפשרת קריאה. מספר טרנזקציות יכולות להחזיק נעילה משותפת על אותו פריט בו-זמנית.
- נעילה בלעדית (Exclusive Lock - X): מאפשרת קריאה וכתיבה. רק טרנזקציה אחת יכולה להחזיק נעילה בלעדית על פריט נתונים נתון בכל רגע נתון.
פרוטוקול נעילה דו-שלבי (Two-Phase Locking - 2PL)
2PL הוא פרוטוקול נעילה שמבטיח Serializability. הוא מחלק את חיי הטרנזקציה לשני שלבים:
- שלב הגדילה (Growing Phase): הטרנזקציה יכולה לרכוש נעילות חדשות, אך אינה יכולה לשחרר אף נעילה.
- שלב ההתכווצות (Shrinking Phase): הטרנזקציה יכולה לשחרר נעילות, אך אינה יכולה לרכוש נעילות חדשות.
נקודת המעבר בין השלבים נקראת "נקודת הנעילה" (Lock Point). ברגע שטרנזקציה משחררת נעילה, היא נכנסת לשלב ההתכווצות ואינה יכולה לרכוש נעילות נוספות.
קיפאון (Deadlock)
אחד החסרונות המרכזיים של פרוטוקולי נעילה הוא הפוטנציאל לקיפאון. קיפאון מתרחש כאשר שתי טרנזקציות או יותר ממתינות זו לזו לשחרר נעילות, ויוצרות מעגל המתנה.
מניעת קיפאון
שיטות שמונעות מראש היווצרות קיפאון, למשל: דרישת רכישת כל הנעילות מראש, או שימוש באלגוריתמים כמו Wait-Die ו-Wound-Wait המבוססים על חותמות זמן של טרנזקציות.
זיהוי וטיפול בקיפאון
מערכת ה-DB מזהה קיפאון באמצעות גרף המתנה (Wait-For Graph), וברגע שמעגל מזוהה, היא בוחרת "קורבן" (טרנזקציה אחת) לבצע עליה Rollback כדי לשבור את המעגל.
פרוטוקולי חותמות זמן
פרוטוקולי חותמות זמן מציעים גישה חלופית לבקרת מקביליות, המבוססת על הקצאת חותמת זמן ייחודית לכל טרנזקציה בעת התחלתה. חותמת זמן זו קובעת את הסדר הסדרתי הלוגי של הטרנזקציות.
פרוטוקול סדר חותמות זמן בסיסי (Basic Timestamp Ordering - T/O)
כל פריט נתונים X שומר שתי חותמות זמן:
- Read_TS(X): חותמת הזמן הגבוהה ביותר של טרנזקציה שקראה את X.
- Write_TS(X): חותמת הזמן הגבוהה ביותר של טרנזקציה שכתבה את X.
כאשר טרנזקציה T עם חותמת זמן TS(T) מנסה לבצע פעולה:
- קריאה (Read(X)): אם TS(T)
- כתיבה (Write(X)): אם TS(T)
פרוטוקול זה מבטיח סדרתיות אך עלול לגרום לביטולים רבים של טרנזקציות.