共计 4586 个字符，预计需要花费 12 分钟才能阅读完成。
本篇文章为大家展示了如何分析 memcached 的分布式算法，内容简明扼要并且容易理解，绝对能使你眼前一亮，通过这篇文章的详细介绍希望你能有所收获。
下面开始介绍 memcached 的分布式，不再介绍 memcached 的内部结构。
memcached 的分布式
memcached 虽然称为“分布式”缓存服务器，但服务器端并没有“分布式”功能。服务器端内存存储功能，其实现非常简单。至于 memcached 的分布式，则是完全由客户端程序库实现的。这种分布式是 memcached 的最大特点。
memcached 的分布式是什么意思？
这里多次使用了“分布式”这个词，但并未做详细解释。现在开始简单地介绍一下其原理，各个客户端的实现基本相同。
下面假设 memcached 服务器有 node1～node3 三台，应用程序要保存键名为“tokyo”“kanagawa”“chiba”“saitama”“gunma”的数据。
图 1 分布式简介：准备
首先向 memcached 中添加“tokyo”。将“tokyo”传给客户端程序库后，客户端实现的算法就会根据“键”来决定保存数据的 memcached 服务器。服务器选定后，即命令它保存“tokyo”及其值。
图 2 分布式简介：添加时
同样，“kanagawa”“chiba”“saitama”“gunma”都是先选择服务器再保存。
接下来获取保存的数据。获取时也要将要获取的键“tokyo”传递给函数库。函数库通过与数据保存时相同的算法，根据“键”选择服务器。使用的算法相同，就能选中与保存时相同的服务器，然后发送 get 命令。只要数据没有因为某些原因被删除，就能获得保存的值。
图 3 分布式简介：获取时
这样，将不同的键保存到不同的服务器上，就实现了 memcached 的分布式。memcached 服务器增多后，键就会分散，即使一台 memcached 服务器发生故障 无法连接，也不会影响其他的缓存，系统依然能继续运行。
接下来介绍第 1 次 中提到的 Perl 客户端函数库 Cache::Memcached 实现的分布式方法。
Cache::Memcached 的分布式方法
Perl 的 memcached 客户端函数库 Cache::Memcached 是 memcached 的作者 Brad Fitzpatrick 的作品，可以说是原装的函数库了。
Cache::Memcached – search.cpan.org
该函数库实现了分布式功能，是 memcached 标准的分布式方法。
根据余数计算分散
Cache::Memcached 的分布式方法简单来说，就是“根据服务器台数的余数进行分散”。求得键的整数哈希值，再除以服务器台数，根据其余数来选择服务器。
下面将 Cache::Memcached 简化成以下的 Perl 脚本来进行说明。
use strict;
use warnings;
use String::CRC32;
my @nodes = ( node1 , node2 , node3
my @keys = ( tokyo , kanagawa , chiba , saitama , gunma
foreach my $key (@keys) { my $crc = crc32($key); # CRC 値
my $mod = $crc % ( $#nodes + 1 );
my $server = $nodes[ $mod ]; # 根据余数选择服务器
printf %s = %s\n , $key, $server;
}Cache::Memcached 在求哈希值时使用了 CRC。
String::CRC32 – search.cpan.org
首先求得字符串的 CRC 值，根据该值除以服务器节点数目得到的余数决定服务器。上面的代码执行后输入以下结果：
tokyo = node2
kanagawa = node3
chiba = node2
saitama = node1
gunma = node1根据该结果，“tokyo”分散到 node2，“kanagawa”分散到 node3 等。多说一句，当选择的服务器无法连接时，Cache::Memcached 会将连接次数 添加到键之后，再次计算哈希值并尝试连接。这个动作称为 rehash。不希望 rehash 时可以在生成 Cache::Memcached 对象时指定“rehash = 0”选项。
根据余数计算分散的缺点
余数计算的方法简单，数据的分散性也相当优秀，但也有其缺点。那就是当添加或移除服务器时，缓存重组的代价相当巨大。添加服务器后，余数就会产生巨变，这样就无法获取与保存时相同的服务器，从而影响缓存的命中率。用 Perl 写段代码来验证其代价。
use strict;
use warnings;
use String::CRC32;
my @nodes = @ARGV;
my @keys = ( a .. z
my %nodes;
foreach my $key ( @keys ) { my $hash = crc32($key);
my $mod = $hash % ( $#nodes + 1 );
my $server = $nodes[ $mod ];
push @{ $nodes{ $server } }, $key;
foreach my $node ( sort keys %nodes ) { printf %s: %s\n , $node, join , , @{ $nodes{$node} };
}这段 Perl 脚本演示了将“a”到“z”的键保存到 memcached 并访问的情况。将其保存为 mod.pl 并执行。
首先，当服务器只有三台时：
$ mod.pl node1 node2 nod3
node1: a,c,d,e,h,j,n,u,w,x
node2: g,i,k,l,p,r,s,y
node3: b,f,m,o,q,t,v,z结果如上，node1 保存 a、c、d、e……，node2 保存 g、i、k……，每台服务器都保存了 8 个到 10 个数据。
接下来增加一台 memcached 服务器。
$ mod.pl node1 node2 node3 node4
node1: d,f,m,o,t,v
node2: b,i,k,p,r,y
node3: e,g,l,n,u,w
node4: a,c,h,j,q,s,x,z添加了 node4。可见，只有 d、i、k、p、r、y 命中了。像这样，添加节点后 键分散到的服务器会发生巨大变化。26 个键中只有六个在访问原来的服务器，其他的全都移到了其他服务器。命中率降低到 23%。在 Web 应用程序中使用 memcached 时，在添加 memcached 服务器的瞬间缓存效率会大幅度下降，负载会集中到数据库服务器上，有可能会发生无法提供正常服务的情况。
mixi 的 Web 应用程序运用中也有这个问题，导致无法添加 memcached 服务器。但由于使用了新的分布式方法，现在可以轻而易举地添加 memcached 服务器了。这种分布式方法称为 Consistent Hashing。
Consistent Hashing
关于 Consistent Hashing 的思想，mixi 株式会社的开发 blog 等许多地方都介绍过，这里只简单地说明一下。
mixi Engineers Blog – スマートな分散で快適キャッシュライフ
ConsistentHashing – コンシステント ハッシュ法
Consistent Hashing 的简单说明
Consistent Hashing 如下所示：首先求出 memcached 服务器（节点）的哈希值，并将其配置到 0～232 的圆（continuum）上。然后用同样的方法求出存储数据的键的哈希值，并映射到圆上。然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上。如果超过 232 仍然找不到服务器，就会保存到第一台 memcached 服务器上。
图 4 Consistent Hashing：基本原理
从上图的状态中添加一台 memcached 服务器。余数分布式算法由于保存键的服务器会发生巨大变化 而影响缓存的命中率，但 Consistent Hashing 中，只有在 continuum 上增加服务器的地点逆时针方向的 第一台服务器上的键会受到影响。
图 5 Consistent Hashing：添加服务器
因此，Consistent Hashing 最大限度地抑制了键的重新分布。而且，有的 Consistent Hashing 的实现方法还采用了虚拟节点的思想。使用一般的 hash 函数的话，服务器的映射地点的分布非常不均匀。因此，使用虚拟节点的思想，为每个物理节点（服务器）在 continuum 上分配 100～200 个点。这样就能抑制分布不均匀，最大限度地减小服务器增减时的缓存重新分布。
通过下文中介绍的使用 Consistent Hashing 算法的 memcached 客户端函数库进行测试的结果是，由服务器台数（n）和增加的服务器台数（m）计算增加服务器后的命中率计算公式如下：
(1 – n/(n+m)) * 100
支持 Consistent Hashing 的函数库
本连载中多次介绍的 Cache::Memcached 虽然不支持 Consistent Hashing，但已有几个客户端函数库支持了这种新的分布式算法。第一个支持 Consistent Hashing 和虚拟节点的 memcached 客户端函数库是 名为 libketama 的 PHP 库，由 last.fm 开发。
libketama – a consistent hashing algo for memcache clients – RJ ブログ – Users at Last.fm
至于 Perl 客户端，连载的第 1 次 中介绍过的 Cache::Memcached::Fast 和 Cache::Memcached::libmemcached 支持 Consistent Hashing。
Cache::Memcached::Fast – search.cpan.org
Cache::Memcached::libmemcached – search.cpan.org
两者的接口都与 Cache::Memcached 几乎相同，如果正在使用 Cache::Memcached，那么就可以方便地替换过来。Cache::Memcached::Fast 重新实现了 libketama，使用 Consistent Hashing 创建对象时可以指定 ketama_points 选项。
my $memcached = Cache::Memcached::Fast- new({ servers = [ 192.168.0.1:11211 , 192.168.0.2:11211],
ketama_points = 150
});另外，Cache::Memcached::libmemcached 是一个使用了 Brain Aker 开发的 C 函数库 libmemcached 的 Perl 模块。libmemcached 本身支持几种分布式算法，也支持 Consistent Hashing，其 Perl 绑定也支持 Consistent Hashing。
Tangent Software: libmemcached
上述内容就是如何分析 memcached 的分布式算法，你们学到知识或技能了吗？如果还想学到更多技能或者丰富自己的知识储备，欢迎关注丸趣 TV 行业资讯频道。
