Konsistentes Hashing – PHP

/**
 * Flexihash – Eine einfache konsistente Hashing-Implementierung für PHP.
 * 
 * Die MIT-Lizenz
 * 
 * Copyright (c) 2008 Paul Annesley
 * 
 * Erlaubnis ist Hiermit wird jeder Person, die eine Kopie
 * dieser Software und der zugehörigen Dokumentationsdateien (die „Software“) erhält, kostenlos gestattet, mit der Software ohne Einschränkung zu handeln
 *, einschließlich und ohne Einschränkung der Rechte
 * Kopien der Software zu verwenden, zu kopieren, zu ändern, zusammenzuführen, zu veröffentlichen, zu verteilen, unterzulizenzieren und/oder zu verkaufen
 * und Personen, denen die Software zur Verfügung gestellt wird, dies zu gestatten, vorbehaltlich die folgenden Bedingungen:
 * 
 * Der obige Urheberrechtshinweis und dieser Genehmigungshinweis müssen in
 * allen Kopien oder wesentlichen Teilen der Software enthalten sein.
 * 
 * DIE SOFTWARE WIRD ZUR VERFÜGUNG GESTELLT " WIE BESEHEN“, OHNE JEGLICHE AUSDRÜCKLICHE ODER STILLSCHWEIGENDE GEWÄHRLEISTUNG, EINSCHLIESSLICH, ABER NICHT BESCHRÄNKT AUF DIE GEWÄHRLEISTUNG DER MARKTGÄNGIGKEIT,
 * EIGNUNG FÜR EINEN BESTIMMTEN ZWECK UND NICHTVERLETZUNG. IN KEINEM FALL SIND DIE
 * AUTOREN ODER COPYRIGHT-INHABER FÜR JEGLICHE ANSPRÜCHE, SCHÄDEN ODER ANDERE
 * HAFTUNG, SEI ES AUS EINER VERTRAGLICHEN HANDLUNG, unerlaubter Handlung ODER ANDERWEITIG, ENTSTEHEND AUS
 * AUS ODER IN VERBINDUNG MIT DER SOFTWARE ODER DER NUTZUNG ODER ANDEREN HANDELN IN
 * DER SOFTWARE.
 * 
 * @author Paul Annesley
 * @link http://paul.annesley.cc/
 * @copyright Paul Annesley, 2008
 * @comment by MyZ (http://blog.csdn.net/mayongzhan)
 */
/**
 * Eine einfache konsistente Hashing-Implementierung mit steckbaren Hash-Algorithmen.
 *
 * @author Paul Annesley
 * @package Flexihash
 * @licence http://www.opensource.org/licenses /mit-license.php
 */
class Flexihash
{
/**
* Die Anzahl der Positionen, auf die jedes Ziel gehasht werden soll.
*
* @var int
* @comment Die Anzahl der virtuellen Knoten, um das Problem der ungleichmäßigen Knotenverteilung zu lösen
*/
private $_replicas = 64;
/**
* Der Hash-Algorithmus, gekapselt in einer Flexihash_Hasher-Implementierung.
* @var object Flexihash_Hasher
* @comment 使用的hash方法 : md5,crc32
*/
private $_hasher;
/**
* Interner Zähler für die aktuelle Anzahl an Zielen.
* @var int
* @comment Knotenzähler
*/
private $_targetCount = 0;
/ **
* Interne Zuordnung von Positionen (Hash-Ausgaben) zu Zielen
* @var array { position => target, ... }
* @comment Position entsprechender Knoten, wird verwendet, um Ziele basierend auf der Position in der Suche zu bestimmen Besuchter Knoten
*/
private $_positionToTarget = array();
/**
* Interne Zuordnung von Zielen zu Listen von Positionen, zu denen das Ziel gehasht wird.
* @var array { target => [ position, position, ... ], ... }
* @comment The entsprechende Position des Knotens, wird zum Löschen des Knotens
verwendet*/
private $_targetToPositions = array();
/**
* Ob die interne Karte von Positionen zu Zielen bereits sortiert ist.
* @var boolean
* @comment Ob die interne Karte von Positionen zu Zielen bereits sortiert ist.
* /
private $_positionToTargetSorted = false;
/**
* Konstruktor
* @param object $hasher Flexihash_Hasher
* @param int $replicas Anzahl der Positionen, an die jedes Ziel gehasht werden soll.
* @comment Konstruktor, bestimmen Sie die zu verwendende Hash-Methode und die Anforderungen Anzahl virtueller Knoten Je mehr virtuelle Knoten vorhanden sind, desto gleichmäßiger ist die Verteilung, aber desto langsamer wird der verteilte Betrieb des Programms sein
*/
public function __construct(Flexihash_Hasher $hasher = null, $replicas = null)
{
$this-> ;_hasher = $hasher ? $hasher : new Flexihash_Crc32Hasher();
if (!empty($replicas)) $this->_replicas = $replicas;
}
/**
* Ein Ziel hinzufügen.
* @param string $target
* @chainable
* @comment Einen Knoten hinzufügen und die Knoten entsprechend der Anzahl der virtuellen Knoten auf mehrere virtuelle Standorte verteilen
*/
öffentliche Funktion addTarget($target)
{
if (isset($this->_targetToPositions[$target]))
{
throw new Flexihash_
Exception
("Target '$ target' existiert bereits.");}$this->_targetToPositions[$target] = array();
// hash das Ziel in mehrere Positionen
für ($i = 0 ; $i < $this->_replicas; $i++)
{
$position = $this->_hasher->hash($target . $i);
$this-> ;_positionToTarget[$position] = $target; // lookup
$this->_targetToPositions[$target] []= $position; // Zielentfernung
}
$this->_positionToTargetSorted = false;
$this->_targetCount++;
return $this;
}
/**
* Fügen Sie eine Liste von Zielen hinzu.
* @param array $targets
* @chainable
*/
öffentliche Funktion addTargets($targets)
{
foreach ($targets as $target)
{
$this->addTarget($target);
}
$this zurückgeben;
}
/**
* 대상을 제거합니다.
* @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);
}
/**
 * Verwendet CRC32, um einen Wert in einen signierten 32-Bit-Int-Adressraum zu hashen.
 * Unter 32-Bit-PHP läuft dies (sicher) in negative Ints über.
 *
 * @author Paul Annesley
 * @package Flexihash
 * @licence http://www.opensource.org/licenses/mit-license.php
 */
Klasse Flexihash_Crc32Hasher
implementiert Flexihash_Hasher
{
/* (nicht-phpdoc)
* @see Flexihash_Hasher::hash()
*/
public function hash($string)
{
return crc32($string);
}
}
/**
 * Verwendet CRC32, um einen Wert in einen 32-Bit-Binärzeichenfolgen-Datenadressraum zu hashen.
 *
 * @author Paul Annesley
 * @package Flexihash
 * @licence http://www. opensource.org/licenses/mit-license.php
 */
class Flexihash_Md5Hasher
implementiert Flexihash_Hasher
{
/* (nicht-phpdoc)
* @see Flexihash_Hasher::hash()
*/
public function hash($string)
{
return substr(md5($string), 0, 8); // 8 Hexits = 32bit
// 4 Bytes binärer MD5-Daten könnten ebenfalls verwendet werden, aber
// Leistung scheint zu sein gleich.
}
}
/**
 * Eine von Flexihash ausgelöste Ausnahme.
 *
 * @author Paul Annesley
 * @package Flexihash
 * @licence http://www.opensource.org /licenses/mit-license.php
 */
class Flexihash_Exception erweitert Exception
{
}

Das Obige hat einen konsistenten Hash-PHP eingeführt, einschließlich Ausnahmeinhalten. Ich hoffe, dass es für Freunde hilfreich sein wird, die sich für PHP-Tutorials interessieren.