一致性hash与虚拟节点.pptVIP

一致性?hash?算法 虚拟节点 分布式缓存 $nodes = array(node1,node2,node3); //memcache服务器$keys = array(tokyo,kanagawa,chiba,saitama,gunma,ghwet,ufaiosuid,afsdfasdfasd,487); //测试键值//返会mamcache服务器名function getMs ($key){ //判断键值是否合法 if (strlen($key) = 0 || !preg_match(/^\w+$/, $key)) { return false; } global $nodes; $crc = abs(crc32($key)); $mod = $crc % (count($nodes)); return $nodes[$mod];}foreach ($keys as $val){ echo $val=; echo getMs($val); echo br;} 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} };} 接下来增加一台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 首先，当服务器只有三台时：$ mod.pl node1 node2 nod3node1: a,c,d,e,h,j,n,u,w,xnode2: g,i,k,l,p,r,s,ynode3: b,f,m,o,q,t,v,z  hash?算法的单调性 Hash?算法的一个衡量指标是单调性（?Monotonicity?），定义如下： 　　单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲 中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。 容易看到，上面的简单?hash?算法?hash(object)%N?难以满足单调性要求。 0 2^32-1? 环形?hash?空间 0 2^32-1? ?对象映射 Hash object1 key1 object4 object2 object3 key3 key2 key4 0 2^32-1? ?一致性hash Hash object1 key1 object4 object2 object3 key3 key2 key4 cacheA keyA keyB keyC cacheC cacheB 0 2^32-1? ?移除cacheB? Hash object1 key1 object4 object2 object3 key3 key2 key4 cacheA keyA keyB keyC cacheC cacheB 0 2^32-1? ?增加cacheD Hash object1 key1 object4 object2 object3 key3 key2 key4 cacheA keyA keyB keyC cacheC cacheB cacheD keyD  hash?算法的平衡性 Hash?算法的另一个衡量指标是平衡性（? Balance ?），定义如下： 　　平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。 容易看到，上面的算法仍然难以满足平衡性要求。 0 2^32-1? ?虚拟节点 Hash object1 key1 object4 object2 object3 key3 key2 key4 cacheA1 keyA1 keyC1 cach