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

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

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

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

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

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

עושים Hash מזה

טבלאות Hash הן בין מבני הנתונים הוותיקים, הפשוטים, המהירים והנפוצים ביותר כיום. הם נועדו לבצע שלוש פעולות בסיסיות: הוספות, שמוסיפות פריטים חדשים למסד הנתונים; שאילתות, הניגשות לפריט או בודקות אם הוא קיים; ומחיקות. טבלת גיבוב יכולה להיות ארעית - קיימת רק כל עוד תוכנית מסוימת פועלת - או שהיא יכולה להיות חלק קבוע ממערכת ההפעלה של המחשב שלך. דפדפן אינטרנט כגון Chrome או Safari עשוי לכלול מספר טבלאות hash מובנות שנועדו לעקוב אחר סוגים שונים של נתונים.

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

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

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

ערבוב הנתונים

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

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

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

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

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

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

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

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

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

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

חייב להצליח

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

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

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

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

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

הגשש אל העתיד

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

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

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

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

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