PHP 구현 의 일치 성 Hash 알고리즘 상세 설명[분산 알고리즘]
일치 성 해시 알고리즘 은 분포 식 시스템 에서 자주 사용 하 는 알고리즘 인 데 왜 이 알고리즘 을 사용 합 니까?
예 를 들 어 분포 식 저장 시스템 은 데 이 터 를 구체 적 인 노드(서버)에 저장 해 야 한다.서버 수량 이 변 하지 않 는 상황 에서 일반적인 hash 를 사용 하여 서버 총 수량 을 모델 링 하 는 방법(예 를 들 어 key%서버 총 수량)을 사용 하면 그 동안 서버 가 다운 되 거나 서버 를 늘 려 야 한다 면 문제 가 발생 한다.같은 key 가 hash 를 거 친 후에 서버 의 총 수량 과 모델 링 결 과 는 이전 결과 와 다 르 기 때문에 이전에 저 장 된 데 이 터 를 잃 어 버 렸 습 니 다.따라서 일치 성 Hash(Consistent Hashing)분포 알고리즘 을 도입 했다.
데 이 터 를 hash 함수(예 를 들 어 md5,sha 1)로 원 링 에 투사 합 니 다.위의 그림 에서 보 듯 이 데 이 터 를 저장 할 때 hash 알고리즘 에 따라 key 의 hash 값 을 계산 하고 이 링 의 위치 에 대응 합 니 다.예 를 들 어 k1 대응 그림 에서 보 여 준 위치 가 같 습 니 다.그리고 시계 방향 으로 서버 노드 B 를 찾 은 다음 에 k1 을 B 노드 에 저장 합 니 다.
만약 에 B 노드 가 지연 되면 B 의 데 이 터 는 C 노드 에 떨 어 질 것 이다.아래 그림 과 같다.
이렇게 하면 C 노드 에 만 영향 을 주 고 다른 노드 A,D 의 데이터 에 영향 을 주지 않 는 다.그러나 문제 가 생 겼 다.그러면 C 노드 의 부하 가 너무 무 거 운 상황 을 초래 할 수 있다.C 노드 가 B 노드 의 데 이 터 를 부담 하기 때문에 C 노드 가 쉽게 지연 되 고 분포 가 고 르 지 않다.
이 문 제 를 해결 하기 위해'가상 노드'라 는 개념 을 도입 했다.즉,빈 고리 에'가상 노드'가 많다 고 상상 하고 진실 한 서버 노드 는 여러 개의 가상 노드 에 대응 하 며 데 이 터 를 저장 할 때 링 의 시계 방향 을 따라 가상 노드 를 찾 으 면 해당 하 는 실제 서버 노드 를 찾 을 수 있다.아래 그림
그림 속 A1,A2,B1,B2,C1,C2,D1,D2 는 모두 가상 노드 이 고 기계 A 는 A1,A2 의 데 이 터 를 부하 로 저장 하 며 기계 B 는 B1,B2 의 데 이 터 를 부하 로 저장 하고 기계 C 는 C1,C2 의 데 이 터 를 부하 로 저장한다.이러한 가상 노드 의 수량 이 매우 많 고 고 르 게 분포 하기 때문에'눈사태'현상 을 일 으 키 지 않 을 것 이다.
일치 성 해시 알고리즘 PHP 구현
다음은 인 터 페 이 스 를 드 리 겠 습 니 다.
/**
*
* Interface ConsistentHash
*/
interface ConsistentHash
{
// hash
public function cHash($str);
//
public function addServer($server);
//
public function removeServer($server);
//
public function lookup($key);
}
다음은 이 인터페이스의 구체 적 인 실현 을 제시 합 니 다.
/**
*
* 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 을 server 에 저장 하기:192.168.1.2
키 2 를 server 에 저장 하기:192.168.1.1
key 3 를 server 에 저장 하기:192.168.1.6
키 4 를 server 에 저장 하기:192.168.1.8
키 5 를 server 에 저장 하기:192.168.1.9
키 6 을 server 에 저장 하기:192.168.1.10
키 7 을 server 에 저장 하기:192.168.1.7
키 8 을 server 에 저장 하기:192.168.1.4
server 에 key 9 저장 하기:192.168.1.7
key 10 을 server 에 저장:192.168.1.4
서버 192.168.1.2 제거
키 1 을 server 에 저장 하기:192.168.1.7
키 2 를 server 에 저장 하기:192.168.1.1
key 3 를 server 에 저장 하기:192.168.1.6
키 4 를 server 에 저장 하기:192.168.1.8
키 5 를 server 에 저장 하기:192.168.1.9
키 6 을 server 에 저장 하기:192.168.1.10
키 7 을 server 에 저장 하기:192.168.1.7
키 8 을 server 에 저장 하기:192.168.1.4
server 에 key 9 저장 하기:192.168.1.7
key 10 을 server 에 저장:192.168.1.4
서버 192.168.1.6 제거
키 1 을 server 에 저장 하기:192.168.1.7
키 2 를 server 에 저장 하기:192.168.1.1
server 에 key 3 저장:192.168.1.3
키 4 를 server 에 저장 하기:192.168.1.8
키 5 를 server 에 저장 하기:192.168.1.9
키 6 을 server 에 저장 하기:192.168.1.10
키 7 을 server 에 저장 하기:192.168.1.7
키 8 을 server 에 저장 하기:192.168.1.4
server 에 key 9 저장 하기:192.168.1.7
key 10 을 server 에 저장:192.168.1.4
서버 192.168.1.8 제거
키 1 을 server 에 저장 하기:192.168.1.7
키 2 를 server 에 저장 하기:192.168.1.1
server 에 key 3 저장:192.168.1.3
키 4 를 server 에 저장 하기:192.168.1.10
키 5 를 server 에 저장 하기:192.168.1.9
키 6 을 server 에 저장 하기:192.168.1.10
키 7 을 server 에 저장 하기:192.168.1.7
키 8 을 server 에 저장 하기:192.168.1.4
server 에 key 9 저장 하기:192.168.1.7
key 10 을 server 에 저장:192.168.1.4
서버 192.168.1.2 제거
키 1 을 server 에 저장 하기:192.168.1.7
키 2 를 server 에 저장 하기:192.168.1.1
server 에 key 3 저장:192.168.1.3
키 4 를 server 에 저장 하기:192.168.1.10
키 5 를 server 에 저장 하기:192.168.1.9
키 6 을 server 에 저장 하기:192.168.1.10
키 7 을 server 에 저장 하기:192.168.1.7
키 8 을 server 에 저장 하기:192.168.1.4
server 에 key 9 저장 하기:192.168.1.7
key 10 을 server 에 저장:192.168.1.4
서버 한 대 추가 192.168.11
키 1 을 server 에 저장 하기:192.168.1.7
키 2 를 server 에 저장 하기:192.168.1.1
server 에 key 3 저장:192.168.11
키 4 를 server 에 저장 하기:192.168.1.10
키 5 를 server 에 저장 하기:192.168.1.9
키 6 을 server 에 저장 하기:192.168.1.10
키 7 을 server 에 저장 하기:192.168.1.7
키 8 을 server 에 저장 하기:192.168.1.4
server 에 key 9 저장 하기:192.168.1.7
key 10 을 server 에 저장:192.168.1.4
이 를 통 해 알 수 있 듯 이 일치 성 하 시 를 사용 한 후에 서버 를 증가 시 키 는 지 서버 를 감소 시 키 는 지 데이터 의 완전 성,균일 성 을 최대한 확보 했다.
PS:여기 서 hash 관련 온라인 도 구 를 2 가지 더 제공 하여 참고 하 시기 바 랍 니 다.
온라인 해시/해시 알고리즘 암호 화 도구:
http://tools.jb51.net/password/hash_encrypt
온라인 MD5/hash/SHA-1/SHA-2/SHA-256/SHA-512/SHA-3/RIPEMD-160 암호 화 도구:
http://tools.jb51.net/password/hash_md5_sha
더 많은 PHP 관련 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있다.
본 논문 에서 말 한 것 이 여러분 의 PHP 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
laravel에 yo에서 angularJs&coffeescript를 사용할 수 있도록 한다.먼저 yo 명령을 사용할 수 있어야하므로 아래에서 설치 global에 설치한 곳에서 laravel의 프로젝트 루트로 이동. 클라이언트 코드를 관리하는 디렉토리를 만들고 이동합니다. 클라이언트 환경 만들기 이것으로 히...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
