search
JVM 上最快的 Bloom filter 實現

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 數據結構。對此有何經驗嗎?

熱門推薦

本文由 一點資訊 提供 原文連結

一點資訊
寫了5860317篇文章,獲得23246次喜歡
留言回覆
回覆
精彩推薦