Bringing together the Apache Cassandra experts from the community and DataStax.

Want to learn? Have a question? Want to share your expertise? You are in the right place!

Not sure where to begin? Getting Started

 

question

wjjfree avatar image
wjjfree asked wjjfree commented

咨询下,Murmur3Partitioner中getHash使用了hash3_x64_128,返回的是两个long型,为什token只使用了hash[0]?

如标题,关于Murmur3Partitioner有两个问题

1、Murmur3Partitioner中getHash使用了hash3_x64_128,返回的是两个long型,为什token只使用了hash[0]? 没有使用128位的BigIntegerToken是基于什么考虑?

2、在token使用了64位long的情况下,getHash依旧使用hash3_x64_128并保留了两个long的计算结果,我理解是在BloomFilter过滤时少运行一次Hash计算,不知理解是否正确?


partitioner
10 |1000 characters needed characters left characters exceeded

Up to 8 attachments (including images) can be used with a maximum of 1.0 MiB each and 10.0 MiB total.

1 Answer

wdeng avatar image
wdeng answered wjjfree commented

如果你仔细对比Random和Murmur3这两个Partitioner的实现(源码在这里:https://github.com/apache/cassandra/blob/9d57d216f5530e5b80adb753e5daa0d469ae0944/src/java/org/apache/cassandra/dht/Murmur3Partitioner.javahttps://github.com/apache/cassandra/blob/9d57d216f5530e5b80adb753e5daa0d469ae0944/src/java/org/apache/cassandra/dht/RandomPartitioner.java ),你会发现它们一个(Murmur3)用的 LongToken,一个(Random)用的是BigIntegerToken。


这样带来的结果是:Cassandra里的Murmur3产生的Token值会小一倍,这样Murmur3在计算和存储Token值的时候都会要比Random的BigIntegerToken快很多。从官方的文档里可以看到,这是Cassandra里的Murmur3实现相对于Random来说最大的一个优势:"The Murmur3Partitioner provides faster hashing and improved performance than the RandomPartitioner."


而当时从生产环境的实际经验里发现64-bit的LongToken提供的token space也足够大了,因此后来默认的Partitioner在C* 1.2版本里也切换成了Murmur3,以提高token计算的性能。


至于为什么要使用hash3_x64_128,然后只取hash[0],这是因为当年的Murmur hash3的实现里只提供了128-bit输出的这个选项。所以为了匹配LongToken的大小,必须把这个值切成64-bit的。这个做法有可能造成token->key的inversion更容易,但是C*使用这个Hash函数的目的是为了让hash值均匀分布,不需要像安全领域的*one-way* hash function那样专注于避免inversion,所以这个做法不会带来太大的问题。C* 1.0-beta以来这么多年生产环境中的实践也证明了用Murmur3替换Random不是一个坏的决定。

1 comment Share
10 |1000 characters needed characters left characters exceeded

Up to 8 attachments (including images) can be used with a maximum of 1.0 MiB each and 10.0 MiB total.

了解了,感谢你这么详细的答复。

0 Likes 0 ·