Spark之BloomFilter有趣的bitwise运算-阿里云开发者社区

开发者社区> dasein58> 正文

Spark之BloomFilter有趣的bitwise运算

简介: 最近好奇的研究了下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) { d
+关注继续查看

最近好奇的研究了下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中找到了答案:

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自己真是孤陋寡闻了,看来平时还得多看看源码。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Kubernetes + Spring Cloud 集成链路追踪 SkyWalking
分布式系统的应用程序性能监视工具,专为微服务、云原生架构和基于容器(Docker、K8s、Mesos)架构而设计。 提供分布式追踪、服务网格遥测分析、度量聚合和可视化一体化解决方案。
4 0
冬季实战营第一期学习总结
冬季实战营第一期:https://developer.aliyun.com/adc/series/wintercamplist1
9 0
《冬季实战营第一期:从零到一上手玩转云服务器》实践报告
在大数据时代,制作个人网站,学会ECS云服务器是必要之选。 本文主要说明第一期冬季实战营ECS云服务器实践目的,实践步骤以及实践成果。完成门户网站的搭建,可以根据公司的需求自定义门户网站的内容。
10 0
从零到一上手玩转云服务器
从零到一上手玩转云服务器
10 0
大学生第一次使用阿里云的感受
阿里云、服务器、tomcat、xshell
8 0
06_spring_ 依赖注入| 学习笔记
快速学习 06_spring_ 依赖注入
11 0
【冬季实战营第一期:从零到一上手玩转云服务器】学习报告
这篇内容主要是描述了我在学习实战营第一期课程中遇到的问题和部分解决方案。 注:为了复现问题,因此多次体验并截图,因此可能存在前后图片中账号不一致的问题。不过描述的问题是确实存在的。
8 0
05_spring_ 配置文件| 学习笔记
快速学习05_spring_ 配置文件
6 0
初始ECS
物联网学习的硬性需求,我们需要搭建一台自己的服务器,在不断查找资料和方法后,获知阿里云ECS云服务器有学生体验资格,继而我将利用ECS云服务器搭建一个自己的EMQX服务器端。
17 0
+关注
765
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载