How to implement a cache system of LRU algorithm in golang

LRU (Least Recently Used) is a caching algorithm. It can cache recently used data first and eliminate data that has not been used for a long time under limited cache capacity, thereby achieving efficient use of cache space and improving data efficiency. access speed.

Go language (golang) is an efficient programming language that is favored by developers for its excellent concurrency and memory management capabilities. In this article, we will implement a caching system for the LRU algorithm and use the Go language to implement it.

Design ideas

Before implementing an LRU cache system, we need to first determine the system requirements and design ideas.

First of all, we need a data structure to save the cached data. This data structure needs to support fast access and updates, and also needs to support the elimination of data according to usage time. Commonly used data structures include linked lists, hash tables, doubly linked lists, etc. Among them, doubly linked lists are the best choice for implementing the LRU algorithm.

Secondly, we need some operations to access and update this data structure. Common operations include: reading cache data, writing cache data, updating cache data, deleting cache data, etc.

Finally, we need some caching strategies to control the size of the cache and prevent the cache from filling up the entire memory. Commonly used strategies include FIFO (first in, first out), LFU (least frequently used), LRU (least recently used), etc. Among them, LRU is the best choice to implement an LRU cache system.

Code Implementation

Now, we have a clear design idea and can start to implement our LRU cache system. The code is as follows:

package lruCache

import "container/list"

type Cache struct {
    MaxBytes  int64
    nBytes    int64
    ll        *list.List
    cache     map[string]*list.Element
    OnEvicted func(key string, value Value)
}

type entry struct {
    key   string
    value Value
}

type Value interface {
    Len() int
}

func (c *Cache) Add(key string, value Value) {
    if e, ok := c.cache[key]; ok {
        c.ll.MoveToFront(e)
        kv := e.Value.(*entry)
        c.nBytes += int64(value.Len()) - int64(kv.value.Len())
        kv.value = value
    } else {
        ele := c.ll.PushFront(&entry{key, value})
        c.cache[key] = ele
        c.nBytes += int64(len(key)) + int64(value.Len())
    }
    for c.MaxBytes != 0 && c.MaxBytes < c.nBytes {
        c.RemoveOldest()
    }
}

func (c *Cache) Get(key string) (value Value, ok bool) {
    if ele, ok := c.cache[key]; ok {
        c.ll.MoveToFront(ele)
        kv := ele.Value.(*entry)
        return kv.value, true
    }
    return
}

func (c *Cache) RemoveOldest() {
    ele := c.ll.Back()
    if ele != nil {
        c.ll.Remove(ele)
        kv := ele.Value.(*entry)
        delete(c.cache, kv.key)
        c.nBytes -= int64(len(kv.key)) + int64(kv.value.Len())
        if c.OnEvicted != nil {
            c.OnEvicted(kv.key, kv.value)
        }
    }
}

Usage example

Now, we have implemented a simple LRU cache system. We can use it through the following sample code:

package main

import (
    "fmt"
    "go-lru-cache/lruCache"
)

type stringValue string

func (s stringValue) Len() int {
    return len(s)
}

func main() {
    cache := lruCache.Cache{
        MaxBytes: 1000,
        OnEvicted: func(key string, value lruCache.Value) {
            fmt.Printf("key=%s, value=%s is evicted\n", key, value)
        },
    }
    cache.Add("key1", stringValue("123"))
    cache.Add("key2", stringValue("456"))
    cache.Add("key3", stringValue("789"))
    if value, ok := cache.Get("key1"); ok {
        fmt.Println(value.(stringValue))
    }
    cache.Add("key4", stringValue("101"))
    fmt.Printf("cache.Len() = %d\n", cache.Len())
    cache.RemoveOldest()
    fmt.Printf("cache.Len() = %d\n", cache.Len())
}

In the above sample code, we defined a stringValue type, which implements the Value interface, for Represents the value in the cache. Then, we created an LRU cache system and added 4 cache items, where MaxBytes represents the maximum capacity of the cache. Next, we obtained the value corresponding to key1 in the cache through the Get method, then added a new cache item, and finally deleted the oldest cache item.

Summary

So far, we have successfully implemented an LRU cache system. Through this article, we not only learned the implementation of the LRU cache algorithm, but also learned how to use the Go language to implement the cache system. In actual development, rational use of the cache system can significantly improve program performance and reduce system load. Therefore, caching system is one of the important skills that every developer should understand and master.

The above is the detailed content of How to implement a cache system of LRU algorithm in golang. For more information, please follow other related articles on the PHP Chinese website!