缓存设计相关问题

申请免费试用、咨询电话：400-8352-114

　　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，缓存相关优化的任务照样比拟少的。往后的一年左右工夫，我们将会投入必然的精神在系统优化上，置信到时分再来总结的时分看法会愈加深入。我想，缓存相关的优化任务起首要做的是依据需求制订一个大致的评价规范，接着运用实践数据做一些实行，最终能够会还保存两到三种完成方法或许装备稍微有所分歧的缓存完成