4

ここ数日、PHP のコンシステント ハッシュ アルゴリズムについて調べてきました。コンシステント ハッシュが実際にどのように機能するかをよりよく理解し、今後のプロジェクトで利用できるようにしたいと考えています。私には、Flexihashが本当に理解しやすい唯一のピュア PHP 実装であるように思われるので、そこからいくつかのメモを取りました。

私は独自の小さなアルゴリズムを作成して、それがどのように機能するか、およびできるだけ速く機能させる方法を理解しようとしました。私のアルゴリズムが Flexihash と比較して非常に高速であることに驚きました。これにより、私の実装に何らかの欠陥があるのではないかと考えたり、概念全体の重要な部分を把握していない可能性があります。

100 万個のシーケンシャル キー (0 ～ 1,000,000) の反復における速度の違いを以下に示します。各ノードが表示され、その特定のノードに実際にハッシュされたキーの数が示されます。

Flexihash:
 Time: 269 seconds
Speed: 3714 hashes/sec

 node1: 80729
 node2: 88390
 node3: 103623
 node4: 112338
 node5: 79893
 node6: 85377
 node7: 80966
 node8: 134462
 node9: 117046
node10: 117176

My implementation:
 Time: 3 seconds
Speed: 265589 hashes/sec

 node1: 100152
 node2: 100018
 node3: 99884
 node4: 99889
 node5: 100057
 node6: 100030
 node7: 99948
 node8: 99918
 node9: 100011
node10: 100093

これがハッシュアルゴリズムの現在の実装です。

class Base_Hasher_Consistent
{
    protected $_nodes;

    public function __construct($nodes=NULL)
    {
        $this->_nodes = array();

        $node_count = count($nodes);
        $hashes_per_node = (int)(PHP_INT_MAX / $node_count);

        $old_hash_count = 0;

        foreach($nodes as $node){
            if(!($node == $nodes[$node_count-1])){
                $this->_nodes[] = array(
                    'name' => $node,
                    'begin' => $old_hash_count,
                    'end' => $old_hash_count + $hashes_per_node - 1
                );

                $old_hash_count += $hashes_per_node;
            }else{
                $this->_nodes[] = array(
                    'name' => $node,
                    'begin' => $old_hash_count,
                    'end' => PHP_INT_MAX
                );
            }
        }
    }

    public function hashToNode($data_key,$count=0)
    {
        $hash_code = (int)abs(crc32($data_key));

        foreach($this->_nodes as $node){
            if($hash_code >= $node['begin']){
                if($hash_code <= $node['end']){
                    return($node['name']);
                }
            }
        }
    }
}

私は何かを見逃していますか、それともアルゴリズムは Flexihash よりも本当に高速ですか? また、Flexihash が複数のノードの検索をサポートしていることは理解しているので、それが関係しているかどうかはわかりません。

コンシステント ハッシュがどのように機能するかを理解しているという安心感、または実際にそれをよく説明している記事へのリンクを希望します。

ありがとう！

4

2 に答える 2

1

それで、crc32 がどのように機能するかを知りたいですか、それとも適切な「バケット」実装の書き方を知りたいですか?

バケットの実装は問題ないようです。次のようにすれば、おそらくより速く実行できます。

$bucket_index = floor($hash_code / $hashes_per_node);
return $this->_nodes[$bucket_index]['name'];

あなたが書いた「アルゴリズム」は$nodes、バケットの数を作成し、それらのバケットのどれに$data_key入る必要があるかを判断します。使用している実際のハッシュ アルゴリズムは crc32 です。バケットを使用している場合、これは理想的なアルゴリズムではない可能性があります。

crc32 の仕組みと、ハッシュが一貫している理由を知りたい場合は、ウィキペディアなどで調べてください。私の知る限り、一貫性のないハッシュなどは存在しないため、すべてのハッシュ アルゴリズムは定義上一貫しています。

ハッシュ アルゴリズムの特徴の 1 つは、似ている data_key に対して非常に似ていないハッシュを生成できることです。これは、crc32 が小さな変更を検出することを目的としているため、crc32 にも当てはまります。ただし、結果のハッシュが「十分に分散」していることは保証されません。バケツをやっているので、スペクトル全体でハッシュを生成する特定のプロパティを持つハッシュアルゴリズムが必要です。crc32 の場合、偶然にも非常にうまく機能する可能性があります。私はmd5を使用するだけです。

于 2011-06-11T13:13:20.280 に答える
1

EstelS 氏は次のように述べています。

コンシステント ハッシュがどのように機能するかを理解しているという安心感、または実際にそれをよく説明している記事へのリンクを希望します。

これは私が Flexihash を書くきっかけとなった素晴らしい記事です: http://www.tomkleinpeter.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/

私は長い間コードを見ていませんでした-あなたのコードがはるかに高速である可能性は十分にあります..速度は私の関心事ではありませんでした. しかし、あなたがまったく違うことをしている可能性もあります:)

バイナリ検索を使用することで 70 倍の速度向上を主張する GitHub の rs によるこのコミットも参照してください。誰かが商品であることが確認できたら、私はそれをマージします.

乾杯！ポール

于 2011-06-18T07:49:25.693 に答える