איך קאש מחליט מה למחוק כשהוא מתמלא - LRU מוסבר

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

למה זה עקרון טוב

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

הדרישה הקשה - צריך למחוק ולעדכן, מהר, בכל פעולה

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

הפתרון - hashmap ורשימה מקושרת כפולה

המימוש הקלאסי של LRU משלב שני מבנים:

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

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

למה זה חשוב יותר משנדמה

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

וריאציות שחשוב להכיר

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

למה כדאי להבין את זה

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

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

יש לכם קאש שמתנהג לא כמו שציפיתם? שאלו בדיסקורד.

הצטרפו לקהילה בדיסקורד

לסיכום

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