前言

在大部分业务系统中，都会使用诸如 Redis、Memcached 等远程缓存，一方面可以避免自身进程内存占用过大而导致的 OOM 或 GC 问题，另一方面也可以实现多个进程共享同一份一致的缓存数据。但对于某些底层服务（例如数据库服务），远程缓存的网络延迟是不可接受的，这就势必需要引入本地内存缓存。

缓存框架的必备需求

本地内存缓存可被视作一个基于本地内存的「KeyValue 数据库」。但相比较于传统数据库而言，它对一致性的要求十分宽松：

对于更新与删除的操作，需要保证强一致性
对于插入操作可以容忍少量丢失
对于读取操作可以容忍少量 Miss

与磁盘数据库的另一个不同之处在于，磁盘数据库的设计有一个前提假设是磁盘是可以随需要而不断扩容的，倘若一个磁盘数据库因磁盘占满而崩溃主要责任是在使用方。而内存缓存则没有这么宽容的假设可以建立，它必须考虑到内存是昂贵且有限的这一事实。

除此之外，由于本地内存缓存处于业务进程当中，所以其需要考虑更多业务向的问题，比如：

由于自身大量老生代的内存占用，是否会对所处进程产生 GC 问题。
当多线程场景下，如何同时解决线程安全、数据竞争、高吞吐等问题。
需要能够适应一些非随机的访问统计规律，例如 Zipf。

综上所述，我们可以归纳出对一个优秀的本地内存缓存系统的要求：

并发线程安全
内存限制 ( 限制最大的可使用空间 )
在多核和多 Goroutines 之间更好的扩展
在非随机key的情况下，很好地扩展 (eg. Zipf)
更高的缓存命中率

本地缓存的组成

在实现一个完整的缓存系统前，我们需要将目标一步步拆解。

首先为了实现缓存逻辑，我们必须有一个类 Map 的 KeyValue 数据结构，同时它必须是线程安全的。为了支持内存限制，我们必须要能够驱逐一些 key，所以需要实现一个驱逐器。为了实现驱逐的同时维持高命中率，我们还需要告诉驱逐器每个 key 的访问记录，让它能够从中分析出哪些 key 可以被驱逐。综上分析，我们可以整理出一个大概的 Roadmap：

实现一个线程安全的 Map 数据结构：存储缓存内容
实现一个访问记录队列：存储访问记录
实现一个驱逐器：管理缓存内容

线程安全的 Map

Go map 与 sync.Mutex 的结合使用

直接用 Go 的 map 来做缓存，这种方法当然简单实在，加上 sync.Mutex 可以避免并发的问题。

但首先它不会限制内存的使用，其次，goroutine 一旦多了，所有 goroutine 都在等锁释放，性能下降了。

map 存储 keys 也是有限制的，当 map 中 keys 数量超过千万级，有可能造成性能瓶颈。是当 map 中存在大量 keys 时，GC 扫描 map 产生的停顿将不能忽略。

好消息是 2015 年 Go 开发者已经对 map 中无指针的情况进行了优化：

我们参考其中的代码，写个GC 测试程序验证下：

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102


package main

import (
  "fmt"
  "os"
  "runtime"
  "time"
)

// Results of this program on my machine:
//
// for t in 1 2 3 4 5; do go run maps.go $t; done
//
// Higher parallelism does help, to some extent:
//
// for t in 1 2 3 4 5; do GOMAXPROCS=8 go run maps.go $t; done
//
// Output(go 1.14):
// With map[int32]*int32, GC took 456.159324ms
// With map[int32]int32, GC took 10.644116ms
// With map shards ([]map[int32]*int32), GC took 383.296446ms
// With map shards ([]map[int32]int32), GC took 1.023655ms
// With a plain slice ([]main.t), GC took 172.776µs

func main() {
  const N = 5e7 // 5000w

  if len(os.Args) != 2 {
    fmt.Printf("usage: %s [1 2 3 4]\n(number selects the test)\n", os.Args[0])
    return
  }

  switch os.Args[1] {
  case "1":
    // Big map with a pointer in the value
    m := make(map[int32]*int32)
    for i := 0; i < N; i++ {
      n := int32(i)
      m[n] = &n
    }
    runtime.GC()
    fmt.Printf("With %T, GC took %s\n", m, timeGC())
    _ = m[0] // Preserve m until here, hopefully
  case "2":
    // Big map, no pointer in the value
    m := make(map[int32]int32)
    for i := 0; i < N; i++ {
      n := int32(i)
      m[n] = n
    }
    runtime.GC()
    fmt.Printf("With %T, GC took %s\n", m, timeGC())
    _ = m[0]
  case "3":
    // Split the map into 100 shards
    shards := make([]map[int32]*int32, 100)
    for i := range shards {
      shards[i] = make(map[int32]*int32)
    }
    for i := 0; i < N; i++ {
      n := int32(i)
      shards[i%100][n] = &n
    }
    runtime.GC()
    fmt.Printf("With map shards (%T), GC took %s\n", shards, timeGC())
    _ = shards[0][0]
  case "4":
    // Split the map into 100 shards
    shards := make([]map[int32]int32, 100)
    for i := range shards {
      shards[i] = make(map[int32]int32)
    }
    for i := 0; i < N; i++ {
      n := int32(i)
      shards[i%100][n] = n
    }
    runtime.GC()
    fmt.Printf("With map shards (%T), GC took %s\n", shards, timeGC())
    _ = shards[0][0]
  case "5":
    // A slice, just for comparison to show that
    // merely holding onto millions of int32s is fine
    // if they're in a slice.
    type t struct {
      p, q int32
    }
    var s []t
    for i := 0; i < N; i++ {
      n := int32(i)
      s = append(s, t{n, n})
    }
    runtime.GC()
    fmt.Printf("With a plain slice (%T), GC took %s\n", s, timeGC())
    _ = s[0]
  }
}

func timeGC() time.Duration {
  start := time.Now()
  runtime.GC()
  return time.Since(start)
}

代码中一共测试了 5 种情况，写入5000w的 keys 后，主动触发 2 次 GC 来测量耗时：

1
2
3
4
5


[1] With map[int32]*int32, GC took 456.159324ms
[2] With map[int32]int32, GC took 10.644116ms
[3] With map shards ([]map[int32]*int32), GC took 383.296446ms
[4] With map shards ([]map[int32]int32), GC took 1.023655ms
[5] With a plain slice ([]main.t), GC took 172.776µs

可以看到，当 map 中没有指针时，扫描停顿时间大约在 10ms 左右，而包含指针int32时则会扩大 45 倍。

不满足上面的 2,3,4 条

Go maps 与分段锁

这个方式的原理与上面的一样，但是锁的粒度更小:假设基础数组包含1024个元素分段锁实际上将其转换为包含64个元素的16个不同子数组，例如{0，63}，{64，127}等。每个子数组都有自己的锁，因此修改{0，63}子数组不会影响{64，127}子数组,一个线程可以写入第一个子数组，而另一个线程写入第二个子数组。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


type SafeMap struct {
    locks []*sync.Mutex
    store []map[string]string
}

func NewSafeMap() SafeMap {
    return SafeMap{
        locks: []*sync.Mutex{{}, {}, {}},
        store: []map[string]string{{}, {}, {}},
    }
}

func hash(k string) int {
    h := fnv.New32a()
    h.Write([]byte(k))
    return int(h.Sum32())
}

func (m *SafeMap) GetLock(k string) *sync.Mutex {
    idx := hash(k) % len(m.locks)
    return m.locks[idx]
}

func (m *SafeMap) GetStore(k string) map[string]string {
    idx := hash(k) % len(m.locks)
    return m.store[idx]
}

func (m *SafeMap) Get(k string) string {
    lock := m.GetLock(k)
    lock.Lock()
    defer lock.Unlock()

    return m.GetStore(k)[k]
}

func (m *SafeMap) Set(k, v string) {
    lock := m.GetLock(k)
    lock.Lock()
    defer lock.Unlock()

    m.GetStore(k)[k] = v
}

一个很自然的想法是将 key 进行分桶，从而分散对锁的竞争。这种方法类似于将「数据库锁」打散成「表锁」。到这一步，我们基本已经完成了一个最简单的高并发缓存。

很多程序员错误的认为，降低锁的粒度可以很好地避免竞争，特别是在分片数超过程序的线程数时 (GOMAXPROCS)

在我们尝试编写一个简单的内存限制缓存的时候，我们也是这样做的。为了保证内存可以在释放之后还给操作系统。我们定期扫描我们的分片，然后释放掉创建的 map，方便以后被再次使用。这种粗浅的方式却很有效，并且性能优于 LRU( 后面会解释 ), 但是也有很多不足。

Go 请求内存很容易，但释放给操作系统却很难。当碎片被清空的同时，goroutines 去访问 key 的时候，会开始分配内存空间，此时之前的内存空间并没有被完全释放，这导致内存的激增，甚至会触发 OOM 错误。
我们没有意识到，访问的模式还受 Zipf 定律的束缚。最常访问的几个 key 仍然存在几个锁，因此产生 Goroutines 的竞争问题。这种方式不满足多核之间的扩展的需求。

考虑到缓存系统读远大于写，我们可以对上述 Map 的互斥锁 Mutex 改为 RWMutex ，从而使得读时并不互斥，改善读性能。

不满足上面的 2,4 条

使用 sync.Map 实现无锁

准确来说，sync.Map 并不是完全的「无锁」，只是一个在绝大部分读场景是无锁的线程安全 Map。具体原理可以参见相关文档。但由于其底层实现并未采取分段锁的方法，所以写的时候会有一个 dirty 上的全局锁，进而会影响到高并发写时的性能。所以对于不在乎写性能同时写也相对不密集的时候，该数据结构是非常理想的选择。

LRU 缓存

groupcache 中的 lru 实现非常经典：一条限制了长度的链表记录了对应的 key 的新旧情况，然后一个 map 记录了对应的 key-value 对。通过限制链表长度来限制内存使用存在不足。当然还对这个 lru 做了二次开发——加了锁。然后发现，这种双链表的 lru 实现每次读都要写一次链表（更新记录的新旧情况）带来了大量的 contention,同样地会引入竞争的问题。

这个缓存的大小同样也依赖于缓存的条数，而不是他们消耗的内存量。在 Go 的堆上面计算复杂的数据结构所消耗的内存大小是非常麻烦的，几乎不可能实现。我们尝试了很多方式，但是都无法奏效。缓存被放入之后，大小也在不停地变化 ( 我们计划之后避免这种情况 )

我们无法预估缓存会引起多少的竞争。在使用了近一年的情况下，我们意识到缓存上面的竞争有多严重，删除掉这块之后，我们的缓存效率提高了 10 倍。

在这块的实现上，每次读取缓存会更新链表中的相对位置。因此每个访问都在等待一个互斥锁。此外 LRU 的速度比 Map 要慢，而且在反复的进行指针的释放，维护一个 map 和一个双向链表。尽管我们在惰性加载上面不断地优化，但依然遭受到严重竞争的影响。

不满足 3,4

分片 LRU 缓存

我们没有实际的去尝试，但是依据我们的经验，这只会是一个暂时的解决方法，而且并不能很好地扩展。( 不过在下面的测试里面，我们依然实现了这个解决方案 )

不满足 4

访问记录队列

对于访问记录的读写，同样牵涉到多线程同时操作同一个内存地址的情况。但我们对其一致性会比缓存内容存储更低，尤其是在高并发数据的假设下，少量的数据丢失并不会影响最终判断结果。

与缓存内容存储的场景不同的是，对于访问记录，每次 Get/Set 的时候都会需要进行一次写入操作，所以它的写速度要求远高于前面的缓存内存存储。更为关键的是，即便是在如此高密度的写情况下，它也同样需要保证线程安全。

虽然上述要求看似十分复杂，我们依然可以试着通过几个方面的分析，来拆解这个问题。

在性能方面，我们需要保证该数据结构写入时是无锁的，因为一旦有锁，前面做的降低锁颗粒度优化都会被这个有锁的结构给拖累。

在写入方式方面，由于我们可以接受少量数据丢失，并且我们没有非常实时的要求，所以我们可以接受异步的写入。

在存储内容方面，我们只需要存储 Key 数据。

根据上述分析，我们不难发现我们需要的是一个基于内存的线程安全的无锁 Lossy 队列。但似乎并没有现成的这种数据结构实现，所以我们可以退一步将这个问题变成，先实现一个 Lossy 队列，再在此基础上，实现线程安全的功能。

环形缓冲：RingBuffer

RingBuffer 是一个非常简单的环形缓冲队列，由一个数组，加上一个读指针和写指针构成。读指针永远只能读到写指针前的数据。

线程安全支持：sync.Pool

Golang 自带的 sync.Pool 可以非常好地和 Ring Buffer 协同工作，实现在近乎无锁的情况下，构造出一个线程安全的高吞吐缓冲队列。

sync.Pool 会在每个线程中维护一个 private 的 Pool（无锁），以及一个可以被其他线程 shared的 Pool（有锁），细节原理可以参考相关文档。在高并发场景下，它基本能够保证每个线程都能够获得一个线程私有的 RingBuffer 对象，从而不需要对其加锁。但 sync.Pool 有一个缺点是在 GC 时会被释放掉，此时会丢失缓冲区内的数据。不过由于我们的前提假设是高并发场景，故而可以推导出数据的丢失量较之于全局是微乎其微的。然而在低并发场景下，这种做法有可能导致缓冲区一直被 GC 清理掉而丧失大部分统计数据。

这里对 RingBuffer 做了一些简单的改动，当缓冲区写满后，会将数据交给驱逐器统计，然后清空缓冲区。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48


import (
    "sync"
)

type ringStripe struct {
    store    []uint64
    capacity uint64
}

func newRingStripe(capacity uint64) *ringStripe {
    return &ringStripe{
        store:    make([]uint64, 0, capacity),
        capacity: capacity,
    }
}

func (s *ringStripe) PushOrReturn(item uint64) []uint64 {
    s.store = append(s.store, item)
    if uint64(len(s.store)) >= s.capacity {
        ret := s.store[:]
        s.store = make([]uint64, 0, s.capacity)
        return ret
    }
    return nil
}

type ringBuffer struct {
    stripes []*ringStripe
    pool    *sync.Pool
}

func newRingBuffer(capacity uint64) *ringBuffer {
    return &ringBuffer{
        pool: &sync.Pool{
            New: func() interface{} {
                return newRingStripe(capacity)
            },
        },
    }
}

func (b *ringBuffer) PushOrReturn(item uint64) []uint64 {
    stripe := b.pool.Get().(*ringStripe)
    defer b.pool.Put(stripe)

    got := stripe.PushOrReturn(item)
    return got
}

设计

驱逐器

驱逐策略

W-TinyLFU 算法在 TinyLFU 前面放了一个基于 LRU 的 Window Cache，从而可以使得前面提到的突发性稀疏流量会缓存在 Window Cache 里，只有在 Window Cache 里被淘汰的缓存才会过继给后面的 TinyLFU。至于最后的 Main Cache，虽然 W-TinyLFU 使用了分段式 LRU 来实现，但我们也可以根据实际情况修改使其符合我们需要的场景。

为了简化本文的实现，我们暂时先不实现 W-TinyLFU 算法，而是实现一个简单的 LFU 驱逐策略。因此我们需要一个能够用来记录访问频率的数据结构。同时由于我们需要存储所有 key 的信息，所以还需要这个数据结构能够有效减少 key 的存储体积。

即便有了上面的频率计数器，为了找到那个需要被驱逐的 LFU key，我们似乎需要遍历所有 key。所以我们不得不再引入一个驱逐候选列表来帮助我们提前排序好需要驱逐的 key。

综上，我们还需要再实现：

能够有效压缩数据大小的频率计数器
预先排序的驱逐候选池

频率计数器：Count-Min Sketch

Count-Min 算法和布隆过滤器类似，核心思想还是通过将相同 Hash 值的数据共享同一份存储空间，以减小整体体积。h1~hd 代表不同的 Hash 算法，这里的 value 代表我们要存储的 key，横坐标表示 Hash 后的值，对哈希值对应每个网格进行 +1 操作。当需要计算某个 key 的估计值时，取对应所有网格数值的最小值。

为了避免一些短时间热度的 key 一直残留在缓存中，每隔一个时间间隔，还需要将所有网格计数器衰减一半。

流行的缓存实现方式

许多方法的优化点是节省 GC 在 map 碎片上花费的时间。GC 的时间会随着 map 存数数量的增加而增大。减少的方案就是分配更少的数量，单位空间更大的区域，在每个空间上存储更多的内容。这确实是一个有效地方法，我们在 Badger 里面大量的使用了这个方法 (Skiplist,Table builder 等 )。很多 Go 流行的缓存框架也是这么做的。

BigCache

超大 map 的内存池导致的 GC 延迟，是可以通过 bigcache 解决的。那 bigcache 到底怎么做到的？

简单来说：shards map + map[uint]uint + []byte + free link = BigCache

定义 shards cache，避免锁粒度过大
map 里只存放 uint 避免指针
实现一个 queue 结构（实际是[]byte，通过 uint 下标追加分配）
采用 free 链机制，删除保留空洞最后一起回收

bigcache 先对 key hash 分配到不同的 shard 中，shard 的数量可配置（默认1024）。每个 shard 有一个 ring buffer 实际存储数据，有一个 map 记录 key 对应的 index，如果同一个 key 被 set 多次，那么前面的 entry 会被置为 invalid。 shard 会在容量不够切且没有到达上限的时候扩容。缓存有生存周期，每个生存周期都会把过期的缓存清除。

每个 map 的 key 都是一个 uint32 的 hash 值，每个值对应一个存储着元数据的 ring buffer。如果 hash 值碰撞了，BigCache 会忽略旧 key，然后把新的值存储到 map 中。预先分配更少，更大的 ring buffer，使用 map [uint32] uint32 是避免支付 GC 扫描成本的好方法

FreeCache

FreeCache 将缓存分成了 256 个segement，每个segement包括 256 个slot和一个 ring buffer 存储数据。当一个新的元素被添加进来的时候，使用 hash 值下 8 位作为标识 id，通过使用 LSB 9-16 的值作为slot ID。将数据分配到多个slot里面，有助于优化查询的时间 ( 分治策略 )。

数据被存储在 ring buffer 中，位置被保存在一个排序的数组里面。如果 ring buffer 内存不足，则会利用 LRU 的策略在 ring buffer 逐个扫描，如果缓存的最后访问时间小于平均访问的时间，就会被删掉。要找到一个缓存内容，在slot中是通过二分查找法对一个已经排好的数据进行查询。读写的时候， segement 会上锁。

GroupCache

GroupCache 使用链表和 Map 实现了一个精准的 LRU 删除策略的缓存。实现内存池的要点：

内存池用 map 不用 sync.Map；map 要加读写锁
map 尽量存非指针(key 和 value 都不包含指针)
map 里存放指针，需要注意 keys 过多会带来的 GC 停顿问题
使用 shards map

然后我们看看GroupCache 的实现方法，这个定义在 lru/lru.go 里：

1
2
3
4


// Cache is an LRU cache. It is not safe for concurrent access.
type Cache struct {
  cache map[interface{}]*list.Element
}

从 cache 的定义可以看出，这是我们说的 map 里包含指针的情况，而且还是不分 shards 的。所以如果你单机 GroupCache 里 keys 过多，还是要注意下用法的。

为了进行公平的比较，我们在 GroupCache 的基础上，实现了一个包括 256 个分片的切片结构。

性能对比

为了比较各种缓存的性能，我们生成了一个 zipf 分布式工作负载，并使用 n1-highcpu-32 机器运行基准测试。下表比较了三个缓存库在只读工作负载下的性能。

只读情况

我们可以看到，由于读锁是无消耗的，所以 BigCache 的伸缩性更好。FreeCache 和 GroupCache 读锁是有消耗的，并且在并发数达到 20 的时候，伸缩性下降了。(Y 轴越大越好 )

只写情况

在只写的情况下，三者的性能表现比较接近，FreeCache 比另两个的情况，稍微好一点。

读写情况 (25% 写，75% 读 )

两者混合的情况下，BigCache 看起来是唯一一个在伸缩性上表现完美的，正如下一节所解释的那样，命中率对于 Zipf 工作负载是不利的。

命中率比较

就读写性能来说，bigcache 表现最好，但是数据测试表示它的命中率有点惨不忍睹。在 Zipf 分布的情况下，缓存数量达到10000000级别的时候，命中率居然可以低到55%。分析有如下两个原因：

bigcache 没有善用 buffer，往往同一个 key 同时存了多个 entry （写入多次的时候）；
bigcache 不会在读的时候更新 entry，所以可能会清退最近访问的 key；

所以，即使是 bigcache 也没有符合要求5。

Ristretto

从那以后，我们阅读了文献，进行了广泛测试的实现，并讨论了在编写缓存库时要考虑的每个变量。今天，我们很自豪地宣布，它已经准备好供更广泛的Go社区使用和试验。

在我们开始解释Ristretto的设计之前，这里是一个代码片段，展示了如何使用它：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


func main() {
	cache, err := ristretto.NewCache(&ristretto.Config{
		NumCounters: 1e7,     // Num keys to track frequency of (10M).
		MaxCost:     1 << 30, // Maximum cost of cache (1GB).
		BufferItems: 64,      // Number of keys per Get buffer.
	})
	if err != nil {
		panic(err)
	}

	cache.Set("key", "value", 1) // set a value
	// wait for value to pass through buffers
	time.Sleep(10 * time.Millisecond)

	value, found := cache.Get("key")
	if !found {
		panic("missing value")
	}
	fmt.Println(value)
	cache.Del("key")
}

指导原则

Ristretto建立在三个指导原则上：

快速访问
高并发和抗竞争性
内存边界。

在此博客文章中，我们将讨论这三个原理以及如何在Ristretto中实现它们。

快速访问

尽管我们喜欢Go及其在功能方面的坚定立场，但Go的某些设计决策阻止了我们挤出我们想要的所有性能。最值得注意的是Go的并发模型。由于对CSP的关注，大多数其他形式的原子操作都被忽略了。这使得难以实现在缓存库中有用的无锁结构。例如，Go 不提供线程本地存储。

缓存的核心是散列图，其中包含有关进出的规则。如果哈希表的性能不佳，则整个缓存将受到影响。与Java相反，Go没有无锁的并发哈希图。相反，Go中的线程安全是通过显式获取互斥锁来实现的。

我们尝试了多种实现方式（使用storeRistretto中的接口），发现sync.Map对于读取繁重的工作负载表现良好，但对于写入工作负载却表现不佳。考虑到没有线程本地存储，我们发现分片互斥包装的Gomap具有最佳的整体性能。特别是，我们选择使用256个分片以确保即使在64核服务器上也能很好地执行。

使用基于分片的方法，我们还需要找到一种计算密钥应该放入哪个分片的快速方法。这种要求以及对长密钥消耗过多内存的担忧，导致我们不得不使用uint64密钥，而不是存储整个密钥。这样做的理由是，我们需要在多个位置进行键的散列，并且在入口处执行一次即可使我们重新使用该散列，从而避免了更多的计算。

为了生成快速哈希，我们从Go Runtime 借用了runtime.memhash。此函数使用汇编代码快速生成哈希。请注意，哈希具有一个随机化器，该随机化器会在进程启动时进行初始化，这意味着相同的密钥在下一次进程运行时不会生成相同的哈希。但是，对于非永久性缓存来说，这没关系。在我们的实验中，我们发现它可以在10ns内对64字节密钥进行哈希处理。

1
2
3
4


BenchmarkMemHash-32 200000000	 8.88 ns/op
BenchmarkFarm-32    100000000	 17.9 ns/op
BenchmarkSip-32      30000000	 41.1 ns/op
BenchmarkFnv-32      20000000	 70.6 ns/op

然后，我们不仅使用此哈希作为存储的密钥，而且还弄清楚了密钥应放入的分片。这确实会带来按键碰撞的机会，这是我们计划在以后处理的事情。

并发和竞争

要实现高命中率，需要管理有关缓存中存在的内容以及缓存中应存在的内容的元数据。在跨goroutines平衡缓存的性能和可伸缩性时，这变得非常困难。幸运的是，有一篇名为BP-Wrapper的论文，它写了一个系统框架，该框架使得任何替换算法几乎都可以无争用地锁定。本文介绍了两种缓解争用的方法：预取和批处理。我们仅使用批处理。

批处理几乎可以按照您的想法工作。与其为每个元数据突变获取互斥锁，不如在获取互斥锁并处理突变之前等待环形缓冲区填满。如该论文所述，这几乎没有任何开销地降低了竞争。

我们应用这一切的方法Gets，并Sets到缓存中。

Gets

当然，所有获取到缓存的内容都会立即得到服务。困难的部分是捕获Get，因此我们可以跟踪密钥访问。在LRU缓存中，通常将密钥放在链接列表的开头。在基于LFU的缓存中，我们需要增加项目的点击计数器。这两个操作都需要对缓存全局结构进行线程安全访问。BP-Wrapper建议使用批处理来处理命中计数器的增量，但问题是我们如何在不获取另一个锁的情况下实现此批处理过程。

这听起来像是Go渠道的完美用例，事实确实如此。不幸的是，通道的吞吐量性能使我们无法使用它们。取而代之的是，我们设计了一种巧妙的方法来sync.Pool实现带状，有损环形缓冲区，这些缓冲区性能出色，数据丢失很少。

池中存储的任何项目都可以随时自动删除，恕不另行通知。这就引入了一种有损行为。池中的每个项目实际上都是一批密钥。批次填满后，将其推送到某个渠道。故意将通道大小保持较小，以避免消耗太多的CPU周期来处理它。如果通道已满，则删除该批次。这引入了有损行为的第二级。一个goroutine从内部通道中提取此批次并处理密钥，从而更新其命中计数器。

1
2
3
4


AddToLossyBuffer(key):
  stripe := b.pool.Get().(*ringStripe)
  stripe.Push(key)
  b.pool.Put(stripe)

Once buffer fills up, push to channel:

1
2
3
4
5
6
7
8


  select {
  case p.itemsCh <- keys:
      p.stats.Add(keepGets, keys[0], uint64(len(keys)))
      return true
  default:
      p.stats.Add(dropGets, keys[0], uint64(len(keys)))
      return false
  }

p.itemCh processing:

1
2
3
4
5


  func (p *tinyLFU) Push(keys []uint64) {
    for _, key := range keys {
      p.Increment(key)
    }
  }

使用a sync.Pool优于其他任何功能（切片，带区互斥锁等）的性能优势主要是由于内部使用了线程本地存储，而Go使用者无法将其作为公共API使用。

Sets

Set缓冲区的要求与Get稍有不同。在Gets中，我们对键进行缓冲，仅在缓冲区填满后才对其进行处理。在集合中，我们希望尽快处理密钥。因此，我们使用一个通道来捕获Set，如果通道已满，则将它们放在地板上以避免竞争。几个后台goroutine从通道中选择集并处理该集。

与Gets一样，该方法旨在优化竞争阻力。但是，有一些警告，如下所述。

1
2
3
4
5
6
7
8


select {
case c.setBuf <- &item{key: hash, val: val, cost: cost}:
    return true
default:
    // drop the set and avoid blocking
    c.stats.Add(dropSets, hash, 1)
    return false
}

注意事项

Ristretto中的集合被排队到缓冲区中，控制权返回给调用者，然后将该缓冲区应用于高速缓存。这有两个副作用：

不能保证一定会套用。可以立即删除它以避免争用，或者以后可以被该策略拒绝。
即使应用了设置，呼叫返回给用户后也可能需要花费几毫秒的时间。用数据库术语来说，这是一个最终的一致性模型。

但是，如果缓存中已存在密钥，Set将立即更新该密钥。这是为了避免缓存的键保留陈旧的值。

抗争性

Ristretto针对争用进行了优化。在繁重的并发负载下，这确实表现出色，我们将在下面的吞吐量基准中看到这一点。但是，它将损失一些元数据以换取更好的吞吐量性能。

有趣的是，由于密钥访问分布的性质，信息丢失不会损害我们的命中率性能。如果我们确实丢失了元数据，则通常会统一丢失元数据，而密钥访问分配仍保持不一致。因此，我们仍然可以实现较高的命中率，并且命中率的下降很小，如下图所示。

记忆边界

关键成本

无限大的缓存实际上是不可能的。高速缓存必须有大小限制。许多缓存库会将缓存大小视为元素数。我们发现这种方法很幼稚。当然，它可以在大小相同的工作负载中工作。但是，大多数工作负载具有可变大小的值。一个值可能要花几个字节，另一个值要花几千字节，而另一个值要花几兆字节。将它们视为具有相同的内存成本是不现实的。

在Ristretto中，我们将成本附加到每个键值。用户可以在调用Set时指定该费用。我们将此成本与缓存的MaxCost相比较。当缓存以最大容量运行时，沉重的物品可能会取代许多轻量物品。该机制非常不错，因为它适用于所有不同的工作负载，包括幼稚的方法，其中每个键值花费1。

通过TinyLFU的录取政策

“我们应该让什么进入缓存？”

由录取政策回答。显然，目标是让新项目比当前项目更“有价值”。但是，如果您考虑跟踪与“价值”问题相关的相关项目信息所需的开销（延迟和内存），这将成为一个挑战。

尽管是提高命中率的有据可查的策略，但大多数Go缓存库根本没有接纳策略。实际上，许多LRU收回实现都将最新密钥视为最有价值。

此外，大多数Go缓存库使用纯LRU或近似LRU作为其驱逐策略。尽管具有LRU近似值的质量，但某些工作负载更适合LFU驱逐策略。我们发现使用各种跟踪的基准测试就是这种情况。

对于我们的准入策略，我们研究了一篇名为TinyLFU的新颖有趣的论文：高效的高速缓存准入策略。从高度上讲，TinyLFU提供了三种方法：

增量（键uint64）
估计（键uint64）int（称为ɛ）
重启

该论文对此进行了最好的解释，但是TinyLFU是一种与逐出无关的准入策略，旨在以很少的内存开销来提高命中率。主要思想是仅在新项目的估计值高于被逐出的项目的估计值时才允许使用。我们使用Count-Min Sketch 在Ristretto中实现了TinyLFU 。它使用4位计数器来近似项（ɛ）的访问频率。与使用普通键映射到频率映射相比，每个键的这种小成本使我们能够跟踪更大范围的全局键空间样本。

TinyLFU还通过Reset功能保持键访问的新近性。N键4递增后，计数器减半。因此，一段时间未看到的键会将其计数器重置为零；为最近出现的密钥铺平道路。

通过采样LFU驱逐政策

当缓存达到容量时，每个传入密钥都应替换缓存中存在的一个或多个密钥。不仅如此，传入密钥的should应该比被逐出的密钥的higher高。要查找低key的密钥，我们使用了Go map迭代提供的自然随机性来挑选一个密钥样本，并在它们上循环查找最低ɛ的密钥。

然后，我们将此键的against与传入键进行比较。如果输入的密钥具有较高的ɛ，则此密钥将被逐出（逐出策略）。否则，输入密钥将被拒绝（准入策略）。重复此机制，直到可以将传入密钥的成本放入高速缓存中为止。因此，单个输入密钥可以移动一个以上的密钥。请注意，传入密钥的成本不会影响选择退出密钥的成本。

使用这种方法，命中率在各种工作负载的确切LFU策略的1％以内。这意味着我们可以在同一个小包装中获得准入策略，保守的内存使用和较低的争用的好处。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


// Snippet from the Admission and Eviction Algorithm
incHits := p.admit.Estimate(key)
for ; room < 0; room = p.evict.roomLeft(cost) {
    sample = p.evict.fillSample(sample)
    minKey, minHits, minId := uint64(0), int64(math.MaxInt64), 0
    for i, pair := range sample {
        if hits := p.admit.Estimate(pair.key); hits < minHits {
            minKey, minHits, minId = pair.key, hits, i
        }
    }
    if incHits < minHits {
        p.stats.Add(rejectSets, key, 1)
        return victims, false
    }
    p.evict.del(minKey)
    sample[minId] = sample[len(sample)-1]
    sample = sample[:len(sample)-1]
    victims = append(victims, minKey)
}

门卫

在我们将新密钥放入TinyLFU中之前，Ristretto使用bloom过滤器首先检查该密钥是否之前已被查看过。仅当密钥在布隆过滤器中已经存在时，才将其插入TinyLFU。这是为了避免长时间不被看到的长尾键污染 TinyLFU。

计算键的ɛ时，如果该项目包含在Bloom Bloom过滤器中，则其频率估计为TinyLFU的估算值加1。在ResetTinyLFU 期间，还会清除Bloom过滤器。

指标

尽管是可选的，但重要的是要了解缓存的行为方式。我们希望确保不仅可以实现与缓存相关的跟踪指标，而且这样做的开销也足够低以至于可以打开和保持打开状态。

除了命中和遗漏之外，Ristretto还跟踪指标，例如键及其添加，更新和收回的成本，集的丢失或拒绝以及集的丢失或保留。所有这些数字有助于了解各种工作负载上的缓存行为，并为进一步优化铺平道路。

最初，我们使用原子计数器。但是，开销很大。我们将原因归结为虚假分享。考虑一个多核系统，其中不同的原子计数器（每个8字节）位于同一高速缓存行（通常为64字节）中。对这些计数器之一进行的任何更新都会导致其他计数器被标记为无效。这将强制为拥有该缓存的所有其他核心重新加载缓存，从而在缓存行上产生写争用。

为了实现可伸缩性，我们确保每个原子计数器都完全占用完整的缓存行。因此，每个内核都在不同的缓存行上工作。Ristretto通过为每个度量分配256个uint64来使用此功能，在每个活动uint64之间保留9个未使用的uint64。为了避免额外的计算，将密钥哈希值重新使用以确定要增加的uint64。

Add:

1
2
3
4
5


	valp := p.all[t]
	// Avoid false sharing by padding at least 64 bytes of space between two
	// atomic counters which would be incremented.
	idx := (hash % 25) * 10
	atomic.AddUint64(valp[idx], delta)

Read:

1
2
3
4
5
6


	valp := p.all[t]
	var total uint64
	for i := range valp {
		total += atomic.LoadUint64(valp[i])
	}
	return total

读取度量标准时，将读取并汇总所有uint64，以获取最新编号。使用这种方法，指标跟踪仅会增加大约10％的缓存性能开销。

基准测试

既然您已经了解了Ristretto中存在的各种机制，那么让我们看看与其他流行的Go缓存相比，命中率和吞吐量基准。

命中率

使用Damian Gryski的cachetest和我们自己的基准测试套件来衡量命中率。这两个实用程序的命中率数字相同，但是我们增加了读取某些跟踪格式（特别是LIRS和ARC）以及CSV输出的功能，以便于绘制图形。如果要编写自己的基准测试或添加跟踪格式，请签出 sim软件包。

为了更好地了解改进的空间，我们添加了一个理论上最佳的缓存实现，该实现使用未来的知识来逐出在其整个生命周期内命中次数最少的项目。请注意，这是千篇一律的LFU驱逐策略，其他千篇一律的策略可能会使用LRU。根据工作量，LFU或LRU可能更适合，但我们发现通透的LFU对于与Ristretto的Sampled LFU 进行比较很有用。

搜索

将该跟踪描述为“大型商业搜索引擎响应各种Web搜索请求而发起的磁盘读取访问。”

数据库

此跟踪被描述为“在商业站点上运行的数据库服务器，该服务器在商业数据库之上运行ERP应用程序。”

循环播放

此跟踪演示了循环访问模式。在本基准及以下基准中，我们不能包括Fastcache，Freecache或Bigcache实施，因为它们的最小容量要求会使结果产生偏差。一些跟踪文件很小，并且需要较小的容量来进行性能测量。

CODASYL

将此跟踪描述为“在一小时内对CODASYL数据库的引用”。请注意，与此处的其他相比，Ristretto的表现受到影响。这是因为LFU驱逐策略不适合此工作负载。

通量

可以通过使用所测量的相同的效用与以前的博客文章，从而产生了大量的用于获取和根据业务负载设置够程之间键和的交替。

所有吞吐量基准均在具有16GB RAM的Intel Core i7-8700K（3.7GHz）上运行。

混合：25％写入，75％读取

读取：100％读取

写入：100％写入

未来的改进

您可能已经在CODASYL基准测试中注意到，Ristretto的性能在LRU繁重的工作负载中受到影响。但是，对于大多数工作负载，我们的“采样LFU”策略的性能都很好。问题变成了“我们如何才能兼得两全”？

在一纸所谓的自适应软件高速缓存管理，这个确切的问题进行了探讨。基本思想是在主缓存段之前放置一个LRU“窗口”，并使用爬山技术自适应地调整窗口大小以最大化命中率。咖啡因已经看到了巨大的做结果此。我们相信Ristretto将来也会从中受益。

在Dgraph中使用此缓存的一些初步实验看起来很有希望。我们希望在接下来的几个月中将Ristretto集成到Dgraph和 Badger中。请检查一下，也许使用ristretto，以加快您的工作负载！

参考: go cache 实现综述 Go 中的缓存现状设计实现高性能本地内存缓存你应该知道的缓存进化史 Ristretto简介：高性能Go缓存

文章目录

前言