高并发类

设计一个能亿级并发的系统

https://blog.csdn.net/wenlin_xie/article/details/87708371
https://www.cnblogs.com/zhuzhen/p/9340941.html

数据处理类

海量数据场景处理思路

  • 分而治之/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 表示不存在。