Moment For Technology

An elegant LRU cache implementation

Posted on Dec. 2, 2022, 6:36 p.m. by Tina Howard
Category: The back-end Tag: The back-end Go

Golang's various components are flexible and powerful, but they can be difficult for beginners to use well. Recently, a ready-to-use Golang library has been developed. The first component was chosen for caching, mainly because it is a very critical component, but also very difficult to implement well.

Step 1: Define the Cache interface

To design a highly extensible cache package, you need to use the Liskov Substitution Principle to abstract and define the cache as the interface

type Cache interface {
    ...
}
Copy the code

Step 2: Organize the package structure

Then, to implement a specific LRU cache, first organize the package structure as follows:

|-cache
| |-lru
| | |-lru.go
| | |-segment.go
| | |-options.go
| | |-expvar.go
|-cache.go
Copy the code

Using package hierarchy, the interface is placed under the root package as a common language for all subpackages:

// cache.go
package edge
type Cache interface {
    ...
}
Copy the code

Step 3: Implement LRU caching

  1. To prevent poor performance due to lock contention, a piecewise locking approach is used here to reduce lock granularity to improve cache performance
  2. At the same time willsegment,newSegment,cacheUse lowercase names to avoid exposing implementation details
  3. Use higher-order function to implement extensible configuration parameters
  4. useexpvarExpose the state of the cache
// lru.go package lru type cache struct { ... } func New(opts ... Opt) (*cache, error) { ... } // segment.go package lru type segment struct { ... } func newSegment(c int) *segment { ... } // options.go type options struct { ... } type Opt func(*options) func WithConcurrency(c int) Opt { return func(o *options) { o.concurrency = c } } func WithCapacity(c int) Opt { return func(o *options) { o.capacity = c } } // expvar.go var m = struct { Get *expvar.Int Set  *expvar.Int Delete *expvar.Int Exists *expvar.Int Hit *expvar.Int Evict *expvar.Int }{ Get: expvar.NewInt("cache.lru.get"), Set: expvar.NewInt("cache.lru.set"), Delete: expvar.NewInt("cache.lru.delete"), Exists: expvar.NewInt("cache.lru.exists"), Hit: expvar.NewInt("cache.lru.hit"), Evict: expvar.NewInt("cache.lru.evict"), }Copy the code

Step 4: Are we done?

Of course not, as can be seen from the above, the following points:

  1. Options can be shared by multiple implementations and should be stored in the cache folder.
  2. When used, the lru.new () assignment to the Cache interface is slightly unnatural
  3. Segment. go and expvar.go are not open to users but the files are exposed
  4. Segments may later be used to implement other caching algorithms and are not suitable for placing under LRU packages

For the above reasons, the package structure is adjusted again as follows:

|-cache
| |-options.go
| |-lru.go
|-cache.go
|-internal
| |-cache
| | |-lru
| | | |-expvar.go
| | | |-segment.go
Copy the code

Meanwhile, adjust the interface of the LRU cache to:

// cache.go package cache type cache struct { ... } func NewLRU(opts ... Opt) (*cache, error) { ... }Copy the code

Is it a lot more natural to use the example:

var c edge.Cache = cache.NewLRU()
Copy the code

conclusion

To put this to use, this IMPLEMENTATION of LRU applies a lot of previous knowledge. The road to good code is endless. Class dismissed.

Source code: github.com/cyningsun/e...

This article is written by Cyningsun at www.cyningsun.com/07-26-2021/... Copyright Notice: All articles in this blog are under the CC BY-NC-ND 3.0CN license unless otherwise stated. Reprint please indicate the source!

Search
About
mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.