Build a High‑Performance Go Cache Library (EasyCache) from Scratch

Project Overview

The cache implementation creates an *EasyCache instance that is divided into a configurable number of shards. Sharding reduces lock contention by confining each lock to a single shard.

func New(conf Config) (*EasyCache, error) {
    if !utils.IsPowerOfTwo(conf.Shards) {
        return nil, errors.New("shards number must be power of two")
    }
    if conf.Cap <= 0 {
        conf.Cap = defaultCap
    }
    cache := &EasyCache{
        shards:    make([]*cacheShard, conf.Shards),
        conf:      conf,
        hash:      conf.Hasher,
        shardMask: uint64(conf.Shards - 1), // mask
        close:     make(chan struct{}),
    }
    var onRemove OnRemoveCallback
    if conf.OnRemoveWithReason != nil {
        onRemove = conf.OnRemoveWithReason
    } else {
        onRemove = cache.notProvidedOnRemove
    }
    for i := 0; i < conf.Shards; i++ {
        cache.shards[i] = newCacheShard(conf, i, onRemove, cache.close)
    }
    return cache, nil
}

Shard Data Structures

Each *cacheShard holds three containers: items – map of all key/value pairs, regardless of expiration. expireItems – map of keys that have an expiration time; used to limit the scan range when cleaning expired entries. list – a doubly‑linked list that records usage order for LRU eviction.

func newCacheShard(conf Config, id int, onRemove OnRemoveCallback, close chan struct{}) *cacheShard {
    shard := &cacheShard{
        items:           make(map[string]*list.Element),
        expireItems:     make(map[string]*list.Element),
        cap:             conf.Cap,
        list:            list.New(),
        logger:          newLogger(conf.Logger),
        cleanupInterval: defaultInternal,
        cleanupTicker:   time.NewTicker(defaultInternal),
        addChan:         make(chan string),
        isVerbose:       conf.Verbose,
        id:              id,
        onRemove:        onRemove,
        close:           close,
    }
    go shard.expireCleanup()
    return shard
}

Expiration Cleanup

The expireCleanup goroutine runs in a loop and removes keys whose lifespan has elapsed. The ticker interval is recomputed after each run to be the smallest remaining lifespan; if no keys remain, a large default interval is used. The loop also listens on addChan to trigger an immediate scan when a newly added key has a shorter lifespan than the current interval.

func (cs *cacheShard) expireCleanup() {
    for {
        select {
        case <-cs.cleanupTicker.C:
        case <-cs.addChan: // immediate trigger for a new expiring key
        case <-cs.close:
            if cs.isVerbose {
                cs.logger.Printf("[shard %d] flush..", cs.id)
            }
            cs.flush()
            return
        }
        cs.cleanupTicker.Stop()
        smallestInternal := 0 * time.Second
        now := time.Now()
        cs.lock.Lock()
        for key, ele := range cs.expireItems {
            item := ele.Value.(*cacheItem)
            if item.LifeSpan() == 0 {
                cs.logger.Printf("warning wrong data
")
                continue
            }
            if now.Sub(item.CreatedOn()) >= item.LifeSpan() {
                delete(cs.items, key)
                delete(cs.expireItems, key)
                cs.list.Remove(ele)
                cs.onRemove(key, item.Value(), Expired)
                if cs.isVerbose {
                    cs.logger.Printf("[shard %d]: expire del key <%s> createdOn:%v, lifeSpan:%d ms 
", cs.id, key, item.CreatedOn(), item.LifeSpan().Milliseconds())
                }
            } else {
                d := item.LifeSpan() - now.Sub(item.CreatedOn())
                if smallestInternal == 0 || d < smallestInternal {
                    smallestInternal = d
                }
            }
        }
        if smallestInternal == 0 {
            smallestInternal = defaultInternal
        }
        cs.cleanupInterval = smallestInternal
        cs.cleanupTicker.Reset(cs.cleanupInterval)
        cs.lock.Unlock()
    }
}

Set Operation

The set method handles both insertion of new keys and updates of existing keys, adjusting the expiration maps and LRU list accordingly.

func (cs *cacheShard) set(key string, value interface{}, lifeSpan time.Duration) error {
    cs.lock.Lock()
    defer cs.lock.Unlock()

    oldEle, ok := cs.items[key]
    if ok { // update existing item
        oldItem := oldEle.Value.(*cacheItem)
        oldLifeSpan := oldItem.LifeSpan()
        oldEle.Value = newCacheItem(key, value, lifeSpan)
        cs.list.MoveToFront(oldEle)
        if oldLifeSpan > 0 && lifeSpan == 0 {
            delete(cs.expireItems, key)
        }
        if oldLifeSpan == 0 && lifeSpan > 0 {
            cs.expireItems[key] = oldEle
            if lifeSpan < cs.cleanupInterval {
                go func() { cs.addChan <- key }()
            }
        }
    } else { // insert new item
        if len(cs.items) >= int(cs.cap) {
            delVal := cs.list.Remove(cs.list.Back())
            item := delVal.(*cacheItem)
            delete(cs.items, item.Key())
            if item.LifeSpan() > 0 {
                delete(cs.expireItems, item.Key())
            }
            cs.onRemove(key, item.Value(), NoSpace)
            if cs.isVerbose {
                cs.logger.Printf("[shard %d] no space del key <%s>
", cs.id, item.Key())
            }
        }
        ele := cs.list.PushFront(newCacheItem(key, value, lifeSpan))
        cs.items[key] = ele
        if lifeSpan > 0 {
            cs.expireItems[key] = ele
            if lifeSpan < cs.cleanupInterval {
                go func() { cs.addChan <- key }()
            }
        }
    }
    if cs.isVerbose {
        if lifeSpan == 0 {
            cs.logger.Printf("[shard %d]: set persist key <%s>
", cs.id, key)
        } else {
            cs.logger.Printf("[shard %d]: set expired key <%s>", cs.id, key)
        }
    }
    return nil
}

LRU Policy

When a key is set or accessed, its list element is moved to the front.

If the shard exceeds its capacity, the element at the back (least recently used) is evicted.

Reference implementation of the LRU list follows the solution described at the Leetcode LRU article: http://mp.weixin.qq.com/s?__biz=MzkwMTE3NTY5MQ==&mid=2247483975&idx=1&sn=23c92c4c4cb19e577b6a78c27808e529&chksm=c0b982a3f7ce0bb5ed33f3ff7d84e2551d64bd76962a8f4dea381f5b6d6c59fca1778392b3f6&scene=21#wechat_redirect

Repository

Source code is hosted at https://github.com/gofish2020/easycache.