memcache内核，一文搞定！面试再也不怕了！！！（值得收藏）(2)

memcache的做法是，判断旧hash表中，item应该插入的桶，是否已经迁移至新表中：

• 如果已经迁移，则item直接插入新hash表
• 如果还没有被迁移，则直接插入旧hash表，未来等待迁移线程来迁移至新hash表

(8) 为什么要这么做呢，不能直接插入新hash表吗?

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

(9) memcache是怎么实现key过期的，懒淘汰(lazy expiration)具体是怎么玩的?

实现“超时”和“过期”，最常见的两种方法是：

• 启动一个超时线程，对所有item进行扫描，如果发现超时，则进行超时回调处理
• 每个item设定一个超时信号通知，通知触发超时回调处理

这两种方法，都需要有额外的资源消耗。

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

懒淘汰的核心是：

• item不会被主动淘汰，即没有超时线程，也没有信号通知来主动检查
• item每次会查询(get)时，检查一下时间戳，如果已经过期，被动淘汰，并返回cache miss

举个例子，假如set了一个key，有效期100s：

• 在第50s的时候，有用户查询(get)了这个key，判断未过期，返回对应的value值
• 在第200s的时候，又有用户查询(get)了这个key，判断已过期，将item所在的chunk释放，返回cache miss

这种方式的实现代价很小，消耗资源非常低：

• 在item里，加入一个过期时间属性
• 在get时，加入一个时间判断

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

仍然是上面的例子，假如128B的chunk都用完了，用户又set了一个100B的item，要不要挤掉已有的item?要。

这里的启示是：

• 即使item的有效期设置为“永久”，也可能被淘汰;
• 如果要做全量数据缓存，一定要仔细评估，cache的内存大小，必须大于，全量数据的总大小，否则很容易采坑;

(10) 挤掉哪一个item?怎么挤?

这里涉及LRU淘汰机制。

如果操作系统的内存管理，最常见的淘汰算法是FIFO和LRU：

• FIFO(first in first out)：最先被set的item，最先被淘汰
• LRU(least recently used)：最近最少被使用(get/set)的item，最先被淘汰

使用LRU算法挤掉item，需要增加两个属性：

• 最近item访问计数
• 最近item访问时间

并增加一个LRU链表，就能够快速实现。

画外音：所以，管理chunk的每个slab，除了free_chunk_list，还有lru_list。

思路比结论重要。

【本文为51CTO专栏作者“58沈剑”原创稿件，转载请联系原作者】

戳这里，看该作者更多好文

（编辑：ASP站长网）