关于数据库:浅谈布隆过滤器bloom-Filter一

明天和大家聊一下布隆过滤器（bloom Filter）。

布隆过滤器（bloom Filter）是 1970 年由 Bloom,Burton H. 提出的。

布隆过滤器（bloom Filter）是是一种用于反对成员资格查问的数据结构。
简略地说，布隆过滤器（bloom Filter）是用于测试元素是否为给定数据汇合的成员。

布隆过滤器有以下特点：

*   与要测试的数据集的数据量相比，存储布隆过滤器所需的空间量更小。*   检测一个测试对象数据是否属于给定数据集的成员所用的工夫与测试对象数据集汇合中蕴含的元素数无关。*   假反例（False negatives，即如果某个元素的确没有在该汇合中，那么 Bloom Filter 是不会报告该元素存在于汇合中）是不可能呈现。*   假正例（False positives，即 Bloom Filter 报告某一元素存在于某汇合中，然而实际上该元素并不在汇合中）是可能的，但能够管制其产生频率。

换成上面的话可能更容易了解：

布隆过滤器是一种把大数据集换成小数据集以节约下一步解决所须要工夫的办法，它可能没有过滤掉所有不符合标准的数据，但不会把符合标准数据谬误的过滤掉。

那么布隆过滤器是如何实现的呢？

布隆过滤器基于一个最后设置为 0 的 m 位数组（b1、b2、……bm）和 k 个独立的哈希函数（h1、h2、…、hk），每个哈希函数返回介于 1 和 m 之间的值。为了将测试对象数据集 ” 存储 ” 到 m 位数组中，必须将每个哈希函数利用于测试对象数据，并且将每个函数（r1、r2、…、…、rk）的返回值 作为偏移量，设置 m 位数组相应的 BIT 为 1。因为存在 k 个哈希函数，因而位数组中最多为 k 位将设置为 1（也可能比 k 少，因为多个哈希函数可能返回雷同的值）。下图是 m=16、k=4 和 e 是要 ” 存储在 ” 位数组中的元素的示例。

那么如何查看元素是否 ” 存储在 ” 位数组中呢，这个过程和下面相似。惟一的区别是，它不设置数组中的 k 位，而是查看它们中的任何一个都是否设置为 0。如果是，则意味着元素未 ” 存储在 ” 位数组中。

让咱们看一个示例，阐明如何在实践中应用布隆过滤器。

假如有一个应用程序以高吞吐量接管输出数据。在解决它之前，它必须查看该数据是否属于存储在数据库表中的给定集。请留神，此验证的回绝率十分高。若要执行验证，应用程序必须调用近程服务。可怜的是，网络往返和理论查找所需工夫太长。因为无奈进一步优化它（例如，网络提早受物理限度），因而必须实现另一种办法。在这种状况下，个别会想到缓存。通过复制近程数据存储在本地缓存中，而后在本地执行验证。可是在这个场景下，这是不可行的。因为本地没有足够的资源来存储数据。在这种状况下，布隆过滤器可能施展很大的作用。因为布隆过滤器须要的空间比理论数据须要的存储少得多。另外，因为布隆过滤器受到误报（False positives）的影响，不可能将所有不须要的数据都过滤掉，只是在调用近程服务之前尽可能的抛弃不合乎验证函数的输出数据。因而，应用布隆过滤器并不会进步原始验证运行速度，而是将须要验证的数据集变小，以此缩小整个解决所需的工夫和存储空间。

上面我用 PL/SQL 来模仿一个布隆过滤器。

我的 PL/SQL 脚本蕴含以下三个存储过程 / 函数：

•init：用来初始化布隆过滤器
•add_value：用来“存储”字符串到 bit 数组
•contain：用来“查看”一个字符串是否“存储在”bit 数组

PACKAGE 定义：

CREATE OR REPLACE PACKAGE bloom_filter IS
   PROCEDURE init (p_m IN BINARY_INTEGER, p_n IN BINARY_INTEGER);
   FUNCTION add_value (p_value IN VARCHAR2) RETURN BINARY_INTEGER;
   FUNCTION contain (p_value IN VARCHAR2) RETURN BINARY_INTEGER;
END bloom_filter;

PACKAGE BODY 定义：

CREATE OR REPLACE PACKAGE BODY bloom_filter IS
   TYPE t_bitarray IS TABLE OF BOOLEAN;
   g_bitarray t_bitarray;
   g_m BINARY_INTEGER;
   g_k BINARY_INTEGER;

   PROCEDURE init (p_m IN BINARY_INTEGER, p_n IN BINARY_INTEGER) IS
   BEGIN
      g_m := p_m;
      g_bitarray := t_bitarray();
      g_bitarray.extend(p_m);

      FOR i IN g_bitarray.FIRST..g_bitarray.LAST
      LOOP
        g_bitarray(i) := FALSE;
      END LOOP;

      g_k := ceil(p_m / p_n * ln(2));

   END init;

   FUNCTION add_value (p_value IN VARCHAR2) RETURN BINARY_INTEGER IS
   BEGIN
      dbms_random.seed(p_value);

      FOR i IN 0..g_k
      LOOP
         g_bitarray(dbms_random.value(1, g_m)) := TRUE;
      END LOOP;
      RETURN 1;
   END add_value;

   FUNCTION contain (p_value IN VARCHAR2) RETURN BINARY_INTEGER IS
      l_ret BINARY_INTEGER := 1;
   BEGIN
      dbms_random.seed(p_value);

      FOR i IN 0..g_k
      LOOP
         IF NOT g_bitarray(dbms_random.value(1, g_m))
         THEN
            l_ret := 0;
            EXIT;
         END IF;
      END LOOP;
      RETURN l_ret;
   END contain;
END bloom_filter;

接下来来测试一下位数组宽度和假正例（False positives）个数的关系。

SQL> execute bloom_filter.init(1024, 1000);

PL/SQL プロシージャが失常に完了しました。SQL> SELECT count(bloom_filter.add_value(value)) FROM t WHERE rownum <= 1000;

COUNT(BLOOM_FILTER.ADD_VALUE(VALUE))
------------------------------------
                                1000

SQL> SELECT count(*) FROM t WHERE bloom_filter.contain(value) = 1;

  COUNT(*)
----------
      7602

SQL> execute bloom_filter.init(2048, 1000);

PL/SQL プロシージャが失常に完了しました。SQL> SELECT count(bloom_filter.add_value(value)) FROM t WHERE rownum <= 1000;

COUNT(BLOOM_FILTER.ADD_VALUE(VALUE))
------------------------------------
                                1000

SQL> SELECT count(*) FROM t WHERE bloom_filter.contain(value) = 1;

  COUNT(*)
----------
      5072

SQL> execute bloom_filter.init(4096, 1000);

PL/SQL プロシージャが失常に完了しました。SQL> SELECT count(bloom_filter.add_value(value)) FROM t WHERE rownum <= 1000;

COUNT(BLOOM_FILTER.ADD_VALUE(VALUE))
------------------------------------
                                1000

SQL> SELECT count(*) FROM t WHERE bloom_filter.contain(value) = 1;

  COUNT(*)
----------
      2306

SQL> execute bloom_filter.init(8192, 1000);

PL/SQL プロシージャが失常に完了しました。SQL> SELECT count(bloom_filter.add_value(value)) FROM t WHERE rownum <= 1000;

COUNT(BLOOM_FILTER.ADD_VALUE(VALUE))
------------------------------------
                                1000

SQL> SELECT count(*) FROM t WHERE bloom_filter.contain(value) = 1;

  COUNT(*)
----------
      1205

SQL> execute bloom_filter.init(16384, 1000);

PL/SQL プロシージャが失常に完了しました。SQL> SELECT count(bloom_filter.add_value(value)) FROM t WHERE rownum <= 1000;

COUNT(BLOOM_FILTER.ADD_VALUE(VALUE))
------------------------------------
                                1000

SQL> SELECT count(*) FROM t WHERE bloom_filter.contain(value) = 1;

  COUNT(*)
----------
      1003

SQL> execute bloom_filter.init(32768, 1000);

PL/SQL プロシージャが失常に完了しました。SQL> SELECT count(bloom_filter.add_value(value)) FROM t WHERE rownum <= 1000;

COUNT(BLOOM_FILTER.ADD_VALUE(VALUE))
------------------------------------
                                1000

SQL> SELECT count(*) FROM t WHERE bloom_filter.contain(value) = 1;

  COUNT(*)
----------
      1000

通过下面的后果，咱们能够看到随着 Bit 位数组宽度的减少，假正例（False positives）个数相应缩小。

以上，我讲述了布隆过滤器的基本原理和利用场景。
对于布隆过滤器在 ORACLE 数据库中的利用，我会在下一篇文章里介绍。