9.4.3　缓存实现

ChunkServer中包含三种缓存：块缓存（Block Cache）、行缓存（Row Cache）以及块索引缓存（Block Index Cache）。其中，块缓存中存储了SSTable中访问较热的数据块（Block），行缓存中存储了SSTable中访问较热的数据行（Row），而块索引缓存中存储了最近访问过的SSTable的块索引（Block Index）。一般来说，块索引不会太大，ChunkServer中所有SSTable的块索引都是常驻内存的。不同缓存的底层采用相同的实现方式。

1.底层实现

经典的LRU缓存实现包含两个部分：哈希表和LRU链表，其中，哈希表用于查找缓存中的元素，LRU链表用于淘汰。每次访问LRU缓存时，需要将被访问的元素移动到LRU链表的头部，从而避免被很快淘汰，这个过程需要锁住LRU链表。

如图9-10所示，块缓存和行缓存底层都是一个Key-Value Cache，实现步骤如下：

图　9-10　Key-Value Cache的实现

1）OceanBase一次分配1MB的连续内存块（称为memblock），每个memblock包含若干缓存项（item）。添加item时，只需要简单地将item追加到memblock的尾部；另外，缓存淘汰以memblock为单位，而不是以item为单位。

2）OceanBase没有维护LRU链表，而是对每个memblock都维护了访问次数和最近频繁访问时间。访问memblock中的item时将增加memblock的访问次数，如果最近一段时间之内的访问次数超过一定值，那么，更新最近频繁访问时间；淘汰memblock时，对所有的memblock按照最近频繁访问时间排序，淘汰最近一段时间访问较少的memblock。可以看出，读取时只需要更新memblock的访问次数和最近频繁访问时间，不需要移动LRU链表。这种实现方式通过牺牲LRU算法的精确性，来规避LRU链表的全局锁冲突。

3）每个memblock维护了引用计数，读取缓存项时所在memblock的引用计数加1，淘汰memblock时引用计数减1，引用计数为0时memblock可以回收重用。通过引用计数，实现读取memblock中的缓存项不加锁。

2.惊群效应

以行缓存为例，假设ChunkServer中有一个热点行，ChunkServer中的N个工作线程（假设为N=50）同时发现这一行的缓存失效，于是，所有工作线程同时读取这行数据并更新行缓存。可以看出，N-1共49个线程不仅做了无用功，还增加了锁冲突。这种现象称为“惊群效应”。为了解决这个问题，第一个线程发现行缓存失效时会往缓存中加入一个fake标记，其他线程发现这个标记后会等待一段时间，直到第一个线程从SSTable中读到这行数据并加入到行缓存后，再从行缓存中读取。

算法描述如下：

调用internal_get读取一行数据;

if(行不存在){

调用internal_set往缓存中加入一个fake标记;

从SSTable中读取数据行;

将SSTable中读到的行内容加入缓存，清除fake标记，唤醒等待线程;

返回读到的数据行;

}else if(行存在且为fake标记)

{

线程等待，直到清除fake标记;

if(等待成功)返回行缓存中的数据;

if(等待超时)返回读取超时;

}

else

{

返回行缓存中的数据;

}

3.缓存预热

ChunkServer定期合并后需要使用生成的新的SSTable提供服务，如果大量请求同时读取新的SSTable文件，将使得ChunkServer的服务能力在切换SSTable瞬间大幅下降。因此，这里需要一个缓存预热的过程。OceanBase最初的版本实现了主动缓存预热，即：扫描原来的缓存，根据每个缓存项的key读取新的SSTable并将结果加入到新的缓存中。例如，原来缓存数据项的主键分别为100、200、500，那么只需要从新的SSTable中读取主键为100、200、500的数据并加入新的缓存。扫描完成后，原来的缓存可以丢弃。

线上运行一段时间后发现，定期合并基本上都安排在凌晨业务低峰期，合并完成后OceanBase集群收到的用户请求总是由少到多（早上7点之前请求很少，9点以后请求逐步增多），能够很自然地实现被动缓存预热。由于ChunkServer在主动缓存预热期间需要占用两倍的内存，因此，目前的线上版本放弃了这种方式，转而采用被动缓存预热。