Cassandra 之中的Hash 算法: MurMur3

2016年09月05日 38519点热度 3人点赞 4条评论

1. Murmur哈希算法是干什么的?

在之前的文章 [Cassandra教程](十四)浅谈Cassandra的架构 以前之前的文章我们提到了数据模型以及Partition Key, 同时Cassandra维护了一个令牌环,这样当我们写入一条数据或者需要读取数据的时候,就知道首先去哪一台机器执行相应的操作。

在底层支撑令牌的算法,就是默默无闻但是几乎一统江湖的MurmurHash算法。

所谓Murmur,并不是我们常听到的陌陌,而是(multiply and rotate) and (multiply and rotate). 根据维基上面的解释:

MurmurHash 是一种非加密哈希函数,适用于一般的哈希检索操作。[1][2][3]由Austin Appleby在2008年发明,[4][5] 并出现了多个变种,[6] 都已经发布到了公有领域(public domain)。与其它流行的哈希函数相比,对于规律性较强的key,MurmurHash的随机分布特征表现更良好。[7]

来源: https://zh.wikipedia.org/wiki/Murmur%E5%93%88%E5%B8%8C

上面的表述我感觉说的还是不够浅显,Murmur哈希算法最大的特点是:

  1. 碰撞率低
  2. 计算速度快

因此,不仅是Cassandra,在常见的大数据库底层,都使用了这个算法作为底层的存储算法。

注意:原生的MurmurHash算法,并不能保证无碰撞,只是碰撞率比较低。相关测试代码以及测试数据请看下文

原文链接:http://www.flyml.net/2016/09/05/cassandra-tutorial-murmurhash/

2. 几种常见的版本

 

最新的版本是Murmur3, 是原作者被Google挖去之后基于Murmur2的缺陷做了改进。Google之后又基于Murmur3做了SipHash算法,但是应用看起来没有Murmur广泛。

Murmur3只有32-bit跟128-bit两种版本,相比Murmur2,计算速度更快,但是不支持Murmur2里面的64-bit.

原文链接:http://www.flyml.net/2016/09/05/cassandra-tutorial-murmurhash/

3. 应用

Java上面的实现版本很多,可以直接从Cassandra的源码里面抠出来使用。见GitHub. 在使用上比较简单的还是基于Guava,并且也是最新的Murmur3.

具体的使用方法可以参考Google自己写的文档:https://github.com/google/guava/wiki/HashingExplained

 

写的还是比较清晰的。唯一需要强调的一点就是,如果你想在任何时候,相同的String值一定得出相同hash值,就一定要新创建hasher,也就是上面的第二行代码。

具体可以对比下面的代码以及输出结果:

---- 每次都新创建Hasher实例

---- 复用Hasher实例

可以看到,如果复用hasher的话,即使是同一个string对象,hash值也不一样了。

但是Guava的hasher创建效率非常非常高。几乎体会不到差别时间。

 

再来一个测试碰撞率的实验代码:

第15行可以自行调试测试数据量。

我的测试结果:

containsSize=46241
dup_ratio =0.00231205

 

结论:在我的测试之中,2KW条测试记录(虽然都是int)完全没有冲突发生的情况。 如果是使用Guava自带的32bit,或者是128-bit但是返回int值,就会出现冲突碰撞的情况发生。

 

本文为原创文章,转载请注明出处
原文链接:http://www.flyml.net/2016/09/05/cassandra-tutorial-murmurhash/

 

 

RangerWolf

保持饥渴的专注,追求最佳的品质

文章评论

  • sandwich

    没看懂结论,“”“完全没有冲突发生的情况”,这个怎样理解,是按照测试用例就没有嘛?

    2018年07月27日
    • rangerwolf

      "完全没有冲突发生的情况" 就是在2KW这个测试用例里面, 没有出现冲突的情况

      2018年08月06日
  • sandwich

    String(i).hashCode();的方式计算,发现冲突的更少,为何会这样的? :lol:

    2018年07月27日
    • rangerwolf

      在底层String跟Integer还是不太一样的, 只不过具体算法是如何计算的, 我也不是非常非常了解.
      各种字符操作...

      2018年08月06日