तो आपको एक छोटे कैश की आवश्यकता है और रेडिस या मेम्केच्ड उदाहरण को उचित नहीं ठहराया जा सकता है। आइए देखें कि इसे गो में लागू करने में क्या लगता है। मनोरंजन के लिए, हम इसे जेनेरिक का उपयोग करके बनाएंगे ताकि यह हमारे प्रोजेक्ट में पुन: प्रयोज्य हो।

एलआरयू कैश में आम तौर पर एक निश्चित क्षमता और सबसे सरल इजेक्शन नीति होती है: उस तत्व को बाहर निकालें जिसके पास पहुंचने के बाद से सबसे लंबा समय है। एक साधारण एलआरयू कैश निम्नलिखित इंटरफ़ेस लागू करेगा:

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
}

हम जानते हैं कि कैश एक डेटा आइटम को एक प्रविष्टि के रूप में संग्रहीत करेगा जो कुछ मूल्य से कुंजीबद्ध है। यह एक मानचित्र जैसा लगता है। इजेक्शन नीति लागू करने के बारे में क्या? ऐसा करने का एक तरीका प्रत्येक आइटम के साथ एक timeAccessed प्रॉपर्टी रखना है। कुछ इस तरह:

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
}

वास्तविक रूप से, आप संभवतः कैश कुंजी के लिए एक इंटरफ़ेस का उपयोग करेंगे। मैं कोड को सरल बनाए रखने के लिए एक स्ट्रिंग का उपयोग कर रहा हूं।

यहां कार्यान्वयन में, कैश में सबसे हाल ही में एक्सेस की गई प्रविष्टि शीर्ष पर होगी और सबसे कम हाल ही में उपयोग की गई प्रविष्टि पीछे होगी। इसलिए, जब बेदखल करने का समय आता है, तो हम बस लिंक की गई सूची के टेल तत्व को हटा देते हैं।

गेट() फ़ंक्शन को कार्यान्वित करना सरल है:

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
}

गेट को केवल कुंजी के लिए मानचित्र प्रविष्टि पुनर्प्राप्त करने की आवश्यकता है, फिर नोड को सूची के शीर्ष पर ले जाएं क्योंकि यह अब 'सबसे हाल ही में उपयोग किया गया' है।

पुट() फ़ंक्शन वह जगह है जहां हम आवश्यक होने पर निष्कासन को संभालेंगे:

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)
    }
}

पुट() के लिए, हम पहले यह जांचते हैं कि दी गई कुंजी के लिए पहले से ही कोई मान है या नहीं। यदि ऐसा है, तो मान अपडेट करें और नोड को सूची के शीर्ष पर ले जाएं। अन्यथा, हम एक नई कैश प्रविष्टि बनाते हैं, इसे सूची में शीर्ष के रूप में जोड़ते हैं, और इसे अपने मानचित्र में जोड़ते हैं।

अंत में, क्षमता की जांच करना न भूलें। यदि नई प्रविष्टि हमें क्षमता से ऊपर रखती है, तो हम सबसे पुरानी प्रविष्टि को बेदखल कर देते हैं जो सूची का अंतिम भाग है और हमारे मानचित्र से प्रविष्टि को हटा देते हैं।

ध्यान दें कि कैश प्रविष्टि के हिस्से के रूप में कुंजी को संग्रहीत करने से हमें मानचित्र से कुंजी को तेजी से हटाने की अनुमति मिलती है। यदि हमने डेटा को केवल कैश प्रविष्टि में संग्रहीत किया है, तो हमें इसे खोजने के लिए मानचित्र पर पुनरावृति करने की आवश्यकता होगी।

इस कैश में मल्टी-थ्रेडेड ऐप के लिए कुछ महत्वपूर्ण कमी है। कोई तुल्यकालन नहीं है. वास्तविक रूप से, एक कैश को कई थ्रेड्स द्वारा एक्सेस किया जाएगा। तुल्यकालन एक जटिल विषय है. हमारे कार्यान्वयन के लिए, हम कैश संरचना में एक म्यूटेक्स जोड़ सकते हैं:

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()

ध्यान दें कि हम पढ़ने/लिखने वाले लॉक का उपयोग कर रहे हैं। कुछ फ़ंक्शन कैश की संरचना को नहीं बदलते हैं, इसलिए हम प्रदान की गई रीड लॉक विधि का उपयोग कर सकते हैं, उदाहरण के लिए लेन() फ़ंक्शन:

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

ध्यान दें कि यदि बड़ी संख्या में थ्रेड कैश तक पहुंचने का प्रयास कर रहे हैं तो यहां चुनी गई सिंक्रनाइज़ेशन रणनीति विफल हो सकती है। यह एक जटिल विषय है जो अपने आप में पोस्टों की एक श्रृंखला हो सकता है।

नीचे दिए गए लिंक में दिए गए भंडार में पूर्ण कार्यान्वयन देखें।

कैश लागू करने के लिए आप क्या अलग करेंगे? आप सिंक्रनाइज़ेशन को कैसे संबोधित करेंगे? मुझे इस पर आपके विचार सुनने में दिलचस्पी है। इसका कोई एक समाधान नहीं है इसलिए अपनी टिप्पणियाँ नीचे दें।

धन्यवाद!

इस पोस्ट और इस श्रृंखला के सभी पोस्ट का कोड यहां पाया जा सकता है