일관된 해싱 - PHP

/**
 * Flexihash - PHP를 위한 간단하고 일관된 해싱 구현입니다.
 * 
 * MIT 라이선스
 * 
 * Copyright (c) 2008 Paul Annesley
 * 
 * 권한은 다음과 같습니다. 이에 따라 이 소프트웨어 및 관련 문서 파일(이하 "소프트웨어")의 사본
 *을 취득한 모든 사람에게
* 권리를 포함하되 이에 국한되지 않고 제한 없이 소프트웨어를 처리할 수 있는
 * 권한이 무료로 부여됩니다
 * 소프트웨어 사본을 사용, 복사, 수정, 병합, 게시, 배포, 재라이센스 부여 및/또는 판매
 *하고, 소프트웨어를 제공받은 사람에게
 * 그렇게 하도록 허용합니다. 다음 조건:
 * 
 * 위의 저작권 고지 및 본 허가 고지는
 * 소프트웨어의 모든 사본 또는 상당 부분에 포함됩니다.
 * 
 * 소프트웨어가 제공됩니다. " 있는 그대로", 어떠한 종류의 명시적 또는 묵시적 보증도 없이
 * 상품성,
 * 특정 목적에의 적합성 및 비침해에 대한 보증을 포함하되 이에 국한되지 않습니다. 어떠한 경우에도
 * 작성자 또는 저작권 보유자는 모든 청구, 손해 또는 기타
 * 법적 책임(계약, 불법 행위 또는 기타 행위로 인해 발생함)에 대해 책임을 지지 않습니다.
 * 소프트웨어와의 연결,
 * 소프트웨어의 사용 또는 기타 거래.
 * 
 * @author Paul Annesley
 * @link http://paul.annesley.cc/
 * @copyright Paul Annesley, 2008
 * MyZ의 @댓글(http://blog.csdn.net/mayongzhan)
 */
/**
 * 플러그형 해시 알고리즘을 사용한 간단하고 일관된 해싱 구현.
 *
 * @author Paul Annesley
 * @package Flexihash
 * @licence http://www.opensource.org/licenses /mit-license.php
 */
class Flexihash
{
/**
* 각 대상을 해시할 위치 수.
*
* @var int
* @comment 불균등한 노드 분포 문제를 해결하기 위한 가상 노드 수
*/
private $_replicas = 64;
/**
* Flexihash_Hasher 구현에 캡슐화된 해시 알고리즘.
* @var object Flexihash_Hasher
* @comment 使用的hash방법 : md5,crc32
*/
private $_hasher;
/**
* 현재 대상 수에 대한 내부 카운터.
* @var int
* @comment 노드 카운터
*/
private $_targetCount = 0;
/ **
* 대상에 대한 위치(해시 출력)의 내부 맵
* @var array { position => target, ... }
* @comment 위치 해당 노드, 조회 위치를 기반으로 대상을 결정하는 데 사용됨 방문한 노드
*/
비공개 $_positionToTarget = array();
/**
* 대상이 해시된 위치 목록에 대한 대상의 내부 맵.
* @var array { target => [ position, position, ... ], ... }
* @comment The 노드를 삭제하는 데 사용되는 노드의 해당 위치
*/
비공개 $_targetToPositions = array();
/**
* 위치-대상 내부 맵이 이미 정렬되어 있는지 여부
* @var boolean
* @comment 위치-대상 내부 맵이 이미 정렬되어 있는지 여부
* /
private $_positionToTargetSorted = false;
/**
* 생성자
* @param object $hasher Flexihash_Hasher
* @param int $replicas 각 대상을 해시할 위치의 양.
* @comment 생성자, 사용할 해시 방법과 요구 사항 가상 노드 수 가상 노드가 많을수록 배포가 더 균일해지지만 프로그램의 배포 작업이 느려집니다.
*/
public 함수 __construct(Flexihash_Hasher $hasher = null, $replicas = null)
{
$this-> ;_hasher = $해셔 ? $hasher: new Flexihash_Crc32Hasher();
if (!empty($replicas)) $this->_replicas = $replicas;
}
/**
* 타겟을 추가합니다.
* @param string $target
* @chainable
* @comment 노드를 추가하고 가상 노드 수에 따라 노드를 여러 가상 위치에 배포합니다
*/
공개 함수 addTarget($target)
{
if (isset($this->_targetToPositions[$target]))
{throw new Flexihash_Exception
("Target '$ target'이 이미 존재합니다.");
}
$this->_targetToPositions[$target] = array();
// 대상을 여러 위치로 해시
for ($i = 0 ; $i < $this->_replicas; $i++)
{
$position = $this->_hasher->hash($target . $i);
$this-> ;_positionToTarget[$position] = $target; // 조회
$this->_targetToPositions[$target] []= $position; // 대상 제거
}
$this->_positionToTargetSorted = false;
$this->_targetCount++;
return $this;
}
/**
* 대상 목록을 추가합니다.
* @param array $targets
* @chainable
*/
공용 함수 addTargets($targets)
{
foreach($targets를 $target으로)
{
$this->addTarget($target);
}
$this를 반환합니다.}
/**
* 대상을 제거합니다.
* @param string $target
* @chainable
*/
공용 함수 RemoveTarget($target)
{
if (!isset($this->_targetToPositions[$target]))
{
새 Flexihash 발생_예외("'$target' 대상이 존재하지 않습니다.");
}
foreach ($this->_targetToPositions[$target] as $position)
{
unset($this->_positionToTarget[$position]);
}
unset($this->_targetToPositions[$target]);
$this->_targetCount --;
return $this;
}
/**
* 모든 잠재적 대상 목록
* @return array
*/
공용 함수 getAllTargets()
{
return array_keys($this->_targetToPositions) ;
}
/**
* 주어진 리소스에 대한 대상을 조회합니다.
* @param string $resource
* @return string
*/
공개 함수 조회($resource)
{
$targets = $this->lookupList($resource, 1);
if (empty($targets)) throw new Flexihash_예외('대상이 존재하지 않음');
return $targets[0];
}
/**
* 우선순위에 따라 리소스에 대한 대상 목록을 가져옵니다.
* 최대 $requestedCount 대상이 반환되며 총 개수가 적으면 그보다 적습니다.
*
* @param string $ resources
* @param int $requestedCount 반환할 목록의 길이
* @return array 대상 목록
* @comment 현재 리소스에 해당하는 노드를 찾습니다.
* 노드가 있으면 반환합니다. 비어 있음 노드를 반환하는 노드는 하나만 있습니다.
* 현재 리소스를 갖고, 모든 위치를 정렬하고, 순서대로 목록에서 현재 리소스의 위치를 ​​찾습니다.
* 찾을 수 없으면 찾을 수 없고, 찾을 수 없을 때 리소스의 위치를 ​​첫 번째 순서 위치로 결정(링 형성)
* 찾은 노드를 반환
*/
공용 함수 lookupList($resource, $requestedCount)
{
if (!$requestedCount)
throw new Flexihash_Exception('잘못된 개수 요청됨');
// 대상 없음
if (empty($this->_positionToTarget))
return array();
// 단일 대상 최적화
if ($this->_targetCount == 1)
return array_unique(array_values($this->_positionToTarget));
// 리소스를 위치로 해시
$resourcePosition = $this->_hasher->hash($resource );
$results = array();
$collect = false;
$this->_sortPositionTargets();
//resourcePosition
foreach($this- >_positionToTarget as $key => $value)
{
// 리소스 위치 전달 후 대상 수집 시작
if (!$collect && $key > $resourcePosition)
{
$collect = true;
}
// 모든 대상의 첫 번째 인스턴스만 수집
if ($collect && !in_array($value, $results))
{
$results []= $value;
}
// 결과가 충분할 때 반환하거나 소진된 목록
if (count($results) == $requestedCount || count($results) == $this->_targetCount)
{
return $results;
}
}
// 루프 시작 - resourcesPosition
foreach($this->_positionToTarget as $key => $value)
아래의 값 검색 {
if (!in_array($value, $results))
{
$results []= $value;
}
// 결과가 충분하면 반환하거나 목록이 소진되면 반환
if (count($results) == $requestedCount || count($results) == $this->_targetCount)
{
return $results;
}
}
// 두 "부분"을 모두 반복한 후 결과를 반환
return $results;
}
공용 함수 __toString()
{
return sprintf(
'%s{targets:[ %s]}',
get_class($this),
implode(',', $this->getAllTargets())
);
}
// --- ------------------------
// 비공개 메소드
/**
* 위치별로 내부 매핑(위치에서 대상까지)을 정렬합니다
*/
비공개 함수 _sortPositionTargets()
{
// 아직 키(위치)로 정렬하지 않은 경우
if (!$this->_positionToTargetSorted)
{
ksort($this->_positionToTarget, SORT_REGULAR);
$this->_positionToTargetSorted = true;
}
}
}
/**
 * 주어진 값을 정렬 가능한 고정 크기 주소 공간으로 해시합니다.
 *
 * @author Paul Annesley
 * @package Flexihash
 * @licence http://www.opensource.org/ 라이센스/mit-license.php
 */
인터페이스 Flexihash_Hasher
{
/**
* 주어진 문자열을 32비트 주소 공간으로 해시합니다.
*
* 출력은 32비트 이상의 원시 데이터일 수 있습니다(예:
* 32비트 값을 나타내는 16진수 문자).
*
* 데이터는 0xFFFFFFFF 가능한 값을 가져야 하며
* SORT_REGULAR를 사용하는 PHP 정렬 함수로 정렬할 수 있어야 합니다.
*
* @param string
* @return 혼합 다음을 사용하여 정렬 가능한 형식 0xFFFFFFFF 가능한 값
*/
공개 함수 해시($string);
}
/**
 * CRC32를 사용하여 값을 서명된 32비트 int 주소 공간으로 해시합니다.
 * 32비트 PHP에서는 (안전하게) 음수 정수로 오버플로됩니다.
 *
 * @author Paul Annesley
 * @package Flexihash
 * @licence http://www.opensource.org/licenses/mit-license.php
 */
class Flexihash_Crc32Hasher
Flexihash_Hasher 구현
{
/* (phpdoc 아님)
* @see Flexihash_Hasher::hash()
*/
공용 함수 해시($string)
{
return crc32($string);
}
}
/**
 * CRC32를 사용하여 값을 32비트 바이너리 문자열 데이터 주소 공간으로 해시합니다.
 *
 * @author Paul Annesley
 * @package Flexihash
 * @licence http://www. opensource.org/licenses/mit-license.php
 */
class Flexihash_Md5Hasher
Flexihash_Hasher 구현
{
/* (phpdoc이 아님)
* @see Flexihash_Hasher::hash()
*/
공개 함수 해시($string)
{
return substr(md5($string), 0, 8); // 8 hexits = 32bit
// 4바이트의 바이너리 md5 데이터도 사용할 수 있지만
// 성능은 동일합니다.
}
}
/**
 * Flexihash에서 발생한 예외.
 *
 * @author Paul Annesley
 * @package Flexihash
 * @licence http://www.opensource.org /licenses/mit-license.php
 */
class Flexihash_Exception은 Exception
{
}