Promacanthus

场景

同一个网页链接被包含在多个页面中时，会导致爬虫在爬取的过程中，重复爬取相同的网页，如何避免这些重复的爬取呢？

解决方案

记录已经爬取过的URL，爬取新网页前查看是否爬取过
已爬取过则忽略
未爬取过则先爬取后记录

注意点：

查询和添加操作要高效
上亿的网页，消耗内存非常高，存储效率要高

满足上述需求的数据结构有：

散列表
红黑树
跳表

在支持快速查询和插入的同时需要关注内存的消耗。

假设有10亿网页，一条URL平均长度64byte，全部存储起来需要大约60GB的内存。散列表需要保证较低的装填因子，采用链表法则还需要保存指针，实际使用的存储空间可能需要超过100GB。大型搜索引擎会使用分治的思想将这100GB的数据保存在多台服务器上。

分治+散列表的思路可以实现，那么在添加、查询和内存消耗上是否还有优化空间？

注意：时间复杂度只是表示执行时间随数据规模的变化趋势，并不能度量在特定的数据规模下，代码执行时间的多少。在数据量很大的情况下，常数、系数和低阶的优化都能带来非常可观的收益。

性能优化

执行效率

分治+散列表思路中耗时的点在于：通过哈希函数定位到某个链表之后，还要依次比对每个链表中的 URL。

一方面，链表中的结点在内存中不是连续存储的，不能一下子加载到 CPU 缓存中，没法很好地利用到 CPU 高速缓存，所以数据访问性能方面会打折扣。
另一方面，链表中的每个数据都是 URL，而 URL 不是简单的数字，是平均长度为 64 字节的字符串，要让待判重的 URL，跟链表中的每个 URL，做字符串匹配。这样一个字符串匹配操作，比起单纯的数字比对，要慢很多。

内存消耗

在内存消耗方面的优化，可以将散列表更换为布隆过滤器。布隆过滤器基于位图，且对位图进行了改进。

位图

问题

如何在数据范围是1~1亿之间的1千万个整数中快速查找某个整数是否存在。

散列表可以解决，位图也可以解决。

解决方案

使用位图来解决。

申请一个大小为 1 亿、数据类型为布尔类型（true 或者 false）的数组
将这 1 千万个整数作为数组下标，将对应的数组值设置成 true，如整数 5 对应下标为 5 的数组值设置为 true（array[5]=true）
查询某个整数 K 是否存在，只要将对应的数组值 array[K] 取出来判断是否为true
如果等于 true，说明存在整数 K
如果不等于true，说明不存在整数 K

注意：很多编程语言中提供的布尔类型，大小是 1 byte，并不能节省太多内存空间。实际上，表示 true 和 false 两个值，只需要用一个二进制位（bit）就可以。

如何通过编程语言，来表示一个二进制位（bit）可以使用位运算。

借助编程语言中提供的数据类型，比如 int、long、char 等类型，通过位运算，用其中的某个位表示某个数字。如下示例：

// byte占1个字节，8bit
type BitMap struct {
 bytes []byte
 nbits int
}

func NewBitMap(bits int) *BitMap {
 return &BitMap{
  bytes: make([]byte, bits/8+1),
  nbits: bits,
 }
}

func (b *BitMap) set(k int) {
 if k > b.nbits {
  return
 }
 byteIndex := k / 8
 bitIndex := k % 8
 b.bytes[byteIndex] |= 1 << bitIndex
}

func (b *BitMap) get(k int) bool {
 if k > b.nbits {
  return false
 }
 byteIndex := k / 8
 bitIndex := k % 8
 return (b.bytes[byteIndex] & (1 << bitIndex)) != 0
}

位图通过数组下标来定位数据，所以访问效率非常高
每个数字用一个二进制位（bit）表示，在数字范围不大的情况下，需要的内存空间非常节省

数据范围是1~1亿之间的1千万数据：

散列表存储：每个数据占32位（4个字节），总共有1千万个数据需要大约40MB
位图存储：每个数据占1位，数据最大范围1亿需要大约12.5MB

如果数据的范围更大，是1~10亿，数据量还是1千万，那么位图存储的空间是125MB，这就远大于散列表需要的存储空间。

这是就需要布隆过滤器来解决数据范围非常大这个问题了。

布隆过滤器

数据范围是1~10亿之间的1千万数据，使用布隆过滤器的处理策略是：

创建一个 1 亿个二进制大小的位图
通过哈希函数（如f(x)=x%n，n表示位图大小，即对数字跟位图的大小进行取模求余），对数字进行处理，让它落在这 1 到 1 亿范围内

注意：哈希会存在冲突，如一亿零一和 1 两个数字最终都存储在1这个位置。为了降低这种冲突概率，可以设计一个复杂点、随机点的哈希函数。

布隆过滤器的处理方法是：一个哈希函数可能会存在冲突，用多个哈希函数一块儿定位一个数据，来降低冲突的概率。

使用 K 个哈希函数，对同一个数字进行求哈希值，那会得到 K 个不同的哈希值，分别记作 X1，X2，X3，…，XK
把这 K 个数字作为位图中的下标，将对应的 BitMap[X1]，BitMap[X2]，BitMap[X3]，…，BitMap[XK]都设置成 true，用 K 个二进制位，来表示一个数字的存在
查询某个数字是否存在的时候，用同样的 K 个哈希函数，对这个数字求哈希值，分别得到 Y1，Y2，Y3，…，YK
看这 K 个哈希值，对应位图中的数值是否都为 true
1. 如果都是 true，则说明这个数字存在
2. 如果其中任意一个不为 true，说明这个数字不存在

对于两个不同的数字来说，经过一个哈希函数处理，可能会产生相同的哈希值。但是经过 K 个哈希函数处理之后，K 个哈希值都相同的概率就非常低了。

尽管采用 K 个哈希函数之后，两个数字哈希冲突的概率降低了，但是，这种处理方式又带来了新的问题，那就是容易误判。

bloom filter: False is always false. True is maybe true.

布隆过滤器只会对存在有误判：

如果某个数字经过布隆过滤器判断不存在，那这个数字真的不存在，不会误判
如果某个数字经过布隆过滤器判断存在，这时有可能误判，可能数字并不存在

只要调整哈希函数的个数、位图大小跟要存储数字的个数之间的比例，就可以将这种误判的概率降到非常低。

布隆过滤器的误判率，主要跟哈希函数的个数、位图的大小有关。

往布隆过滤器中不停地加入数据之后，位图中不是 true 的位置就越来越少了，误判率就越来越高。所以，对于无法事先知道要判重的数据个数的情况，需要支持自动扩容的功能
当布隆过滤器中，数据个数与位图大小的比例超过某个阈值，就重新申请一个新的位图。后面来的新数据，会被放置到新的位图中
如果要判断某个数据是否在布隆过滤器中已经存在，就需要查看多个位图，相应的执行效率就降低了一些

一般不用来删除，如果非要支持删除，可以再弄个数据结构记录删除的数据。

应用

尽管布隆过滤器会存在误判，但是，这并不影响它发挥大作用。很多场景对误判有一定的容忍度。

比如要解决的爬虫判重这个问题，即便一个没有被爬取过的网页，被误判为已经被爬取，对于搜索引擎来说，也并不是什么大事情，是可以容忍的，毕竟网页太多了，搜索引擎也不可能 100% 都爬取到。

布隆过滤器非常适合这种不需要 100% 准确的、允许存在小概率误判的大规模判重场景。

比如，统计一个大型网站的每天的 UV（Unique Visitor，独立访客）数，就可以使用布隆过滤器，对重复访问的用户进行去重。

存储优化

使用布隆过滤器解决爬虫去重问题：

用布隆过滤器来记录已经爬取过的网页链接
假设需要判重的网页有 10 亿，那可以用一个 10 倍大小的位图（100 亿个二进制位，约 1.2GB）来存储
用散列表判重，需要至少 100GB 的空间
相比来讲，布隆过滤器在存储空间的消耗上，降低了非常多

执行优化

布隆过滤器用多个哈希函数对同一个网页链接进行处理
CPU 只需要将网页链接从内存中读取一次，进行多次哈希计算，理论上讲这组操作是 CPU 密集型的
在散列表的处理方式中，需要读取散列值相同（散列冲突）的多个网页链接，分别跟待判重的网页链接，进行字符串匹配。这个操作涉及很多内存数据的读取，所以是内存密集型的
CPU 计算要比内存访问更快速，所以，理论上布隆过滤器的判重方式，更加快速

工业实现

Java 中的 BitSet 类是一个位图
Redis 提供了 BitMap 位图类
Google 的 Guava 工具包提供了 BloomFilter 布隆过滤器的实现

19 位图

场景

解决方案

性能优化

执行效率

内存消耗

位图

问题

解决方案

布隆过滤器

应用

存储优化

执行优化

工业实现