缓存设计的一些思考

from: http://www.nosqlnotes.net/archives/222

互联网架构中缓存无处不在，某厂牛人曾经说过：”缓存就像清凉油，哪里不舒服，抹一下就好了”。高品质的存储容量小，价格高；低品质存储容量大，价格低，缓存的目的就在于”扩充”高品质存储的容量。本文探讨缓存相关的一些问题。

LRU替换算法

缓存的技术点包括内存管理和替换算法。LRU是使用最多的替换算法，每次淘汰最久没有使用的元素。LRU缓存实现分为两个部分：Hash表和LRU链表，Hash表用于查找缓存中的元素，LRU链表用于淘汰。内存常以Slab的方式管理。

上图是Memcache的内存管理示意图，Memcache以Slab方式管理内存块，从系统申请1MB大小的大块内存并划分为不同大小的Chunk，不同Slab的Chunk大小依次为80字节，80 * 1.25，80 * 1.25^2, …。向Memcache中添加item时，Memcache会根据item的大小选择合适的Chunk。

Oceanbase最初也采用LRU算法，只是内存管理有些不同。Oceanbase向系统申请2MB大小的大块内存，插入item时直接追加到最后一个2MB内存块的尾部，当缓存的内存量太大需要回收时根据一定的策略整块回收2MB的内存，比如回收最近最少使用的item所在的2MB内存块。这样的做法虽然不是特别精确，但是内存管理简单，对于系统初期很有好处。

缓存锁

缓存需要操作两个数据结构：Hash表和LRU链表。多线程操作cache时需要加锁，比较直接的做法是整体加一把大锁后再操作Hash表和LRU链表。有如下的优化思路：

1, Hash表和LRU链表使用两把不同的锁，且Hash表锁的粒度可以降低到每个Hash桶一把锁。这种做法的难点是需要处理两种数据结构不一致导致的问题，假设操作顺序为read hash -> del hash item -> del lru item -> read lru item，最后一次read lru item时item所在的内存块可能已经被回收或者重用，一般需要引入引用计数并考虑复杂的时序问题。

2, 采用多个LRU链表以减少LRU表锁粒度。Hash表的锁冲突可以通过增加Hash桶的个数来解决，而LRU链表是一个整体，难以分解。可以将缓存的数据分成多个工作集，每个item属于某个工作集，每个工作集一个LRU链表。这样做的主要问题是可能不均衡，比如某个工作集很热，某些从整体上看比较热的数据也可能被淘汰。

3, 牺牲LRU的精确性以减少锁。比如Mysql中的LRU算法变形，大致如下：将LRU链表分成两部分，前半部分和后半部分，如果访问的item在前半部分，什么也不做，而不是像传统的LRU算法那样将item移动到链表头部；又如Linux Page Cache中的CLOCK算法。Oceanbase目前的缓存算法也是通过牺牲精确性来减少锁。前面提到，Oceanbase缓存以2MB的内存块为单位进行淘汰，最开始采用LRU策略，每次淘汰最近最少使用的item所在的2MB内存块，然而，这样做的问题是需要维护最近最少使用的item，即每次读写缓存都需要加锁。后续我们将淘汰策略修改为：每个2MB的内存块记录一个访问次数和一个最近访问时间，每次读取item时，如果访问次数大于所有2MB内存块访问次数的平均值，更新最近访问时间；否则，将访问次数加1。根据记录的最近访问时间淘汰2MB内存块。虽然，这个算法的缓存命中率不容易评估，但是缓存读取只需要一些原子操作，不需要加锁，大大减少了锁粒度。

4, 批量操作。缓存命中时不需要立即更新LRU链表，而是可以将命中的item保存在线程Buffer中，积累了一定数量后一次性更新LRU链表。

LIRS思想

Cache有两个问题：一个是前面提到的降低锁粒度，另一个是提高精准度，或者称为提高命中率。LRU在大多数情况下表现是不错的，但是有如下的问题：

1, 顺序扫描。顺序扫描的情况下LRU没有命中情况，而且会淘汰其它将要被访问的item从而污染cache。

2, 循环的数据集大于缓存大小。如果循环访问且数据集大于缓存大小，那么没有命中情况。

之所以会出现上述一些比较极端的问题，是因为LRU只考虑访问时间而没有考虑访问频率，而LIRS在这方面做得比较好。LIRS将数据分为两部分：LIR（Low Inner-reference Recency）和HIR（High Inner-reference Recency），其中，LIR中的数据是热点，在较短的时间内被访问了至少两次。LIRS可以看成是一种分级思想：第一级是HIR，第二级是LIR，数据先进入到第一级，当数据在较短的时间内被访问两次时成为热点数据则进入LIR，HIR和LIR内部都采用LRU策略。这样，LIR中的数据比较稳定，解决了LRU的上述两个问题。LIRS论文中提出了一种实现方式，不过我们可以做一些变化，如可以实现两级cache，cache元素先进入第一级cache，当访问频率达到一定值（比如2）时升级到第二级，第一级和第二级均内部采用LRU进行替换。Oracle Buffer Cache中的Touch Count算法也是采用了类似的思想。

SSD与缓存

SSD发展很快，大有取代传统磁盘之势。SSD的发展是否会使得单机缓存变得毫无必要我们无从得知，目前，Memory + SSD + 磁盘的混合存储方案还是比较靠谱的。SSD使用可以有如下不同的模式：

1, write-back：数据读写都走SSD，内存中的数据写入到SSD即可，另外有单独的线程定期将SSD中的数据刷到磁盘。典型的代表如Facebook Flashcache。

2, write-through：数据写操作需要先写到磁盘，内存和SSD合在一起看成两级缓存，即cache中相对较冷的数据在SSD，相对较热的数据在内存。

当然，随着SSD的应用，我想减少缓存锁粒度的重要性会越来越突出。

总结&推荐资料

到目前为止，我们在SSD，缓存相关优化的工作还是比较少的。今后的一年左右时间，我们将会投入一定的精力在系统优化上，相信到时候再来总结的时候认识会更加深刻。我想，缓存相关的优化工作首先要做的是根据需求制定一个大致的评价标准，接着使用实际数据做一些实验，最终可能会同时保留两到三种实现方式或者配置略微有所不同的缓存实现。缓存相关的推荐资料如下：

[1] Touch Count Algorithm. http://youyus.com/wp-content/uploads/resource/Shallahamer%20TC4a.pdf

[2] LIRS. http://portal.acm.org/citation.cfm?id=511340