Comprehensive analysis of memcached – 4. Memcached's distributed algorithm_PHP tutorial

Original link: http://gihyo.jp/dev/feature/01/memcached/0004

The link to this series of articles is here:

• The 1st time: http://www.phpchina.com/html/29/n-35329.html
• The 2nd time: http://www.phpchina.com/html/ 30/n-35330.html
• The 3rd time: http://www.phpchina.com/html/31/n-35331.html
• The 4th time: http:// www.phpchina.com/html/32/n-35332.html href="http://www.phpchina.com/html/32/n-35332.html">
• The 5th time: http://www.phpchina.com/html/32/n-35333.html href="http://www.phpchina.com/html/32/n-35333.html">  href="http://www.phpchina.com/html/32/n-35332.html">

I am Nagano from Mixi. The 2nd and 3rd times Maesaka introduced the internal situation of memcached. This time I will no longer introduce the internal structure of memcached, but start to introduce the distribution of memcached.

• Memcached’s distribution
  • What does memcached’s distribution mean?
• Cache::Memcached’s distributed method
  • Calculate dispersion based on remainder
  • Disadvantages of calculating dispersion based on remainder
• Consistent Hashing
  • A brief description of Consistent Hashing
  • Function library that supports Consistent Hashing
• Summary

Distribution of memcached

As introduced in the first time, although memcached is called a "distributed" cache server, the server side does not have a "distributed" function. The server side only includes the memory storage function introduced by Maesaka in the second and third times, and its implementation is very simple. As for the distribution of memcached, it is completely implemented by the client library. This distribution is the biggest feature of memcached.

What does memcached’s distribution mean?

The word "distributed" is used many times here, but it is not explained in detail. Now let’s briefly introduce the principle. The implementation of each client is basically the same.

Assume below that there are three memcached servers, node1~node3, and the application needs to save data with key names "tokyo", "kanagawa", "chiba", "saitama" and "gunma".

Figure 1 Distribution introduction: preparation

First add "tokyo" to memcached. After passing "tokyo" to the client library, the algorithm implemented by the client will determine the memcached server to save the data based on the "key". Once the server is selected, it is commanded to save "tokyo" and its value.

Figure 2 Distribution introduction: when adding

Similarly, "kanagawa", "chiba", "saitama" and "gunma" all select the server first and then save.

Next get the saved data. When obtaining, the key "tokyo" to be obtained must also be passed to the function library. The function library selects the server based on the "key" through the same algorithm used when saving data. Using the same algorithm, you can select the same server as when saving, and then send the get command. As long as the data has not been deleted for some reason, the saved value can be obtained.

Figure 3 Introduction to distribution: when obtaining

In this way, saving different keys to different servers realizes the distribution of memcached. As the number of memcached servers increases, the keys will be dispersed. Even if one memcached server fails and cannot be connected, it will not affect other caches and the system can still continue to run.

The following introduces the distributed method implemented by the Perl client function library Cache::Memcached mentioned in the first time.

Cache::Memcached's distributed method

Perl's memcached client function library Cache::Memcached is the work of Brad Fitzpatrick, the author of memcached, and can be said to be the original function library.

• Cache::Memcached - search.cpan.org

This function library implements distributed functions and is the standard distributed method of memcached.

Calculation of dispersion based on the remainder

The distributed method of Cache::Memcached is simply "dispersion based on the remainder of the number of servers". Find the integer hash value of the key, divide it by the number of servers, and select the server based on the remaining number.

The following simplifies Cache::Memcached into the following Perl script for explanation.

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 uses CRC when calculating the hash value.

• String::CRC32 - search.cpan.org

First find the CRC value of the string, and determine the server based on the remainder obtained by dividing this value by the number of server nodes . After executing the above code, enter the following results:

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～2³²的圆（continuum）上。 然后用同样的方法求出存储数据的键的哈希值，并映射到圆上。 然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上。 如果超过2³²仍然找不到服务器，就会保存到第一台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的分布式算法，主要有memcached的分布式是由客户端函数库实现， 以及高效率地分散数据的Consistent Hashing算法。下次将介绍mixi在memcached应用方面的一些经验， 和相关的兼容应用程序。

版权声明：可以任意转载，但转载时必须标明原作者charlee、原始链接以及本声明。

http://www.bkjia.com/PHPjc/735131.htmlwww.bkjia.comtruehttp://www.bkjia.com/PHPjc/735131.htmlTechArticle原文链接：http://gihyo.jp/dev/feature/01/memcached/0004 这个系列文章的链接在这里： 第1次：http://www.phpchina.com/html/29/n-35329.html 第2次：http://www.php...