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) {
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官方的 ofollow,noindex">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自己真是孤陋寡聞了，看來平時還得多看看原始碼。