本篇文章读左神书籍有感

布隆过滤器

不安全网页的黑名单包含100亿个黑名单网页，每个网页的URL最多占用64B。现在想要实现一个网页过滤系统，可以根据网页的URL判断该网页是否在黑名单上，请设计该系统。

要求：1，该系统允许有万分之一以下的判断失误率；2，使用的额外空间不要超过30GB。

解答：

保存全部的网页就需要640GB空间，所以用哈希表是不行的。这道题奇怪的地方在于，“允许有万分之一以下的判断失误率”，这是以前没有遇到过的。

如果面试者遇到网页黑名单系统、垃圾邮件过滤系统、爬虫的网址判重系统等题目，又看到系统容忍一定程度的失误率，但是对空间要求比较严格，那么很可能是面试官希望面试者具备布隆过滤器的知识。一个布隆过滤器精确地代表一个集合，可以精确的判断一个元素是否在集合中。注意，只是精确代表和精确判断，到底有多精确呢？则完全取决于具体的设计，但想做到完全正确是不可能的。布隆过滤器的优势就在于使用很少的空间就可以将准确率做到很高的程度。

假设有一个长度为m的bit类型的数组，另有k个哈希函数，这些哈希函数的输出域都大于或等于m，彼此之间完全独立。那么对同一个输入对象，经过k个哈希函数算出k个结果，每个结果对m取余（%m），然后在bit数组上将相应的位置涂黑（设为1）。

 

 

按上述方法处理所有的输入对象。

如何检查某个对象a是否在集合中呢？对a作上述同样处理，看计算出的k个位置是否全部为黑，如果有一个不为黑，说明a一定不在集合中；如果全部为黑，说明a在这个集合里，但可能有误判。

宁杀错，不放过。

参数计算

n：集合中元素个数；p：失误率

布隆过滤器的大小：m = - n * In(p) / (In2)^2
哈希函数的个数：k = 0.7 * m / n

布隆过滤器会有误报，对已经发现的误报样本可以通过建立白名单来防止误报。

 

只用2GB内存在20亿个整数中找到出现次数最多的数

有一个包含20亿个全是32位整数的大文件，在其中找到出现次数最多的数。

内存限制为2GB。

解答

注意点1，用哈希表来计数的话，键和值都要占用4B空间；2，关键不是有多少个数，而是有多少不同的数。

解决办法是把包含20亿个数的大文件用哈希函数分成10个小文件，根据哈希函数的性质，同一种数不可能被哈希到不同的小文件上，同时每个小文件中不同的数一定不会超过2亿种（20亿个数全部不同），假设哈希函数足够好。然后对每一个小文件用哈希表来统计每种数出现的次数（最多2亿个不同的数，0.2G * 4B * 2 = 1.6GB），这样就得到了10个小文件中出现次数最多的数，接下来只要选出最大的即可。

把一个大的集合通过哈希函数分配到多台机器中，或者分配到多个文件里，这种技巧是处理大数据面试题时最常用的技巧之一。但是到底分配多少台机器、分配到多少个小文件中，在解题时一定要确定下来。

 

 

40亿个非负整数中找到没有出现的数  bitmap

32位无符号整数的范围是0~4294967295，现在有一个真好包含40亿个无符号整数的文件，所以在整个范围内必然有没有出现的数。可以使用最多1GB内存，怎么找到所有没出现过的数？

进阶：内存限制为10MB，但是只用找到一个没出现过的数即可。

解答：

“出没出现”——用位图。正好0.5GB。

进阶：分区间统计落在各区间的数的个数，必有少的，再用10MB位图统计该区间各个数出现与否。

区间不能太大，否则10MB位图就不够了；合适大小是：（2^32）/（10* 2^20 *8）= 51.2，所以取一个64，挺合适。64个区间，每个区间的大小是：（232）/（26）= 2^26b = 8MB.

找到100亿个URL中重复的URL以及搜索词汇的top K问题

有一个包含100亿个URL 的大文件，假设每个URL占用64B，请找出其中所有重复的URL。

补充题目：某搜索公司一天的用户搜索词汇是海量的（百亿数据量），请设计一种方法求出每天最热top 100词汇。

大文件通过哈希分配到多台机器或多个小文件上。

首先，你要向面试官询问在资源上的限制有哪些，包括内存、计算时间等要求。在明确了限制要求之后，可以将每条URL通过哈希函数分配到若干台机器或拆分成若干小文件，这里的“若干”由具体的资源限制来计算出精确的数量。

原问题：哈希成若干小文件之后，再利用哈希表遍历，找出重复的URL。

补充问题：哈希成若干小文件之后，通过哈希表遍历，统计词频；再利用小根堆或直接排序找出每个小文件中的top 100词汇及其词频；然后把每个小文件的top 100再进行排序或利用小根堆，找出整个大文件的top 100.

40亿个非负整数中找到出现两次的数和所有数的中位数

32位无符号整数的范围是0~4294967295，现在有40亿个无符号数，可以使用最多1GB内存，找出所有出现了两次的数。

补充题目：可以使用最多10MB内存，怎么找到这40亿个整数的中位数（即排序后的第20亿个数）？

解答：

原问题：每个数用2位统计词频，需要2^32 * 1 / 4 B = 1GB.

补充问题：区间计数。划分区间统计落在每个区间的数的个数，这样就可以知道第20亿个数落在了哪个区间；然后用长度为区间大小的数组对落在该区间的数做频率统计，就可以得到第20亿个数。

这里用的是数组来统计频率而不是哈希表，省了一半的空间，而且不用排序。

数组大小或区间大小取2M，比较合适。这样就是2048个区间。

 

 

一致性哈希算法的基本原理

工程师常使用服务器集群来设计和实现数据缓存，以下是常见的策略：

1，无论是添加、查询还是删除数据，都先将数据的id通过哈希函数转换成一个哈希值，记为key；
2，如果目前机器有N台，则计算key%N的值，这个值就是该数据所属的机器编号，无论是添加、删除还是查询操作，都只在这台机器上进行。

以上缓存策略的潜在问题是如果增加或删除机器时（N变化），代价会很高，所有的数据都需要重新哈希一次，进行大规模的数据迁移。

为了解决这些问题，下面介绍一下一致性哈希算法。

一致性哈希算法中的哈希值范围是2^32，我们可以将这些值首尾相连，想象成一个闭合的环形，那么一个数据经过哈希之后就对应到环中的一个位置上。对服务器作同样的处理也将其映射到环的某个位置上。查找数据时，从数据映射的位置沿环顺时针查找离这个位置最近的服务器，那台服务器就是该数据的归属。

 

 

添加服务器时的处理：只用将m1到m3这一段的数据从m2迁移到m3上；
删除服务器：将删除服务器上的数据全部复制到顺时针找到的下一台服务器上即可。

image.png

机器负载不均衡时的处理

如果机器较少，很有可能造成机器在整个环上的分布不均匀，从而导致机器之间的负载不均衡。

为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即对每一台机器通过不同的哈希函数计算出多个哈希值，对多个位置都放置一个服务节点，称为虚拟节点。节点数变多了，根据哈希函数的性质，平衡性自然会变好。