JVM 上最快的 Bloom filter 實現

colobu.com/2016/07/02/bloom-filter-for-scala/

本文介紹的是我用Scala實現的Bloom filter。 源代碼在github（https://github.com/alexandrnikitin/bloom-filter-scala）上。依照性能測試結果，它是JVM上的最快的Bloom filter實現。零分配(Zero-allocation)和高度優化的代碼。 無內存限制，所以沒有包含元素的數量限制和可控的誤報率(false positive rate)。

擴展：可插拔的Hash演算法，任意的元素類型。

沒錯，它使用sun.misc.unsafe。

1 介紹

「A Bloom filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not. In other words, a query returns either 「possibly in set」 or 「definitely not in set」. Elements can be added to the set, but not removed,」 says Wikipedia.

Bloom filter 是由 Howard Bloom 在 1970 年提出的二進位向量數據結構，它具有很好的空間和時間效率，被用來檢測一個元素是不是集合中的一個成員。如果檢測結果為是，該元素不一定在集合中；但如果檢測結果為否，該元素一定不在集合中。因此Bloom filter具有100%的召回率。這樣每個檢測請求返回有「在集合內（可能錯報）」和「不在集合內（絕對不在集合內）」兩種情況，可見 Bloom filter 是犧牲了正確率和時間以節省空間。 引自 百度百科

簡而言之，Bloom filter是:

• 優化內存佔用， 當整個集合太大而不能全部放到內存中。Optimization for memory. It comes into play when you cannot put whole set into memory.

• 解決成員存在性的問題。它可以回答下面的問題：一個元素屬於一個集合還是不屬於？

• 概率(有損)數據結構。它可以返回一個元素有多大的概率屬於一個集合

後面這篇文章介紹的Bloom filter很詳盡 - 「What are Bloom filters, and why are they useful?」（https://sc5.io/posts/what-are-bloom-filters-and-why-are-they-useful/） by @Max Pagels。我沒必要再獻醜了，如果你還不熟悉Bloom filter不妨看一看。

2 為何再造輪子？

因為性能或者內存限制的原因，已有的Bloom filter並不能滿足我們的需求，或者你發現你可以做的更好。坦率的說，都不是。只不過有時候你厭倦了而已。(作者吐槽，可忽略之)

主要的原因是性能。當開發高性能和低延遲的系統的時候，你可不想被外部的庫所拖累，甚至分配了很多的內存。你的注意力應該集中在業務邏輯上，依賴的庫應該儘可能的有效。

另一個原因還是內存限制。所有的實現都會因為JVM數組的大小的限制而受限制。JVM中，數字使用整數integer做索引，所以數組的最大長度也就是整數的最大值2147483647。如果我們創建一個元素類型為long的數組存儲比特位bit的值，那麼最多我們可以存儲64 bit * 2147483647 = 137438953408 bits,大概需要15 GB左右的內存。你可以放入大約10000000000左右的元素到誤報率為0.1%的Bloom filter。這對於大部分軟體來說足夠了，但是當你處理大數據，比如URL，圖標廣告，實時競價請求或者是事件流的時候，100億的數據只是一個起步量。當然你可以有一些變通的辦法：部署多個Bloom filter,將它們分佈到多個節點，或者設計你的軟體適應這些限制，但這些辦法並不總是有效，可能花費較高護著不滿足你的架構。

讓我們看看當前已有的一些Bllom filter的實現。

2.1 Google guava

Guava是Google開發的一個高質量的核心庫，它包含集合、基本數據、併發、I/O、Cache等模塊。 它也包含一個Bloom filter實現。Guava是我的初始選擇，它經受考驗、也很快，但是……

令人咂舌的是，它會額外分配內存。我使用Google的Allocation Instrumenter監控所有的分配allocation。下面的分配監控顯示了檢查包含100字元的字元串是否存在於一個Bloom filter中:

I just allocated the object [B@39420d59 of type byte whose size is 40 It's an array of size 23

I just allocated the object java.nio.HeapByteBuffer[pos=0 lim=23 cap=23] of type java/nio/HeapByteBuffer whose size is 48

I just allocated the object com.google.common.hash.Murmur3_128HashFunction$Murmur3_128Hasher@5dd227b7 of type com/google/common/hash/Murmur3_128HashFunction$Murmur3_128Hasher whose size is 48

I just allocated the object [B@3d3b852e of type byte whose size is 24 It's an array of size 1

I just allocated the object [B@14ba7f15 of type byte whose size is 24 It's an array of size 1

I just allocated the object sun.nio.cs.UTF_8$Encoder@55cb3b7 of type sun/nio/cs/UTF_8$Encoder whose size is 56

I just allocated the object [B@497fd334 of type byte whose size is 320 It's an array of size 300

I just allocated the object [B@280c3dc0 of type byte whose size is 312 It's an array of size 296

I just allocated the object java.nio.HeapByteBuffer[pos=0 lim=296 cap=296] of type java/nio/HeapByteBuffer whose size is 48

I just allocated the object [B@6f89ad03 of type byte whose size is 32 It's an array of size 16

I just allocated the object java.nio.HeapByteBuffer[pos=0 lim=16 cap=16] of type java/nio/HeapByteBuffer whose size is 48

I just allocated the object 36db757cdd5ae408ef61dca2406d0d35 of type com/google/common/hash/HashCode$BytesHashCode whose size is 16

一共1016個位元組。想象一下，我們計算一個短字元串的hash值，檢查它相應的bit位設置已經設置，它需要分配大於1Kb的數據。太多了。那你可能會說內存佔用已經很小了，好吧，當你做一個單獨的微性能測試的時候，影響不是很大，但是在產品級的環境中，它會變得更糟：它會影響GC，導致分配變慢，觸發GC，導致更高的延遲等。

不管怎樣，review一下代碼會很有趣，有時候你會發現一些復活節彩蛋在裡面，比如下面的例子：

這些註釋行來自Naughty by Nature說唱組合的歌曲「O.P.P.」,在上世紀90年代早期很流行。這段代碼的開發者可能那時是四五十歲的人(偏題了)。

2.2 Twitter Algebird

Algebird 「為Scala提供的抽象代數庫，這些代碼主要是用於建立聚合系統（通過Scalding或Storm）。 它是函數式functional，不可變

immutable, monadic,但是非常非常非常慢，並且僅僅支持字元串作為元素類型。字元串是萬能的數據格式，你可硬用它存任何值 :) 。

它使用人人皆愛的MurmurHash3演算法，它是最好的通用的hash演算法。它計算出128-bit的 hash值，分割成4個32-bit的數字。然後它為每個32-bit的數字設置相應的位，而不是整個的hash值。這是相當有爭議的設計，我進行了粗略的測試，測試表明Teitter Bloom filter有超過 10% 的誤報率。

更深一步，有趣的是Twitter Bloom filter 底層使用 EWAHCompressedBitmap,它是一個壓縮的可替代BitSet的實現。它專門為內存佔用而優化，適合稀疏數據的場景。比如，如果你的位數從1000000開始，EWAH可以優化set而不會為前面的0位分配內存。集合的操作如交集、並集和差也更快。但是隨機訪問卻很慢。 而且hash的目標就是有一個均勻分佈的hash值，越均勻越好。這兩點就排除了使用壓縮bitset的好處。我做了一點點測試來檢查整個的內存分配，結果顯示Twitter Bloom filter比我的實現還要分配更多的內存。 同樣，在我看來，Twitter的實現也是相當有爭議。

內存檢查的結果很長我就不貼了。為包含100個字元的字元串的檢查要分配1808位元組，我哭!

同樣，它是函數式functional, 不可變immutable, 使用持久化數據結構, monad, 但這些不足以讓我們使用它。 大話說在前， 它的讀性能要比我的實現慢10倍，寫要慢100倍。

2.3 ScalaNLP』s Breeze

Breeze is a generic, clean and powerful Scala numerical processing library… Breeze is a part of ScalaNLP project, a scientific computing platform for Scala

Breeze的介紹看起來很有吸引力，如清爽的新風，但是，有一個花招在它的實現里。它直接使用對象的hash值。 「WTF,我鍾愛的MurmurHash3哪去了」，你可能會問。MurmurHash3僅僅用來計算最終的對象的hash值，沒錯，它可以和任意類型一起工作，但是你不會知道你的大數據集的細微差別(編者按:較難理解，需要配合代碼一起理解。 英文原意為：It』s used only for 「finalizing」 the object』s hash. Yeah, it works with any type out-of-the-box but if you don』t know that little nuance you are done with large datasets.)

測試中它會分配544位元組，看看代碼你會發現通用的Scala的問題：

看起來很簡潔：for語句，延遲計算,漂亮的DSL。但是當它編譯成Java代碼的時候就不那麼好看了，它會分配很多對象: intWrapper, RichInt, Range.Inclusive, VectorBuilder/Vector, boxing/unboxing 等等：

return (IndexedSeq)RichInt$.MODULE$.to$extension0(Predef$.MODULE$.intWrapper(0), numHashFunctions).map(new Serializable(hash1, hash2) {

public final int apply(int i)

{

return apply$mcII$sp(i);

}

public int apply$mcII$sp(int i)

{

int h = hash1$1 + i * hash2$1;

int nextHash = h >= 0 ? h : ~h;

return nextHash % $outer.numBuckets;

}

public final volatile Object apply(Object v1)

{

return BoxesRunTime.boxToInteger(apply(BoxesRunTime.unboxToInt(v1)));

}

public static final long serialVersionUID = 0L;

private final BloomFilter $outer;

private final int hash1$1;

private final int hash2$1;

public

{

if(BloomFilter.this == null)

{

throw null;

} else

{

this.$outer = BloomFilter.this;

this.hash1$1 = hash1$1;

this.hash2$1 = hash2$1;

super;

return;

}

}

}

, IndexedSeq$.MODULE$.canBuildFrom);

震撼嗎？我想你被震驚了。接下來看看我的實現。

3 我是如何實現的？

一句話，我重新實現了Bloom filter的數據結構。源代碼在github上，可以通過maven repository引用:

libraryDependencies += "com.github.alexandrnikitin" %% "bloom-filter" % "0.3.1"

下面是使用的例子：

import bloomfilter.mutable.BloomFilter

val expectedElements = 1000

val falsePositiveRate = 0.1

val bf = BloomFilter[String](expectedElements, falsePositiveRate)

bf.add("some string")

bf.mightContain("some string")

bf.dispose

3.1 Unsafe

一個重要的設計就是底層使用sun.misc.unsafe包。使用它分配一塊內存來保存bit，所以你需要主動dispose Bloom filter 實例和不受管的內存釋放。而且我的實現還使用 usafe做了一些花招以避免內存分配，比如直接訪問字元串內部的char數組。

3.2 type class模式

我的實現是可擴展的，你可以為任意類型使用任意的hash演算法。它通過type class模式實現。如果你不熟悉它，你可以閱讀@Daniel Westheide的文章 「The Neophyte』s Guide to Scala」。

基本上，你所需的就是實現CanGenerateHashFrom[From] trait,就像這樣:

trait CanGenerateHashFrom[From] {

def generateHash(from: From): Long

}

不幸的是，它是invariant不變類型。我想實現為逆變類型contravariant但是Scala編譯器不能正確的解決contravariant implicits,將來在Dotty編譯器中會支持。

預設地提供了一個MurmurHash3的通用實現。我使用Scala實現了它，比Guava、Algebird、Cassandra的實現更快（希望我沒有犯錯）。為Long、String、Array[Byte]提供可開箱即用的庫。作為一個福利，為無限唯一性(unlimited uniqueness)提供了128bit的版本。

3.3 零分配Zero-allocation

我的Bloom filter實現沒有分配任何對象，代碼被高度優化。我計劃寫一篇獨立的文章來描述這些優化，敬請關注。通過一系列的unsafe技巧來實現的。下面是為String類型實現的 CanGenerateHashFrom trait:

implicit object CanGenerateHashFromString extends CanGenerateHashFrom[String] {

import scala.concurrent.util.Unsafe.{instance => unsafe}

private val valueOffset = unsafe.objectFieldOffset(classOf[String].getDeclaredField("value"))

override def generateHash(from: String): Long = {

val value = unsafe.getObject(from, valueOffset).asInstanceOf[Array[Char]]

MurmurHash3Generic.murmurhash3_x64_64(value, 0, from.length, 0)

}

}

使用unsafe.objectFieldOffset方法獲取String類型的value欄位，它是字元串底層的char數組。然後使用unsafe.getObject方法訪問字元數組,用來計算hash值。

不幸的是，128-bit的實現會分配一個對象。我在(Long, Long) tuple和 ThreadLocal的欄位選擇上很猶豫，對於整體的性能，沒有影響，有什麼意見嗎？在我的有生之年我希望能看到JVM的值類型, @Gil Tene的ObjectLayout嘗試實現它。

限制

你可能已經注意到了，當前實現有一些限制。CanGenerateHashFrom[From] trait是不可變的invariant,它不允許回退到對象的hashCode方法。你需要為你的類型實現它的hash演算法。但我相信，為了性能這也是值得的。

並不是所有的JVM都支持，因為底層使用了「unsafe」 包，而且這也沒有退路(fallback )的實現。

sun.misc.Unsafe至少從2004年Java1.4開始就存在於Java中了。在Java9中，為了提高JVM的可維護性，Unsafe和許多其他的東西一起都被作為內部使用類隱藏起來了。但是究竟是什麼取代Unsafe不得而知。 摘自: http://www.importnew.com/14511.html

可以在Java中用它嗎？

可以，但是代碼不會和Scala一樣漂亮，當然你已經習慣了這一切。Java中沒有implicit，而且Java編譯器也不會幫你調用它。在Java中使用它很醜但是能工作：

import bloomfilter.CanGenerateHashFrom;

import bloomfilter.mutable.BloomFilter;

long expectedElements = 10000000;

double falsePositiveRate = 0.1;

BloomFilter<byte> bf = BloomFilter.apply(

expectedElements,

falsePositiveRate,

CanGenerateHashFrom.CanGenerateHashFromByteArray$.MODULE$);

byte element = new byte[100];

bf.add(element);

bf.mightContain(element);

bf.dispose;

4 性能benchmark

我們都喜歡性能基準數據，對不？令人興奮的數字在空中遊盪，是那麼的迷人。如果你準備寫性能基準的測試，請使用JMH。 它是Oracle的性能工程師 @Aleksey Shipilev創建的一個微性能基準庫： 「for building, running, and analyzing nano/micro/milli/macro benchmarks written in Java and other languages targeting the JVM.」， @Konrad Malawski寫了一個SBT的插件。

下面是一個String類型的基準測試，其它類型的測試結果和此類似：

[info] Benchmark (length) Mode Cnt Score Error Units

[info] alternatives.algebird.StringItemBenchmark.algebirdGet 1024 thrpt 20 1181080.172 ▒ 9867.840 ops/s

[info] alternatives.algebird.StringItemBenchmark.algebirdPut 1024 thrpt 20 157158.453 ▒ 844.623 ops/s

[info] alternatives.breeze.StringItemBenchmark.breezeGet 1024 thrpt 20 5113222.168 ▒ 47005.466 ops/s

[info] alternatives.breeze.StringItemBenchmark.breezePut 1024 thrpt 20 4482377.337 ▒ 19971.209 ops/s

[info] alternatives.guava.StringItemBenchmark.guavaGet 1024 thrpt 20 5712237.339 ▒ 115453.495 ops/s

[info] alternatives.guava.StringItemBenchmark.guavaPut 1024 thrpt 20 5621712.282 ▒ 307133.297 ops/s

// My Bloom filter

[info] bloomfilter.mutable.StringItemBenchmark.myGet 1024 thrpt 20 11483828.730 ▒ 342980.166 ops/s

[info] bloomfilter.mutable.StringItemBenchmark.myPut 1024 thrpt 20 11634399.272 ▒ 45645.105 ops/s

[info] bloomfilter.mutable._128bit.StringItemBenchmark.myGet 1024 thrpt 20 11119086.965 ▒ 43696.519 ops/s

[info] bloomfilter.mutable._128bit.StringItemBenchmark.myPut 1024 thrpt 20 11303765.075 ▒ 52581.059 ops/s

我的實現大致要比Goole Guava的實現快2倍， 比Twitter Algebird快10 ~ 80倍，其它的benchmark你可以在github上的「benchmarks』模塊找到。

警告：這是在獨立環境中的綜合測試。通常吞吐率和延遲的差別要比產品環境中要大，因為它會對GC有壓力，導致分配很慢，更高的延遲，觸發GC等。

5 用在哪裡？

高性能和低延遲系統。

大數據和機器學習系統，有巨量唯一的數據。

5.1 什麼時候不用它?

如果你當前的解決方案已滿足需求，大部分軟體都不需要這麼快。

你只信任那些大公司如Google、Twitter出品的已被證明的、經受考驗的庫。

歡迎你的意見和建議。下一步我會實現一個穩定的(Stable) Bloom filter 數據結構，因為目前沒有好的實現。我計劃研究一下 Cuckoo filer 數據結構。對此有何經驗嗎？