Explication détaillée des étapes pour implémenter un algorithme de hachage cohérent en PHP-tutoriel php-php.cn

Cette fois, je vais vous apporter une explication détaillée des étapes pour implémenter l'algorithme de hachage cohérent en PHP. Quelles sont les précautions pour implémenter l'algorithme de hachage cohérent en PHP. Voici un cas pratique, voyons. jetez un oeil.

L'algorithme de hachage cohérent est un algorithme couramment utilisé dans les systèmes distribués. Pourquoi cet algorithme devrait-il être utilisé ? Par exemple : un système de stockage distribué doit stocker des données sur des nœuds spécifiques (serveurs) Si le nombre de serveurs ne change pas, si un hachage ordinaire est utilisé, puis la méthode de prise. le module du nombre total de serveurs (comme la clé% du nombre total de serveurs), si un serveur tombe en panne pendant la période ou doit ajouter des serveurs, des problèmes surviendront. Après avoir haché la même clé, le résultat modulo le nombre total de serveurs sera différent du résultat précédent, ce qui entraîne la perte des données précédemment sauvegardées. Par conséquent, l'algorithme de distribution Consistent Hash (Consistent Hashing) est introduit

pour mapper les données sur un anneau à l'aide d'une fonction de hachage (telle que md5, sha1), comme indiqué dans la figure ci-dessus montre que lorsque les données sont stockées, calculez d'abord la valeur de hachage de la clé selon l'algorithme de hachage, correspondant à la position dans l'anneau, telle que k1 correspondant à la même position comme indiqué sur la figure, puis recherchez le serveur nœud B dans le sens des aiguilles d'une montre, puis k1 Enregistrez-le sur le nœud B.

Si le nœud B est en panne, les données sur B tomberont sur le nœud C, comme le montre la figure ci-dessous

De cette façon, il ne fera que affecter le nœud C n’affectera pas les données des autres nœuds A et D. Mais voici le problème : cela entraînera une surcharge du nœud C. Étant donné que le nœud C contient les données du nœud B, le nœud C est sujet à des temps d'arrêt, ce qui entraîne une distribution inégale.

Afin de résoudre ce problème, le concept de « nœud virtuel » est introduit : c'est-à-dire imaginez qu'il y ait de nombreux « nœuds virtuels » sur l'anneau. Un nœud de serveur réel correspond à plusieurs nœuds virtuels. les données sont stockées, elles se trouvent le long de l'anneau. Si vous trouvez le nœud virtuel dans le sens des aiguilles d'une montre, vous trouverez le nœud de serveur réel correspondant. Comme le montre la figure ci-dessous

A1, A2, B1, B2, C1, C2, D1 et D2 dans la figure sont tous des nœuds virtuels. La machine A charge les données. de A1 et A2. La machine B charge les données de B1 et B2, et la machine C charge les données de C1 et C2. Ces nœuds virtuels étant nombreux et uniformément répartis, ils ne provoqueront pas de phénomène « d’avalanche ».

Implémentation PHP d'un algorithme de hachage cohérent

Une interface est donnée ci-dessous

Cette interface est définie séparément Là il y a 4 méthodes, cHash (traiter les chaînes en valeurs de hachage), addServer (ajouter un serveur), removeServer (supprimer un serveur), lookup (trouver un serveur pour stocker des données)

ci-dessous Donnez une implémentation spécifique de cette interface

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

Copier après la connexion

Ensuite, testons l'algorithme

/**
 * 具体一致性哈希实现
 * 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;
 }
}

Copier après la connexion

Les résultats d'exécution sont les suivants

Ajouter dix serveurs 192.168.1.1~192.168.1.10
Enregistrer la clé 1 sur le serveur : 192.168.1.2
Enregistrer la clé 2 sur le serveur : 192.168.1.1
Enregistrer la clé 3 sur le serveur : 192.168.1.6
Enregistrer la clé4 sur le serveur :192.168.1.8
Enregistrer la clé5 sur le serveur :192.168.1.9
Enregistrer la clé6 sur le serveur :192.168.1.10
Enregistrer la clé7 sur le serveur :192.168.1.7
Enregistrer la clé8 sur le serveur :192.168.1.4
Enregistrer la clé9 sur le serveur :192.168.1.7
Enregistrer la clé10 sur le serveur :192.168.1.4
Supprimer un serveur 192.168.1.2
Enregistrer la clé1 sur le serveur :192.168.1.7
Enregistrer key2 sur le serveur :192.168.1.1
Enregistrez la clé3 sur le serveur :192.168.1.6
Enregistrez la clé4 sur le serveur :192.168.1.8
Enregistrez la clé5 sur le serveur :192.168.1.9
Enregistrez la clé6 sur le serveur :192.168. 1.10
Enregistrer la clé7 sur le serveur :192.168.1.7
Enregistrer la clé8 sur le serveur :192.168.1.4
Enregistrer la clé9 sur le serveur :192.168.1.7
Enregistrer la clé10 sur le serveur :192.168.1.4
Supprimer un serveur 192.168.1.6
Enregistrer la clé1 sur le serveur :192.168.1.7
Enregistrer la clé2 sur le serveur :192.168.1.1
Enregistrer la clé3 sur le serveur :192.168.1.3
Enregistrer la clé4 sur le serveur : 192.168.1.8
Enregistrer la clé5 sur le serveur :192.168.1.9
Enregistrer la clé6 sur le serveur :192.168.1.10
Enregistrer la clé7 sur le serveur :192.168.1.7
Enregistrer la clé8 sur le serveur :192.168.1.4
Enregistrer la clé9 sur le serveur : 192.168.1.7
Enregistrer la clé10 sur le serveur :192.168.1.4
Supprimer un serveur 192.168.1.8
Enregistrer la clé1 sur le serveur :192.168.1.7
Enregistrer la clé2 sur le serveur :192.168 .1.1
Enregistrer la clé3 sur le serveur :192.168.1.3
Enregistrer la clé4 sur le serveur :192.168.1.10
Enregistrer la clé5 sur le serveur :192.168.1.9
Enregistrer la clé6 sur le serveur :192.168.1.10
Enregistrer la clé7 sur le serveur :192.168.1.7
Enregistrer la clé8 sur le serveur :192.168.1.4
Enregistrer la clé9 sur le serveur :192.168.1.7
Enregistrer la clé10 sur le serveur :192.168.1.4
Supprimer un serveur 192.168 1.2
Enregistrer la clé1 sur le serveur : 192.168.1.7
Enregistrer la clé2 sur le serveur :192.168.1.1
Enregistrer la clé3 sur le serveur :192.168.1.3
Enregistrer la clé4 sur le serveur :192.168.1.10
Enregistrer la clé5 sur le serveur :192.168.1.9
Enregistrez la clé 6 sur le serveur : 192.168.1.10
Enregistrez la clé 7 sur le serveur : 192.168.1.7
Enregistrez la clé 8 sur le serveur : 192.168.1.4
Enregistrez la clé 9 sur le serveur : 192.168.1.7
Enregistrez la clé 10 sur le serveur : 192.168 .1.4
Ajouter un serveur 192.168.1.11
Enregistrer la clé1 sur le serveur :192.168.1.7
Enregistrer la clé2 sur le serveur :192.168.1.1
Enregistrer la clé3 sur le serveur :192.168.1.11
Enregistrer la clé4 sur serveur:192.168.1.10
Enregistrer la clé5 sur le serveur:192.168.1.9
Enregistrer la clé6 sur le serveur:192.168.1.10
Enregistrer la clé7 sur le serveur:192.168.1.7
Enregistrer la clé8 sur le serveur:192.168.1.4
Enregistrer la clé9 sur le serveur :192.168.1.7
Enregistrer la clé10 sur le serveur :192.168.1.4

Oui, vous pouvez voir qu'un hachage cohérent est utilisé. Enfin, qu'il s'agisse d'ajouter des serveurs ou de réduire serveurs, l'intégrité et l'uniformité des données sont garanties dans la plus grande mesure

Je pense que vous maîtrisez la méthode après avoir lu le cas dans cet article. Pour des informations plus intéressantes, veuillez faire attention aux autres sites Web chinois php. .Articles connexes!

Lecture recommandée :

Explication détaillée des principes et de l'utilisation du remplissage automatique du framework thinkPHP

Explication détaillée de l'utilisation du décorateur PHP mode

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!