布隆过滤器的原理分析
1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误判率率和删除困难。
实现原理
在实现上，布隆过滤器是通过一个或者多个Hash函数将一个元素映射成一个位阵列（Bit array）中的一个点。这样一来，我们只要看看这个点是不是1就可以知道集合中有没有它了，这就是布隆过滤器的基本思想。
误判率计算
由于布隆过滤器存在一定的误判率，所以在实际业务应用中，需要通过计算误判率和业务可接受的程度来确定是否使用布隆过滤器和如何使用。
具体与以下参数相关：
|
参数 |
说明 |
|
m |
布隆过滤器空间总大小，单位bit |
|
n |
布隆过滤器预期能够存储的元素个数 |
|
p |
误判率 |
|
k |
Hash函数个数 |
计算公式如下：
上面参数只要确定了两个，剩下两个也确定了，在应用中我们一般会先确定p，然后确定n或m，具体推论如下：
1、如果误判率是1%， 那么每个条目消耗的空间是 9.6bits
2、如果误判率是0.1%，那么每个条目消耗的空间是 14.4bits
3、如果误判率是0.01%，那么每个条目消耗的空间是 19.2bits
4、误判率最低时,k=m/n*ln2
布隆过滤器在推荐系统中的实践
在推荐系统中，为了提高给用户的推荐质量，需要对用户产生过行为的物品进行去重。通俗的说，就是不要给用户推荐用户看过的东西。
为了实现上述的功能，需要为每个用户建立曝光历史。在给用户进行推荐时拉取用户的曝光历史，根据曝光历史从推荐候选集中踢出用户已经消费过的物品。在推荐过后，将曝光的物品记录到用户的曝光历史中。所以可以使用布隆过滤器来存储用户的曝光历史，即曝光过的物品在布隆过滤器中记录为1。
以下以我以往工作中的信息流内容推荐场景方案的文章去重的方案设计来介绍布隆过滤器的实践。
存储量考虑
1、根据文章实际的业务场景，对于用户曝光记录，不太可能无限制的增加，考虑到新闻的时效性，每个用户保留最近5000条曝光记录足矣，用户5天内没有新增曝光记录则记录淘汰，这样既能保证去重效果，又能节省资源。
2、5000条记录不能单独存在一个布隆块中，这样用户初始数据量太大，就算只曝光一条记录也需要分配足以容纳5000条记录的位数组，浪费严重，所以需要对其进行分片。
分片设计
1、分片多少比较合适？这里需要兼顾性能和效率，片太小，需要维护的分片太多，最终比较的时候性能低；片太大，比较时效率高，但是初始资源占的多，浪费资源。最终我选择每块布隆过滤器容量为1000，最终用户可增加至5片布隆存储数据。
2、最终的设计方案如下图所示，以list形式将布隆过滤器数据块存储到redis，单块容量未超限时，更新最新的一块数据，否则新增新的布隆数据块，单个用户超出最大块数限制时，则对老的数据块进行裁剪：
推荐决策逻辑
判断时将该用户所有的布隆数据块进行加载，并且生成对应数量的布隆过滤器，然后将需要判断的文章id与每个布隆过滤器进行对比，只要有一个命中，说明它已经曝光过，否则说明该文章未推荐给过该用户。
不足之处
1、无法删除数据
2. 存在误判率
3. 不保存原数据，debug问题不方便
