如何设计一个海量数据过滤模块

系统设计

背景

所有的推荐系统都有一个基本的要求：不给用户推荐重复的信息

这里的重复的信息有两层含义

  1. 这个信息是id完全相同的一条信息
    这个很好理解，就是一模一样的两条信息，从数据库的角度将就是信息记录的主键id都相同
    如果用户已经接受过一次id为10086的信息的推荐，那这个10086就不能出现在后续的同类推荐中

  2. 这两个个信息相似度很高，但是id不同
    这种情况出现于两条信息内容相似，比如有两篇文章10001，10002都在说特朗普要在美国边境造墙的事情
    那如果用户观看过10001，此时再给用户推荐10002，就可能会让用户觉得推荐的东西已经看到过了，毫无意义

处理相同id的过滤

我们的目的是给定一个id, 和一个已推荐集合，判断id是否在给定的集合以内

HashMap的方案

如果集合数据量比较少的情况下，我们可以使用Java中的HashSet存储集合， 使用contains来直接判断id是否在给定集合中，其他编程语言中也都有类似HashSet的数据结构

由于HashSet的底层原理是使用的HashMap， 所以我直接使用 HashMap来进行原理的说明

这种做法的原理其实是先将我们要查找的数据进行hash散列，映射到一个固定长度的地址空间
然后使用数组存储，如果有多个id经过hash映射到相同的地址空间那就做一个链表，存储相同hashcode对应的值

具体结构如下：

1
2
3
4
5
|0|1009|0|1008|1998|          // hash数组槽
    ↓           ↓     
   107          87            // 槽内的指针对应的数据
    ↓            
   16

当我们查找id时， 也是先将要查找的id进行hash, 然后去对应的hashcode位置沿着链表/红黑树寻找是否有要查找的数字

优点

  1. 使用简单，性能好，比较通用
  2. 容易理解，无误判

缺点

  1. 空间利用率太低

Bitmap

考虑到HashMap的空间利用率太低，不适合海量数据的存储，我们可以利用计算机存储的一些特性，用另外一种方式来。

我们都知道计算机底层是用bit来存储信息的，每个bit能存储一个0或者1的信息，如果我们使用二进制bit的位置信息来表示数字，对应位的bit值是1来代表这个数字存在，我们就可以在极小的空间存储大量的信息，使用时只需使用位运算，查看对应位置的bit值即可。

Java中的bitset，redis中的bit操作都提供了这种bitmap的实现，bitmap的详情可以查看 使用bitmap构建用户标签

如下表示 【6，4，3】的集合，第6，4，3位为1，其他位为0

1
2
bit值     0 1 0 1 1 0 0 0        // 0x01011000
bit位     7 6 5 4 3 2 1 0

优点

  1. 空间利用率高，性能好，无误判

缺点

  1. 不够通用，要求数据的类型必须是数字且元素范围跨度不能太大

BloomFilter

bloomfilter跟bitmap具有相似的原理， 都是使用位来存储信息，区别在于

bitmap使用元素自身数字对应的位置信息来存储数据，如果要存储的元素是个字符串或者其他类型的数据就无法使用这种方式了，或者你要存储的数字范围特别的大，比如你要存储一个100亿的数字， 那样即使只有一个数字你也需要一个前面的位置都是0的100亿bit来表示，对空间的利用率还是不高 (现在有一些空间压缩的bitmap实现能一定程度解决数据范围分布过大和分布稀疏的问题)

BloomFilter就是针对这些做了优化，如果我们把要处理的数字进行hash, 映射到一个固定长度的地址空间，这样就同时解决了以上两个问题， 即缩减了映射的空间范围，又可以存储更通用的对象。但是由于hash函数本身会有冲突，就会出现两个不同元素因为同样的hashcode而产生误判的情况。

既如果判定结果是不存在(False)，则一定不存在；但是如果判定结果是存在(True)，则实际情况其实是可能存在，而不是一定存在，即假阳性。

误判率的计算

我们假设

  • 欲插入Bloom Filter中的元素数目: n
  • Bloom Filter误判率: P(true)
  • BitArray数组的大小: m
  • Hash Function的数目: k

则有误判率：
$$P(true) = (P^n_1)^k=[1-(1-\frac{1}{m})^kn]^k \tag{1}$$
即：
$$P(true)\approx(1-e^{-\frac{nk}{m}})^k \tag{2}$$
也就是说当BitArray数组的大小m增大 或 欲插入Bloom Filter中的元素数目n 减小时，均可以使得误判率P(true)下降

至于hash function的数目k

$$f(k)=(1-e^{-\frac{nk}{m}})^k \tag{3}$$
令 $a=e^{\frac{nk}{m}}$ ，则有：
$$f(k)=(1-e^{-1})^k$$
分别对上式两边，先取对数，再对k求一次导，可有：
$$\frac{1}{f(k)}f(k’)=\ln(1-a^{-k})+\frac{ka^{-k} \ln a}{1-a^{-k}}$$
易知，当k取极值点时，有 $f(k)’=0$ ，故将其带入上式即可求出k
$$\ln(1-a^{-k})+\frac{ka^{-k} \ln a}{1-a^{-k}}=0$$
$$=> (1-a^{-k}) \ln(1-a^{-k})=-ka^{-k} \ln a$$
$$=> e^{-\frac{kn}{m}}=\frac{1}{2}$$
$$=> k=\frac{m}{n}\ln2\approx0.7\frac{m}{n}$$
所以我们通过调整k的值也能一定程度上降低误判率， 但是基于概率的问题，误判率依然存在。所以这种方法适合于允许一定误判率，并拥有海量数据要过滤的场景

优点

  1. 通用，空间效率高，灵活，可以在性能和误判率之间做取舍

缺点

  1. 有误判，性能不如bitmap

处理相似文本的重复

能处理相同的id造成的重复之后，如果我们可以找出一个文章的相似内容， 只要把相似的内容id也添加到需要过滤的集合， 就可以完成对相似内容的过滤

simhash

如果只是检测一模一样的两个字符串，那我们完全可以采用md5之类的摘要算法， 但是这种方法对文章内容又哪怕一个字的差别，就不再适用

所以我们使用simhash来处理内容相似度的问题

simhash的核心思想是先提取文章的最重要核心特征， 如果两篇文章的核心特征重复度较高，那就有可能是相似文章，具体步骤如下

  1. 我们先对文本进行分词，并计算每个词的权重
  2. 对每个词进行hash，并把hash结果的对应二进制位的 0 变为 -1
  3. 把每个文章的每个词的处理过的 hash值 x 权重，得到加权向量，并把每个加权向量相加得到最终向量
  4. 把这个最终向量中的负数变为0，正数变为1

然后通过汉明距离比较二进制位不同的个数，其实就是计算两个指纹的异或结果，结果中如果包含较少的1， 比如小于3个， 那就说明内容相同