两周速成系统设计系列之七 缓存鼻祖Memcached
Memcached是一个高性能分布式缓存系统，它诞生于2003年，其的设计初衷是为愈加复杂的网站降低数据库载荷。
虽然在诞生初期，它是一款革命性的软件，帮助了很多公司包括Facebook创造出了各种各样的服务，从今天（2020）的视角上看，Redis已经在绝大多数领域里替代和超越了Memcached，在设计新服务时选用Redis往往更优。在下一篇中我们会深入了解Redis。
既然如此，学习Memcached的意义为何呢？
-
Memcached是一款功能单一的软件，为我们在系统设计面试中设计Cache提出了可以借鉴的思路。 -
学习Memcached可以帮助我们学习Cache最基础的知识，对比分析Redis时能够加深理解。
1 核心功能
分布式缓存。当我们有一些数据需要反复被调取时，与其总是访问数据库，我们暂时把它存在内存中，直接返回。
API层面上提供简单的GET和SET API读写一组键值对 (Key-value Pair)。
function get_foo(foo_id)foo = memcached_get("foo:" . foo_id)return foo if defined foofoo = fetch_foo_from_database(foo_id)memcached_set("foo:" . foo_id, foo)return fooend
值得注意的是每个Key只存在在memcache集群的一台memcached机器上，而不会同步写到每一台上，从而使整个memcached集群可以存储更多数据。
2 内存分配
Memcached默认将内存分为1MB大小的page。每个page会被分配到特定的slab class，然后被进一步根据slab class (以下简称class) 规定的大小，分成chunks。
$ ./memcached -vvslab class 1: chunk size 80 perslab 13107slab class 2: chunk size 104 perslab 10082slab class 3: chunk size 136 perslab 7710slab class 4: chunk size 176 perslab 5957slab class 5: chunk size 224 perslab 4681slab class 6: chunk size 280 perslab 3744slab class 7: chunk size 352 perslab 2978slab class 8: chunk size 440 perslab 2383slab class 9: chunk size 552 perslab 1899slab class 10: chunk size 696 perslab 1506[...etc...]
从上面的例子上可以看出序号较小的class会有更小的chunk size，意味着这个class是用来存较小的数据的。比如chunk size为80 bytes的class，存储数据量小于80 bytes的数据 (key + value + misc data)，多余下来的会被浪费。
我们可以把每一个class理解成独立的缓存，拥有自己独立的LRU (Least Recently Used) 数据结构。
设计赏析
C的malloc/free会造成内存碎片化。memcached这样可预测的内存分配形式浪费了一些内存，但是保证服务的长期稳定运行。
3 内存回收
下面我们介绍memcached新版 (2018) 的内存回收机制，还是很巧妙的。其内存回收机制有三个重要的优化，Segmented LRU，LRU Crawler和 Slab Rebalance。这一节内容很多，详细介绍了以上三个机制的细节，请同学们细细品味。
值得注意的是，memcached采用的LRU机制远非严格意义上的绝对的LRU，最显而易见的一点就是不同class之间不会区分访问先后顺序。这里所说的LRU指的是我们下面规定的这个特殊的类LRU机制。
THREADS + STRUCTURES+----------------------+ ||-----------| | | +----------++------+ +--v-----+ +--v-----+ | |hash table||listen| |worker 1| |worker 2| | +----------++------+ +--------+ +--------+ |+---------> +---+| |LRU|+--------------+ | +---+|lru maintainer+------------------>+--------------+ | +--------------+| |slab allocator|+-----------+ | +--------------+|lru crawler+--------------------->+-----------+ ||+---------------+ ||slab page mover+----------------->+---------------+ |+
设计目标
-
防止常被访问的Key被踢出 -
降低延迟 - 减少LRU Lock的使用 -
合理协调各class的内存
3.1 Segmented LRU
即分段式LRU。
数据状态
我们对于单个数据会维护两个状态。
-
Fetched 当数据被访问时，设置为1。 -
Active 当数据被访问第二次时设置为1。被往前提 (Bump) 或移动时设置为0。
子LRU的规则
LRU被分成四个子LRU。
-
HOT -
新的数据从这里进来 -
数据在这里排成队列，一旦到了队尾，如果Active，放入WARM；如果不是，放入COLD -
数据即使被访问了，顺序也始终不变 -
此LRU占用内存的大小主要会被限制在全部内存的一定百分比 -
队尾数据的年龄会相对COLD队尾数据的年龄被限制 -
WARM -
只有当数据被访问至少两次时，才会被放到WARM -
如果队尾数据是Active，放到队头；如果不是，放入COLD -
此LRU占用内存的大小主要会被限制在全部内存的一定百分比 (与HOT相同) -
队尾数据的年龄会相对COLD队尾数据的年龄被限制 (与HOT相同) -
COLD -
内存满之后，COLD的队尾数据会被踢出 -
当COLD队列里的数据变得Active，该数据会被异步放入WARM。 -
这个异步放入WARM的操作可能不及时，甚至在过载情况下变得在部分时候随机发生。 -
TEMP -
默认不使用 -
用于超短TTL数据 -
数据即使被访问了，顺序也始终不变，也不会移到其他地方
机制实现
以上四个子LRU规则的维护是由称为LRU Maintainer的后台线程实现的。
-
遍历所有的子LRU，看一下队尾 -
保证每个子LRU在大小范围以及队尾在年龄范围内，如果不满足，移动一些数据。 -
回收过期数据内存 -
异步将COLD队列里的Active数据放入WARM -
如果特定class已经没有COLD数据可以踢了，那么普通的worker线程会block SET指令，将数据踢出HOT和WARM，而不是依赖后台线程处理。
设计赏析
回顾一下我们最初的设计目标 - 降低延迟，这个机制很巧妙地做到了。
-
LRU维护不会在取数据时发生，也就不会有LRU lock -
LRU维护绝大多数情况下是异步发生的 -
多个子LRU各自维护自己的LRU lock，使得一个子LRU lock时，别的依旧可以写 -
每个数据的状态仅2 bit
相比于单LRU lock的设计，延迟降低了一个级别。
3.2 LRU Crawler
回顾一下前面内存分配的章节的知识，每个class都是自己独立的缓存，每个都拥有自己的Segmented LRU。那么问题来了，如何保证class之间的内存分配是合理的呢？要准确了解内存情况就得先处理掉内存中的过期数据。
LRU Crawler就是解决这个问题的后台进程。
Crawler规则
-
从每个class的每个子LRU的队尾 同步开始向队头方向寻找，回收过期数据。这里同步的意思是排好队齐步走，这样较短的class会很快完成，不至于要一直等到较长的class完成后被处理。 -
Crawler边走边维护一个TTL直方图，并根据直方图决定多久以后再重新扫描该LRU。如果一个class有很多马上就要过期的数据，那么Crawler就会在短时间内重新扫描，反之，则可以等等。
设计赏析
这里的设计目标是尽快地回收最大量的内存。
上述的规则会自然地反复快速地回收序号较大的class来回收尽可能多的内存，也会根据使用特征来在不同class之间平衡数据回收的频率。
3.3 Slab Rebalance
这是一个可选的功能。
随着信息结构的变化，信息的大小会有起伏，使得某一些class的大小不再合适。Slab Automove和Slab Reassign功能使得一个class的内存可以重新分配到别的class里。
-
Slab Automove 会根据每个class里一定时间内内存被提出的次数来找到需要更多内存的class -
Slab Automove 会根据每个class里空余的内存来找到可以减少内存的class -
Slab Reassign 实现将一个page从class A移交到class B的交接工作，使用一个后台进程将这个page内所有的数据全部提出并且完成移交。
参考资料
-
dormando. (2018). Replacing the cache replacement algorithm in memcached -
dormando. (2018). About Memcached -
dormando. (2016). A Story of Caching -
dormando. (2017). User Internals -
dormando. (2017). New LRU -
dormando. (2019). External sotrage -
dormando. (2016). Answer to "Possible issue with slab rebalance"
更多文章：
有用就点击"在看"，你的支持是我的原创动力！