PHPでConsistentHashingを実装してみた

ConsistentHasher.php

<?php

/**
 * ConsistentHashing法で分散してくれるクラス
 */
class ConsistentHasher {

	protected $ring;
	protected $keys;

	//仮想ノード数
	const COPY_NUM = 100;
	//ハッシュのアルゴリズム
	const HASH_ALGORITHM = 'md5';

	/**
	 * コンストラクタ
	 * @param array<string> $nodes ノードとなるものの配列
	 * @throws Exception $nodeが不正なとき
	 */
	public function __construct(array $nodes) {
		if (count($nodes) < 1) {
			throw new Exception('$nodeは一つ以上の要素を持つ配列を指定してください。');
		}
		$this->createNodes($nodes);
	}

	/**
	 * ノードを円状に配置する
	 * @param array<string> $nodes ノードとなるものの配列
	 */
	private function createNodes(array $nodes) {
		$this->ring = array();
		$this->keys = array();
		foreach ($nodes as $node) {
			$this->addNode($node);
		}
		arsort($this->keys);
	}

	/**
	 * ノードを円に加える
	 * @param string|int|float $node
	 */
	private function addNode($node) {
		for ($i = 0; $i < self::COPY_NUM; $i++) {
			$key = $this->hash($node . '_' . $i);
			$this->ring[$key] = $node;
			$this->keys[$key] = hexdec($key);
		}
	}

	/**
	 * ハッシュ関数
	 * @param string $text
	 * @return string 16進数
	 */
	private function hash($text) {
		return hash(self::HASH_ALGORITHM, $text);
	}

	/**
	 * データのキーを渡すと最も近いノードを取得する
	 * @param string|int|float $data_key データのキーとなるもの
	 * @return string ノード
	 */
	public function getNode($data_key) {
		$hash_number = hexdec($this->hash($data_key));
		foreach ($this->keys as $key => $key_number) {
			if ($hash_number > $key_number) {
				return $this->ring[$key];
			}
		}
		//最後まで大きいのがなければ最後のノードにいれてしまう。偏りそうだけど、特に大きな偏りはなかったのでこれで。
		end($this->keys);
		$key = key($this->keys);
		return $this->ring[$key];
	}

}