第26章 高级库设计：构建一个布隆过滤器

布隆过滤器介绍

布隆过滤器（Bloom Filter）是类似集合的一种数据结构，它的特点是空间利用的高效性。布隆过滤器只支持两种操作：插入和成员查询。与常规的集合数据结构不同，布隆过滤器可能会给出不正确的结果。如果我们查询的某个元素存在，布隆过滤器会返回肯定的结果。但是如果我们查询一个之前没有插入过的元素，那么布隆过滤器可能会返回错误的结果，即声称它是存在的。

对大多数应用来说，低概率的误判是可以容忍的。举个例子，网络流量整形（traffic shaper）的主要工作是限制批量传输（比如 BitTorrent），使得一些交互式会话（比如 ssh 或者游戏）可以得到优秀的响应时间。流量整形可能会使用布隆过滤器来判断一个特定会话的数据包是批量的还是交互的。如果布隆过滤器在 10000 个批量数据包中误判其中的 1 个为交互式数据包且没有截止，也不会造成任何问题。

布隆过滤器吸引人的地方在于它的空间效率。举个例子，假设现在有一个包含一百万个单词的词典，我们想基于这个词典构建一个拼写检查器，若使用集合数据结构则可能会消耗 20MB 的空间。相比之下，布隆过滤器会消耗大约 0.5MB，代价是漏掉大约 1% 拼错的单词。

布隆过滤器的内部非常简单。它由一个位数组（bit array）和少数哈希函数组成。我们使用 k 表示哈希函数的数量。向布隆过滤器中插入数据时，先用哈希函数为数据计算出 k 个哈希值，然后在位数组中将这些位设置为 1。如果我们想要看看某个数据是否存在，那么就为这个数据计算出 k 个哈希值，然后检查位数组中这些哈希值的位是否都为 1。

下面通过一个例子理解整个过程。现在我们想向布隆过滤器中插入字符串 "foo" 和 "bar" ，这个布隆过滤器有 8 位宽，并且我们有两个哈希函数：

  • 假设用两个哈希函数分别计算 "foo" 的哈希值，得到 1 和 6
  • 在位数组中置位 1 和 6
  • 同样用 1 中的两个哈希函数计算 "bar" 的哈希值，得到 6 和 3
  • 在位数组中置位 6 和 3

这个例子解释了为什么我们不能从布隆过滤器中移除一个元素：插入 "foo" 和 "bar" 都会导致位数组中的第 6 位被置位。

假设我们现在想要查询布隆过滤器中 "quux" 和 "baz" 是否存在：

  • 用和之前相同的两个哈希函数计算 "quux" 的哈希值，得到 4 和 0
  • 检查位数组中的位 4，位 4 没有被置位，所以 "quux" 不可能存在，我们不需要检查位 0
  • 计算 “baz” 的两个哈希值，得到 1 和 3
  • 检查位数组中的位 1 ，位 1 被置位；同样，位 3 也被置位。所以我们认为 "baz" 存在。但是实际上 "bar" 并不存在，这里我们得到了一个误判。

如果你想了解布隆过滤器的一些使用案例，请参阅 [Broder02]

使用场景与封装设计

不是所有布隆过滤器的使用需求都完全相同。在某些使用场景中，只需要一次性创建布隆过滤器，之后只有查询。对于其他应用，我们可能需要在创建布隆过滤器之后持续更新。我们通过把可变和不可变的 API 放在不同的模块中来对它们实施分离，其中 BloomFilter 用于实现不可变的布隆过滤器，而 BloomFilter.Mutable 则用于实现可变的布隆过滤器。

我们将可变与不可变的API分离，通过把他们放在不同的模块中： BloomFilter 用于不可变的代码，BloomFilter.Mutable 用于可变代码。

另外，我们将创建一些辅助模块，这些模块不会在公开的API中出现，但它们可以让内部代码变得更清晰。

最后，我们让API的使用者提供用来产生多个哈希的函数。这个函数的类型是 a -> [Word32] 。我们将使用这个函数返回的全部哈希值，所以这个函数返回的列表不能为无穷的。

基本设计

跟前面介绍布隆过滤器实现原理时提到的数据结构一样，我们的 Haskell 版布隆过滤器也会用到一个位数组和一个能够计算出多个哈希值的函数。

  1. -- file: BloomFilter/Internal.hs
  2. module BloomFilter.Internal
  3.     (
  4.       Bloom(..)
  5.     , MutBloom(..)
  6.     ) where
  7.  
  8. import Data.Array.ST (STUArray)
  9. import Data.Array.Unboxed (UArray)
  10. import Data.Word (Word32)
  11.  
  12. data Bloom a = B {
  13.       blmHash  :: (a -> [Word32])
  14.     , blmArray :: UArray Word32 Bool
  15.     }

因为 BloomFilter.Internal 模块纯粹是为了控制名称的可见性而存在的，所以在创建 Cabal 包时，我们将不会导出这个模块。我们把 BloomFilter.Internal 导入可变和不可变的模块中，但是我们会从各个模块中重新导出和模块 API 相关的类型。

拆箱，提升和bottom

与其他 Haskell 的数组不同， UArray 包含未装箱的值。

对于一个常规的 Haskell 类型来说，它的值既可以是完全求值的（full evaluated），也可以是未求值的形式程序（thunk），又或者特殊值 ⊥ ，发音为（有时候也写作） “bottom”。值 ⊥ 是一个用来表示计算未成功的占位符。这里的计算可以有多种形式。它可能是一个无限循环，一个 error 应用，或者特殊值 undefined 。

一个可以包含bottom的类型被称为已提升的。所有常规Haskell类型都是已提升的。实际中，这意味着我们可以写 error "eek!" 或者 undefined 来代替常规表达式。

存储形式程序和 bottom 的能力会带来性能上的损耗：这种能力增加了额外的间接层。为了理解为什么我们需要这种间接，考虑 Word32 类型。这种类型的值是全 32 位宽的，所以在 32 位系统上，没有办法直接用 32 位来编码bottom。运行时系统不得不维护，并且检查一些额外的数据来跟踪这个值是不是 ⊥ 。

一个未装箱的值没有这种间接性。通过未装箱可以获得性能，但是牺牲了表示形式程序或者 bottom 的能力。因为未装箱的数组可以比常规 Haskell 的数组更加紧凑，所以这对于大量数据和位来说是一个非常好的选择。

GHC 通过将 8 个数组元素组装成 1 个字节，实现了一种 Bool 类型的 UArray 数组，这种数组非常适合我们的需求。

ST monad

正如前面的 修改数组元素 部分所说，因为修改一个不可变数组需要对整个数组进行复制，所以这种修改的代价是非常高的。即使使用 UArray ，这一问题仍然会存在。那么我们如何才能将复制不可变数组的代价降低至我们可以承受的水平呢？

在指令式语言中，我们可以简单地原地修改数组元素，并且在 Haskell 里面也可以这样做。

Haskell 提供了一个特殊的 Monad，叫做 ST [58] （State Transformer） 。 ST 允许我们安全地工作在可变状态下。与 State Monad 相比，ST Monad 有一些额外的强大功能。

  • 解冻一个不可变数组并得到一个可变数组，接着原地对可变数组进行修改，然后在修改完成之后冻结出一个新的不可变数组。
  • 通过 可变引用（mutable references） 可以构建出一种数据结构，这种数据结构允许用户像命令式语言一样随时对其进行修改。对于那些尚未找到高效纯函数替代的命令式数据结构和算法来说，这个功能尤为重要。

IO Monad 同样提供了这些功能。两者的主要区别在于， ST Monad 是为了让用户能够从 Monad 中回退到纯 Haskell 代码中而设计的。和大部分 Haskell Monad（当然除了 IO ）一样，我们通过执行函数 runST 进入 ST Monad，然后通过从 runST 中 return 来退出。

当我们应用一个 Monad 的执行函数的时候，我们希望它可以反复运行：如果给予相同的函数体（body）和参数，我们每次都能得到相同的结果。这同样可以应用于 runST 。为了达到这种可重复性（repeatablility），ST Monad比 IO Monad 更加严格。我们不能读写文件，创建全局变量，或者创建线程。甚至，即使我们可以创建并且使用可变的引用和数组，类型系统也不允许它们逃逸到 runST 的调用方。在返回数据之前，可变数组必须被冻结（frozen）为不可变数组，并且可变引用不可以逃逸。

设计一个合格的输入API

我们需要讨论一下用来处理布隆过滤器的公开接口。

  1. -- file: BloomFilter/Mutable.hs
  2. module BloomFilter.Mutable
  3.     (
  4.       MutBloom
  5.     , elem
  6.     , notElem
  7.     , insert
  8.     , length
  9.     , new
  10.     ) where
  11.  
  12. import Control.Monad (liftM)
  13. import Control.Monad.ST (ST)
  14. import Data.Array.MArray (getBounds, newArray, readArray, writeArray)
  15. import Data.Word (Word32)
  16. import Prelude hiding (elem, length, notElem)
  17.  
  18. import BloomFilter.Internal (MutBloom(..))

在我们导出的函数当中，有几个函数和 Prelude 导出的函数具有相同的名称。这么做是经过考虑的：我们希望用户使用限制名称导入我们的模块，这减轻了用户记忆的负担，因为他们对 Prelude 中的 elem ，notElem 和 length 函数已经相当熟悉了。

在导入这种风格的模块时，我们通常会使用单个字母来作为前缀。例如，用户在代码中使用 import qualified BloomFilter.Mutable as M 导入模块，此时用户可以将导入模块中的 length 写为 M.length ，这保持了代码的紧凑型和可读性。

我们也可以不使用限制名称导入模块，但这样一来的话，我们就需要通过 import Prelude hiding (length) 来隐藏 Prelude 与模块相冲突的函数。我们不建议使用这种做法，因为它使读者容易忽视代码中的 length 并非 Prelude 模块的 length 。

当然，我们在上面定义的模块头中违背了这个规则：我们导入了 Prelude 并且隐藏了它的一些函数名。这是因为我们在模块中定义了自己的函数 length ，如果不先隐藏 Prelude 包中的同名函数，编译器将无法确定它该导出我们自定义的 length 还是 Prelude 中的 length 。

虽然导出完全限定名称 BloomFilter.Mutable.length 能够消除歧义，但它看起来更丑陋。这个决定对使用模块的用户没有影响，它仅仅针对我们自己 —— 黑盒的设计者，所以这里一般不会导致混淆。

创建一个可变的布隆过滤器

我们将可变布隆过滤器和不可变的 Bloom 类型均声明在 BloomFilter.Internal 模块中。

  1. -- file: BloomFilter/Internal.hs
  2. data MutBloom s a = MB {
  3.           mutHash :: (a -> [Word32])
  4.         , mutArray :: STUArray s Word32 Bool
  5.         }

STUArray 类型提供了可以在 ST monad 中使用的可变数组，我们可以使用 newArray 函数创建一个 STUArray 。下面的 new 函数属于 BloomFilter.Mutable 模块（译注：此处应为 module ，原著中此处为 function ）。

  1. -- file: BloomFilter/Mutable.hs
  2. new :: (a -> [Word32]) -> Word32 -> ST s (MutBloom s a)
  3. new hash numBits = MB hash `liftM` newArray (0,numBits-1) False

STUArray 的大多数方法实际上是 MArray 类型类的实现，这个类型类在 Data.Array.MArray 模块中定义。

有两个因素导致我们自己定义的 length 函数略显复杂：函数依赖于位数组对自己边界的记录，且 MArray 实例的 getBounds 函数有一个 monadic 类型。此外最终的结果还需要加 1，因为数组的上限比实际长度小 1。

布隆过滤器在添加元素时，需要将哈希函数计算出的所有位置位。 mod 函数确保了所有计算出的哈希值都限制在位数组范围之内，并将计算位数组偏移量的代码独立为一个函数。（译注：这里使用 mod 函数最好保证散列的范围是取模的倍数，否则使用 mod 会使散列结果倾向于某种概率分布。由于布隆过滤器和散列通常基于概率，因此应当避免概率分布过分偏离平均）

  1. -- file: BloomFilter/Mutable.hs
  2. insert :: MutBloom s a -> a -> ST s ()
  3. insert filt elt = indices filt elt >>=
  4.                                   mapM_ (\bit -> writeArray (mutArray filt) bit True)
  5.  
  6. indices :: MutBloom s a -> a -> ST s [Word32]
  7. indices filt elt = do
  8.   modulus <- length filt
  9.   return $ map (`mod` modulus) (mutHash filt elt)

判断一个元素是否属于布隆过滤器的成员非常简单：如果根据元素计算出的哈希值对应的每一位都已经被置位，则可以认为这个元素已经位于布隆过滤器中。

  1. -- file: BloomFilter/Mutable.hs
  2. elem, notElem :: a -> MutBloom s a -> ST s Bool
  3.  
  4. elem elt filt = indices filt elt >>=
  5.                                 allM (readArray (mutArray filt))
  6.  
  7. notElem elt filt = not `liftM` elem elt filt

我们需要再编写一个简单的支持函数：monadic 版本的 all ，这里将其命名为 allM 。

  1. -- file: BloomFilter/Mutable.hs
  2. allM :: Monad m => (a -> m Bool) -> [a] -> m Bool
  3. allM p (x:xs) = do
  4.   ok <- p x
  5.   if ok
  6.         then allM p xs
  7.         else return False
  8. allM _ [] = return True

不可变的 API

我们为可变布隆过滤器保留的接口与不可变布隆过滤器的 API 拥有相同的结构：

  1. -- file: ch26/BloomFilter.hs
  2. module BloomFilter
  3.         (
  4.           Bloom
  5.         , length
  6.         , elem
  7.         , notElem
  8.         , fromList
  9.         ) where
  10.  
  11. import BloomFilter.Internal
  12. import BloomFilter.Mutable (insert, new)
  13. import Data.Array.ST (runSTUArray)
  14. import Data.Array.IArray ((!), bounds)
  15. import Data.Word (Word32)
  16. import Prelude hiding (elem, length, notElem)
  17.  
  18. length :: Bloom a -> Int
  19. length = fromIntegral . len
  20.  
  21. len :: Bloom a -> Word32
  22. len = succ . snd . bounds . blmArray
  23.  
  24. elem :: a -> Bloom a -> Bool
  25. elt `elem` filt   = all test (blmHash filt elt)
  26.   where test hash = blmArray filt ! (hash `mod` len filt)
  27.  
  28. notElem :: a -> Bloom a -> Bool
  29. elt `notElem` filt = not (elt `elem` filt)

我们还提供了一个易于使用的方法，用户可以通过 fromList 函数创建不可变的布隆过滤器。这个函数对用户隐藏了 ST monad，因此他们只能看到不可变类型。

  1. -- file: ch26/BloomFilter.hs
  2. fromList :: (a -> [Word32])    -- family of hash functions to use
  3.                  -> Word32             -- number of bits in filter
  4.                  -> [a]                -- values to populate with
  5.                  -> Bloom a
  6. fromList hash numBits values =
  7.         B hash . runSTUArray $
  8.           do mb <- new hash numBits
  9.                  mapM_ (insert mb) values
  10.                  return (mutArray mb)

[Forec 译注：上面的代码在 GHC 7.x 中无法通过编译，可以作如下修改来通过编译。

  1. fromList hash numBits values =
  2.         (B hash . runSTUArray) (new hash numBits >>= \mb -> do
  3.         mapM_ (insert mb) values
  4.         return (mutArray mb))

]

fromList 函数的关键在于 runSTUArray 。前面提过，为了从 ST monad 返回一个不可变数组，我们必须冻结一个可变数组，而 runSTUArray 函数将执行和冻结相结合。给定一个返回 STUArray 的动作， runSTUArray 会使用 runST 执行这个动作，之后冻结返回的 STUArray 并将结果作为 UArray 返回。

MArray 类型类同样提供了一个可用的冻结函数，不过 runSTUArray 更方便，也更有效。这是因为冻结必须将底层数据从 STUArray 复制到新的 UArray 以确保对 STUArray 的后续修改不会影响 UArray 。因为类型系统的存在， runSTUArray 可以在创建 UArray 的同时保证 STUArray 不能被访问。因此 runSTUArray 无需复制也可以共享两个数组之间的底层内容。

创建友好的接口

在创建了布隆过滤器之后，我们就可以直接使用上面提到的不可变布隆过滤器 API 。需要注意的是， fromList 函数还遗留了一些重要的决策没有完成。我们仍然要选择一个合适的哈希函数，并确定布隆过滤器的容量。

  1. -- file: BloomFilter/Easy.hs
  2. easyList :: (Hashable a)
  3.                  => Double        -- false positive rate (between 0 and 1)
  4.                  -> [a]           -- values to populate the filter with
  5.                  -> Either String (B.Bloom a)

这里有一种更 “友好” 的方式创建布隆过滤器：这种方式将计算哈希值的任务交给了 Hashable 类型类，并且允许我们将可容忍的错误率作为参数配置布隆过滤器。它还可以根据容错率和输入列表中的元素数量为我们自动选择合适的过滤器大小。

当然，这种方式不是始终可用的。例如，它可能在输入列表的长度过长时失败。但是这种方法的简便性比起我们之前提供的其他接口都要更胜一筹：它使得接口的用户能够对布隆过滤器的整个创建过程进行一系列控制，并将原来彻头彻尾的命令式接口变成了完完全全的声明式接口。

导出更方便的名称

在模块的导出列表中，我们从基本的 BloomFilter 模块中重新导出了一些名称。这允许临时用户只导入 BloomFilter.Easy 模块，并访问他们可能需要的所有类型和功能。

你可能会好奇，同时导入一个被 BloomFilter.Easy 和 BloomFilter 二者均导出的名称会带来什么后果。我们知道，如果不使用 qualified 导入 BloomFilter 并调用 length 函数，GHC 会发出一个有关歧义的错误，因为 Prelude 中也包含一个同名函数。

Haskell 标准的实现要能够分辨出指向同一个 “事物” 的多个不同名称。例如， BloomFilter 和 BloomFilter.Easy 均导出了 Bloom 类型，如果我们同时导入了这两个模块并使用 Bloom ，GHC 将能够发现这两个模块导出的 Bloom 相同，并且不会报告歧义。

哈希值

一个布隆过滤器的性能取决于快速、高质量的哈希函数，然而编写一个兼具这两种属性的哈希函数非常困难。

幸运的是，一个名为 Bob Jenkins 的开发人员编写了一些具有这些属性的哈希函数，并公开了代码（网址为 http://burtleburtle.net/bob/hash/doobs.html [59]）。这些哈希函数使用 C 语言编写，可以通过 FFI 创建它们的绑定。在该网站上，我们需要的特定源文件名为 lookup3.c ，在本地创建一个 cbits 目录并将这个文件下载到该目录。

还剩下最后一个难题没有解决：我们可能经常需要七个、十个，甚至更多个散列函数，但又不想把这些不同功能的哈希函数混杂到一起。幸运的是，在实际应用中我们多数情况下只需要两个哈希函数，下面很快就会讲到如何实现。Jenkins 的散列库包含两个函数 hashword2 和 hashlittle2 ，它们计算两个哈希值。这里有一个 C 语言的头文件，它描述了这两个函数的 API，我们将它保存为 cbits/lookup3.h 。

  1. /* save this file as lookup3.h */
  2.  
  3. #ifndef _lookup3_h
  4. #define _lookup3_h
  5.  
  6. #include <stdint.h>
  7. #include <sys/types.h>
  8.  
  9. /* only accepts uint32_t aligned arrays of uint32_t */
  10. void hashword2(const uint32_t *key,  /* array of uint32_t */
  11.                    size_t length,            /* number of uint32_t values */
  12.                    uint32_t *pc,             /* in: seed1, out: hash1 */
  13.                    uint32_t *pb);            /* in: seed2, out: hash2 */
  14.  
  15. /* handles arbitrarily aligned arrays of bytes */
  16. void hashlittle2(const void *key,   /* array of bytes */
  17.                  size_t length,     /* number of bytes */
  18.                  uint32_t *pc,      /* in: seed1, out: hash1 */
  19.                  uint32_t *pb);     /* in: seed2, out: hash2 */
  20.  
  21. #endif /* _lookup3_h */

“盐” 是在计算哈希值时加入的干扰值。如果我们用某哈希函数求一个值的散列，并分别加入两个不同的盐，那么将会计算出两个不同的结果。因为即使是同一个哈希函数，接收了两个不同的盐值后，计算结果也会相去甚远。

下面的代码是对这两个函数的绑定：

  1. -- file: BloomFilter/Hash.hs
  2. {-# LANGUAGE BangPatterns, ForeignFunctionInterface #-}
  3. module BloomFilter.Hash
  4.         (
  5.           Hashable(..)
  6.         , hash
  7.         , doubleHash
  8.         ) where
  9.  
  10. import Data.Bits ((.&.), shiftR)
  11. import Foreign.Marshal.Array (withArrayLen)
  12. import Control.Monad (foldM)
  13. import Data.Word (Word32, Word64)
  14. import Foreign.C.Types (CSize)
  15. import Foreign.Marshal.Utils (with)
  16. import Foreign.Ptr (Ptr, castPtr, plusPtr)
  17. import Foreign.Storable (Storable, peek, sizeOf)
  18. import qualified Data.ByteString as Strict
  19. import qualified Data.ByteString.Lazy as Lazy
  20. import System.IO.Unsafe (unsafePerformIO)
  21.  
  22. foreign import ccall unsafe "lookup3.h hashword2" hashWord2
  23.         :: Ptr Word32 -> CSize -> Ptr Word32 -> Ptr Word32 -> IO ()
  24.  
  25. foreign import ccall unsafe "lookup3.h hashlittle2" hashLittle2
  26.         :: Ptr a -> CSize -> Ptr Word32 -> Ptr Word32 -> IO ()

[Forec 译注：上面的代码在 GHC 7.6 后无法通过编译，解决方法是将 import Foreign.C.Types (CSize) 修改为 import Foreign.C.Types (CSize(..)) 或者 import Foreign.C.Types (CSize(CSize)) 。]

函数的定义可以查看我们刚刚创建的 lookup3.h 。

出于对效率和便捷的考虑，我们将 Jenkins 散列函数所需的 32 位盐值和计算出的散列值组成单个 64 位值：

  1. -- file: BloomFilter/Hash.hs
  2. hashIO :: Ptr a    -- value to hash
  3.            -> CSize    -- number of bytes
  4.            -> Word64   -- salt
  5.            -> IO Word64
  6. hashIO ptr bytes salt =
  7.         with (fromIntegral salt) $ \sp -> do
  8.           let p1 = castPtr sp
  9.                   p2 = castPtr sp `plusPtr` 4
  10.           go p1 p2
  11.           peek sp
  12.   where go p1 p2
  13.                   | bytes .&. 3 == 0 = hashWord2 (castPtr ptr) words p1 p2
  14.                   | otherwise        = hashLittle2 ptr bytes p1 p2
  15.                 words = bytes `div` 4

[Forec 译注： with 在下面的段落中会有解释， castPtr 没有介绍过，你可以在 http://hackage.haskell.org/package/base-4.6.0.1/docs/Foreign-Marshal-Utils.html#v:with 查看 with 的文档，在 http://hackage.haskell.org/package/base-4.6.0.1/docs/Foreign-Ptr.html#v:castPtr 查看 castPtr 的文档。此外，这里使用 castPtr 并对 p1 和 p2 使用类型推断虽然简短了代码，但也降低了代码的可读性。]

上面的代码如果没有明确的类型来描述其功能，那么可能看起来就不是很清晰。 with 函数在 C 程序的堆栈段中为盐值分配了空间，并存储了当前的盐值，所以 sp 的类型是 Ptr Word64 。指针 p1 和 p2 的类型是 Ptr Word32 ； p1 指向了 sp 的低位字， p2 指向了 sp 的高位字。这就是我们将一个 Word64 的盐值切分为两个 Ptr Word32 参数的方法。

因为所有的数据指针均来自 Haskell 堆，所以它们会在一个能够安全传递给 hashWord2 （只接受 32 位对齐地址）或者 hashLittle2 的地址上对齐。由于 hashWord2 是两个哈希函数中较快的，所以我们会在数据为 4 字节的倍数时调用 hashWord2 ，否则调用 hashLittle2 。 [Forec 译注：这里原著拼写错误，将 hashWord2 误拼写为 hashWord32 ]

C 语言编写的哈希函数会将计算出的哈希值写入 p1 和 p2 指向的地址，我们可以通过 sp 直接检索计算结果。

使用这个模块的客户不应当被低级细节困扰，所以我们通过类型类来提供一个干净、高级的接口：

  1. -- file: BloomFilter/Hash.hs
  2. class Hashable a where
  3.         hashSalt :: Word64        -- ^ salt
  4.                          -> a             -- ^ value to hash
  5.                          -> Word64
  6.  
  7. hash :: Hashable a => a -> Word64
  8. hash = hashSalt 0x106fc397cf62f64d3

我们还为这个类型类提供了一些实用的实现。要计算基本类型的哈希值，必须先编写一点样板代码：

  1. -- file: BloomFilter/Hash.hs
  2. hashStorable :: Storable a => Word64 -> a -> Word64
  3. hashStorable salt k = unsafePerformIO . with k $ \ptr ->
  4.                                           hashIO ptr (fromIntegral (sizeOf k)) salt
  5.  
  6. instance Hashable Char   where hashSalt = hashStorable
  7. instance Hashable Int    where hashSalt = hashStorable
  8. instance Hashable Double where hashSalt = hashStorable

下面的代码使用 Storable 类型类将声明减少到一个：

  1. -- file: BloomFilter/Hash.hs
  2. instance Storable a => Hashable a where
  3.         hashSalt = hashStorable

[Forec 译注：上面使用 Storable 的代码需要添加 {-# LANGUAGE FlexibleInstances #-} 和 {-# LANGUAGE UndecidableInstances #-} 两个编译选项后才能通过编译。 ]

不幸的是，Haskell 不允许编写这种形式的实例，因为它们会使类型系统无法判定：编译器的类型检查器可能会陷入无限循环中。对不可确定类型的限制使我们必须单独列出声明，但它对于上面的定义并不会造成什么影响。[Forec 译注：上面的例子中如果存在 instance Hashable a => Storable a 这样的代码（虽然这样的代码没什么意义），则编译器会陷入循环。但如果程序开发者能够保证这种情况不会发生，则可以开启编译选项并使用这一扩展功能。]

  1. -- file: BloomFilter/Hash.hs
  2. hashList :: (Storable a) => Word64 -> [a] -> IO Word64
  3. hashList salt xs =
  4.         withArrayLen xs $ \len ptr ->
  5.           hashIO ptr (fromIntegral (len * sizeOf x)) salt
  6.   where x = head xs
  7.  
  8. instance (Storable a) => Hashable [a] where
  9.         hashSalt salt xs = unsafePerformIO $ hashList salt xs

编译器会接受这个实例，因而我们能够对多种列表类型计算哈希值 [60] 。最重要的是，由于 Char 是 Storable 的一个实例，所以 String 类型的哈希值同样可以被计算。

利用函数组合可以计算元组的哈希值：在组合管道的一端取盐，并将元组中每个元素的散列结果作为计算该元组中下一个元素使用的盐值。

  1. -- file: BloomFilter/Hash.hs
  2. hash2 :: (Hashable a) => a -> Word64 -> Word64
  3. hash2 k salt = hashSalt salt k
  4.  
  5. instance (Hashable a, Hashable b) => Hashable (a,b) where
  6.         hashSalt salt (a,b) = hash2 b . hash2 a $ salt
  7.  
  8. instance (Hashable a, Hashable b, Hashable c) => Hashable (a,b,c) where
  9.         hashSalt salt (a,b,c) = hash2 c . hash2 b . hash2 a $ salt

要计算 ByteString 类型的哈希值，我们可以编写一个直接插入到 ByteString 类型内部的特殊实例，其效率非常出色：

  1. -- file: BloomFilter/Hash.hs
  2. hashByteString :: Word64 -> Strict.ByteString -> IO Word64
  3. hashByteString salt bs = Strict.useAsCStringLen bs $ \(ptr, len) ->
  4.                                                  hashIO ptr (fromIntegral len) salt
  5.  
  6. instance Hashable Strict.ByteString where
  7.         hashSalt salt bs = unsafePerformIO $ hashByteString salt bs
  8.  
  9. rechunk :: Lazy.ByteString -> [Strict.ByteString]
  10. rechunk s
  11.         | Lazy.null s = []
  12.         | otherwise   = let (pre,suf) = Lazy.splitAt chunkSize s
  13.                                         in  repack pre : rechunk suf
  14.         where repack    = Strict.concat . Lazy.toChunks
  15.                   chunkSize = 64 * 1024
  16.  
  17. instance Hashable Lazy.ByteString where
  18.         hashSalt salt bs = unsafePerformIO $
  19.                                            foldM hashByteString salt (rechunk bs)

由于惰性的 ByteString 类型是由一系列块表示的，我们必须留意块之间的边界。举个例子，字符串 foobar 可以通过五种不同方式表示，如 ["foob", "ar"] 或者 ["fo", "obar"] 。这一点对于多数用户不可见，但我们直接使用了底层的块。 rechunck 函数能够确保传递给 C 语言代码的块大小统一为 64 KB，所以无论原始边界在哪里，计算出的哈希值都是一致的。

将两个哈希值转换为多个

正如前面所述，我们需要两个以上的哈希函数才能有效地使用布隆过滤器。双重哈希技术能够组合 Jenkins 哈希函数计算出的两个值，并产生更多的哈希值。使用双重哈希技术产生的多个哈希值足够满足我们的需要，并且比计算多个不同的哈希值更容易。

  1. -- file: BloomFilter/Hash.hs
  2. doubleHash :: Hashable a => Int -> a -> [Word32]
  3. doubleHash numHashes value = [h1 + h2 * i | i <- [0..num]]
  4.         where h   = hashSalt 0x9150a946c4a8966e value
  5.                   h1  = fromIntegral (h `shiftR` 32) .&. maxBound
  6.                   h2  = fromIntegral h
  7.                   num = fromIntegral numHashes

[Forec 译注：上面代码中的 maxBound 可以通过在 GHCI 中执行 maxBound::Word32 查看，结果为 4294967295。]

实现简单的创建函数

在 BloomFilter.Easy 模块中，我们使用新的 doubleHash 函数来定义之前已经定义过类型的 easyList 函数。

  1. -- file: BloomFilter/Easy.hs
  2. module BloomFilter.Easy
  3.         (
  4.           suggestSizing
  5.         , sizings
  6.         , easyList
  7.  
  8.         -- re-export useful names from BloomFilter
  9.         , B.Bloom
  10.         , B.length
  11.         , B.elem
  12.         , B.notElem
  13.         ) where
  14.  
  15. import BloomFilter.Hash (Hashable, doubleHash)
  16. import Data.List (genericLength)
  17. import Data.Maybe (catMaybes)
  18. import Data.Word (Word32)
  19. import qualified BloomFilter as B
  20.  
  21. easyList errRate values =
  22.         case suggestSizing (genericLength values) errRate of
  23.           Left err            -> Left err
  24.           Right (bits,hashes) -> Right filt
  25.                 where filt = B.fromList (doubleHash hashes) bits values

上面的代码依赖于一个 suggestSizing 函数，这个函数能够根据用户要求的错误率和期望滤波器包含元素的最大数量来估计滤波器的大小以及要计算的哈希值数量：

  1. -- file: BloomFilter/Easy.hs
  2. suggestSizing
  3.         :: Integer       -- expected maximum capacity
  4.         -> Double        -- desired false positive rate
  5.         -> Either String (Word32,Int) -- (filter size, number of hashes)
  6. suggestSizing capacity errRate
  7.         | capacity <= 0                = Left "capacity too small"
  8.         | errRate <= 0 || errRate >= 1 = Left "invalid error rate"
  9.         | null saneSizes               = Left "capacity too large"
  10.         | otherwise                    = Right (minimum saneSizes)
  11.   where saneSizes = catMaybes . map sanitize $ sizings capacity errRate
  12.                 sanitize (bits,hashes)
  13.                   | bits > maxWord32 - 1 = Nothing
  14.                   | otherwise            = Just (ceiling bits, truncate hashes)
  15.                   where maxWord32 = fromIntegral (maxBound :: Word32)
  16.  
  17. sizings :: Integer -> Double -> [(Double, Double)]
  18. sizings capacity errRate =
  19.         [(((-k) * cap / log (1 - (errRate ** (1 / k)))), k) | k <- [1..50]]
  20.   where cap = fromIntegral capacity

[Forec 译注：关于上面代码中 errRate 的推导，可以参考维基百科上布隆过滤器的词条 http://en.wikipedia.org/wiki/Bloom_filter 。根据维基百科，有式 errRate = (1-e^(-k*cap/size))^k ，因为 suggestSizing 函数接受 k 、 cap 和 errRate ，我们可以重新整理方程，并得到 size = -k*cap/log(1 - errRate^(1/k)) ，这就是代码中使用的公式。]

我们对参数做了一定的规范。例如， sizings 函数虽然受到数组大小和哈希值数量的影响，但它并不验证这两个值。由于使用了 32 位哈希值，我们必须过滤掉太大的数组。

在 suggestSizing 函数中，我们仅仅尝试最小化位数组的大小，而不考虑哈希值的数量。现在让我们通过 GHCI 交互地探索一下数组大小和哈希值数量的关系，并解释这种做法的缘由：

假设要将一千万个元素插入布隆过滤器中，并希望误报率不超过 0.1 %。

  1. ghci> let kbytes (bits,hashes) = (ceiling bits `div` 8192, hashes)
  2. ghci> :m +BloomFilter.Easy Data.List
  3. Could not find module `BloomFilter.Easy':
  4.   Use -v to see a list of the files searched for.
  5. ghci> mapM_ (print . kbytes) . take 10 . sort $ sizings 10000000 0.001
  6.  
  7. (17550,10.0)
  8. (17601,11.0)
  9. (17608,9.0)
  10. (17727,12.0)
  11. (17831,8.0)
  12. (17905,13.0)
  13. (18122,14.0)
  14. (18320,7.0)
  15. (18368,15.0)
  16. (18635,16.0)

[Forec 译注：上面交互式代码在原著中是有误的，原著没有纠正这一错误，上面的结果由译者修改后计算。要想得到上面的结果，可以参考如下步骤：

  1. $ cd cbits
  2. $ gcc -c -fPIC lookup3.c -o lookup3.o
  3. $ gcc -shared -Wl,-soname,liblookup3.so.1 -o liblookup3.so.1.0.1 lookup3.o
  4. $ ln -s liblookup3.so.1.0.1 liblookup3.so
  5. $ cd ..
  6. $ ghci -L./cbits -llookup3
  7. Prelude> :l BloomFilter.Easy
  8. *BloomFilter.Easy> :m +Data.List
  9. *BloomFilter.Easy Data.List> let kb (bits,hashes) = (ceiling bits `div` 8192, hashes)
  10. *BloomFilter.Easy Data.List> mapM_ (print . kb) . take 10 . sort $ sizings 10000000 0.001
  11. Loading package array-0.4.0.0 ... linking ... done.
  12. Loading package bytestring-0.9.2.1 ... linking ... done.
  13. (17550,10.0)
  14. (17601,11.0)
  15. (17608,9.0)
  16. (17727,12.0)
  17. (17831,8.0)
  18. (17905,13.0)
  19. (18122,14.0)
  20. (18320,7.0)
  21. (18368,15.0)
  22. (18635,16.0)

]

通过计算 10 个哈希值，我们得到了一个非常紧凑的表（刚好超过 17 KB）。如果真的对数据进行反复的散列，则哈希值的数量可以减少到 7 个，空间消耗可以减少到 5%。因为 Jenkins 的哈希函数在一轮计算中得到两个哈希值，并通过双重哈希产生额外的哈希值，因此我们计算额外哈希值的成本非常小，所以选择最小的表大小。

如果将最高可容忍误报率增加十倍，变为 1%，则所需的空间和哈希值数量都会下降，尽管下降的幅度不太容易预测。

  1. ghci> mapM_ (print . kbytes) . take 10 . sort $ sizings 10000000 0.01
  2. (11710,7.0)
  3. (11739,6.0)
  4. (11818,8.0)
  5. (12006,9.0)
  6. (12022,5.0)
  7. (12245,10.0)
  8. (12517,11.0)
  9. (12810,12.0)
  10. (12845,4.0)
  11. (13118,13.0)

[Forec 译注：上面的代码在原著中同样有误，计算结果由译者修改后给出，步骤同上。]

创建一个 Cabal 包

至此我们已经创建了一个不算太复杂的库，它包括四个公共模块和一个内部模块。现在创建一个 rwh-bloomfilter.cabal 文件，将这个库打包成容易发布的格式。

Cabal 允许我们在一个包中描述几个库的信息。 .cabal 文件的头部包含了所有库通用的信息，后面跟着各个库不同的部分。

  1. Name:               rwh-bloomfilter
  2. Version:            0.1
  3. License:            BSD3
  4. License-File:       License.txt
  5. Category:           Data
  6. Stability:          experimental
  7. Build-Type:         Simple

由于 C 语言代码 lookup3.c 和库捆绑在一起，所以我们要将这个 C 语言源文件的信息告知 Cabal。

  1. Extra-Source-Files: cbits/lookup3.c cbits/lookup3.h

Extra-Source-Files 指令对包的构建没有影响：它仅仅在我们运行 runhaskell Setup sdist 时指导 Cabal 绑定一些额外的文件，这条指令将创建一个用于发布的源码包。

处理不同的构建设置

在 2007 年以前，Haskell 标准库被组织在少数几个规模较大的包中，其中最大的一个被命名为 base 。这个包将许多互不相关的库绑定到一起，因此 Haskell 社区将 base 包拆分成了几个模块化程度更高的库。

Cabal 包需要指明自己构建时依赖的其它包，这些信息帮助 Cabal 的命令行接口在必要的情况下自动下载并构建包的依赖。我们希望，不管用户使用的 GHC 版本是否具备 base 和其它包的现代布局，我们的代码都能尽量兼容。举个例子，我们的代码要能够在 array 包存在的时候说明自己依赖它，否则就只能依赖 base 包。

Cabal 提供了一个通用的配置功能，它允许我们选择性地启用一个 .cabal 文件的某些部分。构建的配置信息由布尔类型的标识控制，标识为 True 时使用 if flag 之后的文本，而标识为 False 时则使用跟在 else 之后的文本。

  1. Cabal-Version:      >= 1.2
  2.  
  3. Flag split-base
  4.   Description: Has the base package been split up?
  5.   Default: True
  6.  
  7. Flag bytestring-in-base
  8.   Description: Is ByteString in the base or bytestring package?
  9.   Default: False
  • 配置功能在 Cabal 的 1.2 版本中引入，因此指定 Cabal 版本不能低于 1.2。
  • split-base 标识的含义不言而喻。[Forec 译注：该标识表示 base 包是否被划分]
  • bytestring-in-base 标识源于一段更为曲折的历史：bytestring 包在创建之初是和 GHC 6.4 捆绑的，并且它始终独立于 base 包；在 GHC 6.6 中，它被合并到了 base 包中；到了 GHC 6.8.1 版本，它又再次被独立出去。
  • 上面这些标识对构建包的开发者来说通常是不可见的，因为 Cabal 会自动处理它们。在我们进行下一步分析前，了解它们能够帮助理解 .cabal 文件中 Library 部分开头的内容。 
  1. Library
  2.   if flag(bytestring-in-base)
  3.         -- bytestring was in base-2.0 and 2.1.1
  4.         Build-Depends: base >= 2.0 && < 2.2
  5.   else
  6.         -- in base 1.0 and 3.0, bytestring is a separate package
  7.         Build-Depends: base < 2.0 || >= 3, bytestring >= 0.9
  8.  
  9.   if flag(split-base)
  10.         Build-Depends: base >= 3.0, array
  11.   else
  12.         Build-Depends: base < 3.0

Cabal 使用标识的默认值来创建包描述（该标识的默认值为 True ）。如果当前的配置能够构建成功（比如所有需要的包版本都可用）则这个配置将被采用，否则 Cabal 将尝试多种方式组合标识，直到它寻找到一个能够构建成功的配置，又或者所有备选的配置都无法生效为止。

例如，如果我们将 split-base 和 bytestring-in-base 设置为 True，Cabal 会选择以下的包依赖项：

  1. Build-Depends: base >= 2.0 && < 2.2
  2. Build-Depends: base >= 3.0, array

base 包的版本无法同时又高于 3.0 又低于 2.2，所以 Cabal 出于一致性考虑会拒绝这个配置。对于现代版本的 GHC，在几次尝试后，它将产生如下配置：

  1. -- in base 1.0 and 3.0, bytestring is a separate package
  2. Build-Depends: base < 2.0 || >= 3, bytestring >= 0.9
  3. Build-Depends: base >= 3.0, array

在运行 runhaskell Setup configure 时，我们可以使用 --flag 选项手动指定各标识的值，虽然实际中很少需要这么做。

编译选项和针对 C 的接口

下面让我们继续分析 .cabal 文件，并完成与 Haskell 相关的剩余细节。如果在构建过程中启用分析，我们希望所有的顶级函数都显示在分析的输出中。

  1. GHC-Prof-Options: -auto-all

Other-Modules 属性列出了库中私有的 Haskell 模块，这些模块对使用此包的代码不可见。

在 GHC 构建这个包时，Cabal 会将 GHC-Options 属性中的选项传递给编译器。

-O2 选项使 GHC 尽可能地优化我们的代码。不加以优化编译出的代码效率很低，所以在编译生产代码时应当始终使用 -O2 选项。

为了写出更清晰的代码，我们通常添加 -Wall 选项，这个选项会启用 GHC 的所有警告。这将导致 GHC 在遇到潜在问题（例如重叠的模式匹配、未使用的函数参数等其它潜在障碍）时提出警告。尽管忽略这些警告一般是安全的，但我们应该尽量完善代码以消除它们。这一点小小的努力，将催生更容易阅读和维护的代码。

普通情况下 GHC 会直接生成汇编语言代码，而在使用 -fvia-C 编译时，GHC 会生成 C 语言代码并使用系统的 C 编译器来编译它。这会减慢编译速度，但有时 C 编译器能够进一步改善 GHC 优化的代码，所以这也是值得的。

我们这里提到 -fiva-C 主要是为了展示如何使用它编译。

  1. C-Sources:        cbits/lookup3.c
  2. CC-Options:       -O3
  3. Include-Dirs:     cbits
  4. Includes:         lookup3.h
  5. Install-Includes: lookup3.h

对于 C-Sources 属性，我们只需要列出必须编译到库中的文件。 CC-Options 属性包含了提供给 C 编译器的选项（其中选项 -O3 用于指定最高级别的优化）。因为对 Jenkins 散列函数的 FFI 绑定引用了 lookup3.h 头文件，我们需要告诉 Cabal 在哪里可以找到该头文件。Install-Includes 用来告诉 Cabal 安装这个头文件，否则在构建时客户端代码将无法找到头文件。

[Forec 译注：遗憾的是，在较新版本的 GHC 中 -fvia-C 不会产生任何作用，并且它将在未来的 GHC 发布中被移除。所以本节关于 -fvia-C 选项的介绍已经成为历史了。]

用 QuickCheck 测试

在进一步考虑性能之前，我们要确保布隆过滤器的正确性。使用 QuickCheck 可以轻松测试一些基本的属性。

  1. -- file: examples/BloomCheck.hs
  2. {-# LANGUAGE GeneralizedNewtypeDeriving #-}
  3. module Main where
  4.  
  5. import BloomFilter.Hash (Hashable)
  6. import Data.Word (Word8, Word32)
  7. import System.Random (Random(..), RandomGen)
  8. import Test.QuickCheck
  9. import qualified BloomFilter.Easy as B
  10. import qualified Data.ByteString as Strict
  11. import qualified Data.ByteString.Lazy as Lazy

普通的 quickCheck 函数对布隆过滤器属性的测试帮助不大，因为它产生的 100 个测试输入样例无法完整覆盖布隆过滤器的功能。这里我们编写自己的测试函数：

  1. -- file: examples/BloomCheck.hs
  2. handyCheck :: Testable a => Int -> a -> IO ()
  3. handyCheck limit = check defaultConfig {
  4.                                          configMaxTest = limit
  5.                                    , configEvery   = \_ _ -> ""
  6.                                    }

[Forec 译注：在较新版本的 QuickCheck 中，上面的代码应该写成：

  1. handyCheck :: Testable a => Int -> a -> IO ()
  2. handyCheck limit = quickCheckWith (stdArgs { maxSuccess = limit )

]

下面我们要完成的第一个任务是确保：无论用户选择多大的容错率，只要向布隆过滤器添加了一个任意值，则之后针对该值的成员测试都应得到 “值已存在” 的结果。

我们将使用 easyList 函数来创建一个布隆过滤器。 Double 的 Random 实例能够生成 0 到 1 之间的随机数，因此 QuickCheck 可以提供任意大小的错误率。

然而，测试生成的错误率应当排除 0 和 1。QuickCheck 提供了两种方法：

  • 通过结构：指定要生成的有效值的范围。QuickCheck 为此提供了 forAll 组合器。
  • 通过过滤：当 QuickCheck 生成一个任意值时，用 (=~>) 运算符过滤掉不符合标准的值。如果布隆过滤器通过这种方式拒绝一个输入值，测试将显示成功。

如果以上两个方法都可以选择，那么最好采用通过结构的方法：假设 QuickCheck 生成了 1000 个任意值，其中 800 个由于某些原因被过滤掉。看起来我们似乎运行了 1000 次测试，但实际上只有 200 次做了有意义的事。

出于这个原因，当需要产生错误率时，我们不会去消除 QuickCheck 提供的 0 或 1，而是在一个始终有效的区间中构造值：

  1. falsePositive :: Gen Double
  2. falsePositive = choose (epsilon, 1 - epsilon)
  3.         where epsilon = 1e-6
  4.  
  5. (=~>) :: Either a b -> (b -> Bool) -> Bool
  6. k =~> f = either (const True) f k
  7.  
  8. prop_one_present _ elt =
  9.         forAll falsePositive $ \errRate ->
  10.           B.easyList errRate [elt] =~> \filt ->
  11.                 elt `B.elem` filt

[Forec 译注：原著作者似乎在这里犯了一点错误，根据代码， prop_one_present 的型别声明应为 (Hashable a) => t -> a -> Property ，但这无法通过编译，因为 prop_one_present 的第一个参数 _ 隐藏着对类型 t 和 a 的约束，它们二者必须相等。有两种解决方法：一是不指定这个多余的 _ 参数，二是将型别声明显式地指定为 (Hashable a) => a -> a -> Property 。]

组合器 (=~>) 过滤了 easyList 失败的情况：如果失败了，测试会自动通过。

多态测试

[Forec 译注：以下几节，原著作者给出的代码在新版本 GHC 中无法通过编译，如需在 GHC 中运行，请按照译注中的说明修改对应文件。译文仅对代码和部分运行结果进行一定修正。]

QuickCheck 要求属性必须是单型的。鉴于目前有多种可散列类型需要测试，我们有必要设计一个方法，避免对每种类型都编写同样的测试。

注意， prop_one_present 这个函数是多态的，但它忽略了第一个参数。我们可以借助这一点模拟单型性质：

  1. ghci> :load BloomCheck
  2. BloomCheck.hs:9:17:
  3.         Could not find module `BloomFilter.Easy':
  4.           Use -v to see a list of the files searched for.
  5. Failed, modules loaded: none.
  6. ghci> :t prop_one_present
  7. <interactive>:1:0: Not in scope: `prop_one_present'
  8. ghci> :t prop_one_present (undefined :: Int)
  9. <interactive>:1:0: Not in scope: `prop_one_present'

[Forec 译注：原著给出的代码无法正确运行，要想正确运行需要对 BloomCheck.hs 做如下修改：

  • 按上面译注里所述，将 handyCheck limit 部分修改；
  • 移除 Random Word8 、 Arbitary Word8 、 Random Word32 以及 Arbitary Word32 的实例；
  • 删除 Arbitary 的 Lazy.ByteString 实例中 coarbitrary 所属行；
  • 删除 Arbitary 的 Strict.ByteString 实例中 coarbitrary 所属行；

]

任何值都可以作为 prop_one_present 的第一个参数。第二个参数中第一个元素的类型需要和第一个参数保持一致。

  1. ghci> handyCheck 5000 $ prop_one_present (undefined :: Int)
  2. <interactive>:1:0: Not in scope: `handyCheck'
  3. <interactive>:1:18: Not in scope: `prop_one_present'
  4. ghci> handyCheck 5000 $ prop_one_present (undefined :: Double)
  5. <interactive>:1:0: Not in scope: `handyCheck'
  6. <interactive>:1:18: Not in scope: `prop_one_present'

[Forec 译注：请留意本节译注中对 prop_one_present 的修正，我们需要显式声明 prop_one_present 的类型，或者移除 prop_one_present 的 _ 参数。 这里采取第二种方法，定义函数 prop_one_present' ，它与 prop_one_present 的唯一区别在于它没有匿名参数：

  1. prop_one_present' elt =
  2.         forAll falsePositive $ \errRate ->
  3.         B.easyList errRate [elt] =~> \filt ->
  4.         elt `B.elem` filt

载入修改后的文件，并显式指定 prop_one_present' 的型别：

  1. ghci> handyCheck 2 $ (prop_one_present' :: String -> Property)
  2. Passed:
  3. ""
  4. 7.053216229843191e-2
  5. Passed:
  6. "\n9UP'\161O%~S"
  7. 0.5021342445896073

本节剩余部分在 GHCI 中执行 handyCheck 指令均需做类似的修正。下面的译文不再对原著的运行结果予以更正。 ]

在向布隆过滤器添加多个元素之后，这些元素应该都能够被识别出来：

  1. -- file: examples/BloomCheck.hs
  2. prop_all_present _ xs =
  3.         forAll falsePositive $ \errRate ->
  4.           B.easyList errRate xs =~> \filt ->
  5.                 all (`B.elem` filt) xs

测试依然成功：

  1. ghci> handyCheck 2000 $ prop_all_present (undefined :: Int)
  2. <interactive>:1:0: Not in scope: `handyCheck'
  3. <interactive>:1:18: Not in scope: `prop_all_present

为 ByteString 编写任意实例

QuickCheck 库没有为 ByteString 类型提供 Arbitary 的实例，因此我们必须自己编写。 pack 函数可基于 [Word8] 创建一个 ByteString 。

  1. -- file: examples/BloomCheck.hs
  2. instance Arbitrary Lazy.ByteString where
  3.         arbitrary = Lazy.pack `fmap` arbitrary
  4.         coarbitrary = coarbitrary . Lazy.unpack
  5.  
  6. instance Arbitrary Strict.ByteString where
  7.         arbitrary = Strict.pack `fmap` arbitrary
  8.         coarbitrary = coarbitrary . Strict.unpack

[Forec 译注：原著编写时的 Arbitary 类型类到今天已经发生了变化， coarbitrary 函数现在属于 CoArbitrary 类型类。上面的代码需要修正为：

  1. instance Arbitrary Lazy.ByteString where
  2. arbitrary = Lazy.pack `fmap` arbitrary
  3.  
  4. instance CoArbitrary Lazy.ByteString where
  5. coarbitrary = coarbitrary . Lazy.unpack

Strict.ByteString 也要做同样的修改。 ]

QuickCheck 中还缺少针对 Data.Word 和 Data.Int 中固定宽度类型的 Arbitary 实例。我们至少需要为 Word8 实现 Arbitary 实例：

  1. -- file: examples/BloomCheck.hs
  2. instance Random Word8 where
  3.   randomR = integralRandomR
  4.   random = randomR (minBound, maxBound)
  5.  
  6. instance Arbitrary Word8 where
  7.         arbitrary = choose (minBound, maxBound)
  8.         coarbitrary = integralCoarbitrary

[Forec 译注： Word8 的实例不需要定义。当前的 QuickCheck 库已经默认实现了这些实例。]

为这些实例编写几个通用函数，以便在之后为其他整型类型编写实例时重用它们：

  1. -- file: examples/BloomCheck.hs
  2. integralCoarbitrary n =
  3.         variant $ if m >= 0 then 2*m else 2*(-m) + 1
  4.   where m = fromIntegral n
  5.  
  6. integralRandomR (a,b) g = case randomR (c,d) g of
  7.                                                         (x,h) -> (fromIntegral x, h)
  8.         where (c,d) = (fromIntegral a :: Integer,
  9.                                    fromIntegral b :: Integer)
  10.  
  11. instance Random Word32 where
  12.   randomR = integralRandomR
  13.   random = randomR (minBound, maxBound)
  14.  
  15. instance Arbitrary Word32 where
  16.         arbitrary = choose (minBound, maxBound)
  17.         coarbitrary = integralCoarbitrary

[Forec 译注：上面这部分代码也是不需要的，QuickCheck 库已经实现了它们。]

创建了这些 Arbitary 实例后，我们就可以在 ByteString 类型上尝试现有的属性：

  1. ghci> handyCheck 1000 $ prop_one_present (undefined :: Lazy.ByteString)
  2. <interactive>:1:0: Not in scope: `handyCheck'
  3. <interactive>:1:18: Not in scope: `prop_one_present'
  4. <interactive>:1:49:
  5.         Failed to load interface for `Lazy':
  6.           Use -v to see a list of the files searched for.
  7. ghci> handyCheck 1000 $ prop_all_present (undefined :: Strict.ByteString)
  8. <interactive>:1:0: Not in scope: `handyCheck'
  9. <interactive>:1:18: Not in scope: `prop_all_present'
  10. <interactive>:1:49:
  11.         Failed to load interface for `Strict':
  12.           Use -v to see a list of the files searched for.

推荐大小是正确的吗？

随着待运行测试数量的增加，用于测试 easyList 性能的开销也在快速增长。我们希望输入数据规模对 easyList 的性能没有影响。直接测试是不现实的，所以这里使用另一个问题来衡量：面对极端的输入规模时， suggestSizing 是否仍能给出敏感的数组大小以及哈希值？

检查这一特性略微有些棘手：我们需要同时改变期望的错误率和预期容量。根据 sizings 函数给出的结果，这些值之间的关系较难预测。

我们可以尝试忽略复杂性：

  1. -- file: examples/BloomCheck.hs
  2. prop_suggest_try1 =
  3.   forAll falsePositive $ \errRate ->
  4.         forAll (choose (1,maxBound :: Word32)) $ \cap ->
  5.           case B.suggestSizing (fromIntegral cap) errRate of
  6.                 Left err -> False
  7.                 Right (bits,hashes) -> bits > 0 && bits < maxBound && hashes > 0

正如我们所料，这一做法只会带来一个没有实际作用的测试：

  1. ghci> handyCheck 1000 $ prop_suggest_try1
  2. <interactive>:1:0: Not in scope: `handyCheck'
  3. <interactive>:1:18: Not in scope: `prop_suggest_try1'
  4. ghci> handyCheck 1000 $ prop_suggest_try1
  5. <interactive>:1:0: Not in scope: `handyCheck'
  6. <interactive>:1:18: Not in scope: `prop_suggest_try1'

[Forec 译注：一个仅供参考的运行结果如下：

  1. ghci> handyCheck 1000 $ prop_suggest_try1
  2. Passed:
  3. 0.840272094122386
  4. 1533634864
  5. Failed:
  6. 0.13172750223946617
  7. 3002287708
  8. *** Failed! Falsifiable (after 2 tests):
  9. 0.13172750223946617
  10. 3002287708

]

将 QuickCheck 打印的反例交给 suggestSizing 时，我们发现这些输入被拒绝了，因为它们会导致一个过于庞大的位数组。

  1. ghci> B.suggestSizing 1678125842 8.501133057303545e-3
  2. <interactive>:1:0:
  3.         Failed to load interface for `B':
  4.           Use -v to see a list of the files searched for.

[Forec 译注：运行结果如下：

  1. ghci> B.suggestSizing 1678125842 8.501133057303545e-3
  2. Left "capacity too large"

]

由于无法预测哪些组合会导致此问题，我们只能通过限制大小和错误率来防止异常：

  1. -- file: examples/BloomCheck.hs
  2. prop_suggest_try2 =
  3.         forAll falsePositive $ \errRate ->
  4.           forAll (choose (1,fromIntegral maxWord32)) $ \cap ->
  5.                 let bestSize = fst . minimum $ B.sizings cap errRate
  6.                 in bestSize < fromIntegral maxWord32 ==>
  7.                    either (const False) sane $ B.suggestSizing cap errRate
  8.   where sane (bits,hashes) = bits > 0 && bits < maxBound && hashes > 0
  9.                 maxWord32 = maxBound :: Word32

对其加以测试，看起来效果不错：

  1. ghci> handyCheck 1000 $ prop_suggest_try2
  2. <interactive>:1:0: Not in scope: `handyCheck'
  3. <interactive>:1:18: Not in scope: `prop_suggest_try2'

[Forec 译注：预期的运行结果为：

  1. ghci> handyCheck 1000 $ prop_suggest_try2
  2. +++ OK, passed 1000 tests.

]

在过大的测试中，许多组合都被过滤掉了：

  1. ghci> handyCheck 10000 $ prop_suggest_try2
  2. <interactive>:1:0: Not in scope: `handyCheck'
  3. <interactive>:1:19: Not in scope: `prop_suggest_try2'

为了解决此问题，我们要尝试降低生成无效输入的可能性：

  1. -- file: examples/BloomCheck.hs
  2. prop_suggestions_sane =
  3.         forAll falsePositive $ \errRate ->
  4.           forAll (choose (1,fromIntegral maxWord32 `div` 8)) $ \cap ->
  5.                 let size = fst . minimum $ B.sizings cap errRate
  6.                 in size < fromIntegral maxWord32 ==>
  7.                    either (const False) sane $ B.suggestSizing cap errRate
  8.   where sane (bits,hashes) = bits > 0 && bits < maxBound && hashes > 0
  9.                 maxWord32 = maxBound :: Word32

最终，我们得到了更加健壮的性能：

  1. ghci> handyCheck 40000 $ prop_suggestions_sane
  2. <interactive>:1:0: Not in scope: `handyCheck'
  3. <interactive>:1:19: Not in scope: `prop_suggestions_sane'

性能分析和调优

我们可以将程序通过 QuickCheck 测试视为一条证明代码正确的 “基准线”。在调整性能时，随时重新运行测试能够防止修改过程中不小心导致的破坏。

第一步，编写一个用于计时的小程序：

  1. -- file: examples/WordTest.hs
  2. module Main where
  3.  
  4. import Control.Parallel.Strategies (NFData(..))
  5. import Control.Monad (forM_, mapM_)
  6. import qualified BloomFilter.Easy as B
  7. import qualified Data.ByteString.Char8 as BS
  8. import Data.Time.Clock (diffUTCTime, getCurrentTime)
  9. import System.Environment (getArgs)
  10. import System.Exit (exitFailure)
  11.  
  12. timed :: (NFData a) => String -> IO a -> IO a
  13. timed desc act = do
  14.         start <- getCurrentTime
  15.         ret <- act
  16.         end <- rnf ret `seq` getCurrentTime
  17.         putStrLn $ show (diffUTCTime end start) ++ " to " ++ desc
  18.         return ret
  19.  
  20. instance NFData BS.ByteString where
  21.         rnf _ = ()
  22.  
  23. instance NFData (B.Bloom a) where
  24.         rnf filt = B.length filt `seq` ()

[Forec 译注：编译过时的代码总是不尽人意，需要做如下修改：

]

上面的小程序中，我们使用了 24 章中 “将求值从算法中分离” 一节介绍的 rnf 函数来实现简单的时间约束。输出用时这一动作能够确保计算完成，从而准确地评估运算成本。

[Note: 24 章该节尚未翻译，翻译完成后应当将此处替换为 reference。]

主程序根据指定文件创建一个布隆过滤器，它将文件中每一行视为一个要添加到布隆过滤器中的元素：

  1. -- file: examples/WordTest.hs
  2. main = do
  3.   args <- getArgs
  4.   let files | null args = ["/usr/share/dict/words"]
  5.                         | otherwise = args
  6.   forM_ files $ \file -> do
  7.  
  8.         words <- timed "read words" $
  9.           BS.lines `fmap` BS.readFile file
  10.  
  11.         let len = length words
  12.                 errRate = 0.01
  13.  
  14.         putStrLn $ show len ++ " words"
  15.         putStrLn $ "suggested sizings: " ++
  16.                            show (B.suggestSizing (fromIntegral len) errRate)
  17.  
  18.         filt <- timed "construct filter" $
  19.           case B.easyList errRate words of
  20.                 Left errmsg -> do
  21.                   putStrLn $ "Error: " ++ errmsg
  22.                   exitFailure
  23.                 Right filt -> return filt
  24.  
  25.         timed "query every element" $
  26.           mapM_ print $ filter (not . (`B.elem` filt)) words

[Forec 译注：显然，原著给出的程序需要在类 Linux 环境下运行，并且 /usr/share/dict 路径下要存在 words 文件，该文件用于为程序提供输入。]

timed 函数用来计算程序执行中三个不同阶段的成本；读取并按行分割数据、 填充布隆过滤器和查询其中的每个元素。

如果将上述程序编译运行几次，就可以发现执行时间比较长，但多次运行之间的时长差距很小。至此，我们创建了一个看似可信的微基准测试：

  1. $ ghc -O2  --make WordTest
  2. [1 of 1] Compiling Main             ( WordTest.hs, WordTest.o )
  3. Linking WordTest ...
  4. $ ./WordTest
  5. 0.196347s to read words
  6. 479829 words
  7. 1.063537s to construct filter
  8. 4602978 bits
  9. 0.766899s to query every element
  10. $ ./WordTest
  11. 0.179284s to read words
  12. 479829 words
  13. 1.069363s to construct filter
  14. 4602978 bits
  15. 0.780079s to query every element

配置驱动的性能调优

下面重新构建这个程序，并在启用分析的情况下运行，以观察哪些调优能够改善它的性能。

因为此前我们已经构建了 WordTest 且没有对源码做任何改动，如果仅仅重新运行 GHC，GHC 会认为已存在的二进制文件足够新，从而跳过重新构建。我们必须强制重新构建此程序，这里可以通过编辑源文件以更新文件系统来实现。

[Forec 译注：也可以使用 =fforce-recomp 标识，它会强迫 GHC 重新构建。]

  1. $ touch WordTest.hs
  2. $ ghc -O2 -prof -auto-all --make WordTest
  3. [1 of 1] Compiling Main             ( WordTest.hs, WordTest.o )
  4. Linking WordTest ...
  5.  
  6. $ ./WordTest +RTS -p
  7. 0.322675s to read words
  8. 479829 words
  9. suggested sizings: Right (4602978,7)
  10. 2.475339s to construct filter
  11. 1.964404s to query every element
  12.  
  13. $ head -20 WordTest.prof
  14. total time  =          4.10 secs   (205 ticks @ 20 ms)
  15. total alloc = 2,752,287,168 bytes  (excludes profiling overheads)
  16.  
  17. COST CENTRE                    MODULE               %time %alloc
  18.  
  19. doubleHash                     BloomFilter.Hash      48.8   66.4
  20. indices                        BloomFilter.Mutable   13.7   15.8
  21. elem                           BloomFilter            9.8    1.3
  22. hashByteString                 BloomFilter.Hash       6.8    3.8
  23. easyList                       BloomFilter.Easy       5.9    0.3
  24. hashIO                         BloomFilter.Hash       4.4    5.3
  25. main                           Main                   4.4    3.8
  26. insert                         BloomFilter.Mutable    2.9    0.0
  27. len                            BloomFilter            2.0    2.4
  28. length                         BloomFilter.Mutable    1.5    1.0

可以看出， doubleHash 占用了巨大的时空资源。

回忆一下，doubleHash 函数的主体功能是无副作用的列表解析：

  1. -- file: BloomFilter/Hash.hs
  2. doubleHash :: Hashable a => Int -> a -> [Word32]
  3. doubleHash numHashes value = [h1 + h2 * i | i <- [0..num]]
  4.         where h   = hashSalt 0x9150a946c4a8966e value
  5.                   h1  = fromIntegral (h `shiftR` 32) .&. maxBound
  6.                   h2  = fromIntegral h
  7.                   num = fromIntegral numHashes

鉴于 doubleHash 的返回值是列表，它占这么大内存似乎有点道理。但是这么简单的代码却表现出如此之差的性能，难免让人怀疑。

面对这么一个性能上的谜团，我们自然会想到检查编译器的输出。这里并不需要通过汇编语言转储来分析，从更高层次开始会更容易。

GHC 的 -ddump-simpl 选项会打印出执行所有高级优化后生成的代码：

  1. $ ghc -O2 -c -ddump-simpl --make BloomFilter/Hash.hs > dump.txt
  2. [1 of 1] Compiling BloomFilter.Hash ( BloomFilter/Hash.hs )

产生的 dump.txt 大约有一千行，其中多数名字是根据原始 Haskell 表示自动生成的。即使如此，搜索 doubleHash 仍然可以帮助我们立刻定位到函数的定义。下面这个例子说明了如何在 Unix Shell 中寻找到函数的定义：

  1. $ less +/doubleHash dump.txt

刚开始阅读 GHC 简化器的输出会有些困难。这些输出包含了许多自动生成的名称，并且代码中有许多不明显的注释。我们可以忽略掉自己不了解的东西，将注意力集中在看起来很熟悉的部分上。普通的 Haskell 和 Core 语言在语法特性上有一定相似之处，尤其是类型签名、用于变量绑定的 let 和模式匹配的 case 。

如果去除 doubleHash 定义之外的部分，我们将得到类似如下所示的代码：

  1. __letrec { <1>
  2.   go_s1YC :: [GHC.Word.Word32] -> [GHC.Word.Word32] <2>
  3.   [Arity 1
  4.    Str: DmdType S]
  5.   go_s1YC =
  6.         \ (ds_a1DR :: [GHC.Word.Word32]) ->
  7.           case ds_a1DR of wild_a1DS {
  8.         [] -> GHC.Base.[] @ GHC.Word.Word32; <3>
  9.         : y_a1DW ys_a1DX -> <4>
  10.           GHC.Base.: @ GHC.Word.Word32 <5>
  11.                 (case h1_s1YA of wild1_a1Mk { GHC.Word.W32# x#_a1Mm -> <6>
  12.                  case h2_s1Yy of wild2_a1Mu { GHC.Word.W32# x#1_a1Mw ->
  13.                  case y_a1DW of wild11_a1My { GHC.Word.W32# y#_a1MA ->
  14.                  GHC.Word.W32# <7>
  15.                    (GHC.Prim.narrow32Word#
  16.                   (GHC.Prim.plusWord# <8>
  17.                          x#_a1Mm (GHC.Prim.narrow32Word#
  18.                                                           (GHC.Prim.timesWord# x#1_a1Mw y#_a1MA))))
  19.                  }
  20.                  }
  21.                  })
  22.                 (go_s1YC ys_a1DX) <9>
  23.           };
  24. } in
  25.   go_s1YC <10>
  26.         (GHC.Word.$w$dmenumFromTo2
  27.            __word 0 (GHC.Prim.narrow32Word# (GHC.Prim.int2Word# ww_s1X3)))

[Forec 译注：原著中给出的代码包含了图片，译文使用 <编号> 这样的标识代替图片，并在下面给出对应的注释。]

这是列表分析部分的主体。看起来似乎令人生畏，但我们可以逐步分析它。你会发现它并非那么复杂：

  • __letrec 等价于 Haskell 中的 let ；
  • GHC 将列表解析的主体部分编译成了一个名为 go_s1YC 的循环；
  • 如果 case 表达式匹配了空列表，我们就返回空列表。是不是看起来很熟悉？
  • 这个模式在 Haskell 中读作 (y_a1DW:ys_a1DX) 。(:) 构造器之所以出现在操作数之前，是因为 Core 语言出于简单起见使用了前缀表达式；
  • 这是 (:) 构造器的一种应用。符号 @ 表明第一个操作数的类型是 Word32 ；
  • 三个 case 表达式分别对一个 Word32 值拆箱以取出其中包含的原始值。首先处理的是 h1 （这里命名为 h1_s1YA ），然后是 h2 ，最后是当前列表元素 y 。拆箱是通过模式匹配实现的：W32# 是用于将原始值装箱的构造函数。按照惯例，原始类型、值以及使用它们的函数在命名时都会包含一个 #；
  • 这里我们将 W32# 构造器应用于 Word32# 类型的原始值，从而给出类型为 Word32 的正常值；
  • plusWord# 和 timesWord# 函数分别对原始的无符号整数做添加和相乘操作；
  • 这是 (:) 构造器的第二个参数，其中 go_s1YC 函数以递归的方式调用自身；
  • 这里调用了列表解析函数。它的参数是用 Core 语言表示的 [0..n] 。

阅读这段代码，我们发现了两处有趣的行为：

  • 我们创建了一个列表，并且立刻在 go_s1YC 循环中解构它。GHC 通常可以检查出这种生产后立刻消费的模式，并将其转化为一个不包含资源分配的循环。这类变换称为 融合 ，因为生产者和消费者被融合到了一起。不幸的是，在上面的代码中 GHC 并没有为我们实现这一点。
  • 在循环体中重复对 h1 和 he 开箱的行为非常浪费资源。

为了解决这些问题，我们对 doubleHash 函数做了一些细微的修改：

  1. -- file: BloomFilter/Hash.hs
  2. doubleHash :: Hashable a => Int -> a -> [Word32]
  3. doubleHash numHashes value = go 0
  4.         where go n | n == num  = []
  5.                            | otherwise = h1 + h2 * n : go (n + 1)
  6.  
  7.                   !h1 = fromIntegral (h `shiftR` 32) .&. maxBound
  8.                   !h2 = fromIntegral h
  9.  
  10.                   h   = hashSalt 0x9150a946c4a8966e value
  11.                   num = fromIntegral numHashes

上面的代码中，我们手动将 [0..num] 表达式和 “消费” 它的代码合并成单个循环，并为 h1 和 h2 添加了严格注释。这些修改将 6 行代码变成 8 行，除此之外没有任何其它变动。它们会对 Core 的输出有什么影响呢？

  1. __letrec {
  2.   $wgo_s1UH :: GHC.Prim.Word# -> [GHC.Word.Word32]
  3.   [Arity 1
  4.    Str: DmdType L]
  5.   $wgo_s1UH =
  6.         \ (ww2_s1St :: GHC.Prim.Word#) ->
  7.           case GHC.Prim.eqWord# ww2_s1St a_s1T1 of wild1_X2m {
  8.         GHC.Base.False ->
  9.           GHC.Base.: @ GHC.Word.Word32
  10.                 (GHC.Word.W32#
  11.                  (GHC.Prim.narrow32Word#
  12.                   (GHC.Prim.plusWord#
  13.                    ipv_s1B2
  14.                    (GHC.Prim.narrow32Word#
  15.                 (GHC.Prim.timesWord# ipv1_s1AZ ww2_s1St)))))
  16.                 ($wgo_s1UH (GHC.Prim.narrow32Word#
  17.                                                 (GHC.Prim.plusWord# ww2_s1St __word 1)));
  18.         GHC.Base.True -> GHC.Base.[] @ GHC.Word.Word32
  19.           };
  20. } in  $wgo_s1UH __word 0

新函数被编译成了简单的计数循环。多么令人兴奋！来看看它的实际运行效果：

  1. $ touch WordTest.hs
  2. $ ghc -O2 -prof -auto-all --make WordTest
  3. [1 of 1] Compiling Main             ( WordTest.hs, WordTest.o )
  4. Linking WordTest ...
  5.  
  6. $ ./WordTest +RTS -p
  7. 0.304352s to read words
  8. 479829 words
  9. suggested sizings: Right (4602978,7)
  10. 1.516229s to construct filter
  11. 1.069305s to query every element
  12. ~/src/darcs/book/examples/ch27/examples $ head -20 WordTest.prof
  13. total time  =        3.68 secs    (184 ticks @ 20 ms)
  14. total alloc = 2,644,805,536 bytes (excludes profiling overheads)
  15.  
  16. COST CENTRE                    MODULE               %time %alloc
  17.  
  18. doubleHash                     BloomFilter.Hash      45.1   65.0
  19. indices                        BloomFilter.Mutable   19.0   16.4
  20. elem                           BloomFilter           12.5    1.3
  21. insert                         BloomFilter.Mutable    7.6    0.0
  22. easyList                       BloomFilter.Easy       4.3    0.3
  23. len                            BloomFilter            3.3    2.5
  24. hashByteString                 BloomFilter.Hash       3.3    4.0
  25. main                           Main                   2.7    4.0
  26. hashIO                         BloomFilter.Hash       2.2    5.5
  27. length                         BloomFilter.Mutable    0.0    1.0

针对 doubleHash 的调整使性能提高了约 11%。对于仅仅添加两行代码的变动来说已经相当不错了。

练习

  • easyList 中使用的 genericLength 在处理无限列表时会导致函数陷入无限循环。如何修正此问题？
  • 困难 ：编写一个 QuickCheck 属性以检查观察到的错误率是否接近用户可容忍的错误率。
[Broder02]Andrei Broder. Michael Mitzenmacher. “Network applications of Bloom filters: a survey”. Internet Mathematics. 1. 4. 2005. 485-509. A K Peters Ltd..

[58] ST 是 “状态变换器” （state transformer） 的缩写。

[59] 与流行的非加密哈希函数（如 FNV 和 hashpjw）相比，Jenkins 的哈希函数的混合属性要好得多，因此我们建议避免使用那些非加密哈希函数。

[60] 遗憾的是，详细讨论这些情况能否判断不属于本书范畴。