海量数据处理思路
程序员文章站
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. 整合
拆分之后的结果还只是局部结果,需要将局部结果汇总为整体的结果。
参考资料
- 程序员面试金典
- 程序员代码面试指南