Detailed explanation of steps to implement consistent Hash algorithm in PHP

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

This will only affect Node C will not affect the data of other nodes A and D. But here comes the problem. This will cause the C node to be overloaded. Because the C node bears the data of the B node, the C node is prone to downtime, which causes uneven distribution.

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

A1, A2, B1, B2, C1, C2, D1, and D2 in the figure are all virtual nodes. Machine A loads the data of A1 and A2. Machine B loads the data of B1 and B2, and machine C loads the data of C1 and C2. Since these virtual nodes are large in number and evenly distributed, they will not cause an "avalanche" phenomenon.

PHP implementation of consistent hash algorithm

An interface is given below

/**
 * 一致性哈希实现接口
 * Interface ConsistentHash
 */
interface ConsistentHash
{
 //将字符串转为hash值
 public function cHash($str);
 //添加一台服务器到服务器列表中
 public function addServer($server);
 //从服务器删除一台服务器
 public function removeServer($server);
 //在当前的服务器列表中找到合适的服务器存放数据
 public function lookup($key);
}

This 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)

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
";
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '
';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '
';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '
';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '
';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '
';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '
';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '
';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '
';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '
';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '
';
echo '
';
echo "移除一台服务器192.168.1.2
";
$hashServer->removeServer('192.168.1.2');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '
';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '
';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '
';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '
';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '
';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '
';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '
';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '
';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '
';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '
';
echo '
';
echo "移除一台服务器192.168.1.6
";
$hashServer->removeServer('192.168.1.6');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '
';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '
';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '
';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '
';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '
';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '
';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '
';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '
';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '
';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '
';
echo '
';
echo "移除一台服务器192.168.1.8
";
$hashServer->removeServer('192.168.1.8');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '
';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '
';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '
';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '
';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '
';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '
';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '
';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '
';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '
';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '
';
echo '
';
echo "移除一台服务器192.168.1.2
";
$hashServer->removeServer('192.168.1.2');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '
';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '
';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '
';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '
';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '
';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '
';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '
';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '
';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '
';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '
';
echo '
';
echo "增加一台服务器192.168.1.11
";
$hashServer->addServer('192.168.1.11');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '
';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '
';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '
';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '
';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '
';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '
';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '
';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '
';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '
';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '
';
echo '
';

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!