你好,游客 登录 注册 发布搜索
背景:
阅读新闻

印度云端通信公司:我们是如何设计存储4亿个电话号码的

[日期:2015-07-23] 来源:jointforce.com  作者: [字体: ]

  如果你居住在印度,当不希望接受任何电话推销员的骚扰时,你可以在全国客户偏好登记册(National Customer Preference Register,NCPR) 【1 】 中进行注册。政府维护了这个由用户注册的电话号码组成的数据库。现在,差不多有4亿个注册号码。所有注册的电话推销员必须及时更新数据,以保证他们在进行推销时会参考这个偏好设置进行工作。

  这些数据由一捆ZIP文件(当下是40个)提供,每个ZIP文件包含一个10M的CSV文件。这篇文章将会讲述这2.4GB压缩后的数据如何基于一些简单的方式以一种可搜索的格式适配2GB的内存。

  数据

  下面是CSV文件一瞥(出于隐私原因,有些数据进行了混淆)

印度云端通信公司:我们是如何设计存储4亿个电话号码的

 

  关于存储在SQL引擎中的一些说明

  在内存为4GB的 Linode 机房的机器上, PostgreSQL数据表(使用COPY)加载数据约需要10分钟:

  real 10m0.159s

  user 2m42.243s

  sys 0m26.363s

  添加一个主键大约耗时1.5到2个小时:

  real 118m21.637s

  user 0m0.043s

  sys 0m0.020s

  并使用32GB的硬盘空间:

  

印度云端通信公司:我们是如何设计存储4亿个电话号码的

 

  观察CSV数据

  分析了数据之后,我们可以看到:

  * 将近400M行数据

  * 电话号码全部(phone numbers)是10位

  * 服务区域码(service area code)是1-23之间的自然数

  * 偏好(preference)依靠`#`来界定,可能是`0`或者是{1,2,3,4,5,7}的组合

  * Ops类型(Opstype)用A表示启用,用D表示未启用

  * 电话号码类型(Phone Type)是{1,2,3}中的一个

  这意味着一行数据可以用2个字节表示:

  第一个字节:1位存在标志位(existence flag),5位服务区域码,2位电话号码类型。

  第二个字节:7位偏好,1位Ops类型。

  

印度云端通信公司:我们是如何设计存储4亿个电话号码的

 

  数据可以通过2*400MB来表示。存在标志位将会在下面的部分讨论。

  使之可搜索

  每个条目都会按照电话号码进行频繁的搜索,而目前我们并没有将数据与电话号码进行匹配。我们需要添加字节来存储电话号码。不幸的是,10个数字并不能放入32位中(10 digits won't fit in 32 bits),使用5*400MB来存储数字并不是一个乐观的情况,而且根本没办法进行搜索。如果数据按顺序排列(arranged in a sequence),那么索引为 (2*number) 和 (2*number+1)的内存位置便能给出所需的两个字节。空行可以用第一个字节中的存在标志表示。这意味着我们需要20GB的内存(2字节*10B的数字)。我们能进一步压缩吗?该数组看起来很稀疏(只有40%被占用)。

  我们的解决方案是:使用两种格式类型。

  更进一步

  我们还发现对于大多数移动手机号码的数组是密集的 【 2 】 。所以,如果10个数字分成两部分——4位的前缀(我们可以称之为头部)和6位的数字偏移量(尾部)——这样一来,固定的4位前缀的所有可能值按顺序排列时,它们都可以被放入2MB的空间里了。(每个尾部2字节)。现在,搜索变得简单了,因为我们按照尾部进行偏移量计算,直接访问数组即可。

  这个稀疏的数列存储在5字节的序列中,3个字节表示尾部,2个字节表示数据。尾部按照升序排列,所以搜索变的简单了(二分搜索)。

  对于持久化存储,具有相同前缀的数字存储在一个文件中,该文件的第一个字节是类型的指示框。这些共需1.8GB的空间,这些数据可以存储在内存中,通过webserver进行发布。

  加工处理

  使用快速Python脚本来转换CSV数据为我们需要的格式是十分耗时的。分析表明,大部分时间花费在迭代处理2M固定头部数据时。我们尝试使用xrange进行优化,但是5小时对于处理整个数据,尤其是PostgreSQL处理仅需要2小时,实在太多了。我们希望能有些快速响应,更符合心理预期。相同的程序选择Rust来实现,处理整个数据仅用20-30分钟。

  real 21m4.284s

  user 20m58.427s

  sys 1m37.607s

  查找计时

  为了测量该解决方案的速度,我们随机生成了相同序列(固定的头部)的电话号码。结果如下图所示。我们选取“9818”和“9000” 开头的号码去分别计算查找密集框(我们称之为类型0)和稀疏框(类型1)的时间。对于SQL解决方案,头部的密集程度并不影响。注意,在本次测量中,尽管我们为了公平起见,计时时包含了磁盘的读写,但是在我们的解决方案中,数据一旦被加载或放入内存中,不再需要磁盘访问,之后由于数据存储格式的优点,这个进程被加快。

  

印度云端通信公司:我们是如何设计存储4亿个电话号码的

 

  所有的测试都是在4GB的Linode机房机器上跑的,机器配置如下:

  SSD, 4GB RAM, 4 virtual CPU cores, CPU Model: Intel(R) Xeon(R) CPU E5-2680 v2 @ 2.80GHz

  API和开源

  在SparkTG,我们尊重客户的偏好设置。尽管我们的客户大部分都是与注册的客户交流,但我们还是保证他们最终不会拨出一个无关的电话。我们已经将该项目 【3】 开源,并且提供API 【4】 来查找号码NCPR状态,使得电话推销找不到方式拨打注册用户的电话。

收藏 推荐 打印 | 录入:574107552 | 阅读:
相关新闻      
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款