Memcached 之取模与哈希算法命中率实验

Mike

当5台memcache服务器中有一台宕机时的命中率实验。
一、php实现代码
1. config.php

$server = array(
"A" => array("host" => "127.0.0.1", "port" => 11211),
"B" => array("host" => "127.0.0.1", "port" => 11212),
"C" => array("host" => "127.0.0.1", "port" => 11213),
"D" => array("host" => "127.0.0.1", "port" => 11214),
"E" => array("host" => "127.0.0.1", "port" => 11215),
);
$_dis = "Moder";//Consistent

2. hash.php 

interface hasher {public function _hash($str);}
interface distribution {public function lookup($key);}
/**
* 取模算法类
*/
class Moder implements hasher,distribution
{
protected $_nodes = array();
protected $_cnt = 0;
public function _hash($str) {
return sprintf('%u',crc32($str)); // 把字符串转成 32 位符号整数
}
public function addNode($node){
if (in_array($node, $this->_nodes)) {
return true;
}
$this->_nodes[] = $node;
$this->_cnt += 1;
return true;
}
public function delNode($node) {
if (!in_array($node, $this->_nodes)) {
return true;
}
$key = array_search($node, $this->_nodes);
unset($this->_nodes[$key]);
$this->_cnt -= 1;
return true;
}
public function lookup($key) {
$key = $this->_hash($key) % $this->_cnt;
return $this->_nodes[$key];
}
public  function printNodes()
{
print_r($this->_nodes);
}
}
/*
$mode = new Moder();
$mode->addNode('a');
$mode->addNode('b');
$mode->addNode('c');
$key = "sssa";
$mode->printNodes();
echo $mode->_hash($key)."<br/>";
echo $mode->lookup($key);
*/

/**
*一致性hash算法类
*/
class Consistent implements hasher,distribution{
protected $_nodes = array(); //服务器节点
protected $_postion = array();//虚拟节点
protected $_mul = 64; //每个节点对应 64 个虚节点
public function _hash($str) {
return sprintf('%u',crc32($str)); // 把字符串转成 32 位符号整数
}
// 核心功能
public function lookup($key) {
$point = $this->_hash($key);
$node = current($this->_postion); //先取圆环上最小的一个节点,当成结果
foreach($this->_postion as $k=>$v) {
if($point <= $k) 
{
$node = $v;
break;
}
}
reset($this->_postion);
return $node;
}
//添加节点
public function addNode($node) {
if(isset($this->nodes[$node])) {
return;
}
for($i=0; $i<$this->_mul; $i++) {
$pos = $this->_hash($node . '-' . $i);
$this->_postion[$pos] = $node;
$this->_nodes[$node][] = $pos;
}
$this->_sortPos();
}
// 循环所有的虚节点,谁的值==指定的真实节点 ,就把他删掉
public function delNode($node) {
if(!isset($this->_nodes[$node])) {
return;
}
foreach($this->_nodes[$node] as $k) {
unset($this->_postion[$k]);
}
unset($this->_nodes[$node]);
}
//将虚拟节点排序
protected function _sortPos() {
ksort($this->_postion,SORT_REGULAR);
}
}
/*
// 测试
$con = new Consistent();
$con->addNode('a');
$con->addNode('b');
$con->addNode('c');
$key = 'www.zixue.it';
echo '此 key 落在'.$con->lookup($key).'号节点';
*/

3.initData.php（初始化数据）

include './config.php';
include './hash.php';
set_time_limit(0);
$mem = new Memcache();
$diser = new $_dis(); 
foreach ($server as $key => $value) {
$diser->addNode($key);
}
for ($i=0; $i < 1000; $i++) { 
//获取服务器
$serv = $server[$diser->lookup("key" . $i)];
$mem->connect($serv['host'], $serv['port'], 2);
$mem->add("key".$i, "value".$i, 0, 0);
}
echo "full";

4.load.php （获取数据的概率）

include './config.php';
include './hash.php';
set_time_limit(0);
$mem = new Memcache();
$diser = new $_dis(); 
foreach ($server as $key => $value) {
$diser->addNode($key);
}
for ($i=0; $i < 1000; $i++) { 
//获取服务器
$serv = $server[$diser->lookup("key" . $i)];
$mem->connect($serv['host'], $serv['port'], 2);
$mem->add("key".$i, "value".$i, 0, 0);
}
echo "full";

5.exec.php （执行）

//模拟减少一台服务器
include './config.php';
include './hash.php';
$mem = new Memcache();
$diser = new $_dis(); 
foreach ($server as $key => $value) {
$diser->addNode($key);
}
//删除一台服务器
$diser->delNode("D");

for ($i=0; $i < 10000; $i++) { 
//获取服务器
$serv = $server[$diser->lookup("key" . $i)];
if ($serv) {
$mem->connect($serv['host'], $serv['port'], 2);
if(!$mem->get("key" . $i)){
$mem->add("key".$i, "value".$i, 0, 0);
}
}
usleep(3000);
}

二、取模算法命中率
如图：
1.初始状态：

2.过程中状态：

3.结束状态

三、哈希算法命中率
如图：
1.初始状态：

2.过程中：

3.结束状态：

三、总结
1.取模命中率为20%（1 / N），哈希命中率为80%左右（(N - 1) / N）。
2.当 memcached 节点越多时，一致性哈希算法对缓存的命中率比取模算法对缓存的命中率要高很多。