Spark之BloomFilter有趣的bitwise运算 2018-11-28 11:48:22 最近好奇的研究了下Spark的BloomFilter的实现，发现其`org/apache/spark/util/sketch/BitArray.java`对bit处理的实现很巧妙（源码可能是从其他开源项目借鉴的也不好说），从中学到不少东西，记录下。 ## BitArray巧妙的核心设计 BitArray内部采用`long[] data`来表示一个大的bitmap，long类型相比int在相同的数组个数下可以存放更多的bit信息。 比较有意思的是set方法的实现，核心代码如下： ``` // 将指定index位置的bit位设置为1，表示指定的index处有值 void set(long index) { data[(int) (index >>> 6)] |= (1L << index); } ``` 估计不少读者看到这行代码比较懵逼，由于工作中使用bit操作的场景不多，至少我当时是比较懵逼的。 先来说下`>>>`, `>>`是按位右移操作(bitwise shift)相信大家都清楚，`>>`是保留符号位的，`>>>`则是无符号右移，也就说要移的数为正，则高位补0，而若该数为负数，则右移后高位同样补0，还是看个例子比较直观： ``` jshell> -2 >> 1 $1 ==> -1 jshell> -2 >>> 1 $2 ==> 2147483647 ``` 那么`index >>> 6`又是什么鬼？ Java中一个long类型占8个byte，也就是64个bit，如果让我们实现给定一个index，判断该index属于数组的第几个元素，我们可能会这么实现： ``` data[index / 64] ``` 而2^6刚好是64，`index >>> 6`则相当于`index / 64`，而按位(bitwise)操作效率上是高于除法的，所以，会看到代码里采用了`index >>> 6`的实现。 现在定位到了index所处data数组中的位置了，怎么给指定的index设置bit位为1呢？ 假如我们手头上有个int类型的变量a，以`a |= (1 << 3)`为例：采用按位或的操作就可以将a的第3个bit位设置为1，这个比较基础，相信大家都明白。 BitArray中让人懵逼的是直接对一个long类型的值进行了`1L << index`操作，如果让我实现的话，我会这么做：`1 << (index % 64)`，我们知道long只有64位，如果index大于64位呢？ 如果不实际运行代码，`1L << 65`，由于移位数超出了long的表示范围，估计不少人会认为得到的值是0吧，我们先看下实际的结果： ``` jshell> 1L << 65 $1 ==> 2 ``` 为啥会是这样？各种找资料，最后在Oracle官方的[Java SE Specifications](https://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.19)中找到了答案： > If the promoted type of the left-hand operand is long, then only the six lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & (§15.22.1) with the mask value 0x3f (0b111111). The shift distance actually used is therefore always in the range 0 to 63, inclusive. 原来Java内部在做移位(shift operation)操作时，会将右边的shift distance和0x3f按位与后，在做移位操作，这样就能保证移位的范围总是0~63。也就是说对于long类型的位移操作Java内部自动给我们做了`% 64`的处理。类似的，如果是int类型的操作，Java内部会将移位的距离`& 0x1f`确保移位范围在0~31。 我们把`1L << index`按Java内部的处理拆解下： ``` 1L << index 相当于 1L << (index & 0x3f) 相当于 1L << (index & 0b111111) 相当于 1L << (index % 2^6) 相当于 1L << (index % 64) ``` 在回头看下`1L << 65`其实就是`1L << (65 % 64)`等价于`1L << 1`得到的值是2。这个问题就比较清楚了。 回到BitArray的set方法的实现上： ``` void set(long index) { data[(int) (index >>> 6)] |= (1L << index); } // 等价于 void set(long index) { data[index / 64] |= (1L << (index % 64)); } ``` 这下就不懵逼了。bitwise操作性能更好，`data[index / 64] |= (1L << (index % 64))`看起来更直观，顺便查了下这种操作JVM是否会自动优化为bitwise操作，文章提到会优化。 ## 一些常用的bitwise运算实例 鉴于bitwise的操作比较有意思，我整理了些常用实例，至少以后遇到这种操作不让自己那么懵逼。 **判断int型变量a是奇数还是偶数** ``` a & 1 = 0 // 偶数 a & 1 = 1 // 奇数 ``` **取模运算转化成位运算 (在不产生溢出的情况下)** ``` a % (2^n) 等价于 a & (2^n - 1) 如：a % 32 等价于 a & 0x1f ``` **乘法运算转化成位运算 (在不产生溢出的情况下)** ``` a * (2^n) 等价于 a << n ``` **除法运算转化成位运算 (在不产生溢出的情况下)** ``` a / (2^n) 等价于 a >> n ``` **取相反数** ``` x的相反数为~x + 1 // 原理上和计算机采用二进制补码（2's complement）的表示形式有关 ``` **其他** ``` if (x == a): x = b else: x = a 等价于：x = a ^ b ^ x ``` ## 附：Spark的BloomFilter之Hash算法 最后看了下Spark内部的BloomFilter关于Hash算法选择的问题，发现其采用的是Murmur3Hash，第一次听说这个Hash算法，了解下是谷歌的东西，优势在于性能。Spark源码里直接将MurmurHash从Guava包中搬过来了。 Spark内部除了BloomFilter在用MurmurHash以外，UnsafeRow在计算Hash时，也有用到。 查了下MurmurHash应用的还是挺广泛的，Redis，Memcached，Cassandra，HBase，Lucene都有在用。对于MurmurHash自己真是孤陋寡闻了，看来平时还得多看看源码。 ## References - <https://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.19> - <https://blog.csdn.net/abcd1f2/article/details/53463657> 非特殊说明，均为原创，原创文章，未经允许谢绝转载。 原始链接：Spark之BloomFilter有趣的bitwise运算 赏 Prev go为channel设置超时的正确姿势 Next NodeMcu刷入固件无法启动的问题
