سياسات الإخلاء: LRU وLFU وTTL
سياسات الإخلاء: LRU وLFU وTTL
الكاش عبارة عن هيكل ذاكرة ذو حجم محدود. عندما يمتلئ الكاش ويجب تخزين عنصر جديد، لا بدّ من إزالة عنصر موجود لتوفير المساحة. الخوارزمية التي تقرر أيّ عنصر يُزال تُسمى سياسة الإخلاء. اختيار السياسة الصحيحة قد يكون الفرق بين معدل إصابة بالكاش يتجاوز 90 % وآخر لا يتعدى 50 %.
ثمة ثلاث سياسات أساسية يجب أن يعرفها كل مصمم أنظمة: LRU (الأقل استخداماً حديثاً)، وLFU (الأقل استخداماً تكراراً)، وTTL (مدة الصلاحية). تتضمّن كل سياسة افتراضاً مختلفاً حول القيمة المستقبلية للبيانات المخزّنة.
LRU — الأقل استخداماً حديثاً
الافتراض الأساسي: إذا لم يُستخدم عنصر ما منذ فترة طويلة، فمن غير المرجح أن يُطلب قريباً. يُخلي LRU العنصر الذي مضى وقت أطول على آخر وصول إليه.
تُنفَّذ LRU داخلياً عادةً كـقائمة مرتبطة مزدوجة + خريطة هاشية. كل وصول يُنقل العنصر إلى مقدمة القائمة، والإخلاء يُزيل من الذيل. تعمل عمليتا get وput بتعقيد O(1).
مثال واقعي: كاش صفحات تفاصيل المنتجات في موقع تجارة إلكترونية. يصل العملاء الذين يبحثون عن "أحذية الركض" إلى نفس صفحات SKU مراراً خلال موجة اهتمام. تحتفظ LRU بهذه الصفحات الساخنة في الذاكرة وتُزيل بصمت صفحات المنتجات المتوقفة التي لم يزرها أحد في الساعة الأخيرة.
maxmemory-policy إلى allkeys-lru أو volatile-lru. يأخذ عيّنة من عدد قابل للضبط من المفاتيح (5 افتراضياً) ويُخلي الأقل استخداماً حديثاً منها — وهو تقريب احتمالي رخيص لـ LRU الحقيقية.
أين تعجز LRU: أحمال "المسح" — مثلاً، مهمة دُفعية ليلية تتكرر على كل سجل — ستُخرّب كاش LRU بتحميل ملايين العناصر التي لن تُقرأ مرة ثانية، مما يُخلي جميع البيانات الساخنة الحقيقية. يُعرف هذا بـتلوث مسح الكاش.
LFU — الأقل استخداماً تكراراً
الافتراض الأساسي: العناصر التي وُصل إليها كثيراً في الماضي من المرجح أن تُطلب مجدداً. تتتبع LFU عداد إصابات لكل مفتاح وتُخلي المفتاح ذا العدد الأدنى.
تتميز LFU بمقاومة أعلى لتلوث المسح مقارنةً بـ LRU، لأن عنصراً بارداً من مسح دُفعي يجمع إصابات قليلة جداً قبل إخلائه، في حين تمتلك العناصر الشعبية عدادات مرتفعة وتبقى. المقايضة هي التعقيد: تستهلك عدادات الإصابات ذاكرة إضافية، والعناصر المُدرجة حديثاً تبدأ بالعدد 1، ما يجعلها عرضة للإخلاء المبكر حتى لو كانت ستصبح شعبية جداً.
مثال واقعي: CDN لتخزين الأصول الثابتة. شعار موقع يُجلب ملايين المرات يومياً؛ ملف PDF نادراً ما يُشاهَد يُجلب مرتين. تحت ضغط المرور، ستحمي LFU الشعار دائماً وتُضحّي بملف PDF — وهو القرار الصحيح تماماً.
lfu-decay-time) لمنع العناصر الشعبية القديمة من احتلال الكاش إلى الأبد.
TTL — مدة الصلاحية
TTL مختلف مفاهيمياً عن LRU وLFU: بدلاً من الإخلاء بناءً على أنماط الوصول، يُخلي بناءً على العمر. كل عنصر مخزّن يُختم بوقت انتهاء الصلاحية. عندما يتجاوز الوقت هذه اللحظة، يُعدّ العنصر قديماً ويُزال فوراً أو يُحذف كسولاً عند القراءة التالية.
TTL هو الأداة الأساسية لـالاتساق. إذا تغيّر سجل قاعدة البيانات، يصبح مدخل الكاش الخاص به خاطئاً. تعيين TTL = 60 ثانية يعني أن الكاش سيكون قديماً 60 ثانية كحد أقصى — تقايض الاتساق الكامل بأداء الكاش.
مثال واقعي: تخزين بيانات جلسة المستخدم لمدة 30 دقيقة. بعد 30 دقيقة من الخمول، تنتهي الجلسة تلقائياً — لا حاجة لمنطق إخلاء صريح، وتُستعاد الذاكرة. رموز المصادقة وعدادات تحديد المعدل ورموز OTP كلها حالات استخدام طبيعية لـ TTL.
TTL = الأساس + عشوائي(0، 30) ثانية — لتوزيع انتهاءات الصلاحية على فترة زمنية.
مقارنة جانبية
كيف تعمل LRU داخلياً: تعمّق عملي
فهم الآلية الداخلية يساعدك على التنبؤ بالسلوك. تخيّل كاشاً بـسعة = 4. يُصل إلى المفاتيح بهذا الترتيب: A، B، C، D، A، E.
الجمع بين السياسات في الإنتاج
نادراً ما تعتمد الأنظمة الحقيقية على سياسة واحدة. نمط شائع هو استخدام TTL كأرضية للاتساق (لكل مفتاح عمر أقصى) مع استخدام LRU أو LFU كطبقة لإدارة السعة. قد يُخلى المدخل إما لانتهاء TTL أو لامتلاء الكاش — أيهما جاء أولاً.
يعرض Redis هذا مباشرةً. عيّن maxmemory-policy allkeys-lru (إخلاء السعة = LRU عبر جميع المفاتيح) واستخدم EXPIRE key 3600 لكل مفتاح لإضافة TTL. يموت المدخل عندما يبلغ الساعة 3600 ثانية أو عندما يحتاج Redis مساحة، أيهما أسبق.
- هل تصبح البيانات قديمة بعد وقت محدد؟ → أضف TTL دائماً.
- نمط الوصول "80 % من المرور على 20 % من المفاتيح"؟ → LRU مناسبة.
- هل توجد مفاتيح "ساخنة دائماً" يجب أن تبقى حتى تحت ضغط المسح؟ → LFU.
- الكاش صغير جداً وكل بايت مهم؟ → تجنّب عدادات LFU؛ استخدم LRU.
- تخزين رموز مصادقة / نوافذ تحديد المعدل / OTP؟ → TTL فقط، لا حاجة لـ LRU أو LFU.
أرقام أساسية يجب حفظها
- القيمة الافتراضية لـ
maxmemory-policyفي Redis:noeviction(يُعيد خطأ عند الكتابة حين يمتلئ) — غيّرها في الإنتاج! - حجم عيّنة LRU في Redis: الافتراضي
maxmemory-samples 5؛ رفعه إلى 10 يعطي دقة LRU شبه مثالية بتكلفة ضعف استخدام المعالج. - نطاق الاهتزاز النموذجي لـ TTL:
±10–30 %من TTL الأساسي كافٍ لتسطيح ذروة الانتهاء. - Memcached يستخدم LRU فقط (لا LFU، لا حذف خلفي قائم على TTL) — يُطبَّق TTL كسولاً عند القراءة.
الحصول على سياسات الإخلاء الصحيحة هو الفرق بين كاش يساعد نظامك وآخر يُسقط البيانات الثمينة عشوائياً تحت الضغط. في الدرس القادم سننظر في إبطال الكاش — كيفية دفع النضارة بشكل نشط بدلاً من انتظار TTL لإلغائه.