עסקאות ומנגנוני הבקרה שלהן

עסקות

עסקה היא רצף של פעולות על נתונים שיש להם התחלה וסוף.

עסקה היא ביצוע רציף של פעולות קריאה וכתיבה. סיום העסקה יכול להיות שמירת השינויים (התחייבות) או ביטול השינויים (החזרה). ביחס למסד נתונים, עסקה מורכבת ממספר בקשות המטופלות כבקשה אחת.

עסקאות חייבות לעמוד במאפייני ACID

אָטוֹמִיוּת. העסקה הושלמה לחלוטין או לא בכלל.

עֲקֵבִיוּת. בעת השלמת עסקה, אין להפר את ההגבלות המוטלות על הנתונים (למשל אילוצים במאגר). עקביות מרמזת שהמערכת תועבר ממצב נכון אחד למצב תקין אחר.

בידוד. עסקאות הפועלות במקביל לא אמורות להשפיע זו על זו, למשל, שינוי נתונים המשמשים עסקה אחרת. התוצאה של ביצוע עסקאות מקבילות צריכה להיות זהה כאילו העסקאות בוצעו ברצף.

קיימות. לאחר התחייבות, אין לאבד שינויים.

יומן עסקאות

היומן מאחסן שינויים שנעשו על ידי עסקאות, מבטיח אטומיות ויציבות של נתונים במקרה של כשל במערכת

היומן מכיל את הערכים שהיו לנתונים לפני ואחרי שהם שונו על ידי העסקה. אסטרטגיית יומן כתיבה קדימה מחייבת הוספת רישום יומן על ערכים קודמים לפני ההתחלה, ועל ערכים סופיים לאחר השלמת העסקה. במקרה של עצירה פתאומית של המערכת, בסיס הנתונים קורא את היומן בסדר הפוך ומבטל את השינויים שבוצעו בעסקאות. לאחר שנתקל בעסקה מופרעת, מסד הנתונים מבצע אותה ומבצע בה שינויים ביומן. בהיותו במצב בזמן התקלה, מסד הנתונים קורא את היומן בהזמנה קדימה ומחזיר את השינויים שבוצעו על ידי עסקאות. כך נשמרת היציבות של עסקאות שכבר בוצעו והאטומיות של העסקה שנקטעה.

פשוט ביצוע מחדש של עסקאות שנכשלו אינו מספיק לשחזור.

דוגמא. למשתמש יש 500$ בחשבון שלו והמשתמש מחליט למשוך אותם מכספומט. שתי עסקאות מתבצעות. הראשון קורא את ערך היתרה ואם יש מספיק כספים על היתרה, הוא מנפיק כסף למשתמש. השני מפחית מהיתרה את הסכום הנדרש. נניח שהמערכת קרסה והפעולה הראשונה נכשלה, אבל השנייה כן. במקרה זה, לא נוכל להנפיק כסף מחדש למשתמש מבלי להחזיר את המערכת למצבה המקורי עם יתרה חיובית.

רמות בידוד

קרא מחויב

הבעיה של Dirty Read היא שעסקה יכולה לקרוא את תוצאת הביניים של עסקה אחרת.

דוגמא. ערך היתרה הראשוני הוא $0. T1 מוסיף $50 ליתרה שלך. T2 קורא את ערך היתרה ($50). T1 מבטל את השינויים ויוצא. T2 ממשיך בביצוע עם נתוני איזון שגויים.

הפתרון הוא קריאת נתונים קבועים (Read Committed), האוסר לקרוא נתונים שהשתנו בעסקה. אם עסקה א' שינתה קבוצה מסוימת של נתונים, אז עסקה ב', בעת גישה לנתונים אלו, נאלצת להמתין לסיום העסקה א'.

קריאה חוזרת

בעיית עדכונים אבודים. T1 שומר שינויים על השינויים של T2.

דוגמא. ערך היתרה הראשוני הוא $0 ושתי עסקאות בו זמנית ממלאות את היתרה. T1 ו-T2 קוראים יתרה של $0. לאחר מכן T2 מוסיף $200 ל-$0 ושומר את התוצאה. T1 מוסיף $100 ל$0 ושומר את התוצאה. התוצאה הסופית היא $100 במקום $300.

בעיית קריאה בלתי חוזרת. קריאה חוזרת של אותם נתונים מחזירה ערכים שונים.

דוגמא. T1 קורא ערך יתרה של $0. לאחר מכן T2 מוסיף 50$ ליתרה ומסתיים. T1 קורא שוב את הנתונים ומוצא אי התאמה לתוצאה הקודמת.

קריאה חוזרת מבטיחה שקריאה שנייה תחזיר את אותה תוצאה. לא ניתן לשנות נתונים שנקראו על ידי עסקה אחת באחרות עד להשלמת העסקה. אם עסקה א' קראה קבוצה מסוימת של נתונים, אז עסקה ב', בעת גישה לנתונים אלו, נאלצת להמתין עד להשלמת עסקה א'.

קריאה מסודרת (ניתן לסדרה)

בעיה ב-Phantom Reads. שתי שאילתות שבוחרות נתונים על סמך תנאי מסוים מחזירות ערכים שונים.

דוגמא. T1 מבקש את מספר כל המשתמשים שהיתרה שלהם גדולה מ-$0 אך פחות מ-$100. T2 מנכה $1 ממשתמש עם יתרה של $101. T1 מוציאה מחדש את הבקשה.

קריאה מסודרת (ניתן להסדרה). עסקאות מבוצעות ברצף לחלוטין. חל איסור לעדכן או להוסיף רשומות העומדות בתנאי הבקשה. אם עסקה א' ביקשה נתונים מכל הטבלה, אז הטבלה כולה מוקפאת עבור טרנזקציות אחרות עד להשלמת עסקה א'.

מתזמן

מגדיר את הסדר שבו יש לבצע פעולות במהלך עסקאות מקבילות.

מספק רמת בידוד מוגדרת. אם התוצאה של פעולות לא תלויה בסדר שלהן, אז פעולות כאלה הן קומוטטיביות (Permutable). פעולות קריאה ופעולות על נתונים שונים הן קומוטטיביות. פעולות קריאה-כתיבה וכתיבה-כתיבה אינן קומוטטיביות. המשימה של המתזמן היא לשלב פעולות המבוצעות על ידי טרנזקציות מקבילות כך שתוצאת הביצוע תהיה שוות ערך לביצוע רציף של טרנזקציות.

מנגנונים לשליטה בעבודות מקבילות (בקרת במקביל)

אופטימיות מבוססת על איתור ופתרון קונפליקטים, פסימיות מבוססת על מניעת היווצרות קונפליקטים.

בגישה האופטימית, לרשות מספר משתמשים עומדים עותקים של הנתונים. האדם הראשון שהשלים את העריכה שומר את השינויים, בעוד האחרים חייבים למזג את השינויים. אלגוריתם אופטימי מאפשר לקונפליקט להתרחש, אך המערכת חייבת להתאושש מהקונפליקט.

בגישה פסימית, המשתמש הראשון שלוכד את הנתונים מונע מאחרים לקבל את הנתונים. אם קונפליקטים נדירים, כדאי לבחור באסטרטגיה האופטימית, מכיוון שהיא מספקת רמה גבוהה יותר של התאמה.

נְעִילָה

אם לעסקה אחת יש נתונים נעולים, עסקאות אחרות חייבות להמתין עד לביטול הנעילה בעת גישה לנתונים.

ניתן לכסות בלוק על מסד נתונים, טבלה, שורה או תכונה. ניתן להטיל את Shared Lock על אותם נתונים על ידי מספר עסקאות, מאפשרת לקרוא את כל העסקאות (כולל זו שהטילה אותה), אוסר על שינוי ולכידה בלעדית. ניתן להטיל מנעול בלעדי על ידי עסקה אחת בלבד, מאפשר כל פעולה של העסקה המטילה, אוסר על כל פעולה של אחרים.

מבוי סתום הוא מצב שבו עסקאות מסתיימות במצב ממתין שנמשך ללא הגבלת זמן.

דוגמא. העסקה הראשונה ממתינה לשחרור הנתונים שנלכדו על ידי השני, בעוד שהשנייה ממתינה לשחרור הנתונים שנלכדו על ידי הראשון.

פתרון אופטימי לבעיית הקיפאון מאפשר למבוי סתום להתרחש, אך לאחר מכן משחזר את המערכת על ידי ביטול אחת מהעסקאות הכרוכות במבוי סתום.

מחפשים מבוי סתום במרווחי זמן מסוימים. אחת משיטות הזיהוי היא לפי זמן, כלומר, קחו בחשבון שהתרחשה מבוי סתום אם העסקה לוקחת יותר מדי זמן להשלים. כאשר נמצא מבוי סתום, אחת מהעסקאות מתגלגלת לאחור, ומאפשרת להשלים עסקאות אחרות המעורבות במבוי סתום. בחירת הקורבן יכולה להתבסס על שווי העסקאות או הוותק שלהן (סכימות Wait-Die ו- Wound-wait).

כל עסקה T מוקצה חותמת זמן TS המכיל את שעת תחילת העסקה.

חכה-תמות.

אם TS(Ti) < TS(Tj), אז Ti מחכה, אחרת Ti מתגלגל אחורה ומתחיל שוב עם אותה חותמת זמן.

אם עסקה צעירה רכשה משאב ועסקה ישנה יותר מבקשת את אותו משאב, אז העסקה הישנה יותר רשאית להמתין. אם עסקה ישנה יותר רכשה משאב, אז העסקה הצעירה המבקשת משאב זה תוחזר לאחור.

פצע-המתנה.

אם TS(Ti) < TS(Tj), אז Tj מתגלגל אחורה ומתחיל שוב עם אותה חותמת זמן, אחרת Ti הַמתָנָה.

אם עסקה צעירה יותר רכשה משאב ועסקה ישנה יותר מבקשת את אותו משאב, אז העסקה הצעירה יותר תוחזר. אם עסקה ישנה יותר רכשה משאב, אז העסקה הצעירה המבקשת משאב זה מורשה להמתין. בחירת קורבן מבוססת קדימות מונעת מבוי סתום, אך מחזירה עסקאות שאינן מבוי סתום. הבעיה היא שניתן להחזיר עסקאות לאחור פעמים רבות כי... עסקה ישנה יותר עשויה להחזיק את המשאב במשך זמן רב.

פתרון פסימי לבעיית הקיפאון אינו מאפשר תחילת ביצוע עסקה אם קיים סיכון למבוי סתום.

כדי לזהות מבוי סתום, נבנה גרף (מחכה גרף, מחכה-לגרף), שקודקודיו הם טרנזקציות, והקצוות מופנים מעסקות הממתינות לשחרור נתונים לעסקה שתפסה את הנתונים הללו. מבוי סתום נחשב כאילו התרחש אם לגרף יש לולאה. בניית גרף המתנה, במיוחד במסדי נתונים מבוזרים, היא הליך יקר.

נעילה דו-שלבית - מונעת מבוי סתום על ידי תפיסת כל המשאבים שבהם השתמשו עסקה בתחילת העסקה ושחרורם בסופה

כל פעולות החסימה חייבות להקדים את הפתיחה הראשונה. יש לו שני שלבים - שלב הגידול, במהלכו מצטברות האחיזות, ו-Shrinking Phase, במהלכו משתחררים האחיזים. אם אי אפשר לתפוס את אחד המשאבים, העסקה מתחילה מחדש. ייתכן שעסקה לא תוכל לרכוש את המשאבים הנדרשים, למשל אם מספר עסקאות מתחרות על אותם משאבים.

commit דו-שלבי מבטיח שה-commit מבוצע בכל ההעתקים של מסד הנתונים

כל בסיס נתונים מזין מידע על הנתונים שישתנו ביומן ומשיב לרכז OK (שלב ההצבעה). לאחר שכולם הגיבו בסדר, הרכז שולח אות המחייב את כולם להתחייב. לאחר ההתחייבות, השרתים מגיבים בסדר; אם לפחות אחד לא מגיב בסדר, אז הרכז שולח אות לביטול השינויים לכל השרתים (שלב השלמה).

שיטת חותמת זמן

עסקה ישנה יותר מבוטלת כאשר מנסים לגשת לנתונים המעורבים בעסקה צעירה יותר

לכל עסקה מוקצית חותמת זמן TS מתאים לזמן ההתחלה של הביצוע. אם Ti ישן יותר Tj, אז TS(Ti) < TS(Tj).

כאשר עסקה מוחזרת לאחור, מוקצית לה חותמת זמן חדשה. כל אובייקט נתונים Q המעורבים בעסקה מסומן בשתי תוויות. W-TS(Q) - חותמת זמן של העסקה הצעירה ביותר שהשלימה רישום בהצלחה Q. R-TS(Q) - חותמת זמן של העסקה הצעירה ביותר שביצעה רשומת קריאה Q.

כאשר העסקה T בקשות לקריאת נתונים Q ישנן שתי אפשרויות.

אם TS(T) < W-TS(Q), כלומר, הנתונים עודכנו על ידי עסקה צעירה יותר, ולאחר מכן העסקה T מתגלגל לאחור.

אם TS(T) >= W-TS(Q), לאחר מכן מתבצעת הקריאה ו R-TS(Q) הוא הופך MAX(R-TS(Q), TS(T))‎.

כאשר העסקה T מבקש שינויים בנתונים Q ישנן שתי אפשרויות.

אם TS(T) < R-TS(Q)כלומר, הנתונים כבר נקראו על ידי עסקה צעירה יותר ואם יבוצע שינוי, ייווצר קונפליקט. עִסקָה T מתגלגל לאחור.

אם TS(T) < W-TS(Q), כלומר, העסקה מנסה לדרוס ערך חדש יותר, טרנזקציה T מבוטלת. במקרים אחרים, השינוי מתבצע ו W-TS(Q) הופך להיות שווה TS(T).

אין צורך בבניית גרף המתנה יקר. עסקאות ישנות יותר תלויות בעסקאות חדשות יותר, כך שאין מחזורים בגרף ההמתנה. אין מבוי סתום מכיוון שעסקאות לא ממתינות אלא מתגלגלות לאחור מיד. תיתכן החזרה מדורגת לאחור. אם Ti התגלגל ו Tj קראתי את הנתונים ששיניתי Ti, אז Tj צריך גם להתהפך. אם במקביל Tj כבר בוצע, אז תהיה פגיעה בעקרון היציבות.

אחד הפתרונות להחזרות מדורגות. עסקה משלימה את כל פעולות הכתיבה בסוף, ועסקאות אחרות חייבות להמתין לסיום הפעולה. עסקאות ממתינות לביצוע לפני קריאתן.

כלל כתיבה של תומס - גרסה של שיטת חותמת הזמן שבה נאסר על החלפת נתונים שעודכנו על ידי עסקה צעירה יותר על ידי ישנה יותר

עִסקָה T מבקש שינויים בנתונים Q. אם TS(T) < W-TS(Q), כלומר, העסקה מנסה לדרוס ערך חדש יותר, טרנזקציה T אינה מוחזרת לאחור כמו בשיטת חותמת הזמן.

מקור: www.habr.com