【译文】理解布隆过滤器

Fri 10 May 2019

原文:Understanding Bloom filters with Pharo Smalltalk

本文通过 HTML 转录了 PharoPDS 库及其扩展附带的交互式教程,以探索和理解布隆过滤器。

因此,如果您想在真实的环境中修改这些数据结构,请尝试在 Pharo 镜像中安装这个库,并按照交互式教程并使用提供的自定义工具进行操作。

理解布隆过滤器

布隆过滤器是一个非常节省空间的数据结构,由 Burton Howard Bloom 于 1970 年所提出(Space/Time Trade-offs in Hash Coding with Allowable Errors),布隆过滤器用于测试一个元素是否是集合的成员之一。

常规的哈希搜索通过将一系列值存储在哈希表上,不管是基于链表还是开放寻址(open addressing),随着越来越多的元素添加到哈希表中,定位元素的期望时间都会从初始的常量的 O(1) 退化或增加到线性的 O(N)。

布隆过滤器提供了一个替代的数据结构,可以实现在添加元素或检查元素是否是成员上,不管在空间和时间上都可以保证常量级的性能,并且和已经添加到过滤器中的元素数量是无关的。

为了达到如此高效的表现所需要付出的代价是:布隆过滤器是一个概率性的数据结构。Bloom 他在开创性的论文中解释如下:

新的方法打算比传统相关的方法减少一定量哈希码所需要的空间。通过利用某些应用可以容忍少量的误差来减少空间的使用,特别是那些拥有大量的数据参与无法通过传统的方法保留核心哈希区域的应用。

背景

Donald Knuth 在他著名的 The Art of Computer Programming 中写下了如下对布隆过滤器的描述:

想象一个拥有非常大量的数据且如果搜索没有成功则无需完成任何计算的搜索应用。比如,我们可能想检查一些人的信用评级或者护照编号,如果文档中没有该人的任何记录我们就无需做任何调查。类似地,在计算机排版应用程序中,我们可能有一个简单算法可以正确地连接大多数单词,但该算法会对大约 5W 个异常单词无效; 如果我们在异常文件中找不到该单词,就可以放心的使用该简单算法。

同时 Andrei Broder 和 Michael Mitzenmacher 在著名的布隆过滤器原理(The Bloom Filter Principle(Internet Mathematics Vol. 1, No. 4: 485-509Network Applications ofBloom Filters: A Survey))中提出:

在一个空间宝贵的情况下要使用列表或集合并且可以接受误报,则可以考虑使用布隆过滤器。

真实世界的例子

  • Medium 使用布隆过滤器避免推荐给用户已经读过的文章。
  • Google Chrome 使用布隆过滤器识别恶意 URL。
  • Google BigTable,Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找。
  • Squid Web 代理使用布隆过滤器处理缓存摘要。

基本理解

布隆过滤器可以通过舍弃元素的特征来高效的存储大规模集合,比如它仅将通过算法对每一个元素应用哈希函数得到的数字存储到一系列位上进行关联。

事实上,布隆过滤器通过一个长度(m)和不同哈希函数的数量(k)的比特数组(bit arrary)来表示。

该数据结构仅支持两种操作:

  • 添加一个元素到集合中来,
  • 测试一个元素是否集合的成员。

布隆过滤器的数据结构是一个初始比特位都为 0 的比特数组,代表布隆过滤器为空。

举个例子,考虑如下示例中创建的布隆过滤器表示一个包含 10 个元素的集合并且误报率(FPP, False Positive Probability)为 0.1 (10%)。

一个空的布隆过滤器将通过一个长度为 m=48 (storageSize) 和 4 个哈希函数的比特数组用以支持生产范围在 {1, 2, ..., m} 的值。表示如下:

emptyBloomFilter
  <gtExample>
  | bloom |
  bloom := PDSBloomFilter new: 10 fpp: 0.1.
  self assert: bloom size eqauls: 0.
  self assert: bloom hashes equals: 4.
  self assert: bllom storageSize equals: 48.
  ^ bloom

要插入一个元素 x 到布隆过滤器中,需要对元素 x 应用到每一个哈希函数 \(h_i\) 上并计算它的值为 \(j=h_i(x)\) ,然后将布隆过滤器中 j 对应的位设置为 1 。

作为一个例子,我们将在上面的过滤器中插入一些城市的名字。让我们通过 'Madrid' 开始:

withMadridBloomFilter
  <gtExample>
  | bloom |
  bloom := self emptyBloomfilter.
  bloom add: 'Madrid' asByteArray.
  self assert: bloom size equals: 1.
  ^ bloom

布隆过滤器计算出了 4 个哈希值用以在集合中找到关联 'Madrid' 的比特位。如上图所展示,布隆过滤器设置了 9, 18, 39 和 48 。

不同的元素可能共享一个比特位,比如现在我们添加另一个城市 'Barcelona' 到上面相同的布隆过滤器中:

如你所见,在添加 'Barcelona' 到上面布隆过滤器之后只有 30, 36 和 42 所对应的比特位被设置,也就意味着元素 'Madrid''Barcelona' 共享了一个比特位。

要想测试给定的元素 x 是否在布隆过滤器之中,只需要检查所有的哈希函数 k 计算出的对应的比特位。如果所有位都被设置来,则表示元素 x 可能在布隆过滤器中,否则元素 x 一定不在其中。

元素存在不确定性是由于一些比特位可能是被之前添加的其他不同的元素所设置。

考虑前面的例子,在已经添加了元素 'Madrid''Barcelona' 的情况下,我们来测试元素 'Barcelona' 是否是该过滤器的成员,布隆过滤器计算出该元素的 4 个哈希值并且检查对应的比特位是否被设置,结果显示字符串 'Barcelona' 可能存在于过滤器之中,然后 contains: 'Barcelona' 返回 true

withMadridAndBarcelonaCheckBarcelonaBloomFilter
  <gtExample>
  | bloom |
  bloom := self withMadridBloomFilter.
  bloom add: 'Barcelona' asByteArray.
  self assert: bloom size equals: 2.
  self assert: (bloom contains: 'Barcelona' asByteArray).
  ^ bloom

现在如果我们检查元素 'Berlin' ,布隆过滤器为了找到对应的比特位会通过如下方式计算它的哈希值:

withBerlinBloomFilter
  <gtExample>
    | bloom |
    bloom := self emptyBloomFilter.
    bloom add: 'Berlin' asByteArray.
    self assert: bloom size equals: 1.
    ^ bloom

我们看到比特位 27 和 33 没有被设置,所以元素 'Berlin' 一定不存在于布隆过滤器中,所以 contains: 方法返回 false

withMadridAndBarcelonaCheckBerlinBloomFilter
  <gtExample>
  | bloom |
  bloom := self withMadridBloomFilter.
  bloom add: 'Barcelona' asByteArray.
  self assert: bloom size equals: 2.
  self assert: (bloom contains: 'Berlin' asByteArray) not.
  ^ bloom

布隆过滤器的结果也可能是错误的。例如,考虑元素 'Roma' 的 4 个哈希值 36 由于碰撞已经在我们的示例过滤器中设置,所以 contains: 方法认为该元素可能已经存在于过滤器中。

withMadridAndBarcelonaCheckRomaBloomFilter
  <gtExample>
    | bloom |
    bloom := self withMadridBloomFilter.
    bloom add: 'Barcelona' asByteArray.
    self assert: bloom size equals: 2.
    self assert: (bloom contains: 'Roma' asByteArray).
    ^ bloom

就像我们所了解到的,我们并没有添加过该元素到布隆过滤器中,所以这是一个误报的例子。在这个特别的案例中,比特位 36 已经被前面的元素 'Barcelona' 所设置。

特性

误报

如我们前面所展示,布隆过滤器会对一些不是集合中的成员的元素返回 true 。这种情况被成为误报(false positive),产生于哈希碰撞导致的巧合而将不同的元素存储在相同的比特位上。在测试操作中无法得知我们对比的特定的位是否被相同的哈希函数所设置。

幸运的是,布隆过滤器有一个可预测的误报率(FPP):

$$P_fp\approx\left(1-e^{-\frac{kn}{m}}\right)^k$$
  • n 是已经添加元素的数量;
  • k 哈希的次数;
  • m 布隆过滤器的长度(如比特数组的大小)。

极端情况下,当布隆过滤器没有空闲空间时(满),每一次查询都会返回 true 。这也就意味着 m 的选择取决于期望预计添加元素的数量 n ,并且 m 需要远远大于 n

实际情况中,布隆过滤器的长度 m 可以根据给定的误报率(FFP)的和期望添加的元素个数 n 的通过如下公式计算:

$$m=-\frac{n\ln{P_{fp}}}{(\ln2)^2}$$

对于 \(\frac{m}{n}\) 比率表示每一个元素需要分配的比特位的数量,也就是哈希函数 k 的数量可以调整误报率。通过如下公式来选择最佳的 k 可以减少误报率(FPP):

$$k=\frac{m}{n}\ln2$$

我们实现的 PDSBloomFilter 建立在指定预计添加元素的数量( n )和误报率( FPP )之上,然后使用上面的公式去计算最优的哈希次数和比特数组的长度。

比如,要处理 10 亿个元素并且保持 2% 左右的误报率我们需要如下布隆过滤器:

oneBillionBloomFilter
    <gtExample>
      | bloom |
      bloom := PDSBloomFilter new: 1000000000 fpp: 0.02.
      self assert: bloom size equals: 0.
      self assert: bloom hashes equals: 6.
      self assert: bloom storageSize equals: 8142363337.
      ^ bloom

如你所见,最优的哈希次数是 6 并且过滤器的长度是 \(8.14 x 10^9\) 个比特位,大约占用 1 GB 内存。

非误报

如果布隆过滤器返回特定的元素不是成员之一,那么该元素就绝对不在集合之中。

无法删除

要想从过滤器中删除一个元素需要在比特数组中取消设置相应数量( k )的比特位。不幸的是,由于哈希碰撞导致多个元素会共享比特位导致了一个比特位可能关联了多个元素。

分析

前面计算误报率(FPP)的公式为了容易计算从而假设了哈希函数 k 的随机是均匀分布的。

换句话说,一旦将期望的 n 个元素添加到数据结构中, fppPDSBloomFilter 初始化时指定的值应该解释为期望的 fpp 的值。

例如,对于一个刚刚创建依然保持为空的布隆过滤器的 fpp 值为 0,如下图所见:

fpp 的值会随着不断的向过滤器中添加元素而增长,并随着布隆过滤器中的元素数量达到期望值而最终达到目标 fpp ,我们通过如下填充布隆过滤器:

fullBloomFilter
    <gtExample>
    | bloom |
    bloom := self emptyBloomFilter.
    1 to: bloom targetElements
        do: [ :each | bloom add: each asString asByteArray ].
    ^ bloom

不过,你应该知道上面的 FPP 曲线是一个理论值并且实际观测到的 FPP 将会取决于特定的数据集和所使用的哈希函数。为了实验检查我们的实现的优点,我们进行了如下分析:

  1. 随机生成一个包含邮件地址的列表并插入到布隆过滤器。
  2. 随机生成一个包含邮件地址的列表不插入到该过滤器中。
  3. 统计在该过滤器中搜索缺失地址的误报情况。

我们运行的实验值在该过滤器期望元素个数的 10 到 1.5 倍(步长 10)。对于每种实验的元素数量运行 10 次。该分析通过一个图像展示了该过滤器的如下指标:

  • 理论的 FPP 曲线(蓝色)。
  • 每次实验测量到的平均 FPP 值(灰色十字)。
  • 实际的 FPP 曲线(红色)
  • 和标准差(红色阴影)

例如,如下代码运行上面的实验分析并且通过一个图展示一个包含 100 个元素和 3% 的 FPP 的布隆过滤器结果:

PDSBloomFilterAnalysis openFor: (PDSBloomFilter new: 100 fpp: 0.03)

压测

一个布隆过滤器每次操作只需要固定次数的探测( k ),所以在每次插入和查找的处理只需要 O(k) 的时间复杂度,也就是常量级的。

例如,如下代码将基于在前面被填充了 10 个元素的布隆过滤器上执行查找操作来运行一个微型压测并且展示每秒钟运行查找操作的次数:

由于时间复杂度是常量级的,那么一个前面添加了 100W 个元素的布隆过滤器的查找结果应该和上面类似:

一个基于 Collection 数据结构的简单实现将是线性的 O(n) 的时间复杂度,一个有序集合的最优情况将会是 O(log n) 的时间复杂度。你可以通过观察下面压测使用一个长度为 nOrderedCollection 集合的降级行为来检验:

VS

试玩

PharoPDS 提供了一个简单的工具让你可以探索和尝试布隆过滤器。

PDSBloomFilterPlayground 允许你创建一个布隆过滤器尝试一些操作并且进行可视化。甚至你可以基于 UI 运行压测和调优。

可以通过如下代码运行:

PDSBloomFilterPlayground open

引用

Category: Tech Tagged: Bloom Filter 布隆过滤器 Bloom Filter

comments


【译文】什么是幂等

Sun 05 May 2019

原文:WHAT IS IDEMPOTENCE

(原文是一个视频的文字记录版,有兴趣的可以看原文和原文中的视频,本文只翻译文字并结合自己的一些理解做一些整理。)

引子

幂等意味着可以重复,也就是说你可以安全的重试一个操作不会产生任何问题。经典的例子是电梯按钮:你按两次并不会叫来两辆电梯。同时我们来探索为什么在一个 Email 服务中需要这个特性。

什么是幂等?为什么幂等对于分布式编程非常有用?通过这篇文章,你将知道如何在你自己的系统中实现幂等。

幂等之所以重要是因为它抓住了安全重试的本质。没有安全重试也就没有办法实现一个安全的分布式协议。

什么是幂等?

幂等的本质就是你可以请求两次(或多次),但是和请求一次的所产生的副作用一致。经典的例子是电梯按钮。假设你来到一组电梯面前按下按钮,按钮亮起并呼叫电梯。然后另一个人同样来到这组电梯面前,按钮已经点亮但他依然按下相同的按钮。

我们都知道这样做不会产生任何效果(副作用),但是由于某些原因我们依然想这么做,仅仅为了以防万一。也许他是对的,也许一开始信号并没有传递给电梯。由于这样做没有任何坏处,所以为什么不呢?这就是我们想在我们的分布式系统中贯彻的理念。

技术上讲,这是一个属于代数的概念。当我们讨论按下按钮时,我们对现实的世界产生了一个有效的副作用。而在代数中,幂等是纯函数和数学函数的属性。幂等意味着你将字符串中的字母转换成大写两次对其结果没有任何影响,因为第一次操作就可以了。技术上来说,如果将函数 \(F …

Category: Tech Tagged: Idempotence 幂等

comments

Read More

Python 3.8 新增 multiprocessing.SharedMemory 支持共享内存

Thu 28 February 2019

Python 在 2019-02-25 释出了 3.8 早期预览版 3.8.0a2,其中新增了 multiprocessing.SharedMemory 用以支持共享内存,大大提高多进程之间通信效率。简单看了一下实现代码主要涉及如下 Python 模块

在 POSIX 平台下共享内存创建过程如下:

  1. 基于 tmpfs 打开或创建具名(文件名)的共享内存,得到文件描述符
  2. 通过 mmap 将文件描述符映射进程的内存地址空间
  3. 通过 memoryview 直接访问经过 mmap 映射后的的内存地址空间

锁的问题

memoryview 通过如下方式使用:

s = bytearray(b'aaa')
m = memoryview(s)
m[0 …

Category: Python Tagged: Python 3.8 multiprocessing 共享 内存 shared memory

comments

Read More

译文:Go 内存分配器可视化指南

Sat 23 February 2019

当我第一次开始尝试理解 Go 语言的内存分配器时,整个过程让我抓狂。一切看起来都像一个神秘的黑盒子。因为几乎所有技术魔法(technical wizardry)都隐藏在抽象之下,所以你需要一层一层的剥离才能去理解它。

我们将通过这篇文章来一层层的剥离这些细节。如果你想学习所有关于 Go 内存分配器的知识,那么这篇文章正适合你。

物理内存和虚拟内存

每一个内存分配器都需要运行在由底层操作系统管理的虚拟内存空间(Virtual Memory Space)之上。

下图是一个物理内存单元(Physical Memory Cell)的简要说明(非精准)

A simple illustration of a Physical Memory Cell

一个内存单元的概述经过大大简化之后描述如下:

  1. 地址线(Address line)(晶体管做的开关)用于访问电容器(数据到数据线(Data Lines))。
  2. 如果地址线有电流流动(显式为红色),数据线可以写入到电容器,所以电容器带电,逻辑值表示 “1”。
  3. 如果地址线没有电流流动(显式为绿色),数据线不可以写入到电容器,所以电容器不带电,逻辑值表示 “0”
  4. 当 CPU …

Category: Go Tagged: Go memory allocator

comments

Read More

《敏捷革命》读书笔记

Fri 15 February 2019

基本过程

准备

  1. 挑选一位 产品负责人(Product Owner) :负责沟通客户并根据客户反馈规划待办事项
  2. 挑选 团队 :小而精,3 ~ 9 人
  3. 挑选 Scrum 主管(Scrum Master) :培训 Scrum 确保 Scrum 正确运用,消除团队障碍
  4. 确定 冲刺(Sprint) 周期,不要超过一个月,最好 1 ~ 2 周

执行

  1. 产品负责人拟定 待办事项 ,并确定优先级

  2. 让实际开发的团队评估和改进待办事项

  3. 通过 冲刺规划会 规划接下来一个冲刺要完成的待办事项,并将借助 看板 工具将工作透明化

    看板可分为如下几个项:

    1. To do -- 当前冲刺需要完成的任务
    2. In progress …

Category: 读书 Tagged: Scrum Agile 敏捷 阅读

comments

Read More

通过 acme.sh 获取 Let's Encrypt 免费证书

Tue 12 February 2019

配置 Nginx 正确处理 Webroot 验证

在证书签发过程中 Let's Encrypt 会验证你拥有当前域名,最基本的方式在你的网站根目录创建一个文件,并通过域名在外部进行请求,如能请求到则认为你拥有该网站的控制权。假设你有一个域名 example.com, 验证步骤大体如下:

  1. 通过工具在网站根目录下创建 .well-known/acme-challenge/some-random-letters
  2. 工具将创建的路径告知 Let's Encrypt
  3. Let's Encrypt 通过域名请求该文件,如 http://example.com/.well-known/acme-challenge/some-random-letters
  4. 若能请求到则确认拥有该网站的控制权颁发证书,否则拒绝颁发

为了简化多个域名颁发证书需指定不同的 Webroot,我们可以将所有域名的验证统一放在一个目录下,并新增一个配置片段供需要启用 HTTPS 的网站引用,新增 /etc/nginx/snippets/letsencrypt-acme-challenge.conf ,并填充如下内容

#############################################################################
# Configuration file …

Category: Linux Tagged: SSL HTTPS

comments

Read More

修改本地 Git 历史

Wed 21 November 2018

很早之前一篇发表在内部的文章,抽时间整理了一下发布出来。

以下操作会修改提交历史, 可能会造成一些不可恢复的问题, 不是 下面情况不要这么操作

  1. 基于 GitHub Fork -> Pull Request 流程仅针对 Fork 后的仓库进行操作
  2. 非第一种情况的前提是当前修改的提交还未提交到远端

操作下面命令前最好先备份

修改上一条提交的信息

有时候我们在用 Git 提交后发现提交信息(commit message)不是我们预期的内容(错别字或描述错误等), 这个时候我们可能想修改一下上一条提交的信息, 有两种方式可以进行:

$ git commit --amend

这条命令会直接打开你的终端编辑器让你可以修改提交信息, 也可以组合 reset 命令重新提交:

$ git reset HEAD^ --soft
$ git commit -m 'new message'

这条命令会撤销上一条提交, 并将上一条提交的内容放在工作区内(git add 之后的区域), 然后就可以通过 git commit …

Category: Git Tagged: Git

comments

Read More

通过 pyenv 在生产环境安装 Python 3

Wed 21 November 2018

pyenv 是一个简单的 Python 版本管理, 可以安装对应版本的 Python 不依赖系统的包管理, 我用它来在生产和测试环境安装 Python 3.6.

它的基本原理是安装对应版本的 Python 在它自己的目录下, 然后将对应的 bin 目录通过插入 PATH 变量里实现.

安装可以参考官方文档, 但是用它部署 安装在 HOME 目录下会引起一些权限问题, 所以我将安装目录放在了 /srv/pyenv 下:

$ git clone https://github.com/pyenv/pyenv.git /srv/pyenv
$ echo 'export PYENV_ROOT="/srv/pyenv"' >> ~/.bash_profile
$ echo 'export PATH="$PYENV_ROOT/bin …

Category: Python Tagged: Python 2to3

comments

Read More
Page 1 of 11

Next »

Fork me on GitHub