海量数据处理利器之Hash：在线邮件地址过滤

海量数据处理利器之Hash：在线邮件地址过滤2014-04-22 cnblogs MyDetail标题用了了海量数据（Massive datasets）而不用大数据（Big data）。感觉大数据还是略微有点虚，来点实际的。

一、需求

现在我们需要设计一个在线过滤垃圾邮件地址的方案，我们的数据库里面已经有10亿个合法的邮件地址（称为合法地址集S），当有新的邮件发过来时，要检查这个邮件地址是不是在我们的数据库里面，如果在，我们接收邮件，如果不在，我们就把它当做垃圾邮件过滤掉。

二、直觉想到的方法

一拿到这个问题，我就想到了用log（n）的折半查找，先将10亿个邮件地址排序，当收到一个邮件地址时，我利用折半查找，看邮件地址是否在S中，log（1,000,000,000） = 29.89约等于30，对每一个邮件地址我最多也只需要查找30次，感觉也挺快的，应该能满足要求。仔细想一下，折半查找必须放入内存，10个邮件地址还差不多，10亿个邮件地址我们来算一算有多大，邮件地址平均长度按20个字符计算，一个字符占用1Byte，一个email就占了20B，1,000,000,000X20B = 20GB，内存顶得住么，当然可以分多段进行折半，当分段需要多次I/O操作，需要的时间已经不是在线过滤所能承受的了。

三、利用hash处理问题

当数据量很大时，我们一些快速的方法已经不是多给点时间就能解决的，是压根解决不了，折半查找的方法在可接受的范围内是不可行的。我们来介绍一种神奇的方法，利用hash和位图实现常量时间确定邮件地址是否在S中。

1、过滤器初步设计

我们申请一个1GB的内存（虽然大了点，但现在的PC都顶得住了），1B共8位，1GB共有80亿位（实际应该为8X2^30=8,589,934,592位，但为了方便叙述，我们这里用80亿位）这个位图用B表示，B[i]表示位图的第i位；设计一个hash函数，将邮件地址映射到1-80亿的整数空间上。先将80亿位全部置为0 ，然后对S中的每一个邮件地址进行hash，hash得到一个整数k，就将第k位置为1，即B[k]=1，如果 hash函数设计得好，hash完S后，80亿的位图应该有10亿个（实际值比10亿小，后面会详细分析）位的值为1，当收到邮件时，对邮件地址进行hash，记hash得到的结果为p，如果B[p]=0，则邮件地址一定不再S中，即当作垃圾邮件过滤；如果B[p]=1，则邮件通过过滤，接收邮件。可以结合下图理解：

注意当B[p]=1时，我们并不是说新邮件地址一定在S中，而是说很可能在S中。B[p]=1只能说明S中一定有一个邮件地址URL，使得hash（URL）=p，而这不能保证其他垃圾邮件地址的hash值不等于p。B [p]=0说明S中不存在邮件地址URL，使得hash（URL）=p，从而新邮件地址一定不在S中。因此，被当作垃圾邮件过滤的邮件一定不包含合法的地址，而通过过滤的地址仍然有可能是垃圾邮件地址，大约有1/8 （1/8=10亿/80亿，不过实际值比1/8小，后面会详细分析）的垃圾邮件通过过滤，1/8也称为伪阳率。

这样的方案直接上线还是有问题的，因为伪阳率比较高，我们来计算一下照这种方案我们接收的邮件中垃圾邮件的比率是多少。根据新闻报道全球80%的邮件是垃圾邮件，于是P（接收到的垃圾邮件/接收的邮件）=（1/8*80%）/（20%+1/8*80%）=1/3（33.33%），也就是说平均收三封邮件就有一封是垃圾邮件，这对用户来说是不能忍受的，方案必须优化，不过我们应该看到，我们在不漏掉任何一个合法邮件的前提下过滤了7/8的垃圾邮件，已经初显hash利器之锋芒了。