Memcache内部剖析

Memcache在web社区中是一个非常著名的系统，而且有一个好的原因：它速度快、稳定、轻量级，而且如果你在网站服务器安装了memcache后它似乎会自动将网站访问速度提升10倍。虽然这似乎有点不可思议，但是：定制一个好的缓存策略对网站或应用很有用。如果你只是想知道如果在你的网站中应用memcache，那很不幸，本文并不是教你如何使用memcache。我们将抽丝剥茧，看看是什么使memcache如此神奇？

尽管memcache本身并不是一个非常复杂的软件，但它却有许多很好的功能,这要花很长时间来谈论。我将主要关注一下四个方面：

1. Big-O

2. LRU

3. 内存分配（Memory allocation）

4. 一致性哈希（Consistent hashing）

Big-O

memcache大部分函数（add、get、set、flush）的时间复杂度都为o(1)。这意味着它们都是时间常数的函数，与缓存中有多少对象无关，这些函数所花的时间与缓存中只有一条数据时所花的时间相同。更多关于big-o的信息，请阅读博客（https://www.adayinthelifeof.nl/2009/12/21/big-o-notation/）。使用o(1)函数会有很多好处（memcache一直保持快速），但是也有一些缺点。比如：你不能在memcache中不能通过迭代且迭代所有对象（如果非要这么做，那是对memcache的滥用，但这又是另一个话题）。迭代器有可能是一个时间复杂度为o(N)的操作；这意味这如果缓存的对象翻倍，那么所花的时间也要翻倍。这也正式memcache不支持迭代函数的原因。

LRU算法

当你启动一个memcache守护进程之前，你需要告诉它你需要多少内存。memcache将在启动的时候正确分配内存，因此如果你需要1G内存来存放缓存数据的话，那么这1G内存会被直接分配而且不用用作其他用途（就像apache或者数据库实例一样）。但是由于我们已经告诉memcache它可以使用多少内存，memcache有可能会将它的所有内存来存储我们的数据。那么，如果我们需要增加更多的数据会发生什么情况呢？

也许你已经知道，memcache将会删除老的数据来为新数据提供空间，但它需要知道哪些数据对象可以被删除。是我们最近放入的占用空间最大的对象？或者是最先放入缓存的对象，这样我们就可以得到一个基于先进先出算法的缓存系统？真实情况是，memcache使用了一种更先进的技术，叫做LRU:最近最少使用。简单地说就是：它删除最长时间没有没使用的对象。这不一定是最大的对象，而且甚至不一定是最先放入缓存的数据。

在memcache内部,所有对象都有一个“计数器”。这个计数器持有一个时间戳；每次一个新的对象被创建后，这个计数器会被设置为当前时间。当一个对象被获取后，memcache也会重置该计数器为当前时间。一旦memcache需要“删除"一个对象来为新的对象腾出空间时，它将找到最小的计数器。这个对象即为没有被获取或离上次获取的时间最长（也许不需要那么多，否则计数器的值将接近当前时间戳）。

实际上这将创建一个使用缓存非常有效的简单系统。如果它没有被使用，它被从系统系统剔除。

AdamPresley写了一篇博客来教大家如何在php项目中使用这种机制。在memcache中,对这种系统的使用略有不同，它被用来保证绝大部分函数的时间复杂度保持在o(1)。

内存分配

内存分配是大部分php开发人员研究之外的一个方面。这也是为什么高级编程语言更简单的原因：大多数工作由底层的系统如编译器或操作系统来完成。但由于memcache是用C写的，所以它必须自己去做内存分配和管理。幸运的是,大多数的工作(必须)可以委托给操作系统来做，所以，实际上我们只用去使用一个函数（malloc函数）来分配内存、一个在有些情况下不需要的函数（free函数）来释放内存以及可能会用到一个函数（realloc函数）来重新设置当前内存块大小。

现在，你所创建的C项目一切都妥当了，在这个项目中你在创建字符串之前需要为它分配内存空间，然后对它做操作，最后释放你所使用的内存。但是高性能的系统如memcache使用这种方式会有问题。主要原因是malloc函数和free函数在这种系统中实际上并没有被优化。这种情况下内存很容易出现碎片，也就是说会有很多内存溢出；这就像你在磁盘上写入或者删除文件时会造成大量磁盘空间碎片一样（但平心而论，这种情况取决于你所使用的系统）。

现在，你所创建的C项目一切都妥当了，在这个项目中你在创建字符串之前需要为它分配内存空间，然后对它做操作，最后释放你所使用的内存。但是高性能的系统如memcache使用这种方式会有问题。主要原因是malloc函数和free函数在这种系统中实际上并没有被优化。这种情况下内存很容易出现碎片，也就是说会有很多内存溢出；这就像你在磁盘上写入或者删除文件时会造成大量磁盘空间碎片一样（但平心而论，这种情况取决于你所使用的系统）。你还记得你隔一段时间必须整理一次磁盘的时代吗？基本上，同样的事情在内存中同样存在；这意味着最后由于内存碎片将导致内存分配越来越慢以及大量内存不能被使用。

目前，为了解决malloc函数问题，memcache默认使用它自带的内存管理器（你也可以让memcache使用标准的malloc函数，但是这种做法是不明智的）。Memcache的内存管理器将通过一个malloc调用从操作系统分配你设置的最大值（比如64M,或者更多）；从这时起memcache使用自带的被称作slab分配器的内存管理系统。

Slab分配

当memcache启动时，它会将分配给它的内存重新分配为更小的部分被称作页（page）。每页大小为1M（凑巧的是，在memcache中你可以存储的单个对象最大内存也是1M）。每个页可以被分配给一个slab类或者页可以被收回（变成一个空闲页）。slab类决定多大的对象可以被存储在特定的内存页中。同时每个页都会被指定一个特定的sub-class，这样个页被分为更小的块（chunk）。在slab中的每个块都有相同的大小，因此在同一个页中不能有两种不同大小的块。例如，一个页的块大小为64字节(slab类1)，另一个页的块大小为128字节(slab类2)等等，直到拥有最大slab的页只有一个块（1M大小的块）。每种slab类可以存在于多个页中，但是一旦一个页被分配了一个slab类之后（也就是说已经被分成了块），那么该页就不能再次被分配其他slab类。

最小的块大小从80字节开始，并且块大小的增长使用参数1.25（往上进位直到达到下一个2的整数幂大小）。因此，80字节之后下一个最小的块大小为100，依次类推；你可以增加"-vv"参数在mecache启动时来观察它。你也可以通过-f来设置增长参数（译注：改变1.25的值）以及使用-s来设置块的初始化大小；但是，除非你非常明确需要这样做，否则不要改变初始参数值。

你实际上看到的是slab类的数量、slab内块的大小以及有多少块（很显然：块越大，块的数量就越少）。Memcache会为每个slab类初始化一个page,其他页保持空闲（如果slab类需要一个页，就指定一个）。memcache已经对内存做了分区之后就可以往slab中增加数据了。假设我有一个105字节大小的对象（这包括memcache的开销，所以能存储在memcache中的数据会比实际少一些），memcache就会知道该对象应该使用slab类3中块来存储该对象，因为slab类3的大小适合105字节的对象，也就是说我们有128-105=23字节的内存未被使用，而这23字节的内存也不能被用来做其他的事。那个块被标记为已使用，这就是那个对象。这是我们使用slab分配器需要付出的代价，但是内存却不会有碎片。实际上，这是速度和内存浪费之间的权衡。

那么，一旦一个页被使用完（这个页中的所有块都被放满数据）同时我们又要增加其他一些数据，memcache将会获取一个新的空闲页并将该页分配给特性的slab类，再将其分成块并使用第一个有效的块来存储数据。但是如果一旦页被使用完，那么memcache就会使用LRU算法来清除已经存在的块来腾出空间。也就是说，如果我们需要一个128字节的块，它就会清除一个128字节的块出来，尽管可能有256字节块比这个128字节的块中的数据更老。此外，每个slab类都有自己的LRU算法。

所以我们假设：

如果你在所有缓存中都使用的是128字节大小的块来存储数据（以上例子中的slab类3），memcache将会分配所有的页到那个slab类。实际上可能其他的slab类只有一个页（在初始化时分配），也就是说当已经有一个1M的对象存储在块大小为1M的页中时，第二个1M的对象没有新的页可分配。此时，memecache必须使用LRU算法来移除一个对象，而由于只有一个1M的slab类对应的页，那么第一个1M的对象被移除。到了本文最后，你就会知道slab分配器是如何工作的。

一致性哈希（Consistent hashing）

你的web应用和同时和多个不同的memcache服务器来交互，你只需要将你的应用升级为一组memcache服务器的ip即可，因此它默认使用所有的memcache服务器。

当我们添加一个对象到memcache中时，它会自动选择一个可以存储该数据的服务器。当只有一台mecache服务器时这个选择非常容易，但是当你有多个服务器时memcache必须找到一种方式来存储对象。对于这种情况有多种不同的算法，例如：使用轮循系统将每个存储操作按顺序保存至下一个服务器（第一个对象保存在服务器1中，第二个保存至服务器2中，第三个保存至服务器1中，以此类推）。但当我们想获取指定数据时这样的一个系统怎么知道正确的服务器？

memcache所做的非常简单，然而该负载均衡技巧非常有效：为每个存储或获取的键(key)来创建一个哈希(你可能会认为是md5(key)，但事实上，这是一个更专业快速的哈希方法)。至此，我们创建的散列是均匀分布的，所以我们可以使用模函数找出那个服务器存储了我们需要的对象：

在php中，代码如下：

非常好。现在,我们仅仅通过这个简单的公式就可以推断出哪个服务器持有指定的键。这个机制的问题：一旦$servercount(服务器的数量)发生变化，几乎所有的键也都会改变服务器；也许一些键服务器id保持不变,但这纯属巧合。事实上,当你改变了memcache服务器数量（不论是增加或减少，都没关系），你的后端都会增加大量请求，因为所有的键一次性全部都失效了。

现在，让我们来拥抱一致性哈希。通过使用这种算法，在服务器增加或减少时我们不用担心键会改变服务器。以下是它的工作原理：

一致性哈希使用一个类似像时钟的计时器。一旦它到达“12”，它会重新回滚至“1”。假设这个计时器是16位，那么它的取值范围是65535。如果我们设想这是一个时钟，数字0和65535就像时钟上的12点，32200将在6点钟，48000就在9点钟，依此类推。我们称之为连续时钟。

在这个连续时钟上，我们为每个服务器放置（相对）大量的"点"。这些点是随机放置的，就好比我们有一个许多点的时钟一样。

作为例子，让我展示一个拥有3台服务器(s1,s2,s3)，每台服务器有2个点的连续时钟：

如果这个连续时钟是16位的数字，s1上的点或多或少在10到29000之间，s2上的点将在39000到55000之间，s3上的点将在8000到48000之间。现在，当我们存储一个键时，我们创建了一个16位数字的哈希值，这个数字可以绘制在连续时钟之上。假设我们有四个键（k1到k4）,得到的4个哈希值分别是：15000、52000、34000、38000。如下图中的红点所示：

找到一个key应该存储的服务器，我们唯一需要做的就是按照连续时钟顺时针方向找,直到我们达到了“服务器”点上。对于k1来说，我们沿着连续时钟来找直到我们找到s1。K2将找到s2。k3将找到s3,k4将找到s3。到此为止，并没有什么特别的事情发生。实际上，看起来我们本来用模数算法很容易做的事情使用这种方式多做了很多额外的工作。

在这里，一致性哈希是有优势的：假设服务器2将从memcache服务器池中移除，那么如果想要获取k1将会发生什么？没有奇快的事情发生，我们标记的k1仍然在连续时钟上相同的位置，它首先遇到的服务器点仍然是s1。

然而，当获取k3时，由于k3存储在s2上，它将错误s2(因为s2已经被移除)，那么它将移动到s3上。对k2来说同理，它将移动至s1上。

事实上，我们在连续时钟上放置的服务器点越多，在一个服务器被移除（或增加）时丢失的键就会越少。最好的服务器节点数量应该100到200之间，此后如果服务器再多就会是连续时钟上的查找更慢（这当然是一个非常快的过程）。添加的服务器越多，一致性哈希将执行的越好。

不像使用标准取模算法时会导致几乎所有的key发生移动，一致性哈希算法也许只会导致10%~25%的键失效（这个数字还会随着你服务器的增加而快速下降），换句话说，后端服务器（如数据库）的压力会比使用取模算法时更小。

结论

很高兴能在某些系统上做一些深入了解,我们认为是理所当然的。就像在“现实生活”中，事情更加复杂化而且由许多复杂的解决方法组成，这些也许都可以帮助你自己的（发展）生活。像LRU以及一致性哈希这样的算法并不难理解，只是现在你知道它们的存在从长远来看可以帮助你成为一名更好的开发者。

1.本文由程序员学架构摘译

2. 本文译自https://www.adayinthelifeof.nl/2011/02/06/memcache-internals/

3. 转载请务必注明本文出自：程序员学架构(微信号：archleaner )

4. 更多文章请扫码：