关于memcache内核，全网最通俗的讲解！（由浅入深，值得收藏）

memcache曾经是互联网分层架构中&＃xff0c;使用最多的的KV缓存&＃xff0c;如今却几乎被 redis 替代。

画外音&＃xff1a;你还在用mc吗&＃xff0c;还是redis&＃xff1f;

但memcache的内核设计&＃xff0c;却值得每一个技术人学习和借鉴。

第一部分&＃xff1a;知其然

关于memcache一些基础特性&＃xff0c;使用过的小伙伴必须知道&＃xff1a;

&＃xff08;1&＃xff09;mc的核心职能是KV内存管理&＃xff0c;value存储最大为1M&＃xff0c;它不支持复杂数据结构&＃xff08;哈希、列表、集合、有序集合等&＃xff09;&＃xff1b;

&＃xff08;2&＃xff09;mc不支持持久化&＃xff1b;

&＃xff08;3&＃xff09;mc支持key过期&＃xff1b;

&＃xff08;4&＃xff09;mc持续运行很少会出现内存碎片&＃xff0c;速度不会随着服务运行时间降低&＃xff1b;

&＃xff08;5&＃xff09;mc使用非阻塞IO复用网络模型&＃xff0c;使用监听线程/工作线程的多线程模型&＃xff1b;

memcache的这些特性&＃xff0c;成竹在胸了吗&＃xff1f;

第二部分&＃xff1a;知其原理(why, what)

第一部分&＃xff0c;只停留在使用层面&＃xff0c;除此之外&＃xff0c;还必须了解原理。

memcache为什么不支持复杂数据结构&＃xff1f;为什么不支持持久化&＃xff1f;

业务决定技术方案&＃xff0c;mc的诞生&＃xff0c;以“以服务的方式&＃xff0c;而不是库的方式管理KV内存”为设计目标&＃xff0c;它颠覆的是&＃xff0c;KV内存管理组件库&＃xff0c;复杂数据结构与持久化并不是它的初衷。

当然&＃xff0c;用“颠覆”这个词未必不合适&＃xff0c;库和服务各有使用场景&＃xff0c;只是在分布式的环境下&＃xff0c;服务的使用范围更广。设计目标&＃xff0c;诞生背景很重要&＃xff0c;这一定程度上决定了实现方案&＃xff0c;就如redis的出现&＃xff0c;是为了有一个更好用&＃xff0c;更多功能的缓存服务。

memcache是用什么技术实现key过期的&＃xff1f;

懒淘汰(lazy expiration)。

memcache为什么能保证运行性能&＃xff0c;且很少会出现内存碎片&＃xff1f;

提前分配内存。

memcache为什么要使用非阻塞IO复用网络模型&＃xff0c;使用监听线程/工作线程的多线程模型&＃xff0c;有什么优缺点&＃xff1f;

目的是提高吞吐量。多线程能够充分的利用多核&＃xff0c;但会带来一些锁冲突。

第三部分&＃xff1a;知其所以然&＃xff0c;知其内核(how)

一个对技术内核充满“好奇心”的工程师&＃xff0c;必须了解细节&＃xff0c;掌握内核。

画外音&＃xff1a;本文刚刚开始。

memcache是什么实现内存管理&＃xff0c;以减小内存碎片&＃xff0c;是怎么实现分配内存的&＃xff1f;

开讲之前&＃xff0c;先解释几个非常重要的概念&＃xff1a;

chunk&＃xff1a;它是将内存分配给用户使用的最小单元。

item&＃xff1a;用户要存储的数据&＃xff0c;包含key和value&＃xff0c;最终都存储在chunk里。

slab&＃xff1a;它会管理一个固定chunk size的若干个chunk&＃xff0c;而mc的内存管理&＃xff0c;由若干个slab组成。

画外音&＃xff1a;为了避免复杂性&＃xff0c;本文先不引入page的概念了。

如上图所示&＃xff0c;一系列slab&＃xff0c;分别管理128B&＃xff0c;256B&＃xff0c;512B…的chunk内存单元。

将上图中管理128B的slab0放大&＃xff1a;

能够发现slab中的一些核心数据结构是&＃xff1a;

&＃xff08;1&＃xff09;chunk_size&＃xff1a;该slab管理的是128B的chunk&＃xff1b;

&＃xff08;2&＃xff09;free_chunk_list&＃xff1a;用于快速找到空闲的chunk&＃xff1b;

&＃xff08;3&＃xff09;chunk[]&＃xff1a;已经预分配好&＃xff0c;用于存放用户item数据的实际chunk空间&＃xff1b;

画外音&＃xff1a;其实还有lru_list。

假如用户要存储一个100B的item&＃xff0c;是如何找到对应的可用chunk的呢&＃xff1f;

会从最接近item大小的slab的chunk[]中&＃xff0c;通过free_chunk_list快速找到对应的chunk&＃xff0c;如上图所示&＃xff0c;与item大小最接近的chunk是128B。

为什么不会出现内存碎片呢&＃xff1f;

拿到一个128B的chunk&＃xff0c;去存储一个100B的item&＃xff0c;余下的28B不会再被其他的item所使用&＃xff0c;即&＃xff1a;实际上浪费了存储空间&＃xff0c;来减少内存碎片&＃xff0c;保证访问的速度。

画外音&＃xff1a;理论上&＃xff0c;内存碎片几乎不存在。

memcache通过slab&＃xff0c;chunk&＃xff0c;free_chunk_list来快速分配内存&＃xff0c;存储用户的item&＃xff0c;那它又是如何快速实现key的查找的呢&＃xff1f;

没有什么特别算法&＃xff1a;

&＃xff08;1&＃xff09;通过hash表实现快速查找&＃xff1b;

&＃xff08;2&＃xff09;通过链表来解决冲突&＃xff1b;

用最朴素的方式&＃xff0c;实现key的快速查找。

随着item的个数不断增多&＃xff0c;hash冲突越来越大&＃xff0c;hash表如何保证查询效率呢&＃xff1f;

当item总数达到hash表长度的1.5倍时&＃xff0c;hash表会动态扩容&＃xff0c;rehash将数据重新分布&＃xff0c;以保证查找效率不会不断降低。

扩展hash表之后&＃xff0c;同一个key在新旧hash表内的位置会发生变化&＃xff0c;如何保证数据的一致性&＃xff0c;以及如何保证迁移过程服务的可用性呢&＃xff08;肯定不能加一把大锁&＃xff0c;迁移完成数据&＃xff0c;再重新服务吧&＃xff09;&＃xff1f;

哈希表扩展&＃xff0c;数据迁移是一个耗时的操作&＃xff0c;会有一个专门的线程来实施&＃xff0c;为了避免大锁&＃xff0c;采用的是“分段迁移”的策略。

当item数量达到阈值时&＃xff0c;迁移线程会分段迁移&＃xff0c;对hash表中的一部分桶进行加锁&＃xff0c;迁移数据&＃xff0c;解锁&＃xff1a;

&＃xff08;1&＃xff09;一来&＃xff0c;保证不会有长时间的阻塞&＃xff0c;影响服务的可用性&＃xff1b;

&＃xff08;2&＃xff09;二来&＃xff0c;保证item不会在新旧hash表里不一致&＃xff1b;

新的问题来了&＃xff0c;对于已经存在于旧hash表中的item&＃xff0c;可以通过上述方式迁移&＃xff0c;那么在item迁移的过程中&＃xff0c;如果有新的item插入&＃xff0c;是应该插入旧hash表还是新hash表呢&＃xff1f;

memcache的做法是&＃xff0c;判断旧hash表中&＃xff0c;item应该插入的桶&＃xff0c;是否已经迁移至新表中&＃xff1a;

&＃xff08;1&＃xff09;如果已经迁移&＃xff0c;则item直接插入新hash表&＃xff1b;

&＃xff08;2&＃xff09;如果还没有被迁移&＃xff0c;则直接插入旧hash表&＃xff0c;未来等待迁移线程来迁移至新hash表&＃xff1b;

为什么要这么做呢&＃xff0c;不能直接插入新hash表吗&＃xff1f;

memcache没有给出官方的解释&＃xff0c;楼主揣测&＃xff0c;这种方法能够保证一个桶内的数据&＃xff0c;只在一个hash表中&＃xff08;要么新表&＃xff0c;要么旧表&＃xff09;&＃xff0c;任何场景下都不会出现&＃xff0c;旧表新表查询两次&＃xff0c;以提升查询速度。

memcache是怎么实现key过期的&＃xff0c;懒淘汰(lazy expiration)具体是怎么玩的&＃xff1f;

实现“超时”和“过期”&＃xff0c;最常见的两种方法是&＃xff1a;

&＃xff08;1&＃xff09;启动一个超时线程&＃xff0c;对所有item进行扫描&＃xff0c;如果发现超时&＃xff0c;则进行超时回调处理&＃xff1b;

&＃xff08;2&＃xff09;每个item设定一个超时信号通知&＃xff0c;通知触发超时回调处理&＃xff1b;

这两种方法&＃xff0c;都需要有额外的资源消耗。

mc的查询业务非常简单&＃xff0c;只会返回cache hit与cache miss两种结果&＃xff0c;这种场景下&＃xff0c;非常适合使用懒淘汰的方式。

懒淘汰的核心是&＃xff1a;

&＃xff08;1&＃xff09;item不会被主动淘汰&＃xff0c;即没有超时线程&＃xff0c;也没有信号通知来主动检查&＃xff1b;

&＃xff08;2&＃xff09;item每次会查询(get)时&＃xff0c;检查一下时间戳&＃xff0c;如果已经过期&＃xff0c;被动淘汰&＃xff0c;并返回cache miss&＃xff1b;

举个例子&＃xff0c;假如set了一个key&＃xff0c;有效期100s&＃xff1a;

&＃xff08;1&＃xff09;在第50s的时候&＃xff0c;有用户查询(get)了这个key&＃xff0c;判断未过期&＃xff0c;返回对应的value值&＃xff1b;

&＃xff08;2&＃xff09;在第200s的时候&＃xff0c;又有用户查询(get)了这个key&＃xff0c;判断已过期&＃xff0c;将item所在的chunk释放&＃xff0c;返回cache miss&＃xff1b;

这种方式的实现代价很小&＃xff0c;消耗资源非常低&＃xff1a;

&＃xff08;1&＃xff09;在item里&＃xff0c;加入一个过期时间属性&＃xff1b;

&＃xff08;2&＃xff09;在get时&＃xff0c;加入一个时间判断&＃xff1b;

内存总是有限的&＃xff0c;chunk数量有限的情况下&＃xff0c;能够存储的item个数是有限的&＃xff0c;假如chunk被用完了&＃xff0c;该怎么办&＃xff1f;

仍然是上面的例子&＃xff0c;假如128B的chunk都用完了&＃xff0c;用户又set了一个100B的item&＃xff0c;要不要挤掉已有的item&＃xff1f;

要。

这里的启示是&＃xff1a;

&＃xff08;1&＃xff09;即使item的有效期设置为“永久”&＃xff0c;也可能被淘汰&＃xff1b;

&＃xff08;2&＃xff09;如果要做全量数据缓存&＃xff0c;一定要仔细评估&＃xff0c;cache的内存大小&＃xff0c;必须大于&＃xff0c;全量数据的总大小&＃xff0c;否则很容易踩坑&＃xff1b;

挤掉哪一个item&＃xff1f;怎么挤&＃xff1f;

这里涉及LRU淘汰机制。

如果操作系统的内存管理&＃xff0c;最常见的淘汰算法是FIFO和LRU&＃xff1a;

&＃xff08;1&＃xff09;FIFO(first in first out)&＃xff1a;最先被set的item&＃xff0c;最先被淘汰&＃xff1b;

&＃xff08;2&＃xff09;LRU(least recently used)&＃xff1a;最近最少被使用(get/set)的item&＃xff0c;最先被淘汰&＃xff1b;

使用LRU算法挤掉item&＃xff0c;需要增加两个属性&＃xff1a;

&＃xff08;1&＃xff09;最近item访问计数&＃xff1b;

&＃xff08;2&＃xff09;最近item访问时间&＃xff1b;

并增加一个LRU链表&＃xff0c;就能够快速实现。

画外音&＃xff1a;所以&＃xff0c;管理chunk的每个slab&＃xff0c;除了free_chunk_list&＃xff0c;还有lru_list。

memcache&＃xff0c;你学会了吗&＃xff1f;

思路比结论重要。

架构师之路-分享技术思路

文章较长&＃xff0c;帮忙转发&＃43;在看。