גיבוב עקבי מוסבר - Consistent Hashing¶
בפוסט על טבלת גיבוב הסברנו איך פונקציית גיבוב הופכת מפתח למספר, כדי לקפוץ ישר לתא הנכון בזיכרון. עכשיו תדמיינו שבמקום תא בזיכרון, אתם צריכים להחליט לאיזה שרת מתוך כמה עשרות שרתים לשלוח כל בקשה - כמו במאגר קאש מבוזר. השיטה הפשוטה ביותר נשברת בדיוק ברגע שהכי חשוב שהיא תעבוד, וזו הסיבה שהומצא גיבוב עקבי.
הגישה הנאיבית - למה היא נכשלת¶
הפתרון הראשון שכל אחד חושב עליו הוא פשוט - מחשבים hash מהמפתח, ואז לוקחים שארית חלוקה במספר השרתים, hash(key) % מספר_שרתים, וזה קובע לאיזה שרת המפתח שייך. זה עובד מצוין, כל עוד מספר השרתים לא משתנה.
הבעיה מתחילה ברגע שמוסיפים או מסירים שרת. אם היו לכם עשרה שרתים ועכשיו יש אחד עשר, השארית שכל מפתח מקבל משתנה כמעט לגמרי - כי החישוב % 11 נותן תוצאות שונות לגמרי מ-% 10 עבור כמעט כל ערך. התוצאה - כמעט כל מפתח "עובר דירה" לשרת אחר בבת אחת, מה שאומר שכל הקאש שהיה שמור נהיה חסר תועלת בן רגע, וכל השרתים מוצפים בבקשות חדשות למידע שהם לא מחזיקים.
הרעיון של גיבוב עקבי - טבעת במקום מספר¶
גיבוב עקבי פותר את הבעיה הזאת בעזרת מודל שונה לגמרי - טבעת מספרים במקום קו ישר. מדמיינים את כל טווח הערכים האפשריים של פונקציית הגיבוב כמעגל, מ-0 ועד המספר המקסימלי, וחוזר סביב לאפס. כל שרת מחושב לו hash, וממוקם על הטבעת הזאת בנקודה המתאימה. כל מפתח מחושב לו hash גם כן, ומוצא את מקומו על אותה טבעת. הכלל פשוט - כל מפתח שייך לשרת הראשון שנמצא ממנו בכיוון עם השעון על הטבעת.
למה זה פותר את בעיית ההוספה וההסרה¶
עכשיו קורה הקסם. כשמוסיפים שרת חדש לטבעת, הוא תופס נקודה מסוימת עליה, ומקבל אחריות רק על המפתחות שנמצאים בקטע שבין הנקודה הזאת לבין השרת הקודם לו על הטבעת. כל שאר המפתחות, שנמצאים בשאר הטבעת, נשארים משויכים בדיוק לאותם שרתים כמו קודם, בלי שום שינוי. באופן דומה, כשמסירים שרת, רק המפתחות שהיו שייכים לו עוברים לשרת הבא אחריו על הטבעת - שאר הטבעת נשארת יציבה לגמרי. בממוצע, הוספה או הסרה של שרת אחד מתוך N מזיזה רק בערך חלק אחד מ-N מהמפתחות, במקום כמעט את כולם.
הבעיה הקטנה שעדיין נשארת - חלוקה לא אחידה¶
מיקום אקראי של כמה שרתים בודדים על הטבעת יכול ליצור פערים לא אחידים - שרת אחד עלול לקבל קטע גדול הרבה יותר מהטבעת משרת אחר, פשוט בגלל מיקום מקרי. הפתרון הנפוץ הוא להוסיף לכל שרת פיזי כמה "שרתים וירטואליים" על הטבעת, בנקודות שונות - כך שכל שרת אמיתי מיוצג במאה נקודות שונות במקום נקודה אחת, וההסתברות שהחלוקה הכוללת תהיה מאוזנת גדלה משמעותית, כי חוק המספרים הגדולים עובד לטובתכם.
איפה זה משמש בפועל¶
גיבוב עקבי הוא הבסיס למערכות קאש מבוזר כמו Memcached, לבסיסי נתונים מבוזרים שצריכים לפצל נתונים בין שרתים, ולרשתות CDN שצריכות להחליט איזה שרת קצה אחראי על איזה תוכן. בכל מקום שיש בו קבוצת שרתים שיכולה לגדול או להתכווץ, וצריך לפזר עומס ביניהם בלי לגרום לכל המידע "לנוד" בבת אחת בכל שינוי, זו בדיוק הבעיה שגיבוב עקבי נועד לפתור.
למה שווה להבין את זה¶
מפתח שמבין גיבוב עקבי מבין למה מערכות מבוזרות גדולות לא "קורסות" זמנית בכל פעם שמוסיפים שרת, ולמה הוספת קיבולת למערכת קאש היא פעולה שגרתית ולא אירוע דרמטי. זה בדיוק סוג ההבנה של מערכות מבוזרות שבונים בהדרגה בקורס צד-שרת שלנו, מעבר לבניית API בודד לכיוון חשיבה על מערכת שלמה.
קורס צד-שרת המלא נמצא כאן, חינם ובעברית, עם דגש על מדרגיות ומערכות מבוזרות.
יש לכם שאלה על פיזור עומס בין שרתים במערכת שלכם? שאלו בדיסקורד.
לסיכום¶
גיבוב עקבי מחליף את החישוב הפשוט של שארית חלוקה במודל של טבעת, שבו הוספה או הסרה של שרת משפיעה רק על חלק קטן מהמפתחות, ולא על כולם. שרתים וירטואליים מרובים על הטבעת מוודאים שהחלוקה נשארת מאוזנת גם עם מעט שרתים פיזיים. זו בדיוק הסיבה שכל מערכת מבוזרת רצינית משתמשת בשיטה הזאת ולא בחלוקה הנאיבית.