Scala
by Alexandr Nikitin

[译]JVM上最快的Bloom filter实现

英文原始出处: Bloom filter for Scala, the fastest for JVM

本文介绍的是我用Scala实现的Bloom filter。 源代码在github上。依照性能测试结果，它是JVM上的最快的Bloom filter实现。零分配(Zero-allocation)和高度优化的代码。 无内存限制，所以没有包含元素的数量限制和可控的误报率(false positive rate)。
扩展：可插拔的Hash算法，任意的元素类型。
没错，它使用sun.misc.unsafe。

介绍

"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?” by @Max Pagels。我没必要再献丑了，如果你还不熟悉Bloom filter不妨看一看。

为何再造轮子？

因为性能或者内存限制的原因，已有的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的实现。

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年代早期很流行。这段代码的开发者可能那时是四五十岁的人(偏题了)。

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倍。

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的问题：

1
2
3
4
5
6
7
for {
  i <- 0 to numHashFunctions
} yield {
  val h = hash1 + i * hash2
  val nextHash = if (h < 0) ~h else h
  nextHash % numBuckets
}

看起来很简洁：for语句，延迟计算,漂亮的DSL。但是当它编译成Java代码的时候就不那么好看了，它会分配很多对象: intWrapper(), RichInt, Range.Inclusive, VectorBuilder/Vector, boxing/unboxing 等等：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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());

震撼吗？我想你被震惊了。接下来看看我的实现。

我是如何实现的？

一句话，我重新实现了Bloom filter的数据结构。源代码在github上，可以通过maven repository引用:

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

下面是使用的例子：

1
2
3
4
5
6
7
8
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()

Unsafe

一个重要的设计就是底层使用sun.misc.unsafe包。使用它分配一块内存来保存bit，所以你需要主动dispose Bloom filter 实例和不受管的内存释放。而且我的实现还使用 usafe做了一些花招以避免内存分配，比如直接访问字符串内部的char数组。

type class模式

我的实现是可扩展的，你可以为任意类型使用任意的hash算法。它通过type class模式实现。如果你不熟悉它，你可以阅读@Daniel Westheide的文章 “The Neophyte’s Guide to Scala”。

基本上，你所需的就是实现CanGenerateHashFrom[From] trait,就像这样:

1
2
3
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的版本。

零分配Zero-allocation

我的Bloom filter实现没有分配任何对象，代码被高度优化。我计划写一篇独立的文章来描述这些优化，敬请关注。通过一系列的unsafe技巧来实现的。下面是为String类型实现的 CanGenerateHashFrom trait:

1
2
3
4
5
6
7
8
9
10
11
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中使用它很丑但是能工作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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();

性能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等。

用在哪里？

高性能和低延迟系统。

大数据和机器学习系统，有巨量唯一的数据。

什么时候不用它?

如果你当前的解决方案已满足需求，大部分软件都不需要这么快。

你只信任那些大公司如Google、Twitter出品的已被证明的、经受考验的库。

你想要开箱即用的库。

下一步

欢迎你的意见和建议。下一步我会实现一个稳定的(Stable) Bloom filter 数据结构，因为目前没有好的实现。我计划研究一下 Cuckoo filer 数据结构。对此有何经验吗？

谢谢