草庐IT

php - 理解一致性哈希

coder 2024-04-19 原文

过去几天我一直在研究 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 支持查找多个节点，所以我不确定这是否与它有任何关系。

我只是想得到一些保证，我了解一致性哈希的工作原理，或者可能链接到一些真正很好地解释它的文章。

谢谢!

最佳答案

那么您是想知道 crc32 是如何工作的，还是只是想知道如何编写一个好的“桶”实现？

您的存储桶实现看起来不错。如果你这样做，你可能会做得更快:

$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。

关于php - 理解一致性哈希，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6314208/

php理解nodecodenodesconsistent-hashing

有关php - 理解一致性哈希的更多相关文章

  1. ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2

    我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat

  2. ruby - 如何在 Grape 中定义哈希数组？ - 2

    我使用Ember作为我的前端和GrapeAPI来为我的API提供服务。前端发送类似:{"service"=>{"name"=>"Name","duration"=>"30","user"=>nil,"organization"=>"org","category"=>nil,"description"=>"description","disabled"=>true,"color"=>nil,"availabilities"=>[{"day"=>"Saturday","enabled"=>false,"timeSlots"=>[{"startAt"=>"09:00AM","endAt"=>

  3. ruby - 在哈希的键数组中追加元素 - 2

    查看我的Ruby代码:h=Hash.new([])h[0]=:word1h[1]=h[1]输出是:Hash={0=>:word1,1=>[:word2,:word3],2=>[:word2,:word3]}我希望有Hash={0=>:word1,1=>[:word2],2=>[:word3]}为什么要附加第二个哈希元素(数组)？如何将新数组元素附加到第三个哈希元素？ 最佳答案 如果您提供单个值作为Hash.new的参数(例如Hash.new([])，完全相同的对象将用作每个缺失键的默认值。这就是您所拥有的，那是你不想要的。您可以改用

  4. CAN协议的学习与理解 - 2

    最近在学习CAN，记录一下，也供大家参考交流。推荐几个我觉得很好的CAN学习，本文也是在看了他们的好文之后做的笔记首先是瑞萨的CAN入门，真的通透；秀！靠这篇我竟然2天理解了CAN协议！实战STM32F4CAN！原文链接：https://blog.csdn.net/XiaoXiaoPengBo/article/details/116206252CAN详解（小白教程）原文链接：https://blog.csdn.net/xwwwj/article/details/105372234一篇易懂的CAN通讯协议指南1一篇易懂的CAN通讯协议指南1-知乎(zhihu.com)视频推荐CAN总线个人知识总

  5. TimeSformer：抛弃CNN的Transformer视频理解框架 - 2

    Transformers开始在视频识别领域的“猪突猛进”，各种改进和魔改层出不穷。由此作者将开启VideoTransformer系列的讲解，本篇主要介绍了FBAI团队的TimeSformer，这也是第一篇使用纯Transformer结构在视频识别上的文章。如果觉得有用，就请点赞、收藏、关注！paper:https://arxiv.org/abs/2102.05095code(offical):https://github.com/facebookresearch/TimeSformeraccept:ICML2021author:FacebookAI一、前言Transformers(VIT)在图

  6. ruby - 在 Ruby 中创建按公共(public)键值分组的新哈希 - 2

    假设我有一个在Ruby中看起来像这样的哈希:{:ie0=>"Hi",:ex0=>"Hey",:eg0=>"Howdy",:ie1=>"Hello",:ex1=>"Greetings",:eg1=>"Goodday"}有什么好的方法可以将它变成如下内容:{"0"=>{"ie"=>"Hi","ex"=>"Hey","eg"=>"Howdy"},"1"=>{"ie"=>"Hello","ex"=>"Greetings","eg"=>"Goodday"}} 最佳答案 您要求一个好的方法来做到这一点，所以答案是:一种您或同事可以在六个月后理解

  7. ruby - Ruby gsub 替换中的行为不一致？ - 2

    两个gsub产生不同的结果。谁能解释一下为什么？代码也可在https://gist.github.com/franklsf95/6c0f8938f28706b5644d获得.ver=9999str="\tCFBundleDevelopmentRegion\n\ten\n\tCFBundleVersion\n\t0.1.190\n\tAppID\n\t000000000000000"putsstr.gsub/(CFBundleVersion\n\t.*\.).*()/,"#{$1}#{ver}#{$2}"puts'--------'putsstr.gsub/(CFBundleVersio

  8. ruby-on-rails - 使用作为方法的值在 ruby​​ 中搜索哈希 - 2

    我在搜索我的值是方法的散列时遇到问题。我只是不想运行plan_type与键匹配的方法。defmethod(plan_type,plan,user){foo:plan_is_foo(plan,user),bar:plan_is_bar(plan,user),waa:plan_is_waa(plan,user),har:plan_is_har(user)}[plan_type]end目前如果我传入“bar”作为plan_type，所有方法都会运行，我怎么能只运行plan_is_bar方法呢？ 最佳答案 这个变体怎么样？defmethod

  9. ruby - 易于初学者理解的 Ruby 库 - 2

    关闭。这个问题不符合StackOverflowguidelines.它目前不接受答案。我们不允许提问寻求书籍、工具、软件库等的推荐。您可以编辑问题，以便用事实和引用来回答。关闭3年前。Improvethisquestion我正处于学习Ruby的阶段，我想查看一些小型库的源代码以了解它们是如何构建的。我不知道什么是小型图书馆，但希望SO能推荐一些易于理解的图书馆来学习。因此，如果有人知道一两个非常小的库，这是新手Rubyists学习的好例子，请推荐!我想使用Manveru'sInnatelib，因为它试图保持在2000LOC以下，但我还不熟悉其中经常使用的Ruby速记。也许大约100-5

  10. 键删除后 ruby​​ 哈希内存泄漏 - 2

    你好，我无法成功如何在散列中删除key后释放内存。当我从哈希中删除键时，内存不会释放，也不会在手动调用GC.start后释放。当从Hash中删除键并且这些对象在某处泄漏时，这是预期的行为还是GC不释放内存？如何在Ruby中删除Hash中的键并在内存中取消分配它？例子:irb(main):001:0>`ps-orss=-p#{Process.pid}`.to_i=>4748irb(main):002:0>a={}=>{}irb(main):003:0>1000000.times{|i|a[i]="test#{i}"}=>1000000irb(main):004:0>`ps-orss=-p

随机推荐