第4章 Memcached 的分布式算法

优质

小牛编辑

133浏览

2023-12-01

第 2 章、第 3 章介绍了 Memcached 的内部情况。本次不再介绍 Memcached 的内部结构，开始介绍 Memcached 的分布式。

4.1 Memcached 的分布式

正如第1章中介绍的那样，Memcached 虽然称为 分布式 缓存服务器，但服务器端并没有 分布式 功能。服务器端仅包括第2章、第3章介绍的内存存储功能，其实现非常简单。至于 Memcached 的分布式，则是完全由客户端程序库实现的。这种分布式是 Memcached 的最大特点。

Memcached 的分布式是什么意思？

这里多次使用了 分布式 这个词，但并未做详细解释。现在开始简单地介绍一下其原理，各个客户端的实现基本相同。

下面假设 Memcached 服务器有 node1～node3 三台，应用程序要保存键名为 tokyo、kanagawa、chiba、saitama、gunma 的数据。

图 4.1：分布式简介：准备

首先向 Memcached 中添加 tokyo。将 tokyo 传给客户端程序库后，客户端实现的算法就会根据键来决定保存数据的 Memcached 服务器。服务器选定后，即命令它保存 tokyo 及其值。

图 4.2：分布式简介：添加时

同样 kanagawa、chiba、saitama、gunma 都是先选择服务器再保存。

接下来获取保存的数据。获取时也要将要获取的键 tokyo 传递给函数库。函数库通过与数据保存时相同的算法，根据键选择服务器。使用的算法相同，就能选中与保存时相同的服务器，然后发送 get 命令。只要数据没有因为某些原因被删除，就能获得保存的值。

图 4.3：分布式简介：获取时

这样将不同的键保存到不同的服务器上，就实现了 Memcached 的分布式。Memcached 服务器增多后，键就会分散，即使一台 Memcached 服务器发生故障无法连接，也不会影响其他的缓存，系统依然能继续运行。

接下来介绍第1章中提到的 Perl 客户端函数库 Cache::Memcached 实现的分布式方法。

4.2 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。

4.3 Consistent Hashing

关于 Consistent Hashing 的思想，mixi 株式会社的开发 blog 等许多地方都介绍过，这里只简单地说明一下。

mixi Engineers' Blog スマートな分散で快適キャッシュライフ

ConsistentHashing コンシステントハッシュ法

Consistent Hashing 的简单说明

Consistent Hashing 如下所示：首先求出 Memcached 服务器（节点）的哈希值，并将其配置到 0～2³²的圆（continuum）上。然后用同样的方法求出存储数据的键的哈希值，并映射到圆上。然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上。如果超过 2³²仍然找不到服务器，就会保存到第一台 Memcached 服务器上。

图 4.4：Consistent Hashing：基本原理

从上图的状态中添加一台 Memcached 服务器。余数分布式算法由于保存键的服务器会发生巨大变化而影响缓存的命中率，但 Consistent Hashing 中，只有在 continuum 上增加服务器的地点逆时针方向的第一台服务器上的键会受到影响。

图 4.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

4.4 总结

本次介绍了 Memcached 的分布式算法，主要有 Memcached 的分布式是由客户端函数库实现，以及高效率地分散数据的 Consistent Hashing 算法。下次将介绍 mixi 在 Memcached 应用方面的一些经验，和相关的兼容应用程序。