الـ cache اللي مبيتعاملش مع الحد الأقصى للحجم بيفضل يكبر لحد ما الـ process يقع بـ OOM. LRU Cache هو الحل المعياري: لما السعة تمتلئ، نحذف العنصر الأقل استخدامًا حديثًا بـ O(1).
LRU Cache: من الفكرة البسيطة للتنفيذ في الإنتاج
المشكلة باختصار
عندك API بيجيب بيانات مستخدم من قاعدة البيانات. كل طلب بياخد 80ms. حطيت dictionary في الذاكرة عشان تسرّع. بعد مليون مستخدم، العملية بتقع بـ Out-of-Memory. محتاج سقف، ولما توصله، محتاج قرار ذكي: تحذف إيه بالظبط.
LRU (Least Recently Used) بيجاوب على السؤال ده: احذف العنصر اللي الوصول له كان الأبعد زمنيًا. الشرط العملي: كل من get و put لازم يشتغلوا في O(1) — وإلا الـ cache نفسه بقى أبطأ من اللي هو بيسرّعه.
الفكرة بمثال طفل عنده 7 سنين
تخيّل عندك رف ألعاب بيسع 5 لعب بس. كل ما تلعب بلعبة، بترجّعها أول الرف. لما تشتري لعبة جديدة والرف ملّان، بترمي اللي في آخر الرف — دي اللي معتلعبتش بيها من زمان. كده الرف دايمًا فيه الـ 5 لعب اللي بتحبهم دلوقتي.
ده بالظبط اللي LRU بيعمله. كل "لعبة" = entry في الـ cache. "أول الرف" = أحدث استخدام. "آخر الرف" = أقدم استخدام وهو المرشح للحذف.
الشرح العلمي الدقيق
LRU سياسة إزالة (eviction policy) بتفترض إن الوصول في المستقبل القريب شبيه بالوصول في الماضي القريب — افتراض اسمه temporal locality. عشان نحقق O(1) في الإدخال والاسترجاع والحذف، محتاجين بنيتين مع بعض:
- HashMap: بيديك lookup بـ O(1) من المفتاح لمكان العقدة في الذاكرة.
- Doubly Linked List: بيحافظ على الترتيب الزمني، وبيسمح بحذف أي عقدة في O(1) لو عندك مرجعها.
الـ HashMap لوحده مش كافي: مفيهوش ترتيب زمني، فعشان تعرف الأقل استخدامًا لازم تلف على كل المفاتيح — ده O(N) في كل eviction. والـ Linked List لوحده مفيهوش lookup سريع. الجمع بينهم بيحل المشكلتين.
التنفيذ في Python — 40 سطر
class Node:
__slots__ = ("key", "value", "prev", "next")
def __init__(self, key, value):
self.key, self.value = key, value
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.map = {}
self.head = Node(0, 0)
self.tail = Node(0, 0)
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_front(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key):
if key not in self.map:
return -1
node = self.map[key]
self._remove(node)
self._add_front(node)
return node.value
def put(self, key, value):
if key in self.map:
self._remove(self.map[key])
node = Node(key, value)
self.map[key] = node
self._add_front(node)
if len(self.map) > self.cap:
lru = self.tail.prev
self._remove(lru)
del self.map[lru.key]