Memory Leak in LFU Cache Implementation

[RyanDevlin]

Description

There is a fairly severe memory leak in the implementation of the LFU cache. This leak may also manifest itself in the other algorithms, although I haven't checked yet.

Reproducing

Here is what my main function looks like to produce this leak.

func main() {
        defer profile.Start(profile.MemProfile).Stop()
    gc := gcache.New(10).
        LFU().
        Build()
    gc.Set("key0", "ok0")
    gc.Set("key1", "ok1")
    gc.Set("key2", "ok2")
    gc.Set("key3", "ok3")

    for i := 0; i < 400000; i++ {
        v, err := gc.Get("key0")
        if err != nil {
            panic(err)
        }
        if i == 399999 {
            fmt.Println("value:", v)
        }
    }
}

Evidence

As you can see in the function above. We first initialize a new LFU cache that can hold 10 items. We then set 4 of these items to key:value pairs. Finally we read the first item 400,000 times, and print it's value on the last run.

Below is the output of the memory profiler looking at the functions making the most memory allocations.

$ go tool pprof ~/test /tmp/profile958427541/mem.pprof
File: test
Type: inuse_space
Time: Dec 4, 2020 at 12:38pm (EST)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top5
Showing nodes accounting for 14MB, 100% of 14MB total
Showing top 5 nodes out of 8
      flat  flat%   sum%        cum   cum%
   10.58MB 75.53% 75.53%       14MB   100%  github.com/bluele/gcache.(*LFUCache).increment
    3.43MB 24.47%   100%     3.43MB 24.47%  container/list.(*List).insertValue (inline)
         0     0%   100%     3.43MB 24.47%  container/list.(*List).InsertAfter (inline)
         0     0%   100%       14MB   100%  github.com/bluele/gcache.(*LFUCache).Get
         0     0%   100%       14MB   100%  github.com/bluele/gcache.(*LFUCache).get

This immediately indicates that somehow, the 4 key value pairs placed into the cache, along with the 400,000 reads performed, required an allocation of 14MB of memory. As we can see, the majority of all the allocations came from inside the github.com/bluele/gcache.(*LFUCache).increment frunction.

If we take a look at this function we see the following:

func (c *LFUCache) increment(item *lfuItem) {
    currentFreqElement := item.freqElement
    currentFreqEntry := currentFreqElement.Value.(*freqEntry)
    nextFreq := currentFreqEntry.freq + 1
    delete(currentFreqEntry.items, item)

    nextFreqElement := currentFreqElement.Next()
    if nextFreqElement == nil {
        nextFreqElement = c.freqList.InsertAfter(&freqEntry{
            freq:  nextFreq,
            items: make(map[*lfuItem]struct{}),
        }, currentFreqElement)
    }
    nextFreqElement.Value.(*freqEntry).items[item] = struct{}{}
    item.freqElement = nextFreqElement
}

At first glance, it becomes obvious that the frequency list inside the cache struct (c.freqList) is growing quite large. If we trace the increment function upwards we can see it is called every time we request an item from the cache, as long as we did not set a timeout on our items (in this case we did not).

The result of this is that c.freqList grows by one list entry every time we request an item from the cache. We can see this behavior in the Devel debugger:

(hits goroutine(1):1 total:1) (PC: 0x4f9225)
   179:
   180: func (c *LFUCache) increment(item *lfuItem) {
   181:         currentFreqElement := item.freqElement
   182:         currentFreqEntry := currentFreqElement.Value.(*freqEntry)
   183:         nextFreq := currentFreqEntry.freq + 1
=> 184:         delete(currentFreqEntry.items, item)
   185:
   186:         nextFreqElement := currentFreqElement.Next()
   187:         if nextFreqElement == nil {
   188:                 nextFreqElement = c.freqList.InsertAfter(&freqEntry{
   189:                         freq:  nextFreq,
(dlv) continue
(dlv) continue // We skip ahead now 40 calls to increment()
(dlv) continue
.
.
.
.
(hits goroutine(1):40 total:40) (PC: 0x4f9225)
   181:         currentFreqElement := item.freqElement
   182:         currentFreqEntry := currentFreqElement.Value.(*freqEntry)
   183:         nextFreq := currentFreqEntry.freq + 1
   184:         delete(currentFreqEntry.items, item)
   185:
=> 186:         nextFreqElement := currentFreqElement.Next()
   187:         if nextFreqElement == nil {
   188:                 nextFreqElement = c.freqList.InsertAfter(&freqEntry{
   189:                         freq:  nextFreq,
   190:                         items: make(map[*lfuItem]struct{}),
   191:                 }, currentFreqElement)
(dlv) print c.freqList
*container/list.List {
        root: container/list.Element {
                next: *(*"container/list.Element")(0xc000078750),
                prev: *(*"container/list.Element")(0xc0000795f0),
                list: *container/list.List nil,
                Value: interface {} nil,},
        len: 40,}

The above steps were as follows. Set a breakpoint on line 186, in the middle of the increment function. Run continue to skip to the next time we hit the break point. Do this 39 more times to allow 40 consecutive reads from the cache. At this point, we print the frequency list in the cache with (dlv) print c.freqList. This shows us that the list is of length 40, even though there are only 4 items in the cache.

If we follow the debugger further this pattern continues and the list grows linearly. This is obviously unacceptable behavior and ends up consuming large amounts of memory for operations that should consume none.

[shubhati]

I have identified the fix for this issue. Would love to contribute

[RyanDevlin]

Out of curiosity, what was the fix you identified?

[shubhati]

@RyanDevlin Please find the diff for the fix below. Basically when there's only one entry in lfu item's map, increment removes that entry from it and create a new lfu item for that entry. That's why list keeps growing on every increment. Looking in the diff would give you a better explanation.

diff --git a/lfu.go b/lfu.go
index f781a1f..d42d5d2 100644
--- a/lfu.go
+++ b/lfu.go
@@ -181,17 +181,22 @@ func (c *LFUCache) increment(item *lfuItem) {
        currentFreqElement := item.freqElement
        currentFreqEntry := currentFreqElement.Value.(*freqEntry)
        nextFreq := currentFreqEntry.freq + 1
-       delete(currentFreqEntry.items, item)
-
-       nextFreqElement := currentFreqElement.Next()
-       if nextFreqElement == nil {
-               nextFreqElement = c.freqList.InsertAfter(&freqEntry{
-                       freq:  nextFreq,
-                       items: make(map[*lfuItem]struct{}),
-               }, currentFreqElement)
+       if len(currentFreqEntry.items) == 1 {
+               currentFreqEntry.freq = nextFreq
+       } else {
+               delete(currentFreqEntry.items, item)
+
+               nextFreqElement := currentFreqElement.Next()
+               if nextFreqElement == nil {
+                       nextFreqElement = c.freqList.InsertAfter(&freqEntry{
+                               freq:  nextFreq,
+                               items: make(map[*lfuItem]struct{}),
+                       }, currentFreqElement)
+               }
+               nextFreqElement.Value.(*freqEntry).items[item] = struct{}{}
+
+               item.freqElement = nextFreqElement
        }
-       nextFreqElement.Value.(*freqEntry).items[item] = struct{}{}
-       item.freqElement = nextFreqElement
 }

 // evict removes the least frequence item from the cache.

[bluele]

Thanks @RyanDevlin @shubhati.

Definitely, keeping an empty freqEntry is very inefficient in memory usage.

This problem occurs not only when it calls increment, but also when we delete an element of freqEntry that has only one element in remove.

@shubhati, thanks for your patch and contribution! But it seems to not work if nextFreqElement.freq does not match nextFreq. I'll open a pull-request that includes tests and a patch that fixes remove later.