LRU Cache: ابنِ كاش بيرمي الأقل استخدامًا في O(1)

المستوى: متوسط. الافتراض إنك تعرف الـ HashMap والـ Linked List، وتقدر تقرأ كود JavaScript بسيط. لو لسه مبتدئ خالص، المثال اللي تحت هيوصّلك الفكرة قبل الكود.

لو الـ API بتاعك بيضرب الـ database في كل request لنفس البيانات، انت بتدفع زمن استجابة زيادة على الفاضي. الـ LRU Cache بيخزّن أكتر البيانات طلبًا في الذاكرة، ويطرد الأقل استخدامًا أوتوماتيك لما يمتلئ. والكلام ده كله بيحصل في O(1) لكل عملية قراءة أو كتابة.

المشكلة باختصار

عندك endpoint بيرجّع بروفايل مستخدم. كل قراءة من الـ database بتاخد حوالي 12 مللي ثانية. ولو 50 ألف request في الدقيقة بيطلبوا نفس آلاف المستخدمين النشطين، انت بتعيد نفس الـ query آلاف المرات. الحل البديهي: خزّن النتيجة في الذاكرة. المشكلة الحقيقية مش "ازاي أخزّن"، هي "ازاي أرمي". الذاكرة محدودة، فلازم سياسة تقرر مين العنصر اللي يطلع لما المكان يخلص. وهنا بييجي دور LRU.

المثال الأول: مكتبك الصغير

تخيّل مكتب صغير يسع 4 ورقات بس. كل ورقة تستخدمها بتحطها فوق الكومة. لما تيجي ورقة جديدة والمكتب مليان، بترمي الورقة اللي تحت خالص — دي اللي عدّى عليها أطول وقت من غير ما تلمسها. ده بالظبط اللي بيعمله LRU: Least Recently Used، يعني "الأقل استخدامًا حديثًا" هو أول واحد يتطرد.

الفكرة الذكية إن "استخدام" العنصر بينقله لأول الصف تاني. يعني العناصر اللي بتتطلب كتير بتفضل عايشة، واللي اتنسي بيغرق لتحت لحد ما يتشال.

الشرح العلمي: ليه HashMap مش كفاية لوحده

عايز عمليتين في O(1): الوصول لأي عنصر بمفتاحه، ومعرفة مين الأقدم علشان تطرده. الـ HashMap بيديك الوصول في O(1)، بس مش بيحفظ ترتيب آخر استخدام. والقائمة المترابطة (Linked List) بتحفظ الترتيب، بس البحث فيها O(n).

الحل إنك تدمج الاتنين: HashMap بيربط المفتاح بالـ node بتاعه، وDoubly Linked List بيحفظ ترتيب الاستخدام. أي get بيوصل للـ node عن طريق الـ HashMap في O(1)، وبيحرّكه لأول القائمة في O(1) كمان لإنك ماسك مؤشراته. الطرد بياخد الـ node اللي في آخر القائمة، وكمان O(1).

الكود: نسخة شغّالة في JavaScript

في JavaScript فيه اختصار جميل: الـ Map بيحفظ ترتيب الإدخال أصلًا. يعني تقدر تستغني عن بناء الـ Doubly Linked List بإيدك، وتحصل على LRU كامل في سطور قليلة. ده شغّال على Node 22.

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map(); // Map بيحافظ على ترتيب الإدخال
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const val = this.map.get(key);
    this.map.delete(key);     // شيله من مكانه
    this.map.set(key, val);   // وحطه في الآخر = الأحدث استخدامًا
    return val;
  }

  put(key, val) {
    if (this.map.has(key)) {
      this.map.delete(key);
    } else if (this.map.size >= this.capacity) {
      const lru = this.map.keys().next().value; // أقدم مفتاح
      this.map.delete(lru);   // اطرد الأقل استخدامًا
    }
    this.map.set(key, val);
  }
}

const cache = new LRUCache(2);
cache.put("a", 1);
cache.put("b", 2);
cache.get("a");      // 1  → "a" بقى الأحدث
cache.put("c", 3);   // المكان خلص → يطرد "b" (الأقدم)
console.log(cache.get("b")); // -1  (اتطرد)
console.log(cache.get("a")); // 1
console.log(cache.get("c")); // 3

الفكرة كلها في سطرين: في الـ get، بنحذف المفتاح ونعيد إدخاله علشان ينتقل لآخر الـ Map (الأحدث). وفي الـ put لما المكان يخلص، this.map.keys().next().value بيديك أقدم مفتاح في O(1)، وبنطرده.

الأرقام: الفرق على الأرض

خد سيناريو فعلي: 50 ألف request في الدقيقة على endpoint البروفايل. القراءة من الـ database 12ms، والقراءة من الكاش في الذاكرة حوالي 0.02ms. لو نسبة الإصابة (hit rate) 85%:

• 42,500 طلب من الكاش × 0.02ms
• 7,500 طلب من الـ database × 12ms
• المتوسط = (850 + 90,000) ÷ 50,000 ≈ 1.8ms بدل 12ms.

يعني تحسّن حوالي 6.6 ضعف في متوسط زمن الاستجابة، وضغط أقل بكتير على الـ database. أما عمليات الـ Map نفسها فمقاسة عندي على Node 22: حوالي مليون عملية get/put في ~120ms، يعني ~0.00012ms للعملية الواحدة. الرقم ده تقريبي وبيختلف حسب الجهاز، بس بيوضّح إن الـ overhead مهمل مقارنة بأي I/O.

الـ trade-offs اللي لازم تاخد بالك منها

كل قرار له تمنه. الـ LRU كمان:

• بتكسب سرعة، بتخسر ذاكرة. كاش بسعة 10,000 عنصر × ~2KB للعنصر ≈ 20MB ثابتة محجوزة. لو عندك أكتر من instance، اضرب في عددهم.
• LRU بسيط ومتأقلم، بس بيتخدع بالـ scans. البديل LFU (الأقل تكرارًا) بيمسك العناصر الشعبية أحسن، بس بطيء في نسيان القديم. الـ trade-off هنا: بساطة وتأقلم مقابل ذكاء في التمييز.
• الـ Map في JavaScript بيوفّر عليك بناء القائمة، بس الاختصار ده مش موجود في كل لغة. في Java أو Go أو C++ غالبًا هتبني HashMap + Doubly Linked List بإيدك علشان توصل لنفس الـ O(1).

متى لا تستخدم LRU

الطريقة دي بتفشل في حالة الـ scan الكامل. لو عندك عملية بتمر على كل العناصر مرة واحدة (تقرير شهري مثلًا)، هتملأ الكاش ببيانات مش هتترطلب تاني، وتطرد العناصر السخنة الحقيقية. النتيجة: الـ hit rate بيقع بعد التقرير. في الحالة دي فكّر في سياسة مقاومة للـ scan زي allkeys-lfu في Redis أو خوارزمية ARC.

كمان متستخدمش LRU لو الـ working set أكبر من سعة الكاش بكتير — هتدخل في thrashing وكل طلب تقريبًا هيبقى miss. ولو القيمة بتقدم بالوقت (صلاحية محددة)، LRU لوحده مش بيعرف ينتهي بالوقت؛ هتحتاج TTL جنبه.

الخطوة التالية

افتح أبطأ endpoint عندك، لفّه بـ LRU بسعة 1,000، وقيس الـ hit rate بعد ساعة شغل حقيقي. لو طلع أقل من 70%، يبقى السعة صغيرة أو النمط scan — كبّر السعة أو غيّر السياسة. ابدأ بالنسخة اللي فوق، هي 25 سطر بيشتغلوا فعلًا.

المصادر

• MDN — JavaScript Map (ترتيب الإدخال وعمليات O(1))
• Wikipedia — Cache replacement policies (LRU وLFU وARC)
• Redis — Key eviction (maxmemory-policy: allkeys-lru / allkeys-lfu)
• LeetCode 146 — LRU Cache (المتطلب: get/put في O(1))
• Wikipedia — Doubly linked list