Понимание последовательного хеширования - PullRequest
Новая
       30

Понимание последовательного хеширования

4 голосов
/ 11 июня 2011

Последние пару дней я смотрел на согласованные алгоритмы хеширования для PHP.Я хочу лучше понять, как на самом деле работает последовательное хеширование, поэтому я могу использовать его в некоторых будущих проектах.Мне кажется, что Flexihash действительно единственная реализация на чистом PHP, которая была проста для понимания, поэтому я сделал несколько заметок из нее.

Я создал небольшой алгоритм своегопытаться понять, как это работает, и как заставить его работать как можно быстрее.Я был удивлен тем, насколько быстро мой алгоритм сравнивается с Flexihash, что заставляет меня задаться вопросом, не является ли моя реализация ошибочной в какой-то мере, или, возможно, я не осознаю важную часть всей концепции.

Различия в скоростиперечислены ниже, за итерацию из 1 миллиона последовательных ключей (от 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 поддерживает поиск нескольких узлов, поэтому я не уверен, имеет ли это какое-либо отношение к этому.

Мне просто хотелось бы получить некоторое подтверждение того, что я понимаю, как работает согласованное хеширование, или, может быть,ссылки на некоторые статьи, которые действительно хорошо это объясняют.

Спасибо!

Ответы [ 2 ]

1 голос
/ 18 июня 2011

EstelS сказал:

Мне просто хотелось бы получить некоторое подтверждение того, что я понимаю, как работает последовательное хеширование, или, возможно, ссылки на некоторые статьи, которые действительно хорошо это объясняют.

Это отличная статья, которая привела меня к написанию Flexihash: http://www.tomkleinpeter.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/

Я давно не смотрел код - вполне возможно, что ваш намного быстрее ... скорость никогда не была моей проблемой.Но также возможно, что вы делаете что-то совершенно другое:)

См. Также этот коммит rs на GitHub , который требует 70-кратного улучшения скорости с помощью бинарного поиска.Я объединю это, если кто-то может подтвердить, что это товар.

Ура!Пол

1 голос
/ 11 июня 2011

Итак, вы хотите знать, как работает crc32, или вам просто интересно, как написать хорошую реализацию 'bucket'?

Ваша реализация bucket выглядит хорошо.Вероятно, вы могли бы сделать это быстрее, если бы просто сделали: 

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

«Алгоритм», который вы написали, просто составляет $nodes количество сегментов и вычисляет, в каком из этих блоков должен идти $data_key.Фактическим алгоритмом хеширования, который вы используете, является crc32, который, возможно, не является идеальным алгоритмом, если вы выполняете сегменты.

Если вы хотите знать, как работает crc32 и почему хеш-код непротиворечивый ... посмотрите егов википедии или что-то.Насколько мне известно, не существует такой вещи, как несовместимый хеш, поэтому все алгоритмы хеширования по определению согласованы.

Одна из характеристик алгоритма хеширования состоит в том, что он может генерировать хеши, которые очень отличаются для аналогичных data_keys.Это верно для crc32, поскольку crc32 предназначен для обнаружения незначительных изменений.Однако это не гарантирует, что полученные хэши «хорошо распределены».Поскольку вы выполняете сегменты, вам нужен алгоритм хеширования, который обладает определенным свойством, которое генерирует хеши по всему спектру.Для crc32 это может просто случайно работать очень хорошо.Я бы просто использовал md5.

...