这篇文章使它成为Golang subreddit的顶端，并且在Hacker News的头版上呈现＃2趋势。在那里参与讨论，并通过给我们一个GitHub star向我们展示喜爱。
每个数据库系统都需要智能缓存。也就是说，缓存保留最频繁或最近访问的项目并具有可配置的内存利用率限制。
作为图形数据库，Dgraph可以访问每个查询数千甚至数百万个密钥，具体取决于中间结果的数量。通过我们的键值数据库Badger访问这些数据会导致磁盘搜索，这是我们希望因性能原因而减少的。
典型的访问模式遵循Zipfian分布。访问频率最高的密钥的访问次数比其他访问密钥次数多。我们也在Dgraph中看到了这一点。
我们对使用Go语言构建Dgraph的选择非常满意。关于Go为什么要编写一个优秀的语言来编写后端代码，可以说很多，但这本身就是一个帖子。我们不会将Go替换为任何其他现有语言。尽管Go很棒，但Go生态系统仍然缺乏。
围绕Go的一般抱怨源于缺乏围绕该语言的库生态系统。 Go是成熟的，因为它是稳定的，并且已经实现了对机器内核的快速编译，执行和利用的核心承诺。但是，对于围绕并发构建的语言，它仍然缺乏高性能，并发库的生态系统，这些库可以很好地扩展到核心数量。并发列表或映射在很大程度上留给了最终用户 - 如果这是一个串行执行的语言会很好 - 但是当一切都是围绕并发构建时，这感觉就像一个明显的遗漏。
特别是，Go缺少并发LRU（或LFU）缓存，它可以很好地扩展到进程全局缓存。在这篇博文中，我将带你了解通常提倡的各种尝试，包括我们在Dgraph中执行和学习的一些尝试。然后，Aman将展示Go生态系统中现有流行缓存实现的设计，性能和命中率比较。
我将首先列出缓存的要求，我们可以采取的各种方法来实现缓存，以及它们如何无法实现缓存。
缓存的要求
1. 并发。
2. 内存限制（限制为可配置的最大内存使用量）。
3. 随着核心和goroutines数量的增加而扩展。
4. 在非随机密钥访问分配（例如Zipf）下很好地扩展。
5. 高缓存命中率
使用带有sync.Mutex的Go map
使用带有sync.Mutex（或sync.RWMutex）的Go mpa是最常提倡的缓存方法。这确实导致所有goroutines在一次锁定时阻塞，这可能导致争用。这也无法保留内存使用量的选项卡。因此，它本身不能作为内存限制缓存。
不满足2-4
使用Go map进行锁定条带化
这与上面的概念相同，但是使用指纹将密钥拆分为许多由互斥锁保护的较小Go映射分片。许多开发人员错误地认为锁定条带化是避免争用的好方法，特别是在设置分片数超过程序中的线程数（> GOMAXPROCS）时。
在我们构建简化的内存限制缓存的初始尝试中，我们也构建了它。为了允许将内存释放回操作系统，我们会定期选择随机分片并删除其map，以便重新填充。这是一种粗略但简单的技术，其性能优于LRU缓存（如下所述），但有许多缺点。
一，Go很难将内存释放回操作系统，但要快速请求它。一旦碎片被清空，尝试访问该碎片中的键的goroutines将开始分配内存，而前一个内存仍未完全释放，导致内存使用量激增和快速OOM崩溃。
此外，我们当时未能意识到的是，访问模式受Zipf定律的约束。最常访问的密钥仍然在几个锁之下，因此成为所有goroutine争用的原因。这种方法的性能不能很好地适应核心数量。
不满足2，4
LRU缓存
Go有一个基本的LRU缓存实现作为groupcache的一部分。在使用映射分片锁定条带化失败后，我们通过引入锁并使其并发来修改此LRU缓存。虽然这个缓存确实解决了由频繁和一致的内存释放引起的内存峰值的直接问题，但我们意识到它会引入争用。
此缓存的大小也取决于条目数，而不是它们消耗的内存量。试图在Go中估计堆上复杂数据结构的内存使用量是非常昂贵的，而且几乎不可能做到正确，这是我们在尝试使用多种机制后徒劳无功的事情。这变得特别困难，因为我们的数据结构在被放入缓存后正在发生变化（我们计划避免向前发展）。
但是，我们不理解缓存可能导致多少争用。拥有这个缓存超过一年后，我们意识到这个缓存周围的争用是如此重要，删除它导致我们的查询加速10倍！
在该实现中，每次读取都是写入，其更新新近链接列表中的元素的相对定位。因此，所有访问都在等待一个互斥锁。此外，LRU的关键部分比地图慢，并且执行大量指针解引用，维护map和双向链接列表。尽管我们在懒惰的驱逐下做出了努力，但它仍然遭受了严重的争论。
不满足3-4
条带LRU缓存
我们没有费心去尝试这个。 从我们对条纹map碎片的实验中，我们知道它只是一种渐进的改进，并且不能很好地扩展。 （尽管为了对本文的缓存进行基准测试，我们实现了如下所述的条带化LRU缓存。）
不满足4
流行的缓存实现
许多其他方法旨在减少在map分片上花费的GC时间。 GC时间随着map中条目数量的增加而增加。通过分配更少，更大的字节切片并在每个切片中存储许多高速缓存条目来实现减少。这是一种有效的方法 - 我们在Badger的多个地方使用它（Skiplist，Table builder等）。 Go中一些流行的缓存使用这种技术。
BigCache
BigCache根据密钥的哈希将数据划分为分片。每个分片都包含一个映射和一个环形缓冲区。无论何时设置新元素，它都会将元素附加到相应分片的环形缓冲区中，并且缓冲区中的偏移量将存储在映射中。如果多次设置相同的元素，则缓冲区中的先前条目将标记为无效。如果缓冲区太小，则会扩展，直到达到最大容量。
每个映射键都是一个uint32散列，该值是指向缓冲区中偏移量的uint32指针，其中值与元数据信息一起存储。如果存在哈希冲突，BigCache将忽略先前的密钥并将当前密钥存储到映射中。预先分配更少，更大的缓冲区并使用map [uint32] uint32是避免支付GC扫描成本的好方法。
FreeCache
FreeCache将缓存划分为256个段。每个段包含256个插槽和一个用于存储数据的环形缓冲区。当将新密钥添加到高速缓存时，使用密钥的散列的低八位来标识段id。此外，使用密钥的散列的LSB 9-16来选择时隙。将数据划分为插槽有助于在查找缓存中的密钥时减少搜索空间。
然后将数据附加到环形缓冲区中，并将偏移存储到排序的数组中。如果环形缓冲区没有足够的空间，则使用修改的LRU策略从环形缓冲区的开头在段中执行驱逐。如果条目的最后访问时间小于段的平均访问时间，则从环形缓冲区中删除条目。要在Get上的高速缓存中查找条目，将在相应插槽中的已排序数组中执行二进制搜索。
GroupCache
GroupCache使用链表和Go映射实现精确的LRU驱逐策略。为了公平比较，我们在GroupCache之上实现了256个分片的分片逻辑。
绩效比较
为了比较各种缓存的性能，我们生成了Zipf分布式工作负载，并使用n1-highcpu-32机器运行基准测试。 下表比较了只读工作负载的三个缓存库的性能。
只读
对于只写工作负载，所有库似乎执行类似。 尽管如此，FreeCache的表现略好于其他两个。
读写（25％写入，75％读取）
对于包含25％写入和75％读取的混合工作负载，虽然BigCache是唯一显然可以很好地扩展的库，但是Zipf工作负载的命中率是不好的，如下一节所述。
命中率比较
三个缓存的命中率如下所示。 FreeCache非常接近GroupCache实现的LRU策略。 但是，由于以下原因，BigCache对Zipf分布式工作负载效果不佳：
BigCache没有有效利用缓冲区，最终可能会在缓冲区中为同一个密钥存储多个条目。
BigCache不会更新访问（读取）条目，因此导致最近访问的密钥被逐出。
因此，我们可以得出结论，没有一个缓存库满足所有要求。
GroupCache和FreeCache在要求4上失败，而BigCache在要求5上失败。
那么，我们还剩下什么？
好吧，没什么。 我们不知道Go中的智能内存限制缓存可以满足整个需求列表。 如果你知道其中一个，请在评论中告诉我们。
与此同时，我们遇到了Caffeine，一个由Cassandra，Finagle和其他数据库系统使用的Java库。 它使用TinyLFU，一种高效的缓存准入策略，并使用各种技术随着线程和内核数量的增长而扩展和执行，同时提供接近最佳的命中率。 你可以在本文中详细了解它的工作原理。
Caffeine符合我在开始时提到的所有五个要求，所以我们正在研究构建Go等效的Caffeine，它可以满足我们的需求，并可能填补Go语言中并发，高性能，内存限制缓存的空白。 如果你想贡献或者你已经建立了类似的东西，请告诉我们！