海量数据场景处理思路
- 分而治之/hash映射 + hash统计 + 堆/快速/归并排序
- 双层桶划分
- Bloom filter / Bitmap
- Trie树/数据库/倒排索引
- 外排序
- 分布式处理
海量数据排序
1TB的数据需要排序,限定使用32GB的内存如何处理?
例如,考虑一个 1G 文件,只可用内存 100M 的排序方法。首先将文件分成 10 个 100M ,并依次载入内存中进行排序,最后结果存入硬盘。得到的是 10 个分别排序的文件。接着从每个文件载入 9M 的数据到输入缓存区,输出缓存区大小为 10M 。对输入缓存区的数据进行归并排序,输出缓存区写满之后写在硬盘上,缓存区清空继续写接下来的数据。对于输入缓存区,当一个块的 9M 数据全部使用完,载入该块接下来的 9M 数据,一直到所有的 9 个块的所有数据都已经被载入到内存中被处理过。最后我们得到的是一个 1G 的排序好的存在硬盘上的文件。
解法:
- 把磁盘上的 1TB 数据分割为 40 块,每份 25GB。注意,要留一些系统空间!
- 顺序将每份 25GB 数据读入内存,使用 quick sort 算法排序。
- 把排序好的数据存放回磁盘。
- 循环 40 次,现在,所有的 40 个块都已经各自排序了。
- 从 40 个块中分别读取 25G/40 = 0.625G入内存
- 执行 40 路合并,并将合并结果临时存储于2GB 基于内存的输出缓冲区中。当缓冲区写满 2GB 时,写入硬盘上最终文件,并清空输出缓冲区当
- 40 个输入缓冲区中任何一个处理完毕时,写入该缓冲区所对应的块中的下一个 0.625GB ,直到全部处理完成。
继续优化:
- 使用并发:如多磁盘(并发I/O提高)、多线程、使用异步 I/O 、使用多台主机集群计算
- 提升硬件性能:如更大内存、更高 RPM 的磁盘、升级为 SSD 、 Flash 、使用更多核的 CPU
- 提高软件性能:比如采用 radix sort 、压缩文件(提高I/O效率)等
海量数据查询
海量日志数据,提取出某日访问百度次数最多的那个IP
解法:
首先过滤日志文件,将某日的 ip 过滤出来,保存在一个大文件内。然后对这些 ip 求 Hash 值,得到 Hash 值后再对 1000 取模,然后将计算后的值作为该 ip 写入的目标文件下标。上述操作中,每个 IP 仅会保存在 1000 个小文件中的某一个文件中。每个小文件中的数据以键值对的形式保存。最后可从这 1000 个小文件中找到一个或几个出现概率最大的 IP 。
海量日志数据,提取出搜索量前十的查询串,每个查询串的长度为1-255字节,要求内存不能超过1G(Top-K)
解法:
虽然有一千万 个Query,但是由于重复度比较高,因此事实上只有 300 万的 Query ,每个 Query 最大 255 Byte,因此我们可以考虑把他们都放进内存中去,而现在只是需要一个合适的数据结构,在这里, Hash 表是优先的选择。所以摒弃分而治之或 hash 映射的方法,直接上 hash 统计,然后排序。
一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。
解法:
顺序读取文件,对于每个词 x,取 Hash(x)%5000 ,存放到对应的 5000 个小文件中。这样,每个小文件大概为 200k 左右。然后加载每一个小文件并做Hash统计。最后使用堆排序取出前 100 个高频词,使用归并排序进行总排序。
给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?
解法:
顺序读取文件 a ,对每个 url 做如下操作:求 Hash(url)%1000 ,然后根据该值将 url 存放到 1000 个小文件中的某一个小文件并记录出现次数。按照这样划分,每个小文件的大小大约 300M 。同理,对文件 b 做上述操作。此时,如果存在相同的 url ,那么 url 一定会出现在同一个下标内的文件中。接下来只需要遍历这 1000 个文件即可。
2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数
采用 2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)进行,共需内存 2^32*2bit=1GB
内存,还可以接受。然后扫描这 2.5 亿个整数,查看 Bitmap 中相对应位,如果是 00 变 01 , 01 变 10 , 10 保持不变。扫描后,查看 bitmap ,把对应位是 01 的整数输出即可。
5亿个int找它们的中位数
首先我们将 int 划分为 2^16 个区域,然后读取数据统计落到各个区域里的数的个数,之后我们根据统计结果就可以判断中位数落到那个区域,同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。
实际上,如果不是 int 是 int64 ,我们可以经过 3 次这样的划分即可降低到可以接受的程度。即可以先将 int64 分成 2^24 个区域,然后确定区域的第几大数,在将该区域分成 2^20 个子区域,然后确定是子区域的第几大数,然后子区域里的数的个数只有 2^20 ,就可以直接利用direct addr table 进行统计了。
已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数
8 位最多99 999 999,大概需要 99m 个bit,大概 10m 字节的内存即可。 (可以理解为从0-99 999 999的数字,每个数字对应一个Bit位,所以只需要 99m 个Bit==1.2MBytes,这样,就用了小小的 1.2M 左右的内存表示了所有的8位数的电话)
给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?
申请 512M 的内存,一个 bit 位代表一个 unsigned int 值。读入 40 亿个数,设置相应的 bit 位,读入要查询的数,查看相应 bit 位是否为 1 ,为 1 表示存在,为 0 表示不存在。