海量数据处理

来源：http://www.cnblogs.com/200911/archive/2012/09/23/2698681.html

所谓海量数据处理，无非就是基于海量数据上的存储、处理、操作。何谓海量，就是数据量太大，所以导致要么是无法在较短时间内迅速解决，要么是数据太大，导致无法一次性装入内存。

    那解决办法呢?针对时间，我们可以采用巧妙的算法搭配合适的数据结构，如Bloom filter/Hash/bit-map/堆/数据库或倒排索引/trie树，针对空间，无非就一个办法：大而化小：分而治之/hash映射，你不是说规模太大嘛，那简单啊，就把规模大化为规模小的，各个击破不就完了嘛。

    至于所谓的单机及集群问题，通俗点来讲，单机就是处理装载数据的机器有限(只要考虑cpu，内存，硬盘的数据交互)，而集群，机器有多辆，适合分布式处理，并行计算(更多考虑节点和节点间的数据交互)。

    再者，通过本blog内的有关海量数据处理的文章：Big Data Processing，我们已经大致知道，处理海量数据问题，无非就是：

1 分而治之/hash映射 + hash统计 + 堆/快速/归并排序；

2 双层桶划分

3 Bloom filter/Bitmap；

4 Trie树/数据库/倒排索引；

5 外排序；

6 分布式处理之Hadoop/Mapreduce。

    下面，本文第一部分、从set/map谈到hashtable/hash_map/hash_set，简要介绍下set/map/multiset/multimap，及hash_set/hash_map/hash_multiset/hash_multimap之区别(万丈高楼平地起，基础最重要)，而本文第二部分，则针对上述那6种方法模式结合对应的海量数据处理面试题分别具体阐述。

第一部分、从set/map谈到hashtable/hash_map/hash_set

    稍后本文第二部分中将多次提到hash_map/hash_set，下面稍稍介绍下这些容器，以作为基础准备。一般来说，STL容器分两种，

· 序列式容器(vector/list/deque/stack/queue/heap)，

· 关联式容器。关联式容器又分为set(集合)和map(映射表)两大类，以及这两大类的衍生体multiset(多键集合)和multimap(多键映射表)，这些容器均以RB-tree完成。此外，还有第3类关联式容器，如hashtable(散列表)，以及以hashtable为底层机制完成的hash_set(散列集合)/hash_map(散列映射表)/hash_multiset(散列多键集合)/hash_multimap(散列多键映射表)。也就是说，set/map/multiset/multimap都内含一个RB-tree，而hash_set/hash_map/hash_multiset/hash_multimap都内含一个hashtable。

    所谓关联式容器，类似关联式数据库，每笔数据或每个元素都有一个键值(key)和一个实值(value)，即所谓的Key-Value(键-值对)。当元素被插入到关联式容器中时，容器内部结构(RB-tree/hashtable)便依照其键值大小，以某种特定规则将这个元素放置于适当位置。

     包括在非关联式数据库中，比如，在MongoDB内，文档(document)是最基本的数据组织形式，每个文档也是以Key-Value（键-值对）的方式组织起来。一个文档可以有多个Key-Value组合，每个Value可以是不同的类型，比如String、Integer、List等等。
{ "name" : "July", 
  "sex" : "male", 
    "age" : 23 } 

set/map/multiset/multimap

    set，同map一样，所有元素都会根据元素的键值自动被排序，因为set/map两者的所有各种操作，都只是转而调用RB-tree的操作行为，不过，值得注意的是，两者都不允许两个元素有相同的键值。
    不同的是：set的元素不像map那样可以同时拥有实值(value)和键值(key)，set元素的键值就是实值，实值就是键值，而map的所有元素都是pair，同时拥有实值(value)和键值(key)，pair的第一个元素被视为键值，第二个元素被视为实值。
    至于multiset/multimap，他们的特性及用法和set/map完全相同，唯一的差别就在于它们允许键值重复，即所有的插入操作基于RB-tree的insert_equal()而非insert_unique()。

hash_set/hash_map/hash_multiset/hash_multimap

    hash_set/hash_map，两者的一切操作都是基于hashtable之上。不同的是，hash_set同set一样，同时拥有实值和键值，且实质就是键值，键值就是实值，而hash_map同map一样，每一个元素同时拥有一个实值(value)和一个键值(key)，所以其使用方式，和上面的map基本相同。但由于hash_set/hash_map都是基于hashtable之上，所以不具备自动排序功能。为什么?因为hashtable没有自动排序功能。
    至于hash_multiset/hash_multimap的特性与上面的multiset/multimap完全相同，唯一的差别就是它们hash_multiset/hash_multimap的底层实现机制是hashtable(而multiset/multimap，上面说了，底层实现机制是RB-tree)，所以它们的元素都不会被自动排序，不过也都允许键值重复。

    所以，综上，说白了，什么样的结构决定其什么样的性质，因为set/map/multiset/multimap都是基于RB-tree之上，所以有自动排序功能，而hash_set/hash_map/hash_multiset/hash_multimap都是基于hashtable之上，所以不含有自动排序功能，至于加个前缀multi_无非就是允许键值重复而已。

    此外，

· 关于什么hash，请看blog内此篇文章：http://blog.csdn.net/v_JULY_v/article/details/6256463；

· 关于红黑树，请参看blog内系列文章：http://blog.csdn.net/v_july_v/article/category/774945，

· 关于hash_map的具体应用：http://blog.csdn.net/sdhongjun/article/details/4517325，关于hash_set：http://blog.csdn.net/morewindows/article/details/7330323。

    OK，接下来，请看本文第二部分、处理海量数据问题之六把密匙。



第二部分、处理海量数据问题之六把密匙

密匙一、分而治之/Hash映射 + Hash统计 + 堆/快速/归并排序

1、海量日志数据，提取出某日访问百度次数最多的那个IP。

    既然是海量数据处理，那么可想而知，给我们的数据那就一定是海量的。针对这个数据的海量，我们如何着手呢?对的，无非就是分而治之/hash映射 + hash统计 + 堆/快速/归并排序，说白了，就是先映射，而后统计，最后排序：

7 分而治之/hash映射：针对数据太大，内存受限，只能是：把大文件化成(取模映射)小文件，即16字方针：大而化小，各个击破，缩小规模，逐个解决

8 hash统计：当大文件转化了小文件，那么我们便可以采用常规的hash_map(ip，value)来进行频率统计。所谓边映射边统计，在映射成小文件的同时完成hash_map频率的统计。

9 堆/快速排序：统计完了之后，便进行排序(可采取堆排序)，得到次数最多的IP。

   具体而论，则是： “首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最大的IP中，找出那个频率最大的IP，即为所求。”--十道海量数据处理面试题与十个方法大总结。

    关于本题，还有几个问题，如下：

      1、有读者反应：既然用hash_map统计完之后还要排序，为何不直接用map搞定呢，同时完成统计和排序功能?但是凡是有利必有弊，别忘了，hash_map统计时的时间复杂度在O（1）内搞定，而map至少logK(若为K个元素)。

      2、Hash取模是一种等价映射，不会存在同一个元素分散到不同小文件中去的情况，即这里采用的是mod1000算法，那么相同的IP在hash后，只可能落在同一个文件中，不可能被分散的。

      3、那到底什么是hash映射呢？简单来说，就是为了便于计算机在有限的内存中处理big数据，从而通过一种映射散列的方式让数据均匀分布在对应的内存位置(如大数据通过取余的方式映射成小树存放在内存中，或大文件映射成多个小文件)，而这个映射散列方式便是我们通常所说的hash函数，设计的好的hash函数能让数据均匀分布而减少冲突。尽管数据映射到了另外一些不同的位置，但数据还是原来的数据，只是代替和表示这些原始数据的形式发生了变化而已。

    OK，有兴趣的，还可以再了解下一致性hash算法，见blog内此文第五部分：http://blog.csdn.net/v_july_v/article/details/6879101。

2、寻找热门查询：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。

    假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门），请你统计最热门的10个查询串，要求使用的内存不能超过1G。

    由上面第1题，我们知道，数据大则划为小的，但如果数据规模比较小，能一次性装入内存呢?比如这第2题，虽然有一千万个Query，但是由于重复度比较高，因此事实上只有300万的Query，每个Query255Byte，因此我们可以考虑把他们都放进内存中去，而现在只是需要一个合适的数据结构，在这里，Hash Table绝对是我们优先的选择。所以我们摒弃分而治之/hash映射的方法，直接上hash统计，然后排序。So，

10 hash统计：先对这批海量数据预处理(维护一个Key为Query字串，Value为该Query出现次数的HashTable，即hash_map(Query，Value)，每次读取一个Query，如果该字串不在Table中，那么加入该字串，并且将Value值设为1；如果该字串在Table中，那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内用Hash表完成了统计；

11 堆排序：第二步、借助堆这个数据结构，找出Top K，时间复杂度为N‘logK。即借助堆结构，我们可以在log量级的时间内查找和调整/移动。因此，维护一个K(该题目中是10)大小的小根堆，然后遍历300万的Query，分别和根元素进行对比所以，我们最终的时间复杂度是：O（N） + N'*O（logK），（N为1000万，N’为300万）。

    别忘了这篇文章中所述的堆排序思路：“维护k个元素的最小堆，即用容量为k的最小堆存储最先遍历到的k个数，并假设它们即是最大的k个数，建堆费时O（k），并调整堆（费时O（logk））后，有k1>k2>...kmin（kmin设为小顶堆中最小元素）。继续遍历数列，每次遍历一个元素x，与堆顶元素比较，若x>kmin，则更新堆（用时logk），否则不更新堆。这样下来，总费时O（k*logk+（n-k）*logk）=O（n*logk）。此方法得益于在堆中，查找等各项操作时间复杂度均为logk。”--第三章续、Top K算法问题的实现。
    当然，你也可以采用trie树，关键字域存该查询串出现的次数，没有出现为0。最后用10个元素的最小推来对出现频率进行排序。

3、有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
       由上面那两个例题，分而治之 + hash统计 + 堆/快速排序这个套路，我们已经开始有了屡试不爽的感觉。下面，再拿几道再多多验证下。请看此第3题：又是文件很大，又是内存受限，咋办?还能怎么办呢?无非还是：

12 分而治之/hash映射：顺序读文件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个小文件（记为x0,x1,...x4999）中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M。

13 hash统计：对每个小文件，采用trie树/hash_map等统计每个文件中出现的词以及相应的频率。

14 堆/归并排序：取出出现频率最大的100个词（可以用含100个结点的最小堆），并把100个词及相应的频率存入文件，这样又得到了5000个文件。最后就是把这5000个文件进行归并（类似于归并排序）的过程了。

4、海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。

    此题与上面第3题类似，

15 堆排序：在每台电脑上求出TOP10，可以采用包含10个元素的堆完成（TOP10小，用最大堆，TOP10大，用最小堆）。比如求TOP10大，我们首先取前10个元素调整成最小堆，如果发现，然后扫描后面的数据，并与堆顶元素比较，如果比堆顶元素大，那么用该元素替换堆顶，然后再调整为最小堆。最后堆中的元素就是TOP10大。

16 求出每台电脑上的TOP10后，然后把这100台电脑上的TOP10组合起来，共1000个数据，再利用上面类似的方法求出TOP10就可以了。

    上述第4题的此解法，经读者反应有问题，如举个例子如求2个文件中的top2，照上述算法，如果第一个文件里有

a 49次

b 50次

c 2次

d 1次

    第二个文件里有

a 9次

b 1次

c 11次

d 10次

     虽然第一个文件里出来top2是b（50次）,a（49次）,第二个文件里出来top2是c（11次）,d（10次）,然后2个top2：b（50次）a（49次）与c（11次）d（10次）归并，则算出所有的文件的top2是b(50 次),a(49 次),但实际上是a(58 次),b(51 次)。是否真是如此呢?若真如此，那作何解决呢？

    正如老梦所述：

    首先，先把所有的数据遍历一遍做一次hash(保证相同的数据条目划分到同一台电脑上进行运算)，然后根据hash结果重新分布到100台电脑中，接下来的算法按照之前的即可。

    最后由于a可能出现在不同的电脑，各有一定的次数，再对每个相同条目进行求和（由于上一步骤中hash之后，也方便每台电脑只需要对自己分到的条目内进行求和，不涉及到别的电脑，规模缩小）。

5、有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。

   直接上：

17 hash映射：顺序读取10个文件，按照hash(query)%10的结果将query写入到另外10个文件（记为）中。这样新生成的文件每个的大小大约也1G（假设hash函数是随机的）。

18 hash统计：找一台内存在2G左右的机器，依次对用hash_map(query, query_count)来统计每个query出现的次数。注：hash_map(query,query_count)是用来统计每个query的出现次数，不是存储他们的值，出现一次，则count+1。

19 堆/快速/归并排序：利用快速/堆/归并排序按照出现次数进行排序，将排序好的query和对应的query_cout输出到文件中，这样得到了10个排好序的文件（记为）。最后，对这10个文件进行归并排序（内排序与外排序相结合）。

     除此之外，此题还有以下两个方法：
    方案2：一般query的总量是有限的，只是重复的次数比较多而已，可能对于所有的query，一次性就可以加入到内存了。这样，我们就可以采用trie树/hash_map等直接来统计每个query出现的次数，然后按出现次数做快速/堆/归并排序就可以了。

    方案3：与方案1类似，但在做完hash，分成多个文件后，可以交给多个文件来处理，采用分布式的架构来处理（比如MapReduce），最后再进行合并。

6、 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？

    可以估计每个文件安的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

20 分而治之/hash映射：遍历文件a，对每个url求取，然后根据所取得的值将url分别存储到1000个小文件（记为）中。这样每个小文件的大约为300M。遍历文件b，采取和a相同的方式将url分别存储到1000小文件中（记为）。这样处理后，所有可能相同的url都在对应的小文件（）中，不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。

21 hash统计：求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。

    OK，此第一种方法：分而治之/hash映射 + hash统计 + 堆/快速/归并排序，再看最后4道题，如下：

7、怎么在海量数据中找出重复次数最多的一个？

    方案1：先做hash，然后求模映射为小文件，求出每个小文件中重复次数最多的一个，并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求（具体参考前面的题）。

8、上千万或上亿数据（有重复），统计其中出现次数最多的钱N个数据。

    方案1：上千万或上亿的数据，现在的机器的内存应该能存下。所以考虑采用hash_map/搜索二叉树/红黑树等来进行统计次数。然后就是取出前N个出现次数最多的数据了，可以用第2题提到的堆机制完成。

9、一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。

     方案1：这题是考虑时间效率。用trie树统计每个词出现的次数，时间复杂度是O(n*le)（le表示单词的平准长度）。然后是找出出现最频繁的前10个词，可以用堆来实现，前面的题中已经讲到了，时间复杂度是O(n*lg10)。所以总的时间复杂度，是O(n*le)与O(n*lg10)中较大的哪一个。

     10. 1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串。请怎么设计和实现？

· 方案1：这题用trie树比较合适，hash_map也行。

· 方案2：from xjbzju:，1000w的数据规模插入操作完全不现实，以前试过在stl下100w元素插入set中已经慢得不能忍受，觉得基于hash的实现不会比红黑树好太多，使用vector+sort+unique都要可行许多，建议还是先hash成小文件分开处理再综合。

    上述方案2中读者xbzju的方法让我想到了一些问题，即是set/map，与hash_set/hash_map的性能比较?共计3个问题，如下：

· 1、hash_set在千万级数据下，insert操作优于set? 这位blog：http://t.cn/zOibP7t 给的实践数据可靠不?

· 2、那map和hash_map的性能比较呢? 谁做过相关实验?



· 3、那查询操作呢，如下段文字所述?



    或者小数据量时用map，构造快，大数据量时用hash_map?

rbtree PK hashtable

    据朋友№邦卡猫№的做的红黑树和hash table的性能测试中发现：当数据量基本上int型key时，hash table是rbtree的3-4倍，但hash table一般会浪费大概一半内存。

    因为hash table所做的运算就是个%，而rbtree要比较很多，比如rbtree要看value的数据 ，每个节点要多出3个指针（或者偏移量） 如果需要其他功能，比如，统计某个范围内的key的数量，就需要加一个计数成员。

    且1s rbtree能进行大概50w+次插入，hash table大概是差不多200w次。不过很多的时候，其速度可以忍了，例如倒排索引差不多也是这个速度，而且单线程，且倒排表的拉链长度不会太大。正因为基于树的实现其实不比hashtable慢到哪里去，所以数据库的索引一般都是用的B/B+树，而且B+树还对磁盘友好(B树能有效降低它的高度，所以减少磁盘交互次数)。比如现在非常流行的NoSQL数据库，像MongoDB也是采用的B树索引。关于B树系列，请参考本blog内此篇文章：从B树、B+树、B*树谈到R 树。

    OK，更多请待后续实验论证。接下来，咱们来看第二种方法，双层捅划分。

密匙二、双层桶划分

双层桶划分----其实本质上还是分而治之的思想，重在“分”的技巧上！
　　适用范围：第k大，中位数，不重复或重复的数字
　　基本原理及要点：因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。可以通过多次缩小，双层只是一个例子。
　　扩展：
　　问题实例：

11、2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
　　有点像鸽巢原理，整数个数为2^32,也就是，我们可以将这2^32个数，划分为2^8个区域(比如用单个文件代表一个区域)，然后将数据分离到不同的区域，然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间，就可以很方便的解决。

12、5亿个int找它们的中位数。
　　这个例子比上面那个更明显。首先我们将int划分为2^16个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。
　　实际上，如果不是int是int64，我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域，然后确定区域的第几大数，在将该区域分成2^20个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有2^20，就可以直接利用direct addr table进行统计了。



密匙三：Bloom filter/Bitmap

Bloom filter

关于什么是Bloom filter，请参看blog内此文：

· 海量数据处理之Bloom Filter详解

　　适用范围：可以用来实现数据字典，进行数据的判重，或者集合求交集
　　基本原理及要点：
　　对于原理来说很简单，位数组+k个独立hash函数。将hash函数对应的值的位数组置1，查找时如果发现所有hash函数对应位都是1说明存在，很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter，用一个counter数组代替位数组，就可以支持删除了。
　　还有一个比较重要的问题，如何根据输入元素个数n，确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况下，m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些，因为还要保证bit数组里至少一半为0，则m应该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。
　　举个例子我们假设错误率为0.01，则此时m应大概是n的13倍。这样k大概是8个。
　　注意这里m与n的单位不同，m是bit为单位，而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。

　　扩展：
　　Bloom filter将集合中的元素映射到位数组中，用k（k为哈希函数个数）个映射位是否全1表示元素在不在这个集合中。Counting bloom filter（CBF）将位数组中的每一位扩展为一个counter，从而支持了元素的删除操作。Spectral Bloom Filter（SBF）将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。

13、给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。如果是三个乃至n个文件呢？

　　根据这个问题我们来计算下内存的占用，4G=2^32大概是40亿*8大概是340亿，n=50亿，如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿，相差并不多，这样可能会使出错率上升些。另外如果这些urlip是一一对应的，就可以转换成ip，则大大简单了。

    同时，上文的第5题：给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？如果允许有一定的错误率，可以使用Bloom filter，4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit，然后挨个读取另外一个文件的url，检查是否与Bloom filter，如果是，那么该url应该是共同的url（注意会有一定的错误率）。

Bitmap

· 关于什么是Bitmap，请看blog内此文：http://blog.csdn.net/v_july_v/article/details/6685962。

    下面关于Bitmap的应用，直接上题，如下第9、10道：

      14、在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数。

    方案1：采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存2^32 * 2 bit=1 GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。
    方案2：也可采用与第1题类似的方法，进行划分小文件的方法。然后在小文件中找出不重复的整数，并排序。然后再进行归并，注意去除重复的元素。

      15、腾讯面试题：给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？
    方案1：frome oo，用位图/Bitmap的方法，申请512M的内存，一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。

密匙四、Trie树/数据库/倒排索引

Trie树

　　适用范围：数据量大，重复多，但是数据种类小可以放入内存
　　基本原理及要点：实现方式，节点孩子的表示方式
　　扩展：压缩实现。
　　问题实例：

22 上面的第2题：寻找热门查询：查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个，每个不超过255字节。

23 上面的第5题：有10个文件，每个文件1G，每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query的频度排序。

24 1000万字符串，其中有些是相同的(重复),需要把重复的全部去掉，保留没有重复的字符串。请问怎么设计和实现？

25 上面的第8题：一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词。其解决方法是：用trie树统计每个词出现的次数，时间复杂度是O(n*le)（le表示单词的平准长度），然后是找出出现最频繁的前10个词。

    更多有关Trie树的介绍，请参见此文：从Trie树（字典树）谈到后缀树。

数据库索引
　　适用范围：大数据量的增删改查
　　基本原理及要点：利用数据的设计实现方法，对海量数据的增删改查进行处理。

· 关于数据库索引及其优化，更多可参见此文：http://www.cnblogs.com/pkuoliver/archive/2011/08/17/mass-data-topic-7-index-and-optimize.html；

· 关于MySQL索引背后的数据结构及算法原理，这里还有一篇很好的文章：http://www.codinglabs.org/html/theory-of-mysql-index.html；

· 关于B 树、B+ 树、B* 树及R 树，本blog内有篇绝佳文章：http://blog.csdn.net/v_JULY_v/article/details/6530142。

倒排索引(Inverted index)
　　适用范围：搜索引擎，关键字查询
　　基本原理及要点：为何叫倒排索引？一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。
　以英文为例，下面是要被索引的文本：
    T0 = "it is what it is"
    T1 = "what is it"
    T2 = "it is a banana"
    我们就能得到下面的反向文件索引：
    "a":      {2}
    "banana": {2}
    "is":     {0, 1, 2}
    "it":     {0, 1, 2}
    "what":   {0, 1}
　检索的条件"what","is"和"it"将对应集合的交集。

　　正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中，文档占据了中心的位置，每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词，而反向索引则是单词指向了包含它的文档，很容易看到这个反向的关系。
　　扩展：
　　问题实例：文档检索系统，查询那些文件包含了某单词，比如常见的学术论文的关键字搜索。

    关于倒排索引的应用，更多请参见：

· 第二十三、四章：杨氏矩阵查找，倒排索引关键词Hash不重复编码实践，

· 第二十六章：基于给定的文档生成倒排索引的编码与实践。

密匙五、外排序

　　适用范围：大数据的排序，去重
　　基本原理及要点：外排序的归并方法，置换选择败者树原理，最优归并树
　　扩展：
　　问题实例：
　　1).有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词。
　　这个数据具有很明显的特点，词的大小为16个字节，但是内存只有1M做hash明显不够，所以可以用来排序。内存可以当输入缓冲区使用。

    关于多路归并算法及外排序的具体应用场景，请参见blog内此文：

· 第十章、如何给10^7个数据量的磁盘文件排序

密匙六、分布式处理之Mapreduce

    MapReduce是一种计算模型，简单的说就是将大批量的工作（数据）分解（MAP）执行，然后再将结果合并成最终结果（REDUCE）。这样做的好处是可以在任务被分解后，可以通过大量机器进行并行计算，减少整个操作的时间。但如果你要我再通俗点介绍，那么，说白了，Mapreduce的原理就是一个归并排序。

        适用范围：数据量大，但是数据种类小可以放入内存
　　基本原理及要点：将数据交给不同的机器去处理，数据划分，结果归约。
　　扩展：
　　问题实例：

26 The canonical example application of MapReduce is a process to count the appearances of each different word in a set of documents:

27 海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。

28 一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中数(median)？

    更多具体阐述请参见blog内：

· 从Hadhoop框架与MapReduce模式中谈海量数据处理，

· 及MapReduce技术的初步了解与学习。

其它模式/方法论，结合操作系统知识

    至此，六种处理海量数据问题的模式/方法已经阐述完毕。据观察，这方面的面试题无外乎以上一种或其变形，然题目为何取为是：秒杀99%的海量数据处理面试题，而不是100%呢。OK，给读者看最后一道题，如下：

    非常大的文件，装不进内存。每行一个int类型数据，现在要你随机取100个数。

    我们发现上述这道题，无论是以上任何一种模式/方法都不好做，那有什么好的别的方法呢？我们可以看看：操作系统内存分页系统设计(说白了，就是映射+建索引)。

·     Windows 2000使用基于分页机制的虚拟内存。每个进程有4GB的虚拟地址空间。基于分页机制，这4GB地址空间的一些部分被映射了物理内存，一些部分映射硬盘上的交换文 件，一些部分什么也没有映射。程序中使用的都是4GB地址空间中的虚拟地址。而访问物理内存，需要使用物理地址。 关于什么是物理地址和虚拟地址，请看：
物理地址 (physical address): 放在寻址总线上的地址。放在寻址总线上，如果是读，电路根据这个地址每位的值就将相应地址的物理内存中的数据放到数据总线中传输。如果是写，电路根据这个 地址每位的值就将相应地址的物理内存中放入数据总线上的内容。物理内存是以字节(8位)为单位编址的。

· 虚拟地址 (virtual address): 4G虚拟地址空间中的地址，程序中使用的都是虚拟地址。 使用了分页机制之后，4G的地址空间被分成了固定大小的页，每一页或者被映射到物理内存，或者被映射到硬盘上的交换文件中，或者没有映射任何东西。对于一 般程序来说，4G的地址空间，只有一小部分映射了物理内存，大片大片的部分是没有映射任何东西。物理内存也被分页，来映射地址空间。对于32bit的 Win2k，页的大小是4K字节。CPU用来把虚拟地址转换成物理地址的信息存放在叫做页目录和页表的结构里。

    物理内存分页，一个物理页的大小为4K字节，第0个物理页从物理地址 0x00000000 处开始。由于页的大小为4KB，就是0x1000字节，所以第1页从物理地址 0x00001000 处开始。第2页从物理地址 0x00002000 处开始。可以看到由于页的大小是4KB，所以只需要32bit的地址中高20bit来寻址物理页。

    返回上面我们的题目：非常大的文件，装不进内存。每行一个int类型数据，现在要你随机取100个数。针对此题，我们可以借鉴上述操作系统中内存分页的设计方法，做出如下解决方案：

    操作系统中的方法，先生成4G的地址表，在把这个表划分为小的4M的小文件做个索引，二级索引。30位前十位表示第几个4M文件，后20位表示在这个4M文件的第几个，等等，基于key value来设计存储，用key来建索引。

    但如果现在只有10000个数，然后怎么去随机从这一万个数里面随机取100个数？请读者思考。

参考文献

29 十道海量数据处理面试题与十个方法大总结；

30 海量数据处理面试题集锦与Bit-map详解；

31 十一、从头到尾彻底解析Hash表算法；

32 海量数据处理之Bloom Filter详解；

33 从Trie树（字典树）谈到后缀树；

34 第三章续、Top K算法问题的实现；

35 第十章、如何给10^7个数据量的磁盘文件排序；

36 从B树、B+树、B*树谈到R 树；

37 第二十三、四章：杨氏矩阵查找，倒排索引关键词Hash不重复编码实践；

38 第二十六章：基于给定的文档生成倒排索引的编码与实践；

39 从Hadhoop框架与MapReduce模式中谈海量数据处理；

40 第十六~第二十章：全排列，跳台阶，奇偶排序，第一个只出现一次等问题；

41 http://blog.csdn.net/v_JULY_v/article/category/774945；

42 STL源码剖析第五章，侯捷著。

后记

    经过上面这么多海量数据处理面试题的轰炸，我们依然可以看出这类问题是有一定的解决方案/模式的，所以，不必将其神化。然这类面试题所包含的问题还是比较简单的，若您在这方面有更多实践经验，欢迎随时来信与我不吝分享：[e-mail]。当然，自会注明分享者及来源。

    不过，相信你也早就意识到，若单纯论海量数据处理面试题，本blog内的有关海量数据处理面试题的文章已涵盖了你能在网上所找到的70~80%。但有点，必须负责任的敬告大家：无论是这些海量数据处理面试题也好，还是算法也好，面试时，70~80%的人不是倒在这两方面，而是倒在基础之上，所以，无论任何时候，基础最重要，没了基础，便什么都不是。如果你问我什么叫做掌握了基础，很简单，我可以举个例子，如到这里：http://forum.csdn.net/BList/Cpp/，如果你几乎能解决那里的全部问题，那么你的c/c++基础便够了。

    最后，推荐国外一面试题网站：http://www.careercup.com/，以及个人正在读的Redis/MongoDB绝佳站点：http://blog.nosqlfan.com/。本blog算法交流群第20群Algorithms_20，149977547(4月份内有效)。

    OK，本文若有任何问题，欢迎随时不吝留言，评论，赐教，谢谢。完。

         从hadoop框架与MapReduce模式中谈海量数据处理

前言

    几周前，当我最初听到，以致后来初次接触Hadoop与MapReduce这两个东西，我便稍显兴奋，觉得它们很是神秘，而神秘的东西常能勾起我的兴趣，在看过介绍它们的文章或论文之后，觉得Hadoop是一项富有趣味和挑战性的技术，且它还牵扯到了一个我更加感兴趣的话题：海量数据处理。

    由此，最近凡是空闲时，便在看“Hadoop”，“MapReduce”“海量数据处理”这方面的论文。但在看论文的过程中，总觉得那些论文都是浅尝辄止，常常看的很不过瘾，总是一个东西刚要讲到紧要处，它便结束了，让我好生“愤懑”。

    尽管我对这个Hadoop与MapReduce知之甚浅，但我还是想记录自己的学习过程，说不定，关于这个东西的学习能督促我最终写成和“经典算法研究系列”一般的一系列文章。

    Ok，闲话少说。本文从最基本的mapreduce模式，Hadoop框架开始谈起，然后由各自的架构引申开来，谈到海量数据处理，最后谈谈淘宝的海量数据产品技术架构，以为了兼备浅出与深入之效，最终，希望得到读者的喜欢与支持。谢谢。

    由于本人是初次接触这两项技术，文章有任何问题，欢迎不吝指正。再谢一次。Ok，咱们开始吧。

第一部分、mapreduce模式与hadoop框架深入浅出

架构扼要

         想读懂此文，读者必须先要明确以下几点，以作为阅读后续内容的基础知识储备：

1 Mapreduce是一种模式。

2 Hadoop是一种框架。

3 Hadoop是一个实现了mapreduce模式的开源的分布式并行编程框架。

    所以，你现在，知道了什么是mapreduce，什么是hadoop，以及这两者之间最简单的联系，而本文的主旨即是，一句话概括：在hadoop的框架上采取mapreduce的模式处理海量数据。下面，咱们可以依次深入学习和了解mapreduce和hadoop这两个东西了。

Mapreduce模式

    前面说了，mapreduce是一种模式，一种什么模式呢?一种云计算的核心计算模式，一种分布式运算技术，也是简化的分布式编程模式，它主要用于解决问题的程序开发模型，也是开发人员拆解问题的方法。

    Ok，光说不上图，没用。如下图所示，mapreduce模式的主要思想是将自动分割要执行的问题（例如程序）拆解成map（映射）和reduce（化简）的方式，流程图如下图1所示：



    在数据被分割后通过Map 函数的程序将数据映射成不同的区块，分配给计算机机群处理达到分布式运算的效果，在通过Reduce 函数的程序将结果汇整，从而输出开发者需要的结果。

    MapReduce 借鉴了函数式程序设计语言的设计思想，其软件实现是指定一个Map 函数，把键值对(key/value)映射成新的键值对(key/value)，形成一系列中间结果形式的key/value 对，然后把它们传给Reduce(规约)函数，把具有相同中间形式key 的value 合并在一起。Map 和Reduce 函数具有一定的关联性。函数描述如表1 所示：



    MapReduce致力于解决大规模数据处理的问题，因此在设计之初就考虑了数据的局部性原理，利用局部性原理将整个问题分而治之。MapReduce集群由普通PC机构成，为无共享式架构。在处理之前，将数据集分布至各个节点。处理时，每个节点就近读取本地存储的数据处理（map），将处理后的数据进行合并（combine）、排序（shuffle and sort）后再分发（至reduce节点），避免了大量数据的传输，提高了处理效率。无共享式架构的另一个好处是配合复制（replication）策略，集群可以具有良好的容错性，一部分节点的down机对集群的正常工作不会造成影响。

    ok，你可以再简单看看下副图，整幅图是有关hadoop的作业调优参数及原理，图的左边是MapTask运行示意图，右边是ReduceTask运行示意图：



    如上图所示，其中map阶段，当map task开始运算，并产生中间数据后并非直接而简单的写入磁盘，它首先利用内存buffer来对已经产生的buffer进行缓存，并在内存buffer中进行一些预排序来优化整个map的性能。而上图右边的reduce阶段则经历了三个阶段，分别Copy->Sort->reduce。我们能明显的看出，其中的Sort是采用的归并排序，即merge sort。

    了解了什么是mapreduce，接下来，咱们可以来了解实现了mapreduce模式的开源框架—hadoop。

Hadoop框架

    前面说了，hadoop是一个框架，一个什么样的框架呢?Hadoop 是一个实现了MapReduce 计算模型的开源分布式并行编程框架，程序员可以借助Hadoop 编写程序，将所编写的程序运行于计算机机群上，从而实现对海量数据的处理。

    此外，Hadoop 还提供一个分布式文件系统(HDFS）及分布式数据库（HBase）用来将数据存储或部署到各个计算节点上。所以，你可以大致认为：Hadoop=HDFS（文件系统，数据存储技术相关）+HBase（数据库）+MapReduce（数据处理）。Hadoop 框架如图2 所示：



    借助Hadoop 框架及云计算核心技术MapReduce 来实现数据的计算和存储，并且将HDFS 分布式文件系统和HBase 分布式数据库很好的融入到云计算框架中，从而实现云计算的分布式、并行计算和存储，并且得以实现很好的处理大规模数据的能力。

Hadoop的组成部分

    我们已经知道，Hadoop是Google的MapReduce一个Java实现。MapReduce是一种简化的分布式编程模式，让程序自动分布到一个由普通机器组成的超大集群上并发执行。Hadoop主要由HDFS、MapReduce和HBase等组成。具体的hadoop的组成如下图：



    由上图，我们可以看到：

    1、             Hadoop HDFS是Google GFS存储系统的开源实现，主要应用场景是作为并行计算环境（MapReduce）的基础组件，同时也是BigTable（如HBase、HyperTable）的底层分布式文件系统。HDFS采用master/slave架构。一个HDFS集群是有由一个Namenode和一定数目的Datanode组成。Namenode是一个中心服务器，负责管理文件系统的namespace和客户端对文件的访问。Datanode在集群中一般是一个节点一个，负责管理节点上它们附带的存储。在内部，一个文件其实分成一个或多个block，这些block存储在Datanode集合里。如下图所示（HDFS体系结构图）：



    2、             Hadoop MapReduce是一个使用简易的软件框架，基于它写出来的应用程序能够运行在由上千个商用机器组成的大型集群上，并以一种可靠容错的方式并行处理上TB级别的数据集。

    一个MapReduce作业（job）通常会把输入的数据集切分为若干独立的数据块，由 Map任务（task）以完全并行的方式处理它们。框架会对Map的输出先进行排序，然后把结果输入给Reduce任务。通常作业的输入和输出都会被存储在文件系统中。整个框架负责任务的调度和监控，以及重新执行已经失败的任务。如下图所示（Hadoop MapReduce处理流程图）：



    3、             Hive是基于Hadoop的一个数据仓库工具，处理能力强而且成本低廉。

主要特点：

存储方式是将结构化的数据文件映射为一张数据库表。提供类SQL语言，实现完整的SQL查询功能。可以将SQL语句转换为MapReduce任务运行，十分适合数据仓库的统计分析。

不足之处：

采用行存储的方式（SequenceFile）来存储和读取数据。效率低：当要读取数据表某一列数据时需要先取出所有数据然后再提取出某一列的数据，效率很低。同时，它还占用较多的磁盘空间。

由于以上的不足，有人（查礼博士）介绍了一种将分布式数据处理系统中以记录为单位的存储结构变为以列为单位的存储结构，进而减少磁盘访问数量，提高查询处理性能。这样，由于相同属性值具有相同数据类型和相近的数据特性，以属性值为单位进行压缩存储的压缩比更高，能节省更多的存储空间。如下图所示（行列存储的比较图）：



4、             HBase

    HBase是一个分布式的、面向列的开源数据库，它不同于一般的关系数据库,是一个适合于非结构化数据存储的数据库。另一个不同的是HBase基于列的而不是基于行的模式。HBase使用和 BigTable非常相同的数据模型。用户存储数据行在一个表里。一个数据行拥有一个可选择的键和任意数量的列，一个或多个列组成一个ColumnFamily，一个Fmaily下的列位于一个HFile中，易于缓存数据。表是疏松的存储的，因此用户可以给行定义各种不同的列。在HBase中数据按主键排序，同时表按主键划分为多个HRegion，如下图所示（HBase数据表结构图）：



    Ok，行文至此，看似洋洋洒洒近千里，但若给读者造成阅读上的负担，则不是我本意。接下来的内容，我不会再引用诸多繁杂的专业术语，以给读者心里上造成不良影响。

    我再给出一副图，算是对上文所说的hadoop框架及其组成部分做个总结，如下图所示，便是hadoop的内部结构，我们可以看到，海量的数据交给hadoop处理后，在hadoop的内部中，正如上文所述：hadoop提供一个分布式文件系统（HDFS）及分布式数据库（Hbase）用来存储或部署到各个计算点上，最终在内部采取mapreduce的模式对其数据进行处理，然后输出处理结果：



第二部分、淘宝海量数据产品技术架构解读—学习海量数据处理经验

    在上面的本文的第一部分中，我们已经对mapreduce模式及hadoop框架有了一个深入而全面的了解。不过，如果一个东西，或者一个概念不放到实际应用中去，那么你对这个理念永远只是停留在理论之内，无法向实践迈进。

    Ok，接下来，本文的第二部分，咱们以淘宝的数据魔方技术架构为依托，通过介绍淘宝的海量数据产品技术架构，来进一步学习和了解海量数据处理的经验。

淘宝海量数据产品技术架构

    如下图2-1所示，即是淘宝的海量数据产品技术架构，咱们下面要针对这个架构来一一剖析与解读。

    相信，看过本博客内其它文章的细心读者，定会发现，图2-1最初见于本博客内的此篇文章：从几幅架构图中偷得半点海量数据处理经验之上，同时，此图2-1最初发表于《程序员》8月刊，作者：朋春。

    在此之前，有一点必须说明的是：本文下面的内容大都是参考自朋春先生的这篇文章：淘宝数据魔方技术架构解析所写，我个人所作的工作是对这篇文章的一种解读与关键技术和内容的抽取，以为读者更好的理解淘宝的海量数据产品技术架构。与此同时，还能展示我自己读此篇的思路与感悟，顺带学习，何乐而不为呢?。

    Ok，不过，与本博客内之前的那篇文章（几幅架构图中偷得半点海量数据处理经验）不同，本文接下来，要详细阐述这个架构。我也做了不少准备工作（如把这图2-1打印了下来，经常琢磨）：



                                              图2-1 淘宝海量数据产品技术架构

    好的，如上图所示，我们可以看到，淘宝的海量数据产品技术架构，分为以下五个层次，从上至下来看，它们分别是：数据源，计算层，存储层，查询层和产品层。我们来一一了解这五层：

4 数据来源层。存放着淘宝各店的交易数据。在数据源层产生的数据，通过DataX，DbSync和Timetunel准实时的传输到下面第2点所述的“云梯”。

5 计算层。在这个计算层内，淘宝采用的是hadoop集群，这个集群，我们暂且称之为云梯，是计算层的主要组成部分。在云梯上，系统每天会对数据产品进行不同的mapreduce计算。

6 存储层。在这一层，淘宝采用了两个东西，一个使MyFox，一个是Prom。MyFox是基于MySQL的分布式关系型数据库的集群，Prom是基于hadoop Hbase技术 的（读者可别忘了，在上文第一部分中，咱们介绍到了这个hadoop的组成部分之一，Hbase—在hadoop之内的一个分布式的开源数据库）的一个NoSQL的存储集群。

7 查询层。在这一层中，有一个叫做glider的东西，这个glider是以HTTP协议对外提供restful方式的接口。数据产品通过一个唯一的URL来获取到它想要的数据。同时，数据查询即是通过MyFox来查询的。下文将具体介绍MyFox的数据查询过程。

8  产品层。简单理解，不作过多介绍。

    接下来，咱们重点来了解第三层-存储层中的MyFox与Prom，然后会稍带分析下glide的技术架构，最后，再了解下缓存。文章即宣告结束。

    我们知道，关系型数据库在我们现在的工业生产中有着广泛的引用，它包括Oracle，MySQL、DB2、Sybase和SQL Server等等。

MyFOX

    淘宝选择了MySQL的MyISAM引擎作为底层的数据存储引擎。且为了应对海量数据，他们设计了分布式MySQL集群的查询代理层-MyFOX。

如下图所示，是MySQL的数据查询过程：



                                                            图2-2 MyFOX的数据查询过程

    在MyFOX的每一个节点中，存放着热节点和冷节点两种节点数据。顾名思义，热节点存放着最新的，被访问频率较高的数据；冷节点，存放着相对而来比较旧的，访问频率比较低的数据。而为了存储这两种节点数据，出于硬件条件和存储成本的考虑，你当然会考虑选择两种不同的硬盘，来存储这两种访问频率不同的节点数据。如下图所示：



                                                           图2-3 MyFOX节点结构

     “热节点”，选择每分钟15000转的SAS硬盘，按照一个节点两台机器来计算，单位数据的存储成本约为4.5W/TB。相对应地，“冷数据”我们选择了每分钟7500转的SATA硬盘，单碟上能够存放更多的数据，存储成本约为1.6W/TB。

Prom

出于文章篇幅的考虑，本文接下来不再过多阐述这个Prom了。如下面两幅图所示，他们分别表示的是Prom的存储结构以及Prom查询过程：



                                              图2-4 Prom的存储结构



                                                          图2-5 Prom查询过程

glide的技术架构

   

                                               图2-6 glider的技术架构

    在这一层-查询层中，淘宝主要是基于用中间层隔离前后端的理念而考虑。Glider这个中间层负责各个异构表之间的数据JOIN和UNION等计算，并且负责隔离前端产品和后端存储，提供统一的数据查询服务。

缓存

    除了起到隔离前后端以及异构“表”之间的数据整合的作用之外，glider的另外一个不容忽视的作用便是缓存管理。我们有一点须了解，在特定的时间段内，我们认为数据产品中的数据是只读的，这是利用缓存来提高性能的理论基础。

在上文图2-6中我们看到，glider中存在两层缓存，分别是基于各个异构“表”（datasource）的二级缓存和整合之后基于独立请求的一级缓存。除此之外，各个异构“表”内部可能还存在自己的缓存机制。



                                                           图2-7 缓存控制体系

    图2-7向我们展示了数据魔方在缓存控制方面的设计思路。用户的请求中一定是带了缓存控制的“命令”的，这包括URL中的query string，和HTTP头中的“If-None-Match”信息。并且，这个缓存控制“命令”一定会经过层层传递，最终传递到底层存储的异构“表”模块。

    缓存系统往往有两个问题需要面对和考虑：缓存穿透与失效时的雪崩效应。

缓存穿透是指查询一个一定不存在的数据，由于缓存是不命中时被动写的，并且出于容错考虑，如果从存储层查不到数据则不写入缓存，这将导致这个不存在的数据每次请求都要到存储层去查询，失去了缓存的意义。至于如何有效地解决缓存穿透问题，最常见的则是采用布隆过滤器（这个东西，在我的此篇文章中有介绍：），将所有可能存在的数据哈希到一个足够大的bitmap中，一个一定不存在的数据会被这个bitmap拦截掉，从而避免了对底层存储系统的查询压力。

    而在数据魔方里，淘宝采用了一个更为简单粗暴的方法，如果一个查询返回的数据为空（不管是数据不存在，还是系统故障），我们仍然把这个空结果进行缓存，但它的过期时间会很短，最长不超过五分钟。

      2、缓存失效时的雪崩效应尽管对底层系统的冲击非常可怕。但遗憾的是，这个问题目前并没有很完美的解决方案。大多数系统设计者考虑用加锁或者队列的方式保证缓存的单线程（进程）写，从而避免失效时大量的并发请求落到底层存储系统上。

    在数据魔方中，淘宝设计的缓存过期机制理论上能够将各个客户端的数据失效时间均匀地分布在时间轴上，一定程度上能够避免缓存同时失效带来的雪崩效应。

本文参考：

基于云计算的海量数据存储模型，侯建等。

基于hadoop的海量日志数据处理，王小森

基于hadoop的大规模数据处理系统，王丽兵。

淘宝数据魔方技术架构解析，朋春。

Hadoop作业调优参数整理及原理，guili。

十七道十七道海量数据处理面试题与Bit-map详解

海量数据处理面试题与Bit-map详解

作者：小桥流水，redfox66，July。



前言

    本博客内曾经整理过有关海量数据处理的10道面试题（十道海量数据处理面试题与十个方法大总结），此次除了重复了之前的10道面试题之后，重新多整理了7道。仅作各位参考，不作它用。

    同时，程序员编程艺术系列将重新开始创作，第十一章以后的部分题目来源将取自下文中的17道海量数据处理的面试题。因为，我们觉得，下文的每一道面试题都值得重新思考，重新深究与学习。再者，编程艺术系列的前十章也是这么来的。若您有任何问题或建议，欢迎不吝指正。谢谢。

第一部分、十五道海量数据处理面试题

1. 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？

    方案1：可以估计每个文件安的大小为50G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

1 遍历文件a，对每个url求取，然后根据所取得的值将url分别存储到1000个小文件（记为）中。这样每个小文件的大约为300M。

2 遍历文件b，采取和a相同的方式将url分别存储到1000小文件中（记为）。这样处理后，所有可能相同的url都在对应的小文件（）中，不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。

3 求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。

    方案2：如果允许有一定的错误率，可以使用Bloom filter，4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit，然后挨个读取另外一个文件的url，检查是否与Bloom filter，如果是，那么该url应该是共同的url（注意会有一定的错误率）。

    读者反馈@crowgns：

4 hash后要判断每个文件大小，如果hash分的不均衡有文件较大，还应继续hash分文件，换个hash算法第二次再分较大的文件，一直分到没有较大的文件为止。这样文件标号可以用A1-2表示（第一次hash编号为1，文件较大所以参加第二次hash，编号为2）

5 由于1存在，第一次hash如果有大文件，不能用直接set的方法。建议对每个文件都先用字符串自然顺序排序，然后具有相同hash编号的（如都是1-3，而不能a编号是1，b编号是1-1和1-2），可以直接从头到尾比较一遍。对于层级不一致的，如a1，b有1-1，1-2-1，1-2-2，层级浅的要和层级深的每个文件都比较一次，才能确认每个相同的uri。

2. 有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。

方案1：

6 顺序读取10个文件，按照hash(query)%10的结果将query写入到另外10个文件（记为）中。这样新生成的文件每个的大小大约也1G（假设hash函数是随机的）。

7 找一台内存在2G左右的机器，依次对用hash_map(query, query_count)来统计每个query出现的次数。利用快速/堆/归并排序按照出现次数进行排序。将排序好的query和对应的query_cout输出到文件中。这样得到了10个排好序的文件（记为）。

8 对这10个文件进行归并排序（内排序与外排序相结合）。

方案2：

    一般query的总量是有限的，只是重复的次数比较多而已，可能对于所有的query，一次性就可以加入到内存了。这样，我们就可以采用trie树/hash_map等直接来统计每个query出现的次数，然后按出现次数做快速/堆/归并排序就可以了

    （读者反馈@店小二：原文第二个例子中：“找一台内存在2G左右的机器，依次对用hash_map(query, query_count)来统计每个query出现的次数。”由于query会重复，作为key的话，应该使用hash_multimap 。hash_map 不允许key重复。@hywangw:店小二所述的肯定是错的，hash_map(query,query_count)是用来统计每个query的出现次数 又不是存储他们的值 出现一次 把count+1 就行了 用multimap干什么？多谢hywangw）。

方案3：

    与方案1类似，但在做完hash，分成多个文件后，可以交给多个文件来处理，采用分布式的架构来处理（比如MapReduce），最后再进行合并。

3. 有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。

    方案1：顺序读文件中，对于每个词x，取，然后按照该值存到5000个小文件（记为）中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M。对每个小文件，统计每个文件中出现的词以及相应的频率（可以采用trie树/hash_map等），并取出出现频率最大的100个词（可以用含100个结点的最小堆），并把100词及相应的频率存入文件，这样又得到了5000个文件。下一步就是把这5000个文件进行归并（类似与归并排序）的过程了。

4. 海量日志数据，提取出某日访问百度次数最多的那个IP。

    方案1：首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中。注意到IP是32位的，最多有2^32个IP。同样可以采用映射的方法，比如模1000，把整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最大的IP中，找出那个频率最大的IP，即为所求。

5. 在2.5亿个整数中找出不重复的整数，内存不足以容纳这2.5亿个整数。

    方案1：采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存2^32*2bit=1GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。

    方案2：也可采用上题类似的方法，进行划分小文件的方法。然后在小文件中找出不重复的整数，并排序。然后再进行归并，注意去除重复的元素。

6. 海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。

方案1：

9 在每台电脑上求出TOP10，可以采用包含10个元素的堆完成（TOP10小，用最大堆，TOP10大，用最小堆）。比如求TOP10大，我们首先取前10个元素调整成最小堆，如果发现，然后扫描后面的数据，并与堆顶元素比较，如果比堆顶元素大，那么用该元素替换堆顶，然后再调整为最小堆。最后堆中的元素就是TOP10大。

10 求出每台电脑上的TOP10后，然后把这100台电脑上的TOP10组合起来，共1000个数据，再利用上面类似的方法求出TOP10就可以了。

（更多可以参考：第三章、寻找最小的k个数，以及第三章续、Top K算法问题的实现）

    读者反馈@QinLeopard：

第6题的方法中，是不是不能保证每个电脑上的前十条，肯定包含最后频率最高的前十条呢？
比如说第一个文件中：A(4), B(5), C(6), D(3)
第二个文件中：A(4),B(5),C(3),D(6)
第三个文件中: A(6), B(5), C(4), D(3)
如果要选Top(1), 选出来的结果是A，但结果应该是B。

    @July：我想，这位读者可能没有明确提议。本题目中的TOP10是指最大的10个数，而不是指出现频率最多的10个数。但如果说，现在有另外一提，要你求频率最多的 10个，相当于求访问次数最多的10个IP地址那道题，即是本文中上面的第4题。特此说明。

7. 怎么在海量数据中找出重复次数最多的一个？

    方案1：先做hash，然后求模映射为小文件，求出每个小文件中重复次数最多的一个，并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求（具体参考前面的题）。

8. 上千万或上亿数据（有重复），统计其中出现次数最多的钱N个数据。

    方案1：上千万或上亿的数据，现在的机器的内存应该能存下。所以考虑采用hash_map/搜索二叉树/红黑树等来进行统计次数。然后就是取出前N个出现次数最多的数据了，可以用第6题提到的堆机制完成。

9. 1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串。请怎么设计和实现？

    方案1：这题用trie树比较合适，hash_map也应该能行。

10. 一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。

    方案1：这题是考虑时间效率。用trie树统计每个词出现的次数，时间复杂度是O(n*le)（le表示单词的平准长度）。然后是找出出现最频繁的前10个词，可以用堆来实现，前面的题中已经讲到了，时间复杂度是O(n*lg10)。所以总的时间复杂度，是O(n*le)与O(n*lg10)中较大的哪一个。

11. 一个文本文件，找出前10个经常出现的词，但这次文件比较长，说是上亿行或十亿行，总之无法一次读入内存，问最优解。

    方案1：首先根据用hash并求模，将文件分解为多个小文件，对于单个文件利用上题的方法求出每个文件件中10个最常出现的词。然后再进行归并处理，找出最终的10个最常出现的词。

12. 100w个数中找出最大的100个数。

·     方案1：采用局部淘汰法。选取前100个元素，并排序，记为序列L。然后一次扫描剩余的元素x，与排好序的100个元素中最小的元素比，如果比这个最小的要大，那么把这个最小的元素删除，并把x利用插入排序的思想，插入到序列L中。依次循环，知道扫描了所有的元素。复杂度为O(100w*100)。

·     方案2：采用快速排序的思想，每次分割之后只考虑比轴大的一部分，知道比轴大的一部分在比100多的时候，采用传统排序算法排序，取前100个。复杂度为O(100w*100)。

·     方案3：在前面的题中，我们已经提到了，用一个含100个元素的最小堆完成。复杂度为O(100w*lg100)。

13. 寻找热门查询：

搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复读比较高，虽然总数是1千万，但是如果去除重复和，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。

(1) 请描述你解决这个问题的思路；

(2) 请给出主要的处理流程，算法，以及算法的复杂度。

    方案1：采用trie树，关键字域存该查询串出现的次数，没有出现为0。最后用10个元素的最小推来对出现频率进行排序。

    关于此问题的详细解答，请参考此文的第3.1节：第三章续、Top K算法问题的实现。

14. 一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数中的中数？

    方案1：先大体估计一下这些数的范围，比如这里假设这些数都是32位无符号整数（共有2^32个）。我们把0到2^32-1的整数划分为N个范围段，每个段包含（2^32）/N个整数。比如，第一个段位0到2^32/N-1，第二段为（2^32）/N到（2^32）/N-1，…，第N个段为（2^32）（N-1）/N到2^32-1。然后，扫描每个机器上的N个数，把属于第一个区段的数放到第一个机器上，属于第二个区段的数放到第二个机器上，…，属于第N个区段的数放到第N个机器上。注意这个过程每个机器上存储的数应该是O(N)的。下面我们依次统计每个机器上数的个数，一次累加，直到找到第k个机器，在该机器上累加的数大于或等于（N^2）/2，而在第k-1个机器上的累加数小于（N^2）/2，并把这个数记为x。那么我们要找的中位数在第k个机器中，排在第（N^2）/2-x位。然后我们对第k个机器的数排序，并找出第（N^2）/2-x个数，即为所求的中位数的复杂度是O（N^2）的。

    方案2：先对每台机器上的数进行排序。排好序后，我们采用归并排序的思想，将这N个机器上的数归并起来得到最终的排序。找到第（N^2）/2个便是所求。复杂度是O（N^2*lgN^2）的。

15. 最大间隙问题

给定n个实数，求着n个实数在实轴上向量2个数之间的最大差值，要求线性的时间算法。

方案1：最先想到的方法就是先对这n个数据进行排序，然后一遍扫描即可确定相邻的最大间隙。但该方法不能满足线性时间的要求。故采取如下方法：

11 找到n个数据中最大和最小数据max和min。

12 用n-2个点等分区间[min, max]，即将[min, max]等分为n-1个区间（前闭后开区间），将这些区间看作桶，编号为，且桶i 的上界和桶i+1的下届相同，即每个桶的大小相同。每个桶的大小为：。实际上，这些桶的边界构成了一个等差数列（首项为min，公差为），且认为将min放入第一个桶，将max放入第n-1个桶。

13 将n个数放入n-1个桶中：将每个元素x[i] 分配到某个桶（编号为index），其中，并求出分到每个桶的最大最小数据。

14 最大间隙：除最大最小数据max和min以外的n-2个数据放入n-1个桶中，由抽屉原理可知至少有一个桶是空的，又因为每个桶的大小相同，所以最大间隙不会在同一桶中出现，一定是某个桶的上界和气候某个桶的下界之间隙，且该量筒之间的桶（即便好在该连个便好之间的桶）一定是空桶。也就是说，最大间隙在桶i的上界和桶j的下界之间产生j>=i+1。一遍扫描即可完成。

16. 将多个集合合并成没有交集的集合

    给定一个字符串的集合，格式如：。要求将其中交集不为空的集合合并，要求合并完成的集合之间无交集，例如上例应输出。

(1) 请描述你解决这个问题的思路；

(2) 给出主要的处理流程，算法，以及算法的复杂度；

(3) 请描述可能的改进。

    方案1：采用并查集。首先所有的字符串都在单独的并查集中。然后依扫描每个集合，顺序合并将两个相邻元素合并。例如，对于，首先查看aaa和bbb是否在同一个并查集中，如果不在，那么把它们所在的并查集合并，然后再看bbb和ccc是否在同一个并查集中，如果不在，那么也把它们所在的并查集合并。接下来再扫描其他的集合，当所有的集合都扫描完了，并查集代表的集合便是所求。复杂度应该是O(NlgN)的。改进的话，首先可以记录每个节点的根结点，改进查询。合并的时候，可以把大的和小的进行合，这样也减少复杂度。

17. 最大子序列与最大子矩阵问题

数组的最大子序列问题：给定一个数组，其中元素有正，也有负，找出其中一个连续子序列，使和最大。

    方案1：这个问题可以动态规划的思想解决。设b[i]表示以第i个元素a[i]结尾的最大子序列，那么显然。基于这一点可以很快用代码实现。

最大子矩阵问题：给定一个矩阵（二维数组），其中数据有大有小，请找一个子矩阵，使得子矩阵的和最大，并输出这个和。

    方案2：可以采用与最大子序列类似的思想来解决。如果我们确定了选择第i列和第j列之间的元素，那么在这个范围内，其实就是一个最大子序列问题。如何确定第i列和第j列可以词用暴搜的方法进行。



第二部分、海量数据处理之Bti-map详解

    Bloom Filter已在上一篇文章海量数据处理之Bloom Filter详解中予以详细阐述，本文接下来着重阐述Bit-map。有任何问题，欢迎不吝指正。

什么是Bit-map

    所谓的Bit-map就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。

    如果说了这么多还没明白什么是Bit-map，那么我们来看一个具体的例子，假设我们要对0-7内的5个元素(4,7,2,5,3)排序（这里假设这些元素没有重复）。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数，我们就只需要8个Bit（1Bytes），首先我们开辟1Byte的空间，将这些空间的所有Bit位都置为0(如下图：)



    然后遍历这5个元素，首先第一个元素是4，那么就把4对应的位置为1（可以这样操作 p+(i/8)|(0×01<<(i%8)) 当然了这里的操作涉及到Big-ending和Little-ending的情况，这里默认为Big-ending）,因为是从零开始的，所以要把第五位置为一（如下图）：

     

然后再处理第二个元素7，将第八位置为1,，接着再处理第三个元素，一直到最后处理完所有的元素，将相应的位置为1，这时候的内存的Bit位的状态如下：



然后我们现在遍历一遍Bit区域，将该位是一的位的编号输出（2，3，4，5，7），这样就达到了排序的目的。下面的代码给出了一个BitMap的用法：排序。

15 //定义每个Byte中有8个Bit位  

16 #include ＜memory.h＞  

17 #define BYTESIZE 8  

18 void SetBit(char *p, int posi) 

19 { 

20     for(int i=0; i ＜ (posi/BYTESIZE); i++) 

21     { 

22         p++; 

23     } 

24  

25     *p = *p|(0x01＜＜(posi%BYTESIZE));//将该Bit位赋值1  

26     return; 

27 } 

28  

29 void BitMapSortDemo() 

30 { 

31     //为了简单起见，我们不考虑负数  

32     int num[] = {3,5,2,10,6,12,8,14,9}; 

33  

34     //BufferLen这个值是根据待排序的数据中最大值确定的  

35     //待排序中的最大值是14，因此只需要2个Bytes(16个Bit)  

36     //就可以了。  

37     const int BufferLen = 2; 

38     char *pBuffer = new char[BufferLen]; 

39  

40     //要将所有的Bit位置为0，否则结果不可预知。  

41     memset(pBuffer,0,BufferLen); 

42     for(int i=0;i＜9;i++) 

43     { 

44         //首先将相应Bit位上置为1  

45         SetBit(pBuffer,num[i]); 

46     } 

47  

48     //输出排序结果  

49     for(int i=0;i＜BufferLen;i++)//每次处理一个字节(Byte)  

50     { 

51         for(int j=0;j＜BYTESIZE;j++)//处理该字节中的每个Bit位  

52         { 

53             //判断该位上是否是1，进行输出，这里的判断比较笨。  

54             //首先得到该第j位的掩码（0x01＜＜j），将内存区中的  

55             //位和此掩码作与操作。最后判断掩码是否和处理后的  

56             //结果相同  

57             if((*pBuffer&(0x01＜＜j)) == (0x01＜＜j)) 

58             { 

59                 printf("%d ",i*BYTESIZE + j); 

60             } 

61         } 

62         pBuffer++; 

63     } 

64 } 

65  

66 int _tmain(int argc, _TCHAR* argv[]) 

67 { 

68     BitMapSortDemo(); 

69     return 0; 

70 } 

可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下

基本原理及要点

使用bit数组来表示某些元素是否存在，比如8位电话号码

扩展

Bloom filter可以看做是对bit-map的扩展（关于Bloom filter，请参见：海量数据处理之Bloom filter详解）。

问题实例

1)已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。

    8位最多99 999 999，大概需要99m个bit，大概10几m字节的内存即可。 （可以理解为从0-99 999 999的数字，每个数字对应一个Bit位，所以只需要99M个Bit==1.2MBytes，这样，就用了小小的1.2M左右的内存表示了所有的8位数的电话）

2)2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。

    将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出现2次及以上，在遍历这些数的时候，如果对应位置的值是0，则将其置为1；如果是1，将其置为2；如果是2，则保持不变。或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bit-map，都是一样的道理。

参考：

71 http://www.cnblogs.com/youwang/archive/2010/07/20/1781431.html。

72 http://blog.redfox66.com/post/2010/09/26/mass-data-4-bitmap.aspx。