一、知识结构及面试题目分析
缓存技术的大规模使用是互联网架构区别于传统 IT 技术最大的地方，是整体高并发高性能架构设计中是重中之重的关键一笔，也是互联网公司比较偏好的面试题目。按照在软件系统中所处位置的不同，缓存大体可以分为三类：客户端缓存、服务端缓存、网络中的缓存；根据部署方式大体可分为：本地缓存和分布式缓存。专栏将以分布式缓存为重点，挑选其中应用最广的 memcached、redis 分别予以介绍，同时兼顾其他缓存方案，从部署、设计、应用场景等方面展开。
二、典型面试例题及思路分析
问题 1：memchaced 中的一致性哈希算法是怎样工作的？
在计算一致性哈希时采用一般采用如下步骤：
(1) 首先求出 memcached 服务器（节点）的哈希值，并将其配置到 0～2^32-1 的圆上。
(2) 然后采用同样的方法求出存储数据的键的哈希值，并映射到相同的圆上。
(3）然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上。如果超过 2^32-1 仍然找不到服务器，就会保存到第一台 memcached 服务器上。
点评：
传统的哈希算法最常见的是哈希取模算法，即集群中可用机器节点数量为 N，那么 key 值为 K 的的数据请求会路由到 hash (K) mod N 对应的节点。这种算法简单，但并不适用于分布式系统。在分布式系统中，每个节点都可能失效，且节点会随时动态增减，如果用 hash 取模算法，会导致节点增减时的大量缓存无法命中，瞬间穿透缓存，给下游 DB 等系统带来极高的负载，甚至引起宕机。
在分布式缓存中，判定哈希算法好坏有三个标准：
（1）平衡性 (Balance)：指哈希的结果能够尽可能分布到所有的缓存中去，尽可能地利用缓存机器；
（2）单调性 (Monotonicity)：是哈希的结果尽可能地保证原有已分配的内容可以被映射到原有缓存中去，避免在节点增减过程中导致不能命中；
（3）分散性 (Spread)：是指同一个哈希结果，应尽量存储在同一个缓存机器，以提升系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散 性。
相较于哈希取模算法，一致性哈希能比较好地解决单调性（Monotonicity）和分散性 (Spread) 等问题，我们将上一致性哈希的计算步骤更细化一下：
（1）服务器初始化。
整个哈希值空间虚拟成一个有 2^32 节点的圆环，并按顺时针方向组织。假设有 Node A、Node B、Node C、Node D 四台服务器，计算得到各服务器的哈希值（通常使用 ip 或主机名作为关键字进行哈希），分布如下：
假设有四个数据对象 Object A、Object B、Object C、Object D，** 计算得到其哈希值，并映射到上述虚拟圆环的节点上，根据一致性哈希算法，从此位置出发沿环顺时针 “行走”，第一台遇到的服务器就是其应该定位到的服务器。** 在这里，Object A 会存储到 Node A 上，Object B 会存储到 Node B 上，Object C 会存储到 Node C 上，Object D 会存储到 Node D 上。
（3）单调性分析
假设在 Node B 和 Node C 之间新增一个 Node X，可以看到 Object C 被重定位到 Node X，而其余的三个数据对象 Object A/Object B/Object D 都不会有影响。在一致性哈希算法中，如果集群中增加或减少一台服务器，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它数据不会受到影响，因此具有较好的容错性和可扩展性。
（4）虚拟化
在一致性哈希算法中，如果服务节点太少（比如说两台），容易引起数据分布不均。为此，一致性哈希算法引入了虚拟节点机制，即将每一个物理服务节点拆成若干个虚拟的逻辑服务节点（具体做法可以在服务器 ip 或主机名的后面增加编号来实现），这样定位算法会先定位到逻辑服务节点上去，再由逻辑节点映射到真正的物理节点。
问题 2：redis 和 memcached 的区别是什么？
（1）数据类型支持不同。 memcached 仅支持简单的 key-value 结构的数据类型，复杂的对象需要客户端自己处理；Redis 支持的数据类型要丰富得多。最为常用的数据类型主要由五种：String、Hash、List、Set 和 Sorted Set。
（2）持久化支持不同，memcached 不支持数据持久存储 ，数据一直在内存中；redis 支持数据落地持久化存储，可以将内存中的数据保持在磁盘中，因此在某一时刻，redis 中并不是所有的数据都一直存储在内存中；
（3）分布式支持不同。memcached 一般是在客户端通过一致性哈希等算法来实现分布式存储； Redis 更偏向于在服务器端构建分布式存储，支持主从复制等集群模式；
（4）内存管理不同。memcached 默认使用 Slab Allocation 机制管理内存，其主要思想是按照预先规定的大小呈阶梯状分配好，会根据接收到数据的大小选择一个最合适的 Slab Class 进行存储，该方法可以避免内存碎片问题，可也不可避免地出现一定的空间浪费；redis 则采用包装过的 mallc/free 来分配内存，什么时候需要什么时候分配，更简单一些。
（5）应用场景不同。 memcached 是一个分布式内存对象缓存系统（distributed memory object caching system,），旨在通过减轻数据库负载来加速动态 Web 应用程序；redis 是内存中的数据结构存储系统（in-memory data structure store），它可以用作数据库、缓存和消息中间件。
点评:
这个题目也是半开放式的，这类题目之前也出现得比较多了，回答可能会有好几个差异点，但其实除了重要的差异点外，其他差异点多一个少一个不会影响大局，关键还是要有自己的理解，不要表现得像死记硬背。
当然本题目的问法比较直白，在实际上的面试中可能会换一种问法，比如说 “你们的系统当时为什么选择 redis/memcached 作为缓存方案，为什么没有选择 memcached/redis” 等等，本质上是想考察做技术选型背后的逻辑。通常来讲：redis 比 memcached 的功能多一些，实现也更复杂。 不过 memcached 更专注于保存 key-value 数据（这已经能满足大多数使用场景了），而 redis 提供更丰富的数据结构及其他的一些功能。
三、总结
像 memcached 这类分布式缓存在互联网场景下大量应用，因此也或多或少地为开发人员所知。但是大家在简历上写的时候还是要实事求是地写，知道就是知道，了解就是了解，熟悉就是熟悉，如果仅仅是了解，但是写成了熟悉，面试官就可能逮着问，回答不上来还可能留下不诚实的印象。其实像这 memcached 这类缓存，即使手中的业务一时半会儿用不上，如果自己想了解的，也可以简单地在线下环境搭一个，可以去体验一下。毕竟知道和动手用过，还是有一定差距的。
四、扩展阅读及思考题
链接: Memcached slab 分配策略.
链接: Memcached 官网.
问：适用memcached的业务场景？
1）如果网站包含了访问量很大的动态网页，因而数据库的负载将会很高。由于大部分数据库请求都是读操作，那么memcached可以显著地减小数据库负载。
2）如果数据库服务器的负载比较低但CPU使用率很高，这时可以缓存计算好的结果（ computed objects ）和渲染后的网页模板（enderred templates）。
3）利用memcached可以缓存session数据、临时数据以减少对他们的数据库写操作。
4）缓存一些很小但是被频繁访问的文件。
5）缓存Web 'services’或RSS feeds的结果.。
问：不适用memcached的业务场景？
1）缓存对象的大小大于1MB
Memcached本身就不是为了处理庞大的多媒体（large media）和巨大的二进制块（streaming huge blobs）而设计的。
2）key的长度大于250字符
3）虚拟主机不让运行memcached服务
如果应用本身托管在低端的虚拟私有服务器上，像vmware, xen这类虚拟化技术并不适合运行memcached。Memcached需要接管和控制大块的内存，如果memcached管理的内存被OS或 hypervisor交换出去，memcached的性能将大打折扣。
4）应用运行在不安全的环境中
Memcached为提供任何安全策略，仅仅通过telnet就可以访问到memcached。如果应用运行在共享的系统上，需要着重考虑安全问题。
5）业务本身需要的是持久化数据或者说需要的应该是database
问：能够遍历memcached中所有的item吗？
不能，这个操作的速度相对缓慢且阻塞其他的操作（这里的缓慢时相比memcached其他的命令）。memcached所有非调试（non-debug）命令，例如add, set, get, fulsh等无论memcached中存储了多少数据，它们的执行都只消耗常量时间。任何遍历所有item的命令执行所消耗的时间，将随着memcached中数据量的增加而增加。当其他命令因为等待（遍历所有item的命令执行完毕）而不能得到执行，因而阻塞将发生。
问：memcached和MySQL的query cache相比，有什么优缺点？
缺点：
1）相比MySQL的query cache，把memcached引入应用中需要不少的工作量。MySQL的query cache，可以自动地缓存SQL查询的结果，被缓存的SQL查询可以被反复、快速的执行。
优点：
1）当修改表时，MySQL的query cache会立刻被刷新（flush）。当写操作很频繁时，MySQL的query cache会经常让所有缓存数据都失效。
2）在多核CPU上，MySQL的query cache会遇到扩展问题（scalability issues）。在多核CPU上，query cache会增加一个全局锁（global lock）, 由于需要刷新更多的缓存数据，速度会变得更慢。
3）在MySQL的query cache中，是不能存储任意的数据的（只能是SQL查询结果）。利用memcached，我们可以搭建出各种高效的缓存。比如，可以执行多个独立的查询，构建出一个用户对象（user object），然后将用户对象缓存到memcached中。而query cache是SQL语句级别的，不可能做到这一点。在小的网站中，query cache会有所帮助，但随着网站规模的增加，query cache的弊将大于利。
4）query cache能够利用的内存容量受到MySQL服务器空闲内存空间的限制。给数据库服务器增加更多的内存来缓存数据，固然是很好的。但是，有了memcached，只要您有空闲的内存，都可以用来增加memcached集群的规模，然后您就可以缓存更多的数据。
问：memcached和服务器的local cache（比如PHP的APC、mmap文件等）相比，有什么优缺点？
1）首先，local cache面临着严重的内存限制，能够利用的内存容量受到（单台）服务器空闲内存空间的限制。
2）local cache有一点比memcached和query cache都要好，那就是它不但可以存储任意的数据，而且没有网络存取的延迟。因此，local cache的数据查询更快。考虑把highly common的数据放在local cache中吧。如果每个页面都需要加载一些数量较少的数据，可以考虑把它们放在local cached。
3）local cache缺少集体失效（group invalidation）的特性。在memcached集群中，删除或更新一个key会让所有的观察者觉察到。但是在local cache中, 我们只能通知所有的服务器刷新cache（很慢，不具扩展性）或者仅仅依赖缓存超时失效机制。
问：memcached如何处理容错的？
在节点失效的情况下，集群没有必要做任何容错处理。如果发生了节点失效，应对的措施完全取决于用户。节点失效时，下面列出几种方案供您选择：
1）忽略它！ 在失效节点被恢复或替换之前，还有很多其他节点可以应对节点失效带来的影响。
2）把失效的节点从节点列表中移除。做这个操作千万要小心！在默认情况下（余数式哈希算法），客户端添加或移除节点，会导致所有的缓存数据不可用！因为哈希参照的节点列表变化了，大部分key会因为哈希值的改变而被映射到（与原来）不同的节点上。
3）启动热备节点，接管失效节点所占用的IP。这样可以防止哈希紊乱（hashing chaos）。
4）如果希望添加和移除节点，而不影响原先的哈希结果，可以使用一致性哈希算法（consistent hashing）。
5）两次哈希（reshing）。当客户端存取数据时，如果发现一个节点down了，就再做一次哈希（哈希算法与前一次不同），重新选择另一个节点（需要注意的时，客户端并没有把down的节点从节点列表中移除，下次还是有可能先哈希到它）。如果某个节点时好时坏，两次哈希的方法就有风险了，好的节点和坏的节点上都可能存在脏数据（stale data）。
问：memcached是如何做身份验证的？
没有身份认证机制！memcached是运行在应用下层的软件（身份验证应该是应用上层的职责）。memcached的客户端和服务器端之所以是轻量级的，部分原因就是完全没有实现身份验证机制。这样，memcached可以很快地创建新连接，服务器端也无需任何配置。如果您希望限制访问，您可以使用防火墙，或者让memcached监听unix domain socket。
问：memcached能接受的key的最大长度是多少？
memcached能接受的key的最大长度是250个字符。需要注意的是，250是memcached服务器端内部的限制。如果使用的Memcached客户端支持"key的前缀"或类似特性，那么key（前缀+原始key）的最大长度是可以超过250个字符的。推荐使用较短的key，这样可以节省内存和带宽。
问：memcached对item的过期时间有什么限制？
item对象的过期时间最长可以达到30天。memcached把传入的过期时间（时间段）解释成时间点后，一旦到了这个时间点，memcached就把item置为失效状态。
问：memcached最大能存储多大的单个item？
memcached最大能存储1MB的单个item。如果需要被缓存的数据大于1MB，可以考虑在客户端压缩或拆分到多个key中。
问：为什么单个item的大小被限制在1M byte之内？
简单的回答：因为内存分配器的算法就是这样的。
详细的回答：
1）Memcached的内存存储引擎，使用slabs来管理内存。内存被分成大小不等的slabs chunks（先分成大小相等的slabs，然后每个slab被分成大小相等chunks，不同slab的chunk大小是不相等的）。chunk的大小依次从一个最小数开始，按某个因子增长，直到达到最大的可能值。如果最小值为400B，最大值是1MB，因子是1.20，各个slab的chunk的大小依次是：slab1 - 400B；slab2 - 480B；slab3 - 576B …slab中chunk越大，它和前面的slab之间的间隙就越大。因此，最大值越大，内存利用率越低。Memcached必须为每个slab预先分配内存，因此如果设置了较小的因子和较大的最大值，会需要为Memcached提供更多的内存。
2）不要尝试向memcached中存取很大的数据，例如把巨大的网页放到mencached中。因为将大数据load和unpack到内存中需要花费很长的时间，从而导致系统的性能反而不好。如果确实需要存储大于1MB的数据，可以修改slabs.c：POWER_BLOCK的值，然后重新编译memcached；或者使用低效的malloc/free。另外，可以使用数据库、MogileFS等方案代替Memcached系统。
问：memcached的内存分配器是如何工作的？为什么不适用malloc/free！？为何要使用slabs？
实际上，这是一个编译时选项。默认会使用内部的slab分配器，而且确实应该使用内建的slab分配器。最早的时候，memcached只使用malloc/free来管理内存。然而，这种方式不能与OS的内存管理以前很好地工作。反复地malloc/free造成了内存碎片，OS最终花费大量的时间去查找连续的内存块来满足malloc的请求，而不是运行memcached进程。slab分配器就是为了解决这个问题而生的。内存被分配并划分成chunks，一直被重复使用。因为内存被划分成大小不等的slabs，如果item的大小与被选择存放它的slab不是很合适的话，就会浪费一些内存。
问：memcached是原子的吗？
所有的被发送到memcached的单个命令是完全原子的。如果您针对同一份数据同时发送了一个set命令和一个get命令，它们不会影响对方。它们将被串行化、先后执行。即使在多线程模式，所有的命令都是原子的。然是，命令序列不是原子的。如果首先通过get命令获取了一个item，修改了它，然后再把它set回memcached，系统不保证这个item没有被其他进程（process，未必是操作系统中的进程）操作过。
memcached 1.2.5以及更高版本，提供了gets和cas命令，它们可以解决上面的问题。如果使用gets命令查询某个key的item，memcached会返回该item当前值的唯一标识。如果客户端程序覆写了这个item并想把它写回到memcached中，可以通过cas命令把那个唯一标识一起发送给memcached。如果该item存放在memcached中的唯一标识与您提供的一致，写操作将会成功。如果另一个进程在这期间也修改了这个item，那么该item存放在memcached中的唯一标识将会改变，写操作就会失败。
问：什么时候失效的数据项会从缓存中删除？
memcached 使用懒失效，当客户端请求数据项时， memcached 在返回数据前会检查失效时间来确定数据项是否已经失效。同样地，当添加一个新的数据项时，如果缓存已经满了， memcached 就会先替换失效的数据项，然后才是缓存中最少使用的数据项。
问：在设计应用时，可以通过Memcached缓存那些内容？
1）缓存简单的查询结果：查询缓存存储了给定查询语句对应的整个结果集，最合适缓存那些经常被用到，但不会改变的 SQL 语句对查询到的结果集，比如载入特定的过滤内容。记住，如果查询语句对应的结果集改变，该结果集不会展现出来。这种方法不总是有用，但它确实让工作变得比较快。
2）缓存简单的基于行的查询结果：基于行的缓存会检查缓存数据key的列表，那些在缓存中的行可以直接被取出，不在缓存中的行将会从数据库中取出并以唯一的键为标识缓存起来，最后加入到最终的数据集中返回。随着时间的推移，大多数数据都会被缓存，这也意味着相比与数据库，查询语句会更多地从 memcached 中得到数据行。如果数据是相当静态的，我们可以设置一个较长的缓存时间。
基于行的缓存模式对下面这种搜索情况特别有用：数据集本身很大或是数据集是从多张表中得到，而数据集取决于查询的输入参数但是查询的结果集之间的有重复部分。
比如，如果你有用户 A ， B ， C ， D ， E 的数据集。你去点击一张显示用户 A ， B ， E 信息的页面。首先， memcached 得到 3 个不同的键，每个对应一个用户去缓存中查找，全部未命中。然后就到数据库中用 SQL 查询得到 3 个用户的数据行，并缓存他们。现在，你又去点击另一张显示显示 C ， D ， E 信息的页面。当你去查找 memcached 时， C ， D 的数据并没有被命中，但我们命中了 E 的数据。然后从数据库得到 C ， D 的行数据，缓存在 memcached 中。至此以后，无论这些用户信息怎样地排列组合，任何关于 A ， B ， C ， D ， E 信息的页面都可以从 memcached 得到数据了。
3）缓存的不只是 SQL 数据，可以缓存最终完成的部分显示页面，以节省CPU计算时间
例如正在制作一张显示用户信息的页面，你可能得到一段关于用户的信息（姓名，生日，家庭住址，简介），然后你可能会将 XML 格式的简介信息转化为 HTML 格式或做其他的一些工作。相比单独存储这些属性，你可能更愿意存储经过渲染的数据块。那时你就可以简单地取出被预处理后的 HTML 直接填充在页面中，这样节省了宝贵的 CPU 时间。