版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/wl6965307/article/details/51385336
Memcached一般被用于高并发场景下，数据库前的缓存层，用以缓解数据库的读取压力，提高应用速度和可扩展性。
特点：
- 协议简单，基于简单的文本行协议
- 基于libevent的事件处理，使其在linux上能发挥高性能
- 内存机制，所有数据仅存储在内存中，一旦重启则全部失效，容量达到一定阈值，会根据LRU算法删除。同时提供key的expiretime。
- 集群依赖客户端，分布式功能不由服务器实现，而是由客户端管理。服务器之间不进行通信。客户端维护可用服务器列表。直接计算key应该存到哪个服务器，通知服务器添加、删除数据。
单点问题：
服务器：
>>>>存储结构
- 服务器维护一个类似hashmap的表，采用数组存储，大小为2的次幂。
- 每个数组的元素，通常叫做桶。hashcode mode 桶数量定位桶。桶内处理hash冲突和方式与hashmap相同，链表方式。
- 插入时采用头插法。
- 查找时，用hash值定位桶，键值相等判断，定位链表中具体的位置。
- 当总的item数量达到了数组长度的1.5倍时，就扩展。所以桶大小平均最大为1.5个item，查找很快。
- 由于桶的定位是靠mode求余的方式，所以扩展时，桶的位置会大量的发生变化，需要迁移。为了在迁移的过程中，不会新插入和删除数据，迁移过程会锁住整个表。但是迁移是个耗时的过程，为了客户端的请求不被长时间的阻塞，memcached采用逐步迁移。首先表的大小超过了限制，触发迁移，先申请一个旧内存大小1.5倍的新内存，然后以桶为单位，每次迁移若干（默认一个，可配置）就释放锁，然后再去获取锁以便继续迁移。这当中，客户端的请求就有机会获取到锁来处理请求。此时的操作，需要看key对应的桶有没有被迁移而决定在哪个表操作。
>>>>内存分配- memcached采用slab内存分配方法，类似内存池的概念。
- 内部维护一个slab数组，包含多个slab分配器，每个slab能分配固定大小的内存出去，不同的slab间能分配的内存大小可能不同。
- slab内存储自己能分配的每个item的大小，能分配多少块。两个指针分别指向空闲内存区域链表和已使用区域链表。
- 启动时，
- 根据配置初始化一些可分配大小不同的slab分配器，最大的slab支持的item大小不超过1M（可配置，最大为128M）。这就是为什么memcached最大支持1M的单个数据。
- 然后为每个slab预分配一块内存，再将这一块内存按slab对应的item大小划分为几块，加入到空闲链表。
- 当slab不够用时，再去内存池申请内存。
- 申请时，根据不同策略定位到使用哪个分配器。两种策略：
>>>>LRU
- 上面说过，不同slab分配的item大小不一。相同大小的item，我们叫它们同一类item。item实际的管理其实不是由类hashmap那个表管理的，而是LRU队列。每一类item对应一个LRU队列。item从表中删除，只是从桶的冲突链中移除而已。从LRU队列删除，才会被内存池回收。
- item数据结构，包括：
- hash表中的next指针，冲突链使用
- LRU队列使用的pre和next指针。LRU队列是双向队列
- 最后访问时间
- item访问时，会将其从LRU队列移除，重新插入队列头，并更新访问时间。这个操作是要加锁的，有一定消耗，所以memcached采用了更新间隔。同一item两次操作超过了一定的时间间隔，才会进行。
- item从LRU队列删除是懒删除，依赖外部时机：
- get访问
- 申请相同块大小内存时，会从尾部检查5个，如果有过期的，复用内存。没有找到，就申请，申请失败就删掉最旧的。
- flush_all、flush_expired
客户端hash算法：
