ذاكرة تخزين مؤقتة بديلة تكيفية

ذاكرة التخزين المؤقت للاستبدال التكيفي ( ARC ) هي خوارزمية لاستبدال الصفحات تتميز بأداء أفضل ^{[ 1 ]} من خوارزمية LRU (الأقل استخدامًا مؤخرًا). ويتحقق ذلك من خلال تتبع الصفحات المستخدمة بكثرة والصفحات المستخدمة مؤخرًا، بالإضافة إلى سجل عمليات الإخلاء الأخيرة لكليهما. طُوّرت هذه الخوارزمية ^{[ 2 ]} في مركز أبحاث IBM ألمادن . وفي عام 2006، مُنحت IBM براءة اختراع لسياسة ذاكرة التخزين المؤقت للاستبدال التكيفي .

تُحافظ خوارزمية LRU الأساسية على قائمة مُرتبة (دليل التخزين المؤقت) لموارد الذاكرة المؤقتة، حيث يعتمد ترتيب الفرز على وقت آخر وصول. تُضاف العناصر الجديدة في أعلى القائمة، بعد إزالة العنصر الأخير. تنتقل العناصر التي تم الوصول إليها بنجاح إلى أعلى القائمة، دافعةً جميع العناصر الأخرى إلى أسفل.

يحسّن ARC استراتيجية LRU الأساسية بتقسيم دليل ذاكرة التخزين المؤقت إلى قائمتين، T1 وT2، للإدخالات التي يتم الرجوع إليها مؤخرًا وبشكل متكرر. يتم توسيع كل من هاتين القائمتين بقائمة وهمية (B1 أو B2)، تُضاف إلى أسفل القائمتين. تعمل هذه القوائم الوهمية كسجلات أداء من خلال تتبع تاريخ إدخالات ذاكرة التخزين المؤقت التي تم إخراجها مؤخرًا، وتستخدم الخوارزمية عمليات الوصول الوهمية للتكيف مع التغيرات الأخيرة في استخدام الموارد. تجدر الإشارة إلى أن القوائم الوهمية لا تحتوي إلا على البيانات الوصفية (مفاتيح الإدخالات) وليس بيانات الموارد نفسها، أي أنه عند إخراج إدخال إلى قائمة وهمية ، يتم تجاهل بياناته. يتم تنظيم دليل ذاكرة التخزين المؤقت المدمج في أربع قوائم LRU:

1. T1، لإدخالات ذاكرة التخزين المؤقت الأخيرة.
2. T2، للإدخالات المتكررة، المشار إليها مرتين على الأقل.
3. B1، إدخالات وهمية تم إخراجها مؤخرًا من ذاكرة التخزين المؤقت T1، ولكن لا يزال يتم تتبعها.
4. B2، إدخالات وهمية مماثلة ، ولكن تم طردها من T2.

يُشار إلى T1 وB1 معًا باسم L1، وهو تاريخ مُجمّع للمراجع الفردية الحديثة. وبالمثل، فإن L2 هو مزيج من T2 وB2.

يمكن عرض دليل التخزين المؤقت بالكامل في سطر واحد  :

... [ B1 <- [ T1 <- ! -> T2 ] -> B2 ] ... [ ... [ ... ... ! ... ^ ... ] ... ] [ حجم ذاكرة التخزين المؤقت الثابت (ج) ]

تشير الأقواس الداخلية [ ] إلى ذاكرة التخزين المؤقت الفعلية، والتي على الرغم من أنها ثابتة في الحجم، إلا أنها يمكن أن تتحرك بحرية عبر سجل B1 و B2.

يتم الآن عرض L1 من اليمين إلى اليسار، بدءًا من الأعلى، كما هو موضح بعلامة ! . يشير ^ إلى الحجم المستهدف لـ T1، وقد يكون مساويًا للحجم الفعلي أو أصغر منه أو أكبر منه (كما هو موضح بعلامة ! ).

• تدخل المدخلات الجديدة إلى T1، إلى يسار ! ، ويتم دفعها تدريجياً إلى اليسار، وفي النهاية يتم إخراجها من T1 إلى B1، ثم يتم إسقاطها نهائياً.
• أي مدخل في L1 تتم الإشارة إليه مرة أخرى، يحصل على فرصة أخرى، ويدخل L2، مباشرةً إلى يمين علامة التعجب المركزية ! ومن هناك، يُدفع للخارج مرة أخرى، من T2 إلى B2. يمكن للمدخلات في L2 التي تُشار إليها مرة أخرى أن تُكرر هذا إلى ما لا نهاية، حتى تسقط أخيرًا في أقصى يمين B2.

يتم حاليًا نشر ARC في وحدات التحكم في التخزين DS6000/ DS8000 من IBM .

يستخدم نظام الملفات ZFS القابل للتوسع من شركة صن مايكروسيستمز نسخة معدلة ^{[ 3 ]} من ARC كبديل لذاكرة التخزين المؤقت للصفحات في نظام ملفات سولاريس التقليدي في الذاكرة الافتراضية . وقد تم تعديله للسماح بالصفحات المقفلة التي لا يمكن إخلاؤها.

استخدم PostgreSQL تقنية ARC في مدير المخزن المؤقت لفترة وجيزة (الإصدار 8.0.0)، لكنه سرعان ما استبدلها بخوارزمية أخرى، مشيرًا إلى مخاوف بشأن براءة اختراع لشركة IBM تتعلق بتقنية ARC. ^{[ 4 ]}

يُعدّ vSAN من VMware (المعروف سابقًا باسم Virtual SAN) منتجًا للتخزين المتقارب للغاية والمُعرّف برمجياً (SDS) تم تطويره بواسطة VMware. وهو يستخدم نسخة معدلة من ARC في خوارزمية التخزين المؤقت الخاصة به. ^{[ 5 ]}

يدعم نظام الملفات OpenZFS استخدام ARC وL2ARC في ذاكرة تخزين مؤقتة متعددة المستويات كذاكرة قراءة مؤقتة. في OpenZFS، غالبًا ما تصل عمليات قراءة القرص إلى ذاكرة التخزين المؤقتة من المستوى الأول في ذاكرة الوصول العشوائي (RAM) باستخدام ARC. إذا تم إعداد قرص SSD لتخزين ذاكرة التخزين المؤقتة من المستوى الثاني، يُطلق عليه اسم L2ARC. يستخدم L2ARC نفس خوارزمية ARC، ولكن بدلاً من تخزين البيانات المخزنة مؤقتًا في ذاكرة الوصول العشوائي، يقوم L2ARC بتخزينها في قرص SSD سريع. ^{[ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ]}

• ساعة مع استبدال تكيفي
• خوارزمية التخزين المؤقت لـ LIRS

• ARC: ذاكرة تخزين مؤقتة بديلة ذاتية الضبط ومنخفضة الحمل الزائد (2003) بقلم نمرود ميغيدو ودارميندرا مودها
• ويكي إدارة الذاكرة في لينكس
• بوربونيه، روش. ديناميات ZFS
• تطبيق بايثون، الوصفة رقم 576532
• مقارنة بين وحدات الاستبدال طويلة المدى (LRU) ووحدات التتبع المتقدمة (ARC) وغيرها