memcache是??互联网分层架构中使用最多的KV缓存。面试的时候，memcache相关的问题几乎是必答题。Memcache相关的面试问题你能回答到什么程度？画外音：可能跟你拿到的offer的薪资水平有关。***问题：这类问题你知道吗，有没有用过调查，是否知道，比较容易回答。关于memcache的一些基本特性，用过的朋友基本可以回答：mc的核心功能是KV内存管理，值存储最大1M。不支持复杂的数据结构（hash、list、set、orderedCollection等）；mc不支持持久化；mc支持密钥过期；mc在持续运行时很少会出现内存碎片，速度不会随着服务运行时间的延长而降低；mc采用非阻塞IO多路复用网络模型，采用监听线程/工作线程的多线程模型；面对这样的封闭式问题，我们必须果断、毫不犹豫地回答。第二类问题：why（为什么）和what（什么）这样的问题，考察一个工具是否仅仅停留在使用层面，或者还有原则性的思考。(1)为什么memcache不支持复杂的数据结构？为什么不支持持久化？业务决定技术方案，mc的诞生，以“以服务的方式管理KV内存，而不是以库的方式管理KV内存”为设计目标，颠覆的是，KV内存管理组件库，复杂的数据结构和坚持不是它的初衷。当然，用“颠覆”二字未必不妥。库和服务都有各自的使用场景，但是在分布式环境下，服务可以使用的范围更广。设计目标和诞生背景很重要，在一定程度上决定了实现方案，就像redis的出现一样，为了有更好更实用的缓存服务。画外音：我很喜欢问这个问题。大多数考生在面对这个没有标准答案的问题时，可能会一头雾水。（2）memcache使用什么技术实现key过期？懒惰过期。(3)为什么memcache可以保证运行性能，很少出现内存碎片？提前分配内存。(4)为什么memcache采用非阻塞IO多路复用网络模型和监听线程/工作线程的多线程模型？有什么优点和缺点？目的是提高吞吐量。多线程可以充分利用多核，但是会带来一些锁冲突。面对这种半开放式的问题，有些是没有标准答案的，一定要回答自己的想法和看法。第三类问题：如何去做（how）|这类在正文开头的问题，就是检测应聘者对技术的理解程度、细节程度、技术深度。画外音：所谓的“好奇心”真的很重要，而只想“一份工作”的技术人很难有这种好奇心。(1)什么是memcache来实现内存管理减少内存碎片，如何分配内存？讲课前先解释几个很重要的概念：chunk：是给用户分配内存的最小单位。item：用户要存储的数据，包括key和value，最终存储在chunk中。slab：会管理若干个固定chunk大小的chunk，mc的内存管理由若干个slab组成。画外音：为了避免复杂，本文不介绍页面的概念。如上图所示，一系列slab分别管理着128B、256B、512B……的chunk内存单元。放大上图中管理128B的slab0：可以发现slab中的一些核心数据结构：chunk_size：slab管理128B的chunkfree_chunk_list：用于快速查找freechunkschunk[]：已经预分配，使用Voiceover对于实际存储useritem数据的chunk空间：其实还有lru_list。(2)如果用户要存储一个100B的item，如何找到对应的availablechunk？会通过free_chunk_list从最接近itemsize的slab的chunk[]中快速找到对应的chunk，如上图所示，最接近itemsize的chunk为128B。(3)为什么没有内存碎片？得到一个128B的chunk来存放一个100B的item，剩下的28B不会被其他item使用，也就是实际上浪费了存储空间，减少内存碎片，保证访问速度。画外音：理论上，内存碎片几乎不存在。(4)memcache使用slab、chunk、free_chunk_list快速分配内存和存储用户项，那么它是如何快速实现key查找的呢？没有特殊的算法：通过哈希表实现快速查找，通过链表解决冲突最简单的方法就是快速找到key。(5)随着item数量的不断增加，hash冲突也越来越大。哈希表如何保证查询效率？当项目总数达到哈希表长度的1.5倍时，哈希表会动态扩容，rehash会重新分配数据，保证搜索效率不会持续下降。(6)哈希表扩容后，同一个key在新旧哈希表中的位置会发生变化。如何保证迁移过程中数据的一致性和服务的可用性？，然后重新服务）？哈希表扩容，数据迁移是一个比较耗时的操作，会有专门的线程去执行，为了避免大锁，采用了“分段迁移”的策略。当item数量达到阈值时，迁移线程会分段迁移，锁定hash表中的一部分bucket，迁移数据，解锁：首先保证不会有长期阻塞影响服务的可用性。第二，保证新旧哈希表中的Item不会不一致(7)新的问题出现了。可以通过上述方法迁移旧哈希表中已经存在的项。那么在item迁移的过程中，如果插入了一个新的item，应该插入到旧哈希表中还是新哈希表中呢？memcache的方法是判断旧哈希表中应该插入item的bucket是否已经迁移到新表中：如果已经迁移，则直接将item插入到新哈希表中。如果还没有迁移，则直接插入到旧的哈希表中，等待以后迁移线程迁移到新的哈希表中。这种方式可以保证一个桶中的数据只存在于一个哈希表中（新表或者旧表都可以），在任何场景下都不会出现。旧表和新表两次查询，提高查询速度。(9)memcache如何实现key过期，lazyexpiration是如何实现的？“超时”和“过期”最常见的两种实现方式是：启动一个超时线程扫描所有item，如果发现超时，则进行超时回调处理。每一项设置超时信号通知，通知触发超时回调处理。这两种方法都需要额外的资源消耗。mc的查询服务很简单，只返回cachehit和cachemiss两个结果。这种场景下，很适合使用惰性淘汰法。惰性淘汰的核心是：物品不会被主动淘汰，即没有超时线程，也没有信号通知主动检查物品。每次查询（获取）项目时，检查时间戳。如果已经过期，则被动淘汰，返回缓存例如设置一个key，有效期为100s：第50秒，用户查询（获取）该key，则判断为已过期未过期，返回相应的值。第200秒，另一个用户查询（Get）key，判断过期，释放item所在的chunk，返回cachemiss。这种方法的实现成本很小，资源消耗也很低：在item中，添加一个过期时间属性。获取的时候，加上一个时间判断内存一直是有限的。当块数有限时，可以存储的项目数也有限。chunk用完了怎么办？还是上面的例子，如果128B的chunks用完了，用户会设置一个100B的item，要不要挤掉已有的item？是的。这里的启示是：即使将物品的有效期设置为“***”，也有可能被淘汰；如果要缓存全量数据，则必须仔细评估。缓存的内存大小必须大于全量数据的总大小，否则很难挖矿；(10)哪些项目应该被挤出？怎么挤出来？这就涉及到LRU淘汰机制。如果操作系统的内存管理，最常见的淘汰算法是FIFO和LRU：FIFO（先进先出）：***设置的项，***被淘汰LRU（leastrecentlyused）：最少最近使用（get/set）的item最终被淘汰，使用LRU算法挤出item。需要添加两个属性：recentitemaccesscountrecentitemaccesstime和添加一个LRU链表，可以快速实现。画外音：因此，每个管理chunk的slab，除了free_chunk_list之外，还有lru_list。想法比结论更重要。【本文为专栏作者《58神剑》原创稿件，转载请联系原作者】点此阅读更多该作者好文
