精华 解析 node-murmurhash 库:说说 Node.js 二进制操作
发布于 3 年前 作者 alsotang 8649 次浏览 来自 分享

库的地址在这里:https://github.com/node-modules/node-murmurhash

介绍一下 murmurhash。murmurhash 是 Austin Appleby 于2008年创立的一种非加密 hash 算法,适用于基于 hash 进行查找的场景。

相比其他的 hash 算法,对于规律性较强的 key,MurmurHash 的随机分布特性表现更良好。而且很快。

好了就摘抄到这了。。。

至于为什么用到了它,是因为前公司那里,有个分布式缓存服务用了它来做分片。@fengmk2(https://github.com/fengmk2) 和 @dead-horse(https://github.com/dead-horse) 实现了这个缓存服务的 Node 客户端,在这一过程中,也同时需要实现 murmurhash 算法。

我们只要保证跟 Java 那边同样的输入,能得到同样的输出就好了。我不是很懂 murmurhash 这个技术选型的目的。

目前我们实现的这个是 murmurhash v2 的版本。

大家知道,加密算法普遍使用了各种【与】【或】【溢出】等手段来生成最终 hash 值。而 js 对于二进制的操作,有时候是要绕着来做,而且一些 C 语言中不同类型的表现,也需要特殊处理。

C++版本

这是最初的版本。

源码: https://github.com/node-modules/node-murmurhash/blob/4136c63dd87cc1541268e19f54149585d3ebe93b/src/murmurhash.cc

#include "nan.h"
#include "murmurhash.h"

#define MURMURHASH_M 0x5bd1e995

NAN_METHOD(MurmurHash2) {
  NanScope();

  if (args.Length() < 2) {
    NanThrowTypeError("Wrong number of arguments");
    NanReturnUndefined();
  }

  char *key = node::Buffer::Data(args[0]->ToObject());
  int len = node::Buffer::Length(args[0]->ToObject());
  uint32_t seed = args[1]->NumberValue();
  uint32_t h = seed ^ len;
  int index = 0;

  while (len >= 4) {
    uint32_t k = (key[index] & 0xff) | ((key[index + 1] << 8) & 0xff00)
      | ((key[index + 2] << 16) & 0xff0000)
      | (key[index + 3] << 24);

    k *= MURMURHASH_M;
    k ^= (k >> 24);
    k *= MURMURHASH_M;
    h *= MURMURHASH_M;
    h ^= k;
    index += 4;
    len -= 4;
  }

  switch (len) {
    case 3:
      h ^= (key[index + 2] << 16);

    case 2:
      h ^= (key[index + 1] << 8);

    case 1:
      h ^= key[index];
      h *= MURMURHASH_M;
  }

  h ^= (h >> 13);
  h *= MURMURHASH_M;
  h ^= (h >> 15);
  NanReturnValue(NanNew<v8::Number>(h));
}

因为涉及二级制操作嘛,很自然地,一开始的版本是个 C++ 的 addon。找个开源的库,把 v8.h 相关的操作替换进去,再 node-gyp 包一下,就能工作了。

其实这么用着,也倒相安无事。速度很快,代码反正写好就是固定的,也不用改。

但无论对于 Mac 还是 Windows 的用户来说,用上这个库的前提都是需要安装一个编译环境。Mac 下面有 Xcode 的工具可以安装,Windows 下面,不懂怎么弄,好像是弄个 vs 的工具套装。那这么说,对于一些没有环境的新用户,本地开发第一次安装时,始终是不太方便的。

先来说说上述代码里面的几个关键点。

一、【与】【或】【非】的操作,js 都支持,而且结果跟 C++ 里几乎一样。

上述代码中seed ^ len 这样的操作是 js 原生支持的。

在 js 里面,Number 类型在内存中的结构跟 C++ 语言里面 double 是一样的。都是双精度浮点数,也可以叫 64 位浮点数,IEEE 754 标准。在进行二进制操作的时候(比如 100 << 2),js 会把 Number 当做 32 位的有符号整形进行操作,

小数部分直接舍去,比如:

> 2.9 << 1
4

超过 32 位的部分舍去。比如:

> Math.pow(2, 32).toString(2)
'100000000000000000000000000000000'
> Math.pow(2, 33).toString(2)
'1000000000000000000000000000000000'
> (Math.pow(2, 32) + 1).toString(2)
'100000000000000000000000000000001'
> (Math.pow(2, 32) + 1) << 1
2
> ((Math.pow(2, 32) + 1) << 1).toString(2)
'10'

参考: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators

二、

#define MURMURHASH_M 0x5bd1e995 这个宏怎么办?

但其中多处使用的 uint32_t 怎么在 js 中表示?

uint32_t k = (key[index] & 0xff) | ((key[index + 1] << 8) & 0xff00)
  | ((key[index + 2] << 16) & 0xff0000)
  | (key[index + 3] << 24);

这句是在做什么?其中 key[index] 都是 char 类型的。

switch 那个地方,key[index + 2] << 16 这句乍看之下没问题,但大家注意,key[index] 都是 char 类型的。一个 char 类型在 c 语言中进行二进制操作的时候,会发生哪些不为人知的事情?

k *= MURMURHASH_M 这一句,k 作为一个 uint32_t,乘以另一个 32 位正整数,分分钟要溢出,溢出的表现是如何的?

这些事情又怎么在 js 中模拟。下面让我们走近科学…

分解

我们一个个地说

#define MURMURHASH_M 0x5bd1e995

这段宏倒是好处理,虽然这是个宏,但我们 js 中使用赋值,结果也是一样的。之所以使用宏,一是因为 c 语言中,常量习惯使用宏;二是因为,宏是在编译阶段展开的,展开后它嵌到各个使用语句中,运行时不必再去变量中取值。不过既然 js 不支持宏,我们也只能赋值了。效率当然低一点啦,但我们是有心理准备的,而且我们相信 V8。

所以这句,直接 var MURMURHASH_M = 0x5bd1e995

对了,这个数的意义是什么呢?就当它是个 magic number 吧。。。我赌一块钱,这是个质数。

uint32_t

uint32_t k = (key[index] & 0xff) | ((key[index + 1] << 8) & 0xff00)
  | ((key[index + 2] << 16) & 0xff0000)
  | (key[index + 3] << 24);

说到这个地方,要先说说它的右边 key[index] & 0xff 发生了什么。key[index] 是个 char 类型,它的范围是 –128 to 127。

如果一个字符的 ascii 码大于等于0,小于等于127的时候。那么 char 类型会如实记录它的值。

如果大于 127,比如 128,那么在赋值给 char 的时候,C 语言会认为 char 的值是 -128

这个我们可以在 node 里面试试:

> var b = new Buffer(1)
undefined
> b
<Buffer 00>
> b.writeInt8(128, 0, true)
1
> b
<Buffer 80>
> b.readInt8(0)
-128

在 char 转换成 signed int,对应也有两种情况。当值大于等于0,小于等于127的时候,直接转成对应的 int。大于 127 的时候,会变成一个极大的负数。0x79 === 127

0x79 转成 int 的时候,C 语言里面变成 0x0000000790x80 转成 int 的时候,C 语言里面会变成 0xffffff80,这段内存被 int 一解读,就成了极大负数。

(key[index] & 0xff) | ((key[index + 1] << 8) & 0xff00)
  | ((key[index + 2] << 16) & 0xff0000)
  | (key[index + 3] << 24);

这句整体的意思就是,用户传进来的连续4个char(每个8位),用 & 0xff00 的操作,过滤所有跟符号位有关的影响,把本该属于它们的实际两位取出来,然后把它们拼成一个 32 位的值。

假设 key = [0x01, 0x02, 0x80, 0x813],那么这个地方拼出来的值就是 0x13800201。我们可以试一试。

> var key = [0x01, 0x02, 0x80, 0x13]
undefined
> var index = 0
undefined
> (key[index] & 0xff) | ((key[index + 1] << 8) & 0xff00) | ((key[index + 2] << 16) & 0xff0000) | (key[index + 3] << 24)
327156225
> 327156225..toString(16)
'13800201'


// 高级写法,不过比上述要慢。可能V8本来就很快,而 Buffer 操作又涉及与 C++ 层的通信。
// 这里的 key 在 js 中是 Buffer,所以我们可以调用 Buffer 的 read 方法。
// 示例代码
> var key = new Buffer([0x01, 0x02, 0x80, 0x13])
undefined
> key.readInt32LE(0)
327156225

然后这个值被赋给 k 记录下来。无论 k 是 int32_t 还是 uint32_t,都会如实记录下这个值。

不同的是,使用的时候,k 到底被解释负数还是正数。

下面我们马上就要使用 k 了。

先说说 js 对于这个问题的解法:

k = (key[i] |
  (key[i + 1] << 8) |
  (key[i + 2] << 16) |
  (key[i + 3] << 24))

在我们这里,key 是个 Buffer 的实例,里面的每个值,都是大于等于0小于等于255的数字。

由于 js 会把每个索引的部分当成 Number 来看待,所以我们这里没有 char 溢出的问题。不必进行 & 0xff00 等操作。直接移位就能如实拿到它的内存表示。

char to int32

h ^= (key[index + 2] << 16);

这一句,没有只截取需要的 char 部分,而是如实把符号位相关的也使用了。在上一段中,其实 char to int32 的问题我们并没有解,只是刚好没发生。

但到了这一步,就需要解了。

解法也简单:

function negative(num) {
  if (num < 127) {
    return num;
  }
  return num | 0xffffff00
}

就可以了。

在这个函数出来之前,我们的解法是,用一张映射表,把 256 种情况列进来,然后通过查表来决定 char 应该转成什么。这个表的生成其实也简单的,而且效率也很高,哪有比查表更快的嘛。

但我改成这个函数之后,我发现效率没有下降,而且这样更简单,就改成这样了。或许我这样改还拖慢了速度,不过差别不大,根据我们使用的 benchmark,可能会每秒少100w次吧(逃…但我就喜欢这么写。

imul

c语言中,0x5bd1e995 这东西叫做 decimal literal。它并不区分类型,只是严格地记住自己的二进制形式。当赋值或者运算的时候,才根据对方需要的类型,来解读自身。

k *= MURMURHASH_M 这一句发生的时候,它被解释成了 int。由于它的首位不是0,所以它是个正数。

而 k 由于按照无符号数解释,也是个正数。

这时候蛋疼的事情就来了。因为溢出了。

> var k = 3
undefined
> var MURMURHASH_M = 0x5bd1e995
undefined
> k * MURMURHASH_M
4621450431
> 4621450431..toString(16)
'11375bcbf'
> 4621450431..toString(2).length
33
> 4621450431..toString(2)
'100010011011101011011110010111111'

k 作为一个 uint32_t,最多表示 32 位的数,而我们的结果有 33 位,这时候 c 语言只会保留 0b00010011011101011011110010111111 下来,去掉超过 32 位的部分。

> 0b00010011011101011011110010111111
326483135

ok,这种情况我们怎么模拟?

先说为什么需要模拟,上面不是好好地得出了与C语言一样的值吗?

因为 js 中,按照 IEEE 754 的标准,能精确表示的最大整数是 2 ** 53 - 1。

两个 32 位的正整数相乘,最大的结果可以达到64位(但无法到达65位)。

如果我们的 k *= MURMURHASH_M 的结果大于 2 ** 53 - 1,在 js 中,就会变成一个非精确值。相信大家有所耳闻过这一点。

> Math.pow(2, 53) + 1
9007199254740992
> Math.pow(2, 53) + 2
9007199254740994

所以这里不敢让它们直接相乘。

解法就是,拆拆拆!

把 0x5bd1e995 拆成 0x5bd1 和 0xe995。都是16位的,与32位相乘之后,最多48位,js中可以精确表示。

var MURMURHASH_M = 0x5bd1e995;
var L16MURMURHASH_M = MURMURHASH_M >>> 16; // 0x5bd1
var R16MURMURHASH_M = MURMURHASH_M & 0xffff; // 0xe995

L16MURMURHASH_M * k 之后,得到一个最多48位的数。这个数,我们能使用到的部分,是最右的 16 位。因为这个结果值由于某个入参被右移了16位。所以得到结果之后,需要把结果左移16位。而一共就那么32位,左移之后右边全是0。所以有效部分只有16位。

将上述的结果,再加上 R16MURMURHASH_M * k 的值,这个值是最多48位的。与上述32位的结果相加,最多产生一个49位的数。可以精确表示。

所以这个正整数相乘的溢出部分,我们的写法是:

k = (k * L16MURMURHASH_M << 16) + k * R16MURMURHASH_M

后来 es6 出来了一个一个 Math.imul 函数,原生支持我们要的结果。用 Math.imul 改写这个地方之后,速度是原来的 2.5 倍左右。

总结

现在的实现在这里:https://github.com/node-modules/node-murmurhash/blob/master/lib/murmur.js

我就不贴出来了,大家可以对比着看。纯 js 版本。

之前 c 语言版本的速度,对于这样一个 buffer:new Buffer('haha, this is key')。每秒是 800w 次这样。

使用 Math.imul 之前,js 版本也是 800w 次左右,持平。使用了 Math.imul 之后,现在是 2000w 次。

faster than c!!! https://github.com/felixge/faster-than-c

20 回复

这个结果和 jedis 中的 murmurhash 计算结果一致吗?我们有node的系统也遇到了同样的问题,自己实现的发现都有问题

@pangnate 有什么问题?

@alsotang 我是说我们自己实现的结果不一致。场景是实现jedis里面一致的陌陌分配算法,读取redis集群的用户信息。

回头拿这个试一下

@pangnate 有可能那个是变种,也可能那个是 V3 版本。去看看 jedis 源码照着改就好了

吊,发现楼主离开阿里后牛逼了许多!c慢应该是binding有消化。 自豪地采用 CNodeJS ionic

赞,可惜我自己看不懂😂

来自炫酷的 CNodeMD 越来越喜欢material design😁

@fengmk2 嗯嗯。binding 挺耗性能的。文章中,Buffer.readInt32LE 竟然不如直接操作二进制快。

MurmurHash 用来对分片片键做hash,然后路由是不是非常适合?

@DoubleSpout 路由??可以再描述一下吗?

JS 内部机制所有数字都是浮点型,用逻辑运算符的话会先强直转整形,算好之后再转回来——性能消耗。

所以一般不推荐在 JS 里面写逻辑运算。

这一点在阮老师的某一篇文章里面也有提到过。

各种hack啊, 吊吊吊!

@xadillax Buffer 库比 js 强转更慢。。这如何是好

@alsotang 并没有办法,或者我不知道

说到 buffer,以前我写过一个解析 Minecraft 的 nbt 格式文件的包。

https://github.com/boogeedoo/mcnbt

@xadillax 那游戏我在手机上面下了,45元买的…玩了不够10分钟

不愧是大佬,即使今天来看也有不少收获

@zy445566 感谢支持!

回到顶部