כך נראית יתירות

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

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

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

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

1. המהות של קודי יתירות

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

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

כדי לשחזר את כל n בלוקים של נתונים, אתה צריך להיות לפחות n של n + m בלוקים, מכיוון שאינך יכול לקבל n בלוקים על ידי שיש לך רק n-1 בלוק (במקרה זה, תצטרך לקחת בלוק 1 "מהדק" אוויר"). האם מספיקים n בלוקים אקראיים של n+m בלוקים כדי לשחזר את כל הנתונים? זה תלוי בסוג קודי היתירות, למשל, קודי ריד-סולומון מאפשרים לך לשחזר את כל הנתונים באמצעות n בלוקים שרירותיים, אך לא תמיד קודי יתירות של LRC.

אחסון נתונים

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

העברת נתונים

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

* ישנם גם קודי יתירות שבהם הנתונים אינם מחולקים לבלוקים, כגון קודי Hamming ו-CRC, שנמצאים בשימוש נרחב להעברת נתונים ברשתות Ethernet. אלו הם קודים לקידוד תיקון שגיאות, הם נועדו לזהות שגיאות, ולא לתקן אותן (קוד האמינג מאפשר גם תיקון חלקי של שגיאות).

2. קודי ריד-שלמה

קודי ריד-סולומון הם אחד מקודי היתירות הנפוצים ביותר, שהומצאו עוד בשנות ה-1960 ונעשה בו שימוש נרחב לראשונה בשנות ה-1980 לייצור המוני של דיסקים קומפקטיים.

ישנן שתי שאלות מפתח להבנת קודי ריד-סולומון: 1) כיצד ליצור בלוקים של קודי יתירות; 2) כיצד לשחזר נתונים באמצעות בלוקים של קוד יתירות. בואו נמצא להם תשובות.
לשם הפשטות, עוד נניח ש-n=6 ו-m=4. תוכניות אחרות נחשבות באנלוגיה.

כיצד ליצור בלוקים של קוד יתירות

כל בלוק של קודי יתירות נספר ללא תלות באחרים. כל n בלוקי הנתונים משמשים לספירת כל בלוק. בתרשים שלהלן, X1-X6 הם בלוקי נתונים, P1-P4 הם בלוקי קוד יתירות.

כל בלוקי הנתונים חייבים להיות באותו גודל, וניתן להשתמש באפס סיביות ליישור. בלוקי קוד היתירות שיתקבלו יהיו באותו גודל כמו בלוקי הנתונים. כל בלוקי הנתונים מחולקים למילים (לדוגמה, 16 סיביות). נניח שאנו מפצלים את בלוקי הנתונים ל-k מילים. אז כל בלוקים של קודי יתירות יחולקו גם ל-k מילים.

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

כאן הערכים x הם המילים של בלוקי נתונים, p הם המילים של בלוקי קוד יתירות, כל אלפא, בטא, גמא ודלתא הם מספרים שנבחרו במיוחד שהם זהים עבור כל i. יש לומר מיד שכל הערכים הללו אינם מספרים רגילים, אלא אלמנטים של שדה גלואה; הפעולות +, -, *, / אינן פעולות המוכרות לכולנו, אלא פעולות מיוחדות שהוכנסו על אלמנטים של הגלואה. שדה.

מדוע נחוצים שדות גלואה?

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

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

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

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

שדות Galois* הם שדות שעבורם יש תוצאה ייחודית של כל פעולה (+, -, *, /) עבור כל שני אלמנטים של השדה. ניתן לבנות שדות גלואה למספרים שהם חזקה של 2: 2, 4, 8, 16 וכו' (בעצם חזקות של כל מספר ראשוני p, אבל בפועל אנחנו מעוניינים רק בחזקות 2). לדוגמה, עבור מילים של 16 סיביות, זהו שדה המכיל 65 אלמנטים, שלכל זוג מהם ניתן למצוא את התוצאה של כל פעולה (+, -, *, /). הערכים של x, p, alpha, beta, gamma, delta מהמשוואות לעיל ייחשבו כאלמנטים של שדה Galois לחישובים.

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

* זו לא הגדרה נוקשה, אלא תיאור.

כיצד לשחזר נתונים

יש צורך בשחזור כאשר חלק מהבלוקים של n+m חסרים. אלה יכולים להיות גם בלוקים של נתונים וגם בלוקים של קוד יתירות. היעדר בלוקי נתונים ו/או בלוקים של קוד יתירות יגרום לכך שהמשתנים המתאימים x ו/או p אינם ידועים במשוואות לעיל.

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

לדוגמה, תן לבלוק הנתונים 1, 2, 3 ולגוש קוד יתירות 2 להיות לא זמינים, ואז עבור קבוצת המילים ה-i תהיה מערכת המשוואות הבאה (לא ידועים מסומנים באדום):

יש לנו מערכת של 4 משוואות עם 4 לא ידועים, מה שאומר שאנחנו יכולים לפתור אותה ולשחזר את הנתונים!

ממערכת משוואות זו עולות מספר מסקנות לגבי שחזור נתונים עבור קודי ריד-סולומון (n בלוקי נתונים, m בלוקים של קוד יתירות):

• ניתן לשחזר נתונים אם יאבדו כל מ בלוקים או פחות. אם m+1 או יותר בלוקים אובדים, לא ניתן לשחזר את הנתונים: אי אפשר לפתור מערכת של m משוואות עם m + 1 לא ידועים.
• כדי לשחזר אפילו בלוק נתונים אחד, עליך להשתמש בכל n מהבלוקים הנותרים, ותוכל להשתמש בכל אחד מקודי היתירות.

מה עוד אתה צריך לדעת

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

• מערכת המשוואות עבור קודי ריד-סולמון חייבת להיות בעלת פתרון (ייחודי) לכל שילוב של לא ידועים (לא יותר מ-m לא ידועים). בהתבסס על דרישה זו, הערכים של אלפא, בטא, גמא ודלתא נבחרים.
• מערכת משוואות חייבת להיות מסוגלת להיבנות אוטומטית (תלוי באילו בלוקים אינם זמינים) ולפתור אותה.
• אנחנו צריכים לבנות שדה Galois: עבור גודל מילה נתון, להיות מסוגל למצוא את התוצאה של כל פעולה (+, -, *, /) עבור כל שני אלמנטים.

בסוף המאמר יש הפניות לספרות בנושאים חשובים אלו.

בחירה של n ו-m

איך בוחרים n ו-m בפועל? בפועל, במערכות אחסון נתונים משתמשים בקודי יתירות כדי לחסוך במקום, כך ש-m תמיד נבחר פחות מ-n. הערכים הספציפיים שלהם תלויים במספר גורמים, כולל:

• אמינות אחסון נתונים. ככל ש-m גדול יותר, מספר תקלות הדיסק שניתן לשרוד גדול יותר, כלומר, האמינות גבוהה יותר.
• אחסון מיותר. ככל שיחס ה-m/n גבוה יותר, כך יתירות האחסון תהיה גבוהה יותר, והמערכת יקרה יותר.
• בקש זמן עיבוד. ככל שהסכום n+m גדול יותר, זמן התגובה לבקשות יהיה ארוך יותר. מכיוון שקריאת נתונים (במהלך התאוששות) דורשת קריאה של n בלוקים המאוחסנים ב-n דיסקים שונים, זמן הקריאה ייקבע לפי הדיסק האיטי ביותר.

בנוסף, אחסון נתונים במספר DCs מטיל הגבלות נוספות על הבחירה של n ו-m: אם 1 DC כבוי, הנתונים עדיין חייבים להיות זמינים לקריאה. לדוגמה, בעת אחסון נתונים ב-3 DC, יש לעמוד בתנאי הבא: m >= n/2, אחרת עלול להיות מצב שהנתונים אינם זמינים לקריאה כאשר 1 DC כבוי.

3. LRC - קודי שחזור מקומיים

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

השגיאות הנפוצות ביותר הן חוסר נגישות של גוש נתונים אחד עקב כשל או עומס יתר של דיסק אחד. האם ניתן איכשהו להפחית את העומס העודף לשחזור נתונים במקרה זה (הנפוץ ביותר)? מסתבר שאתה יכול: ישנם קודי יתירות של LRC במיוחד למטרה זו.

LRC (קודי שחזור מקומיים) הם קודי יתירות שהומצאו על ידי מיקרוסופט לשימוש ב-Windows Azure Storage. הרעיון של LRC הוא פשוט ככל האפשר: חלק את כל גושי הנתונים לשתי (או יותר) קבוצות וקרא חלק מגושי קוד היתירות עבור כל קבוצה בנפרד. אז כמה בלוקים של קוד יתירות ייספרו באמצעות כל בלוקי הנתונים (ב-LRC הם נקראים קודי יתירות גלובליים), וחלקם - באמצעות אחת משתי קבוצות של בלוקי נתונים (הם נקראים קודי יתירות מקומיים).

LRC מסומן בשלושה מספרים: nrl, כאשר n הוא מספר בלוקי הנתונים, r הוא מספר בלוקי קוד היתירות הגלובלית, l הוא מספר בלוקי קוד היתירות המקומיים. כדי לקרוא נתונים כאשר בלוק נתונים אחד אינו זמין, עליך לקרוא רק n/l בלוקים - זה פי XNUMX פחות מאשר בקודי ריד-סולומון.

לדוגמה, שקול את ערכת LRC 6-2-2. X1–X6 — 6 בלוקי נתונים, P1, P2 — 2 בלוקים של יתירות גלובלית, P3, P4 — 2 בלוקים של יתירות מקומית.

בלוקים של קוד יתירות P1, P2 נספרים באמצעות כל בלוקי הנתונים. בלוק קוד יתירות P3 - באמצעות בלוקי נתונים X1-X3, בלוק קוד יתירות P4 - באמצעות בלוקי נתונים X4-X6.

השאר נעשה ב-LRC באנלוגיה לקודי ריד-סולומון. המשוואות לספירת המילים של בלוקי קוד יתירות יהיו:

כדי לבחור את המספרים אלפא, בטא, גמא, דלתא, יש לעמוד במספר תנאים כדי להבטיח את האפשרות לשחזור נתונים (כלומר, פתרון מערכת המשוואות). תוכל לקרוא עליהם עוד ב статье.
גם בפועל, פעולת XOR משמשת לחישוב קודי יתירות מקומיים P3, P4.

מספר מסקנות נובעות ממערכת המשוואות עבור LRC:

• כדי לשחזר כל בלוק נתונים אחד, זה מספיק לקרוא n/l בלוקים (n/1 בדוגמה שלנו).
• אם בלוקים r + l אינם זמינים, וכל הבלוקים כלולים בקבוצה אחת, לא ניתן לשחזר את הנתונים. קל להסביר זאת בעזרת דוגמה. תן לבלוקים X1–X3 ו-P3 להיות לא זמינים: אלה הם בלוקים r + l מאותה קבוצה, 4 במקרה שלנו. אז יש לנו מערכת של 3 משוואות עם 4 לא ידועים שלא ניתן לפתור.
• בכל שאר המקרים של חוסר זמינות של בלוקים r + l (כאשר לפחות בלוק אחד זמין מכל קבוצה), ניתן לשחזר את הנתונים ב-LRC.

לפיכך, LRC מתעלה על קודי Reed-Solomon בשחזור נתונים לאחר שגיאות בודדות. בקודי Reed-Solomon, כדי לשחזר אפילו בלוק נתונים אחד, אתה צריך להשתמש ב-n בלוקים, וב-LRC, כדי לשחזר בלוק אחד של נתונים, מספיק להשתמש ב-n/l בלוקים (n/2 בדוגמה שלנו). מצד שני, LRC נחות מקודי ריד-סולומון מבחינת המספר המרבי של שגיאות מותרות. בדוגמאות שלמעלה, קודי ריד-סולומון יכולים לשחזר נתונים עבור כל 4 שגיאות, ועבור LRC יש 2 שילובים של 4 שגיאות כאשר לא ניתן לשחזר נתונים.

מה שחשוב יותר תלוי במצב הספציפי, אבל לרוב החיסכון בעומס העודף ש-LRC מספק עולה על האחסון המעט פחות אמין.

4. קודי יתירות אחרים

מלבד קודי Reed-Solomon ו-LRC, ישנם קודי יתירות רבים אחרים. קודי יתירות שונים משתמשים במתמטיקה שונה. הנה כמה קודי יתירות אחרים:

• קוד יתירות באמצעות האופרטור XOR. פעולת ה-XOR מבוצעת על n בלוקים של נתונים, ומתקבל בלוק אחד של קודי יתירות, כלומר, סכימת n+1 (n בלוקי נתונים, קוד יתירות אחד). בשימוש ב RAID 5, שבו בלוקים של נתונים וקודי יתירות נכתבים באופן מחזורי לכל הדיסקים של המערך.
• אלגוריתם זוגי-אי זוגי מבוסס על פעולת XOR. מאפשר לך לבנות 2 בלוקים של קודי יתירות, כלומר, ערכת n+2.
• אלגוריתם STAR מבוסס על פעולת XOR. מאפשר לך לבנות 3 בלוקים של קודי יתירות, כלומר, ערכת n+3.
• קודי פירמידה הם עוד קודי יתירות מבית מיקרוסופט.

5. השתמש ב- Yandex

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

• אחסון אובייקטים פנימי של MDS, עליו כתבתי בתחילת המאמר.
• YT - מערכת MapReduce של Yandex.
• YDB (Yandex DataBase) - מסד נתונים מבוזר של newSQL.

MDS משתמש בקודי יתירות LRC, סכימת 8-2-2. נתונים עם קודי יתירות נכתבים ל-12 דיסקים שונים בשרתים שונים ב-3 DCs שונים: 4 שרתים בכל DC. קרא עוד על זה ב статье.

YT משתמש גם בקודי Reed-Solomon (Scheme 6-3), שהיו הראשונים ליישם, וגם בקודי יתירות LRC (Scheme 12-2-2), כאשר LRC היא שיטת האחסון המועדפת.

YDB משתמש בקודי יתירות מבוססי זוגיות (איור 4-2). על קודי יתירות ב-YDB כבר סיפר ​​ב-Highload.

השימוש בסכימות קוד יתירות שונות נובע מדרישות שונות למערכות. לדוגמה, ב-MDS, נתונים המאוחסנים באמצעות LRC ממוקמים ב-3 DCs בו-זמנית. חשוב לנו שהנתונים יישארו זמינים לקריאה אם ​​1 מתוך DCs נכשל, לכן יש לחלק את הבלוקים על פני DCs כך שאם DC כלשהו אינו זמין, מספר הבלוקים הבלתי נגישים אינו עולה על המותר. בסכמת 8-2-2, אתה יכול למקם 4 בלוקים בכל DC, ואז כאשר כל DC כבוי, 4 בלוקים לא יהיו זמינים, וניתן יהיה לקרוא את הנתונים. לא משנה באיזו סכמה שנבחר כאשר שמים אותו ב-3 DCs, בכל מקרה צריך להיות (r + l) / n >= 0,5, כלומר, יתירות האחסון תהיה לפחות 50%.

ב-YT המצב שונה: כל אשכול YT ממוקם כולו ב-1 DC (אשכולות שונים ב-DCs שונים), כך שאין הגבלה כזו. תכנית 12-2-2 מספקת יתירות של 33%, כלומר, אחסון נתונים זול יותר, והיא יכולה גם לשרוד עד 4 הפסקות דיסק בו-זמנית, בדיוק כמו תכנית ה-MDS.

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

6. קישורים

1. סדרת מאמרים על קודי ריד-שלמה ושדות גלואה: https://habr.com/ru/company/yadro/blog/336286/
   https://habr.com/ru/company/yadro/blog/341506/
   הם בוחנים לעומק את המתמטיקה בשפה נגישה.
2. מאמר ממיקרוסופט על LRC: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/LRC12-cheng20webpage.pdf
   סעיף 2 מסביר בקצרה את התיאוריה ולאחר מכן דן בהתנסויות עם LRC בפועל.
3. סכימה זוגית-אי זוגית: https://people.eecs.berkeley.edu/~kubitron/courses/cs262a-F12/handouts/papers/p245-blaum.pdf
4. ערכת כוכבים: https://www.usenix.org/legacy/event/fast05/tech/full_papers/huang/huang.pdf
5. קודי פירמידה: https://www.microsoft.com/en-us/research/publication/pyramid-codes-flexible-schemes-to-trade-space-for-access-efficiency-in-reliable-data-storage-systems/
6. קודי יתירות ב-MDS: https://habr.com/ru/company/yandex/blog/311806
7. קודי יתירות ב-YT: https://habr.com/ru/company/yandex/blog/311104/
8. קודי יתירות ב-YDB: https://www.youtube.com/watch?v=dCpfGJ35kK8

מקור: www.habr.com