لذا فأنت بحاجة إلى ذاكرة تخزين مؤقت صغيرة ولا يمكنك تبرير مثيل Redis أو memcached. دعونا نرى ما يلزم لتنفيذ واحد في Go. من أجل المتعة، سنصنعه باستخدام الأدوية العامة بحيث يمكن إعادة استخدامه في مشروعنا.

تتمتع ذاكرة التخزين المؤقت LRU بشكل عام بسعة ثابتة وأبسط سياسة إخراج: قم بإخراج العنصر الذي يتمتع بأطول وقت منذ الوصول إليه. ستقوم ذاكرة التخزين المؤقت lru البسيطة بتنفيذ الواجهة التالية:

type LRUCache[T any] interface {
    Get(key string) (value T, found bool)
    Put(key string, value T)
    Keys() []string
    Remove(key string) bool
    Clear()
    Capacity() int
    Len() int
}

نحن نعلم أن ذاكرة التخزين المؤقت ستخزن عنصر بيانات كمدخل يتم إدخاله بواسطة بعض القيمة. هذا يبدو وكأنه خريطة. وماذا عن تطبيق سياسة الطرد؟ إحدى الطرق للقيام بذلك هي الاحتفاظ بخاصية الوصول إلى الوقت مع كل عنصر. شيء مثل:

type cacheEntry[T any] struct {
  Data T
  LastAccessed time.time
}

ومع ذلك، دعونا نفكر في الأداء، نريد أن نكون قادرين على البحث عن مفتاح ذاكرة التخزين المؤقت بالإضافة إلى إدراج وإخراج الأقدم، إذا لزم الأمر، في أسرع وقت ممكن.

سيوفر لنا استخدام الخريطة القابلة للتجزئة أداءً سريعًا جدًا لعمليات البحث. ماذا عن العثور على أقدم إدخال؟ إذا كانت بنية ذاكرة التخزين المؤقت تبدو كما يلي:

type LRUCache[T any] {
  capacity int
  keyMap map[string]cacheEntry[T]
}

سنحتاج بالضرورة إلى التكرار على الخريطة للعثور على الأقدم عندما يحين وقت طرد الإدخال.

نحتاج إلى طريقة لتخزين الإدخالات بطريقة تسمح لنا بكفاءة بالاحتفاظ بقائمة إدخالات ذاكرة التخزين المؤقت مرتبة. ومن الأفضل ألا نحتاج إلى استخدام روتين الفرز.

تعد القائمة المرتبطة المزدوجة طريقة جيدة للقيام بذلك ولا نحتاج إلى تخزين وقت الوصول في الإدخال إلا إذا أردنا ذلك بالفعل. لنفترض أن لدينا قائمة مرتبطة تنفذ ما يلي مع بنية العقدة الخاصة بها:

type DoubleLinkedList[T any] interface {
    Head() *DoubleNode[T]
    Tail() *DoubleNode[T]
    // Append inserts new item at tail
    Append(data T) *DoubleNode[T]
    // Push appends new item at head
    Push(data T) *DoubleNode[T]
    Remove(node *DoubleNode[T]) *DoubleNode[T]
    RemoveTail() *DoubleNode[T]
    MoveToHead(node *DoubleNode[T])
}
type DoubleNode[T any] struct {
    Data T
    Prev *DoubleNode[T]
    Next *DoubleNode[T]
}

يمكن أن تبدو بنية ذاكرة التخزين المؤقت الآن كما يلي:

type lruCache[T any] struct {
    capacity int
    keyMap   map[string]*DoubleNode[lruCacheEntry[T]]
    list     DoubleLinkedList[lruCacheEntry[T]]
}

سيكون هيكل إدخال ذاكرة التخزين المؤقت هو:

type lruCacheEntry[T any] struct {
    key   string
    value T
}

من الناحية الواقعية، ربما تستخدم واجهة لمفتاح ذاكرة التخزين المؤقت. أنا أستخدم سلسلة لإبقاء الكود بسيطًا.

في التنفيذ هنا، سيكون الإدخال الأحدث الذي تم الوصول إليه في ذاكرة التخزين المؤقت في الرأس وسيكون الإدخال الأقل استخدامًا في الذيل. لذلك، عندما يحين وقت الإخلاء، نقوم ببساطة بإزالة العنصر الخلفي للقائمة المرتبطة.

يعد تنفيذ وظيفة Get() أمرًا بسيطًا:

func (l *lruCache[T]) Get(key string) (value T, found bool) {
    if node, ok := l.keyMap[key]; ok {
        l.list.MoveToHead(node)
        return node.Data.value, ok
    }
    var zero T
    return zero, false
}

يحتاج Get فقط إلى استرداد إدخال الخريطة للمفتاح، ثم نقل العقدة إلى رأس القائمة لأنها الآن "الأكثر استخدامًا".

وظيفة Put () هي المكان الذي سنتعامل فيه مع عملية الإخلاء إذا كان ذلك ضروريًا:

func (l *lruCache[T]) Put(key string, value T) {
    if node, ok := l.keyMap[key]; ok {
        node.Data = lruCacheEntry[T]{
            key:   key,
            value: value,
        }
        // move the element to the most recent position
        l.list.MoveToHead(node)
    } else {
        // insert the new element at the head
        newNode := l.list.Push(lruCacheEntry[T]{
            key:   key,
            value: value,
        })
        l.keyMap[key] = newNode
    }
    // is eviction necessary
    if len(l.keyMap) > l.capacity {
        nodeRemoved := l.list.RemoveTail()
        delete(l.keyMap, nodeRemoved.Data.key)
    }
}

بالنسبة لـ Put()، نتحقق أولاً لمعرفة ما إذا كانت هناك بالفعل قيمة للمفتاح المحدد. إذا كان الأمر كذلك، فقم بتحديث القيمة وانقل العقدة إلى رأس القائمة. بخلاف ذلك، فإننا نقوم بإنشاء إدخال ذاكرة تخزين مؤقت جديد، ونضيفه إلى القائمة كرأس، ونضيفه إلى خريطتنا.

أخيرًا، لا تنس التحقق من السعة. إذا وضعنا الإدخال الجديد فوق السعة، فإننا نطرد الإدخال الأقدم الذي يمثل ذيل القائمة ونحذف الإدخال من خريطتنا.

لاحظ أن تخزين المفتاح كجزء من إدخال ذاكرة التخزين المؤقت يسمح لنا بحذف المفتاح بسرعة من الخريطة. إذا قمنا فقط بتخزين البيانات في إدخال ذاكرة التخزين المؤقت، فسنحتاج إلى التكرار على الخريطة للعثور عليها.

تفتقد ذاكرة التخزين المؤقت هذه شيئًا مهمًا لتطبيق متعدد الخيوط. لا يوجد مزامنة. من الناحية الواقعية، سيتم الوصول إلى ذاكرة التخزين المؤقت من خلال سلاسل رسائل متعددة. المزامنة موضوع معقد. لتنفيذنا، يمكننا إضافة كائن المزامنة (mutex) إلى بنية ذاكرة التخزين المؤقت:

type lruCache[T any] struct {
    capacity int
    keyMap   map[string]DoubleNode[lruCacheEntry[T]]
    list     DoubleLinkedList[lruCacheEntry[T]]
    mutex    sync.RWMutex
}

ثم أضف ما يلي في بداية كل وظيفة.

    l.mutex.Lock()
    defer l.mutex.Unlock()

لاحظ أننا نستخدم قفل القراءة/الكتابة. بعض الوظائف لا تغير بنية ذاكرة التخزين المؤقت، لذا يمكننا استخدام طريقة قفل القراءة المتوفرة، على سبيل المثال وظيفة Len():

func (l *lruCache[T]) Len() int {
    l.mutex.RLock()
    defer l.mutex.RUnlock()
    return len(l.keyMap)
}

لاحظ أن استراتيجية المزامنة المختارة هنا قد تتعطل إذا كان هناك عدد كبير من سلاسل الرسائل التي تحاول الوصول إلى ذاكرة التخزين المؤقت. إنه موضوع معقد ويمكن أن يكون سلسلة من المشاركات في حد ذاته.

انظر التنفيذ الكامل في المستودع الموجود في الرابط أدناه.

ما الذي ستفعله بشكل مختلف لتنفيذ ذاكرة التخزين المؤقت؟ كيف يمكنك معالجة المزامنة؟ أنا مهتم بسماع أفكارك حول هذا الموضوع. لا يوجد حل واحد لذلك، لذا ضع تعليقاتك أدناه.

شكرًا!

يمكن العثور على رمز هذه المشاركة وجميع المشاركات في هذه السلسلة هنا