12.3 开发过程

12.3.1  了解“布隆过滤器”的基本原理


1．什么是布隆过滤器

布隆过滤器是一种基于概率进行验重的数据结构。它的基本原理是：小概率事件不容易同时发生。

下面用生活中的例子来形象地描述一下布隆过滤器的实现原理。例如，要从100  000个人里通过以下指标寻找一个从没有见过的目标人物：

●  上衣是红色的。

●  裤子是黑色的。

●  鞋子是咖啡色的。

●  衣服左边口袋别了一个胸针。

●  背了一个绿色的双肩包。

●  双手捂着肚子。

●  脸上全是汗水。

●  表情痛苦。

虽然没有见过目标人物，但由于这些寻找的指标都比较独特，虽然每一个指标都会有一部分人满足，但是能同时满足这些指标的人非常少。所以，当看到一个满足所有指标的人时，这个人就是目标人物的概率非常大。如果这种检测指标足够多、足够随机，一个人能同时满足所有检测指标，则认错人的概率会小到可以容忍，此时就可以认为这种检测是足够准确的。

布隆过滤器使用多个哈希函数把同一个字符串转换成多个不同的哈希值，并记录这些哈希值的特征。下次再面对一个字符串时，布隆过滤器再次使用这些哈希函数把这个字符串转换为多个哈希值。如果这些哈希值全部符合原先的那个字符串对应的各个哈希值的特征，则认为这两个字符串是相同的。

2．哈希函数

哈希算法不是一种加密算法，而是一种不可逆的摘要算法。不同的哈希函数可实现不同的哈希算法。哈希函数能把一个字符串不可逆地转换为一个十六进制值，这个值可能是32位，也可能是64位戓128位，甚至更高。这个值叫作哈希值。

使用同一个哈希算法，能够把同一个字符串转成同一个哈希值。例如，在Python中，可以使用hashlib这个自带的模块计算哈希值，见下方的代码：

>>>  import  hashlib

>>>  code  =  ’我叫青南’

>>>  result  =  hashlib.sha256(code.encode()).hexdigest()

>>>  print(result)

be30e0fe9d27d045ca730f0ca38cf4956c93e08a553e20e3db2856aeedb936cc

>>>

可以看出，使用  sha256算法计算“我叫青南”这个字符串的哈希值，得到的结果是be30e0fe9d27d045ca730f0ca38cf4956c93e08a553e20e3db2856aeedb936cc。这个结果虽然有数字又有字母，但实际上它是一个16进制的数，它是数字。

哈希函数对输入字符串的变化非常敏感，即使输入的字符串只有微小的改变，计算出来的哈希值也完全不同。例如在“我叫青南”后面加一个点，变成“我叫青南．”，继续使用sha256算法，得到的值为：8ea769251f0dae54547e0943aa2196b5161c1cb60a325860f488cb6cd9317a0d。

3．布隆过滤器的原理

假设选择K个哈希函数，对同一个字符串计算哈希值，就可以得到K个完全不同的哈希值。由于哈希值是数字，可以进行数学运算。那么让这K个哈希值同时除以一个数M，可以得到K个余数。记录下这K个余数。

对于一个新的字符串，重复这个过程，如果新字符串获得的K个余数与原来的字符串对应的K个余数完全相同，那么就可以说，这两个字符串“很有可能”是同一个字符串。

这个可能性，可以通过需要检查的字符串的总数N、哈希函数的个数K和被除数M这三个数计算出来。

提示：

这个可能性的计算公式为：

其中的e为自然对数的底，它是一个无理数，约等于2.718281828459045。

4．如何压缩数据容量

K个余数如何保存呢？无论是保存在Python的变量，还是在Redis的列表、集合或者哈希表中，占用的内存都非常可观。如何解决空间限制的问题呢？

举一个例子：一个人有两只手，一般情况下是10根手指，所以能够数0～10一共11个数字。那有没有办法用两只手准确数出100甚至1000个数字呢？答案就是使用二进制的方式。一根手指代表一个二进制位，10根手指就是10个二进制位，一共可以表示0～1023一共1024个数字。原本需要103人一起用10根手指才能数出1024个数，现在一个人就能全部数完。这就是数据的压缩。

在Redis的字符串中，一个字符是8个二进制位，8个二进制位可以储存256个数，见表12-1。

表12-1  8位二进制与十进制的对应关系

Redis的字符串的两个字符就是16个二进制位，可以存储65536个数，3个字符就是24个二进制位，可以存储224  个数。

Redis内部限制一个字符串最多存储232  个字符，那么就对应了  （232  的值作为指数）个数。这个数字，比整个宇宙中的所有细菌还多得多得多。而这么多的数，仅仅需要512MB内存。

5．如何把布隆过滤器与Redis结合起来

具体实现比原理简单。使用Redis字符串的位操作，记录K个余数的位置即可。要对Redis的字符串进行位操作，用到的两个命令为“setbit”和“getbit”。使用方法如下：

client.setbit('key',  offset,  value)

client.getbit('key',  offset)

其中，Key就是字符串的Key,offset就是第几位二进制位。value可以为0或1。例如：

01  import  redis

02  client  =  redis.Redis()

03  client.setbit('test',  100,  1)

04  client.setbit('test',  988,  0)

05  client.getbit('test',  100)

其中，主要说明如下。

●  第3行代码：把名为test的字符串对应的二进制位中的第100位设为1。

●  第4行代码：把名为test的字符串对应的二进制位中的第988位设为0。

●  第5行代码：从名为test的字符串对应的二进制位中，获取第100位。返回的结果为数字1。

在布隆过滤器中，只需要把K个余数作为Redis字符串二进制位的序号，把对应位数的值设为1。这样就把K个余数记录了下来。

6．布隆过滤器的弊端

如果有两个不同的字符串，理论上应该有2×K  个余数。但实际上可能有一部分余数是相同的。这样一来，对应到Redis的字符串二进制位上面，可能值为1的二进制位会少于2×K个。

这是正常现象。就像本章开头那个找人的例子，可能会有不同的人具有部分相同的指标。这样做的一个弊端是，布隆过滤器只能单向验证重复。即：当布隆过滤器把第1个字符串写入Redis的字符串中以后，它可以判断第2个字符串是不是和第1个字符串重复；但是布隆过滤器没有办法根据Redis字符串二进制位中记录的信息恢复第1个字符串。如果布隆过滤器中已经写入了多个不同字符串对应的余数，它也无法知道  Redis  字符串对应的二进制位中的某一位是哪一个字符串设置为1的。因此，布隆过滤器只能添加数据，不能删除数据。

随着Redis字符串对应的二进制位中越来越多的位被设置为1，布隆过滤器误报的概率越来越大，因为可能其他多个字符串对应的余数叠加在一起，其中的K个值刚好和一个新来的字符串的K个余数重合，这样一来就会导致这个本来不重复的字符串会被认为是重复的。

为了降低这种误报的概率，则需要提前规划好布隆过滤器将会验重的数据规模，以及能够容忍的误报率。有了这两个数据以后，就可以算出这个布隆过滤器需要多少个哈希函数，使用多少个二进制位。

提示：

最多需要对n个字符串进行验证重复的操作，能够容忍的最大误报率为p，那么，布隆过滤器将会使用到的二进制位的数量为：

哈希函数的个数为：

其中，ln是求自然对数。

假设需要对1亿个字符串进行验证重复的操作，能够容忍的误报率为0.1%，那么可以计算得到，需要的二进制位数位1437758757位（相当于字符串中的26个字符），需要9个哈希函数。



12.3.2  使用“布隆过滤器”对注册用户进行验重


1．设置去重位

布隆过滤器涉及的Redis操作，对应到RedisUtil.py中为set_bit_value方法。这个方法接收一个参数offset_list，使用for循环展开以后，每一次循环可以得到一个数字，这个数字就是需要在Redis的字符串对应的二进制位中置为1的位置。

为了实现这个过程，修改set_bit_value方法的代码为：

代码12-1  在Redis中设置某几位为1

注意，这里的offset_list是一个生成器，不是一个列表，不能使用offset_list[1]这种方式读取里面的值。

提示：

可能有读者会问，这个地方用循环来写数据，会不会出现并发冲突呢？比如  offset_list本来需要循环9次，但是循环到第5次时别人也在注册，别的用户名的第一次循环恰好要修改的是同一个位置。此时会出现冲突吗？

答案是不会。因为  Redis  内部是单线程单进程的，而且布隆过滤器只需要保证它修改的这位置的值是1就行了，不需要考虑这个位置是不是已经为1了。

2．验证用户名是否已经注册

验证用户名是否已经注册，只需要把用户名经过几个哈希函数计算出对应的字符串二进制位置，然后去Redis中检查这些位置的值是不是为1。

●  如果全部为1，则说明这个用户名已经被注册了，

●  如果至少有1位为0，则说明这个用户名没有被注册。

对应的方法为is_all_bit_1，将上一段代码修改为如下。

代码12-2  验证K位数据是否全为1

需要注意的是，第9行，Redis的getbit返回的数据是整型的1或者0，这和直接读取字符串的值返回bytes型的数据不同。

提示：

第8~9行代码，需要反复使用循环从Redis中读取数据。这个地方也不会出现并发冲突的问题。因为即将读的这一位无论是在循环的过程中被其他的进程设置为1，还是这个位置早就变成1了，并没有什么区别。

第8~9行代码的问题是：会对性能会有一些影响。因为每一次循环都有一次网络通信，而网络通信是非常消耗时间的。在本书这个例子中，因为只需要循环几次，所有网络通信导致的时间消耗可以忽略。但是如果循环的次数太多，则必须考虑网络消耗导致的问题。

3．添加分布式锁

设想这样一个场景，两个人同时使用不同的电脑注册，注册的用户名是相同的。此时，由于这个用户名之前没有注册过，那么这两个人不会被布隆过滤器拦住。由于布隆过滤器不能像Redis集合一样验证重复的同时就把数据添加进去，所以，从布隆过滤器确认一个用户名之前没有注册过，到网站把这个用户名添加到布隆过滤器中，这两步不是线程安全的，中间会有时间差。可能会有这样一种情况：第一个人刚刚通过布隆过滤器，正在把用户名添加到布隆过滤器中，这时另一个人恰好通过了布隆过滤器。这样就会导致两个人使用同一个用户名注册成功，从而出现两个用户名一样的用户。

为了防止这个问题，就需要使用Redis实现一个简单的分布式锁。

这个分布式锁会在Redis中创建一个普通的字符串，在创建字符串时会带上nx参数，使得只有在Redis中不存在这个Key时才能创建成功，如果Redis已经有这个Key了则创建失败。由于Redis是单线程单进程的，即使用两个人同时注册，那么这个添加字符串的过程也会被Redis排队，这会导致只有一个人能添加字符串成功，在另一个人添加时由于字符串已经存在了则添加失败。这就可以有效防止同时注册同一个账号。

设置分布式锁涉及两个方法，具体见下方代码：

代码12-3  设置分布式锁

其中，主要代码说明如下：

●  第8行，添加字符串时，设置nx=True，确保Redis不存在这个Key的情况下才能创建成功。添加了  nx=True  参数以后，如果设置字符串成功，则返回  True；如果设置字符串失败，则返回None。

●  第12行，delete_key方法的作用是，在注册完成以后删除锁，从而释放资源。



12.3.3  让“问题”与“回答”根据点赞数动态排序


根据点赞数排序的原理是：把每个问题和每个回答使用有序集合保存在  Redis  中，点赞数作为有序集合的评分。对评分进行排序也就实现了对问题或者回答根据点赞数进行排序的目的。

1．保存点赞记录

用户点赞和点踩的记录需要用MongoDB记录下来，对应修改MongoUtil.py的代码如下：

代码12-4  保存点赞记录

2．初始化问题的评分

当一个问题刚刚提出时，它的点赞数为0，此时需要把这个问题初始化到Redis的有序集合中。所有问题使用同一个有序集合，集合名为qa_system:question:vote。初始化的代码为：

代码12-5  初始化问题评分



3．初始化回答的评分

“回答”属于不同的“问题”，以“qa_system:answer:<问题ID>:vote”作为每一个问题下面所有回答使用的有序集合。当一个回答刚刚发布时，初始化排序的代码为：

代码12-6  初始化回答评分

4．调整问题或者回答的评分

调整有序集合中问题或者回答的评分。点赞就增加1分，点踩就减少1分。对应的代码为：

代码12-7  调整有序集合中问题或者回答的评分



其中，第10~13行代码，由于所有问题公用一个有序集合进行点赞排序，而不同问题的回答要放在不同的有序集合中进行点赞排序，所以需要根据doc_type的类型来构造redis_key。构造完成以后，使用有序集合的zincrby方法来修改积分。

5．根据点赞数获取问题或者回答的ID

根据点赞数对问题或者回答进行排序。首先在问题对应的有序集合中，使用zrevrange方法根据积分从高到低筛选出问题ID。如果同一个问题的积分相同，则有序集合会自动根据问题的ID从大到小进行排序。而如果问题的ID使用的是ObjectID,ObjectID是随着时间增加而增加的，后添加的问题的ObjectID更大，这样一来自然实现了“相同点赞数的问题，后提的问题排在前面”。

对应的操作Redis的代码为：

代码12-8  根据点赞数获取问题或回答的ID



需要注意的是，第20行代码获取到的结果格式为：

[(问题ID1，问题1点赞数),  (问题ID2，  问题2点赞数),  ...,  (问题IDn，  问题n点赞数)]

或者：

[(回答ID1，回答1点赞数),  (回答ID2，  回答2点赞数),  ...,  (回答IDn，  问题n点赞数)]

并且这里的问题ID或者回答ID，都是bytes型的数据，点赞数是浮点型数据。

由于实现了翻页功能，如果一页是3个问题或者3个回答，那么第1页对应的start为0，第2页对应的start为3，第3页对应的start为6，以此类推。

提示：

由于zrevrange的第2个参数表示截取返回的开始，第3个参数表示截取返回的结束，并且同时包含着两个短点，所以，如果要返回3个元素，则offset就应该设置为2，此时返回的是0、1、2这三个元素。

6．根据问题ID获取特定的问题

从Redis中获取的列表，包含了所有需要查询的问题的ObjectID，于是就需要从MongoDB中一次性把这些ObjectID对应的问题全部查询出来。此时就会使用到MongoDB的“$in”操作符。具体格式如下：

collection.find({'name':  {'$in':  ['kingname',  ’青南’,  ’超人’]}})

表示查询name为kingname或者“青南”或者“超人”的三条数据。

所以，查询问题对应于MongoUtil.py中的以下代码：

代码12-9  根据问题ID获取特定的问题

其中，主要代码说明如下。

●  第7行代码：查询问题的总数，这个数据用来实现翻页功能。

●  第14行代码：构造一个id_socre_dict字典，字符串型的问题ID作为Key，点赞数作为Value，用于记录每个问题的点赞数，避免重复查询MongoDB。

●  第14行代码：构造一个id_order_dict字典，Key为字符串型的问题ID,Value为问题ID对应的排序。用于对结果进行排序。

●  第16行代码：生成所有问题ID构成的列表。

●  第17~23行代码：在MongoDB聚合查询中查询所需要的问题及其对应的回答数。

●  第26~35行代码：对聚合查询的结果进行处理，记录点赞数和回答数。

●  第36行代码：以Redis返回的问题顺序对MongoDB查询的结果进行排序。

这个方法返回的数据中，question_list就是已经按照点赞数和回答时间倒序排序好的问题列表，在前端网页中直接依次列出即可。

7．根据回答ID查询特定的回答

从Redis中获取的回答列表包含了所有需要查询的回答的ObjectID，于是需要从MongoDB中一次把这些ObjectID对应的回答查询出来。

如需查询特定的回答，则需要修改MongoUtil.py中对应的如下代码：

代码12-10  根据回答ID查询特定的回答



其中，主要代码说明如下。

●  第14行代码：构造一个id_socre_dict字典，字符串型的回答ID作为Key，点赞数作为Value，用于记录每个回答的点赞数，避免重复查询MongoDB。

●  第15行代码：构造一个id_order_dict字典，用于对结果进行排序。Key为字符串型的回答ID,Value为回答ID对应的排序。

●  第16行代码：生成所有回答ID构成的列表。

●  第17行代码：查询问题的具体信息。由于在显示回答的页面也需要显示问题的详情，所以还是需要查询一次问题。

●  第18~23行代码：记录问题的详细信息。其中第23行需要记录这个问题一共有多少个回答。所以需要查询问题的全部回答数。

●  第25~32行代码：查询对应的回答，并记录信息。

●  第33行代码：对回答进行排序。

●  第32行代码：把排序好的回答添加到问题详情字典中。

完成上面的功能以后，就可以在问题详情页中显示这个问题按点赞数排列好的回答。



本章小结


本章主要介绍了通过布隆过滤器来实现大规模的用户昵称验重的功能，以及使用  Redis  有序集合实现点赞数动态排序的功能。

到目前为止，本项目并未限制一个用户对同一个问题或者回答点赞数，这将会作为本项目网站的一个特色功能——可以无限次点赞。如果读者希望限制点赞数，则可以使用哈希表记录用户的点赞信息。通过问题ID与用户昵称作为哈希表的字段名，值为1、0或者-1。

●  当值为1时，用户不能赞。

●  当值为-1时，用户不能踩；当值为0或者不存在这个字段时，用户可以点赞也可以踩。

对于回答，也是同样的逻辑。