This time I will bring you a detailed explanation of the steps to implement the consistent Hash algorithm in PHP. What are the precautions for PHP to implement the consistent Hash algorithm? Here are practical cases, let’s take a look.
The consistent hash algorithm is a commonly used algorithm in distributed systems. Why should we use this algorithm? For example: a distributed storage system needs to store data on specific nodes (servers). If the number of servers does not change, if ordinary hash is used and then The method of taking the modulus of the total number of servers (such as key% the total number of servers), if a server goes down during the period or needs to add servers, problems will arise. After hashing the same key, the result modulo the total number of servers will be different from the previous result, which results in the loss of previously saved data. Therefore, the Consistent Hash (Consistent Hashing) distribution algorithm is introduced
Use the hash function (such as md5, sha1) to map the data to a ring, as shown in the figure above shows that when the data is stored, first calculate the hash value of the key according to the hash algorithm, which corresponds to the position in the ring. For example, k1 corresponds to the same position as shown in the figure. Then find the server node B in the clockwise direction, and then put k1 Save it to node B.
If node B goes down, the data on B will fall to node C, as shown in the figure below
In order to solve this problem, the concept of "virtual node" is introduced: that is, imagine that there are many "virtual nodes" on the ring. A real server node corresponds to multiple virtual nodes. When storing data, If you find the virtual node in the clockwise direction of the ring, you will find the corresponding real server node. As shown in the figure below
PHP implementation of consistent hash algorithm
An interface is given belowThis interface defines 4 respectively Methods, cHash (process strings into hash values), addServer (add a server), removeServer (remove a server), lookup (find a server to store data) /**
* 一致性哈希实现接口
* Interface ConsistentHash
*/
interface ConsistentHash
{
//将字符串转为hash值
public function cHash($str);
//添加一台服务器到服务器列表中
public function addServer($server);
//从服务器删除一台服务器
public function removeServer($server);
//在当前的服务器列表中找到合适的服务器存放数据
public function lookup($key);
}Copy after login
are given below A specific implementation of this interface
/**
* 具体一致性哈希实现
* author chenqionghe
* Class MyConsistentHash
*/
class MyConsistentHash implements ConsistentHash
{
public $serverList = array(); //服务器列列表
public $virtualPos = array(); //虚拟节点的位置
public $virtualPosNum = 5; //每个节点对应5个虚节点
/**
* 将字符串转换成32位无符号整数hash值
* @param $str
* @return int
*/
public function cHash($str)
{
$str = md5($str);
return sprintf('%u', crc32($str));
}
/**
* 在当前的服务器列表中找到合适的服务器存放数据
* @param $key 键名
* @return mixed 返回服务器IP地址
*/
public function lookup($key)
{
$point = $this->cHash($key);//落点的hash值
$finalServer = current($this->virtualPos);//先取圆环上最小的一个节点当成结果
foreach($this->virtualPos as $pos=>$server)
{
if($point <= $pos)
{
$finalServer = $server;
break;
}
}
reset($this->virtualPos);//重置圆环的指针为第一个
return $finalServer;
}
/**
* 添加一台服务器到服务器列表中
* @param $server 服务器IP地址
* @return bool
*/
public function addServer($server)
{
if(!isset($this->serverList[$server]))
{
for($i=0; $i<$this->virtualPosNum; $i++)
{
$pos = $this->cHash($server . '-' . $i);
$this->virtualPos[$pos] = $server;
$this->serverList[$server][] = $pos;
}
ksort($this->virtualPos,SORT_NUMERIC);
}
return TRUE;
}
/**
* 移除一台服务器（循环所有的虚节点，删除值为该服务器地址的虚节点）
* @param $key
* @return bool
*/
public function removeServer($key)
{
if(isset($this->serverList[$key]))
{
//删除对应虚节点
foreach($this->serverList[$key] as $pos)
{
unset($this->virtualPos[$pos]);
}
//删除对应服务器
unset($this->serverList[$key]);
}
return TRUE;
}
}Then, let’s test the algorithm
$hashServer = new MyConsistentHash();
$hashServer->addServer('192.168.1.1');
$hashServer->addServer('192.168.1.2');
$hashServer->addServer('192.168.1.3');
$hashServer->addServer('192.168.1.4');
$hashServer->addServer('192.168.1.5');
$hashServer->addServer('192.168.1.6');
$hashServer->addServer('192.168.1.7');
$hashServer->addServer('192.168.1.8');
$hashServer->addServer('192.168.1.9');
$hashServer->addServer('192.168.1.10');
echo "增加十台服务器192.168.1.1~192.168.1.10<br />";
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '<br />';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '<br />';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '<br />';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '<br />';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '<br />';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '<br />';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '<br />';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '<br />';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '<br />';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '<br />';
echo '<hr />';
echo "移除一台服务器192.168.1.2<br />";
$hashServer->removeServer('192.168.1.2');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '<br />';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '<br />';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '<br />';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '<br />';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '<br />';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '<br />';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '<br />';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '<br />';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '<br />';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '<br />';
echo '<hr />';
echo "移除一台服务器192.168.1.6<br />";
$hashServer->removeServer('192.168.1.6');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '<br />';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '<br />';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '<br />';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '<br />';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '<br />';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '<br />';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '<br />';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '<br />';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '<br />';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '<br />';
echo '<hr />';
echo "移除一台服务器192.168.1.8<br />";
$hashServer->removeServer('192.168.1.8');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '<br />';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '<br />';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '<br />';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '<br />';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '<br />';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '<br />';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '<br />';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '<br />';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '<br />';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '<br />';
echo '<hr />';
echo "移除一台服务器192.168.1.2<br />";
$hashServer->removeServer('192.168.1.2');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '<br />';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '<br />';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '<br />';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '<br />';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '<br />';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '<br />';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '<br />';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '<br />';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '<br />';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '<br />';
echo '<hr />';
echo "增加一台服务器192.168.1.11<br />";
$hashServer->addServer('192.168.1.11');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '<br />';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '<br />';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '<br />';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '<br />';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '<br />';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '<br />';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '<br />';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '<br />';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '<br />';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '<br />';
echo '<hr />';The running results are as follows
Add ten servers 192.168.1.1~192.168.1.10
Save key1 to server:192.168.1.2
Save key2 to server:192.168.1.1
Save key3 to server:192.168.1.6
Save key4 to server:192.168.1.8
Save key5 to server:192.168.1.9
Save key6 to server:192.168.1.10
Save key7 to server:192.168.1.7
Save key8 to server:192.168.1.4
Save key9 to server:192.168.1.7
Save key10 to server:192.168.1.4
Remove a server 192.168.1.2
Save key1 to server:192.168.1.7
Save key2 to server:192.168.1.1
Save key3 to server:192.168.1.6
Save key4 to server:192.168.1.8
Save key5 to server:192.168.1.9
Save key6 to server :192.168.1.10
Save key7 to server:192.168.1.7
Save key8 to server:192.168.1.4
Save key9 to server:192.168.1.7
Save key10 to server:192.168.1.4
Remove a server 192.168.1.6
Save key1 to server:192.168.1.7
Save key2 to server:192.168.1.1
Save key3 to server:192.168.1.3
Save key4 to server: 192.168.1.8
Save key5 to server:192.168.1.9
Save key6 to server:192.168.1.10
Save key7 to server:192.168.1.7
Save key8 to server:192.168.1.4
Save key9 to server:192.168.1.7
Save key10 to server:192.168.1.4
Remove a server 192.168.1.8
Save key1 to server:192.168.1.7
Save key2 to server:192.168 .1.1
Save key3 to server:192.168.1.3
Save key4 to server:192.168.1.10
Save key5 to server:192.168.1.9
Save key6 to server:192.168.1.10
Save key7 to server:192.168.1.7
Save key8 to server:192.168.1.4
Save key9 to server:192.168.1.7
Save key10 to server:192.168.1.4
Remove a server 192.168. 1.2
Save key1 to server:192.168.1.7
Save key2 to server:192.168.1.1
Save key3 to server:192.168.1.3
Save key4 to server:192.168.1.10
Save key5 To server:192.168.1.9
Save key6 to server:192.168.1.10
Save key7 to server:192.168.1.7
Save key8 to server:192.168.1.4
Save key9 to server:192.168.1.7
Save key10 to server:192.168.1.4
Add a server 192.168.1.11
Save key1 to server:192.168.1.7
Save key2 to server:192.168.1.1
Save key3 to server :192.168.1.11
Save key4 to server:192.168.1.10
Save key5 to server:192.168.1.9
Save key6 to server:192.168.1.10
Save key7 to server:192.168.1.7
Save key8 to server:192.168.1.4
Save key9 to server:192.168.1.7
Save key10 to server:192.168.1.4
Yes, you can see that consistent hashing is used Finally, regardless of whether to add servers or reduce servers, the integrity and uniformity of the data are guaranteed to the greatest extent.
I believe you have mastered the method after reading the case in this article. For more exciting information, please pay attention to other php Chinese websites. related articles!
Recommended reading:
thinkPHP framework automatic filling principle and usage detailed explanation
PHP decorator mode usage detailed explanation
The above is the detailed content of Detailed explanation of steps to implement consistent Hash algorithm in PHP. For more information, please follow other related articles on the PHP Chinese website!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
