欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

海量数据处理思路

程序员文章站 2022-06-24 23:49:55
...

1. 计算容量

在解决问题之前,要先计算一下海量数据需要占多大的容量。常见的单位换算如下:

  • 1 byte = 8 bit
  • 1 KB = 210 byte = 1024 byte ≈ 10^3 byte
  • 1 MB = 220 byte ≈ 10^6 byte
  • 1 GB = 230 byte ≈ 10^9 byte
  • 1 亿 = 10^8

1 个整数占 4 byte,1 亿个整数占 4*10^8 byte ≈ 400 MB。

 

一些时候你会被要求做出保守估计。比如,你可能需要估计从磁盘中生成 100 张图片的缩略图需要的时间或者一个数据结构需要多少的内存。2 的次方表每个开发者都需要知道的一些时间数据(译注:OSChina 上有这篇文章的译文)都是一些很方便的参考资料。

2 的次方表

Power           Exact Value         Approx Value        Bytes
---------------------------------------------------------------
7                             128
8                             256
10                           1024   1 thousand           1 KB
16                         65,536                       64 KB
20                      1,048,576   1 million            1 MB
30                  1,073,741,824   1 billion            1 GB
32                  4,294,967,296                        4 GB
40              1,099,511,627,776   1 trillion           1 TB

每个程序员都应该知道的延迟数

Latency Comparison Numbers
--------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy            10,000   ns       10 us
Send 1 KB bytes over 1 Gbps network     10,000   ns       10 us
Read 4 KB randomly from SSD*           150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from 1 Gbps  10,000,000   ns   10,000 us   10 ms  40x memory, 10X SSD
Read 1 MB sequentially from disk    30,000,000   ns   30,000 us   30 ms 120x memory, 30X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

Notes
-----
1 ns = 10^-9 seconds
1 us = 10^-6 seconds = 1,000 ns
1 ms = 10^-3 seconds = 1,000 us = 1,000,000 ns

基于上述数字的指标:

  • 从磁盘以 30 MB/s 的速度顺序读取
  • 以 100 MB/s 从 1 Gbps 的以太网顺序读取
  • 从 SSD 以 1 GB/s 的速度读取
  • 以 4 GB/s 的速度从主存读取
  • 每秒能绕地球 6-7 圈
  • 数据中心内每秒有 2,000 次往返

延迟数可视化

海量数据处理思路

 

2. 拆分

可以将海量数据拆分到多台机器上和拆分到多个文件上:

  • 如果数据量很大,无法放在一台机器上,就将数据拆分到多台机器上。这种方式可以让多台机器一起合作,从而使得问题的求解更加快速。但是也会导致系统更加复杂,而且需要考虑系统故障等问题;
  • 如果在程序运行时无法直接加载一个大文件到内存中,就将大文件拆分成小文件,分别对每个小文件进行求解。

有以下策略进行拆分:

  • 按出现的顺序拆分:当有新数据到达时,先放进当前机器,填满之后再将数据放到新增的机器上。这种方法的优点是充分利用系统的资源,因为每台机器都会尽可能被填满。缺点是需要一个查找表来保存数据到机器的映射,查找表可能会非常复杂并且非常大。

 

海量数据处理思路

 

  • 按散列值拆分:选取数据的主键 key,然后通过哈希取模 hash(key)%N 得到该数据应该拆分到的机器编号,其中 N 是机器的数量。优点是不需要使用查找表,缺点是可能会导致一台机器存储的数据过多,甚至超出它的最大容量。

 

海量数据处理思路

 

  • 按数据的实际含义拆分:例如一个社交网站系统,来自同一个地区的用户更有可能成为朋友,如果让同一个地区的用户尽可能存储在同一个机器上,那么在查找一个用户的好友信息时,就可以避免到多台机器上查找,从而降低延迟。缺点同样是需要使用查找表。

 

海量数据处理思路

 

3. 整合

拆分之后的结果还只是局部结果,需要将局部结果汇总为整体的结果。

参考资料

  • 程序员面试金典
  • 程序员代码面试指南
相关标签: 分布式