资讯频道 → 企业架构
阅读更多

0顶
2踩

企业架构

转载新闻 我们是如何设计存储4亿个电话号码的

2015-07-22 16:28 by 副主编 mengyidan1988 评论(3) 有9891人浏览
postgresql python
如果你居住在印度，当不希望接受任何电话推销员的骚扰时，你可以在全国客户偏好登记册（National Customer Preference Register，NCPR） 【1】中进行注册。政府维护了这个由用户注册的电话号码组成的数据库。现在，差不多有4亿个注册号码。所有注册的电话推销员必须及时更新数据，以保证他们在进行推销时会参考这个偏好设置进行工作。

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

数据

下面是CSV文件一瞥（出于隐私原因，有些数据进行了混淆）



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

在内存为4GB的Linode机房的机器上， PostgreSQL数据表（使用COPY）加载数据约需要10分钟：



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



并使用32GB的硬盘空间：



观察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类型。



数据可以通过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分钟。


查找计时

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



所有的测试都是在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状态，使得电话推销找不到方式拨打注册用户的电话。

参考
1. https://en.wikipedia.org/wiki/Do_Not_Disturb_Registry

2. https://en.wikipedia.org/wiki/Mobile_telephone_numbering_in_India

3. Github repository

4. NCPR status lookup

原文：How we store 400M phone number data with fast lookups
译者：杰微刊-张帆
  • 大小: 8.6 KB
  • 大小: 4.3 KB
  • 大小: 4.1 KB
  • 大小: 3.8 KB
  • 大小: 5.5 KB
  • 大小: 4.1 KB
  • 大小: 18.6 KB
0
顶
2
踩
评论 共 3 条 请登录后发表评论
3 楼 windlike 2015-07-29 13:57
直接存储不行吗？
2 楼 MrLee23 2015-07-23 09:45
翻译的跟狗屎一样
1 楼 狗剩菜 2015-07-23 09:00
用的谷歌翻译吧，我还是去看原文

发表评论

您还没有登录,请您登录后再发表评论

相关推荐

  • 【C#进阶3-4】C#设计模式

    文章目录一、目录二、设计原则三、创建型模式3.1、单例模式（Singleton Pattern）3.2、工厂方法模式（Factory Pattern）3.3、抽象工厂模式（Abstract Pattern）3.4、建造者模式（Builder Pattern）3.5、原型模式...

  • mysql 中电话号码_类型-电话号码和地址的mysql数据类型

    如果存储少于100万条记录，而高性能不是问题，那么就使用varchar(20)/ char(20)，否则我发现对于存储甚至1亿部全球商务电话或个人电话，int都是最好的。 原因：较小的键->较高的读/写速度，格式化也可以允许重复...

  • 数据存储技术的相关概念

    每个人家里都会有冰箱，冰箱是用来干什么的？冰箱是用来存放水果蔬菜等食物的地方。同样的，数据库是存放数据的地方。正是因为有了数据库后，我们可以直接查找数据。例如你每天使用余额宝查看自己的账户收益，就是从...

  • 云存储云计算选择开源还是商业版

    每个公司在面临存储运算瓶颈时，都会面临一番挣扎，本篇文章我们来调研梳理开源与商业版本的选择对比。 选择商用云平台还是选择开源云平台创建企业的私有云，这确实是个问题。企业需要综合考虑，权衡利弊，...

  • 系统架构设计——互联网金融系统架构设计

    根据第三方机构预统计，自2016年-2019年，我国零售信贷规模维持20%以上的高复合增长率，2017年中国零售信贷规模达到27万亿，到2019年，总规模超过37万亿。近年来互联网金融蓬勃发展，在借贷、保险、股权等领域涌现出...

  • 海量数据处理 - 10亿个数中找出最大的10000个数（top K问题）

    在大规模数据处理中，经常会遇到的一类问题：在海量数据中找出出现频率最好的前k个数，或者从海量数据中找出最大的前k个数，这类问题通常被称为top K问题。例如，在搜索引擎中，统计搜索最热门的10个查询词；在歌曲...

  • [综述1.3] SSD及固态存储技术30年简史

    这多亏了存储行业的前辈们却摸爬滚打了将近半个世纪，才有了SSD的繁荣， 可惜很多前辈都没有机会看到。所有重大的技术革新都是这样，需要长期的技术积累，一代一代的工程师们默默的投入，最终改变我们的生活。从当年...

  • 1亿个数中找出最大的100个数（top K问题）

    但是在32位的机器上，每个float类型占4个字节，1亿个浮点数就要占用400MB的存储空间，对于一些可用内存小于400M的计算机而言，很显然是不能一次将全部数据读入内存进行排序的。其实即使内存能够满足要求（我机器内存...

  • 详解数据库设计的四个阶段

    数据库设计的第一步，就是了解与分析用户需求，确定系统边界信息需求、处理需求、安全性和完整性需求，然后编写系统分析报告。 系统分析报告的内容主要包括： 随系统分析报告需提供的附件还有： 需求分析有两种...

  • 【数仓】拉链表（极限存储）

    拉链表，我想做数仓的同学应该都是听过这个存储模式，拉链表的产生，源于维表存储中，如何存储和查询历史记录的问题 当然本文不是来介绍概念的（如果后面我觉得有需要，我会单独整理一下），主要是看了《大数据之路...

  • 从10亿个数字中找出最大的前100个数

    先拿10000个数建堆，然后一次添加剩余元素，如果大于堆顶的数（10000中最小的），将这个数替换堆顶，并调整结构使之仍然是一个最小堆，这样，遍历完后，堆中的10000个数就是所需的最大的10000个。建堆时间复杂度是O...

  • 数仓(三)：分层设计 ODS-DWD-DWS-ADS

    1、清晰数据结构：每一个数据分层都有它的作用域，这样我们在使用表的时候能更方便地定位和理解。 数据关系条理化：源系统间存在复杂的数据关系，比如客户信息同时存在于核心系统、信贷系统、理财系统、资金系统，...

  • DSP到底是个什么鬼？看完你就懂了

    至 80 年代中期，随着 CMOS 工艺的 DSP 芯片应运而生，其存储容量和运算速度都得到成倍提高，成为语音处理、图像硬件处理技术的基础。 80 年代后期，第三代 DSP 芯片问世。 运算速度进一步提高，其应用范围逐步扩大...

  • MongoDB 表设计

    12月12日上午，TJ在开源中国的年终盛典会上分享了文档模型设计的进阶技巧，就让我们来回顾一下吧: ——————————————————————————————————————————————————————...

  • 安卓-QQ-课程设计

    1. 前言：2017年学了一个月Android后写的小项目，文档近日才完成，项目与文档均为原创，发布出来以此怀念一下几年前。由于2017年写的项目，代码与技术均落后，但能提供下编写类似项目一点思路以及课程设计文档的编写...

  • HTTP协议理解及服务端与客户端的设计实现

    本文主要帮助读者理解 HTTP 的协作原理、HTTP 相关的各层协议，在服务端和客户端的架构设计和一些优化的技巧，本文中主要讲述逻辑思想和协议远离，会使用部分 Java 代码，但会有详细的讲解，非开发应该也读的明白。...

  • mysql存储手机号为什么不用bigint?

    char(11) 用来存储手机号，会占用11 bytes bigint 用来存储手机号,会占用 8 bytes varchar(11)用来存储手机号,会占用 12 bytes 从容量和速度上看，bigint是最好的选择。 从扩展性上看,如果有国际区号，业务上也不会...

  • PHP语言基础知识详解及常见功能应用.docx

    本文详细介绍了PHP的基本语法、变量类型、运算符号以及文件上传和发邮件功能的实现方法，适合初学者了解和掌握PHP的基础知识。

  • 公司金融课程期末考试题目

    公司金融整理的word文档

Global site tag (gtag.js) - Google Analytics