PHP에서 일관된 해시 알고리즘을 구현하는 단계에 대한 자세한 설명

이번에는 PHP에서 일관된 해시 알고리즘을 구현하는 단계에 대해 자세히 설명하겠습니다. PHP에서 일관된 해시 알고리즘을 구현하는 데 필요한 주의사항은 무엇인가요?

일관적인 해싱 알고리즘은 분산 시스템에서 일반적으로 사용되는 알고리즘입니다. 왜 이 알고리즘을 사용해야 합니까? 예를 들어 분산 스토리지 시스템은 특정 노드(서버)에 데이터를 저장해야 합니다. 서버 수가 변경되지 않는 경우 일반 해시 방법을 사용하여 총 서버 수를 모듈로 계산하는 경우(예: key%) 총 서버 수), 해당 기간 동안 서버가 다운되거나 서버를 추가해야 하는 경우 문제가 발생합니다. 동일한 키를 해싱한 후 총 서버 수를 모듈로 계산한 결과는 이전 결과와 달라지며, 이로 인해 이전에 저장된 데이터가 손실됩니다. 그래서 컨시스턴트 해싱(Condependent Hash) 분포 알고리즘이 도입되었습니다

위 그림과 같이 데이터가 해시 함수(예: md5, sha1)를 사용하여 링에 매핑되어 데이터가 저장되면, 먼저 해시에 따라 저장됩니다. 알고리즘은 키의 해시 값을 계산하여 링의 위치에 해당합니다. 예를 들어 k1의 위치는 해당 그림에 표시된 것과 동일합니다. 그런 다음 서버 노드 B를 찾습니다. 시계 방향으로 이동한 다음 k1을 노드 B에 저장합니다.

노드 B가 다운되면 아래 그림과 같이 B의 데이터는 노드 C로 떨어지게 됩니다.

이런 식으로 노드 C에만 영향을 미치고 노드의 데이터에는 아무런 손상도 입히지 않습니다. 다른 노드 A와 D. 영향. 그러나 여기서 문제가 발생합니다. 이로 인해 C 노드가 B 노드의 데이터를 보유하므로 C 노드는 가동 중지 시간이 발생하여 고르지 못한 분포가 발생합니다.

이 문제를 해결하기 위해 "가상 노드"라는 개념이 도입되었습니다. 즉, 실제 서버 노드는 여러 가상 노드에 해당합니다. 링을 따라 시계방향으로 저장됩니다. 해당 방향에서 가상 노드를 찾으면 해당 실제 서버 노드를 찾을 수 있습니다. 아래 그림과 같이

A1, A2, B1, B2, C1, C2, D1, D2는 모두 가상 노드입니다. 머신 A는 A1과 A2의 데이터를 로드하고 머신 B는 B1의 데이터를 로드합니다. B2는 C1과 C2의 데이터를 로드하고 저장합니다. 이러한 가상 노드는 수가 많고 균등하게 분산되어 있으므로 "눈사태" 현상이 발생하지 않습니다.

일관된 해시 알고리즘의 PHP 구현

인터페이스는 아래와 같습니다

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

이 인터페이스는 각각 cHash(문자열을 해시 값으로 처리), addServer(서버 추가), addServer(서버 추가)의 4가지 메소드를 정의합니다. server), 조회(데이터를 저장할 서버 찾기)

다음은 이 인터페이스의 구체적인 구현입니다

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

그럼 알고리즘을 테스트해 보겠습니다

$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 />';

실행 결과는 다음과 같습니다

서버 10개 추가 192.168.1.1~192.168.1.10
키1을 서버에 저장:192.168.1.2
키2를 서버에 저장:192.168.1.1
키3을 서버에 저장:192.168.1.6
키4를 서버에 저장:192.168.1 .8
key5를 서버에 저장:192.168.1.9
key6을 서버에 저장:192.168.1.10
key7을 서버에 저장:192.168.1.7
key8을 서버에 저장:192.168.1.4
key9를 서버에 저장:192.168.1.7
key10을 서버에 저장 : 192.168.1.4 1 서버 제거 192.168.1.2
key1을 서버에 저장: 192.168.1.7
key2를 서버에 저장: 192.168.1.1
Key3을 서버에 저장: 192.168.1.6
KEY4를 서버에 저장: 192.168.1.8

저장 key5를 서버에 저장:192.168.1.9
key6을 서버에 저장:192.168.1.10
key7을 서버에 저장:192.168.1.7
key8을 서버에 저장:192.168.1.4
key9를 서버에 저장:192.168.1.7
key10을 서버에 저장:192.1 68 .1.4
서버 제거 192.168.1.6
키1을 서버에 저장:192.168.1.7
키2를 서버에 저장:192.168.1.1
키3을 서버에 저장:192.168.1.3
키4를 서버에 저장:192.168.1.8
저장 키5 서버:192.168.1.9
키6을 서버에 저장:192.168.1.10
키7을 서버에 저장:192.168.1.7
키8을 서버:192.168.1.4에 저장
키9를 서버에 저장:192.168.1.7
키10을 서버:192.168에 저장 1.4
서버 192.168.1.8 제거
키1을 서버에 저장:192.168.1.7
키2를 서버에 저장:192.168.1.1
키3을 서버에 저장:192.168.1.3
키4를 서버에 저장:192.168.1.10
키5를 서버에 저장:1 92.168 .1.9aveSave Key6 to Server : 192.168.1.10 key7 to Server : 192.168.1.7
Save key8 to Server : 192.168.1.4 key9 to Server : 192.168.1.7 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
key6을 서버에 저장:192.168.1.10
key7을 서버에 저장:192.168.1.7
key8을 서버에 저장:192.168.1.4
key9를 서버에 저장:192.168.1.7
key10을 서버에 저장:192.168.1 4
추가 서버 192.168.1.11
키1을 서버에 저장:192.168.1.7
키2를 서버에 저장:192.168.1.1
키3을 서버에 저장:192.168.1.11
키4를 서버에 저장:192.168.1.10
키5를 서버에 저장:192.16 8 . 1.9
key6을 서버에 저장:192.168.1.10
key7을 서버에 저장:192.168.1.7
key8을 서버에 저장:192.168.1.4
key9를 서버에 저장:192.168.1.7
key10을 서버에 저장:192.168.1.4


예 , 일관된 해싱을 사용하면 서버를 추가하든, 서버를 줄이든 관계없이 데이터의 무결성과 균일성이 최대한 보장된다는 것을 알 수 있습니다.

이 글의 사례를 읽으신 후 이 방법을 마스터하셨으리라 믿습니다. , 그리고 더 흥미로운 내용이 있을 예정이니 PHP 중국어 웹사이트의 다른 관련 기사도 주목해 주세요!

추천 도서:

thinkPHP 프레임워크 자동 채우기의 원리와 사용법에 대한 자세한 설명

PHP 데코레이터 모드 사용에 대한 자세한 설명

위 내용은 PHP에서 일관된 해시 알고리즘을 구현하는 단계에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!