October 24, 2018

3.5 Billion Mobiles Md5 Analysis

数据总不想给别人,但如果大家都抱着这样的态度,业界便无法再发展。由一个CRM接口想到的手机号md5存储权衡。

前几天在和厂家CRM系统集成时想到一个问题:CRM的某个接口是通过手机号查询信息,据说不是用明文手机号而是md5,我当时就想一个手机号的md5,应该decode不难吧,于是用我自己手机号的md5(十六进制表示)从网上搜索,在某个md5破解网站上很轻松得到md5之前的值,即我的手机号。

所以md5难道是一个噱头么?

拿到文档后发现并不是md5,而是md5的一部分,即十六进制表示的第八位开始,一共十六个字符,用这段不完整的md5来匹配,那看起来就比用完整md5好得多了,因为即便CRM记住你用的这段不完整md5,也很难还原回未完整md5,也就不能得到真实手机号了。


插播一下md5:md5常见结果是一个32位长的字符串,这是md5输出结果的十六进制表示。为何用十六进制表示呢?因为md5的结果是字节序列,并不一定是可打印可见的字符,如果直接输出可能会出现乱码或意想不到的效果,所以用十六进制表示,就全都是可见的字符了(0-9,a-f)。

如果不用十六进制表示,md5原始输出是十六个字节。常见的处理这十六个字节的方法还有一种是base64,也能得到一串可见字符。


因为CRM只需要中间那部分(中间的8个字节)的md5,我想会不会仅用中间这部分就能还原出手机号呢?

于是我把常见的手机号前缀收集起来,再把剩余部分从0到9补全,就得到了常见手机号数据集,有35.3亿条。

一开始打算把这些数据放在内存中比较,能快一些。本机的内存不够,一台闲置服务器内存接近200G,磁盘也够用,但最终发现程序还是被kill了,python自带的数据结构存储如此大量的数据就会出现问题,明明根据估算就算全都存储字符串也才xxx GB内存,我将近200G闲置内存还不游刃有余?可那个估算只能算是存储空间的占用,运行时有很多额外的支出,导致实际内存占用和存储占用值差很远。后来改用numpy,这个专注科学计算的库,相关数据结构和函数为了达到高速都用C实现,比原生数据结构好一些,但还是超了内存被kill。

所以我得想办法减少内存占用,或许就可以放到内存中处理了。

如果按照字节存储,那么一个号码只需要8字节,按照一行一个的话,再多加1字节换行符。但如果把这8字节的数据用十六进制表示出来,那么就需要8*2=16字节,因为一个字节是8个二进制位,1个十六进制字符可表示4个二进制位,所以需要16个十六进制字符来表示8字节数据,也就是说一个手机号用这种方式存储要占16字节数据,外加换行的话就是17字节。

了解了这些对于整个数据集占据的空间就有一定认识,对于选择合适的算法至关重要。大数据集找重复项是常见的面试题,但我在这个问题上花了太长时间,期间考虑了一些办法都没能很快解决(比如创建一个位图,但发现需要2^64这么大的列表,根本不可能创建出来)。最终用了一个办法,感觉效果不错。


对于一般的大数据集中寻找重复项问题,做法是把数据做hash运算,再将hash结果排序,再从排好序的结果中找是不是有连续的两个值是一样的,如果有的话,那么原数据集中就肯定会存在2条一样的数据。用这种方法的前提是选择的hash函数不能将2条不一样的数据映射到相同的hash值,这也是hash函数重要指标之一,所以选择md5、sha1这样常见稳定的都好。

因为这个问题的特殊性,本身数据就已经经过了hash处理,不需要再进行一次运算,直接存储到文件再排序就好了。

存储到文件遇到一个问题,如果把数据存到一个文件,那势必还会遇到读出到内存再把内存挤爆,这没有解决之前遇到的问题。

一般的面试题都会加条件,比如存储有限制、内存有限制、时间有限制等等。这里虽然内存很大,但仍然不能让我任性读到内存中处理,就算读进去了可能做个排序又要慢死了。

分治是一个好办法。

我根据8字节数据的第一个字节将所有数据分散到了256(2^8=256)个文件中,每个文件中存储的都是第一个字节相同的数据。最终每个文件都不大,106MB,存储时用的就是字节,而且没有换行符,等用的时候只需读入到内存中,再按照8字节长度进行分割就得到了hash后的值。

处理这些文件就相对容易了,只需要读入内存、分割、排序、比较。

时间上,分析单个文件不算慢,但全分析一遍也不是你能盯着一会就处理完的,由于闲置服务器有不少cpu核心(24个),我觉得应该用一下多进程模式加速处理。

下面的代码是用来寻找某个特定hash的手机号,用上20个核心处理所有手机号前缀,进程池中有20个,如果有足够的任务那么这20个进程将一刻不停的处理,但任务总是固定的,运行中的进程逐渐减少,最后就只剩下1个,总时间取决于运行时间最长的那个,不到10分钟就处理完了,之前用顺序扫描的方式,一个进程工作,总时间大概是现在的20倍。

# -*- coding: UTF-8 -*-
from __future__ import unicode_literals, print_function, division
import os
from multiprocessing import Pool
from hashlib import md5

POOL_SIZE = 20
prefixes = [134, 135, 136, 137, 138, 139, 150, 151, 157, 158, 159, 152, 188, 187, 182, 147, 183, 184, 1705, 178, 130, 131, 132, 145, 155, 156, 185, 186, 176,
            1709, 175, 133, 153, 189, 180, 181, 1700, 177]


def find_by_prefix(prefix):
    print('pid: {} processing: {}'.format(os.getpid(), prefix))
    min_mobile_no = str(prefix).ljust(11, b'0')
    max_mobile_no = str(prefix).ljust(11, b'9')
    for mobile in xrange(int(min_mobile_no), int(max_mobile_no) + 1):
        h = md5(str(mobile)).hexdigest()
        if 'b278c07e170dd4d3' in h:
            print('{} => {}'.format(mobile, h))


p = Pool(POOL_SIZE)
p.map(find_by_prefix, prefixes)
p.close()
p.join()

  • 用md5中间8字节的方式存储好处非常明显,存储空间降低一半,虽然出现重复,但35.3亿条中仅出现2条重复,对于绝大多数情况都在能接受的范围,数据量减少不仅仅意味着存储空间的减少,更多的可能是内存空间减少、数据库索引速度提升等。

  • 8字节重复的手机号是18928155506和17629858850

只有找特定md5的代码用了多进程,其实生成数据文件、分析文件这两步也可以改造:分析文件和查找特定md5一样,一个进程处理一个文件就好,因为单文件不大,一个进程处理起来时间尚可接受,更重要的是这个文件中第一个字节都是一致的,就应该让一个进程处理它而不是再拆分,当然你可以把分析文件这个任务拆成很多小任务,但那样就很复杂了。

生成数据文件的过程稍微有些特殊,因为第一个字节决定这条数据写到哪个文件中,一定会有多个号段的手机号写到同一个文件的情况,此时可以考虑用“字节编号-进程号”这种格式先写文件,等全部处理完后再将“字节编号”一致的文件合并起来,无所谓顺序,只需要合并到一起,因为在分析的时候会排序。

通过这样的改造,整个生成、分析、查找过程就会快很多,我只是想知道答案就按照怎么方便怎么写,有时候运行一下得几个小时,所以我说花在这上面的时间太长了。

Powered by Hugo & Kiss.