海量数据处理

发表于 更新于 分类于
当前各大互联网公司研究都将重点放在了海量数据处理上，但是，只寄希望于硬件扩容是很难满足海量数据处理的，如何利用现有条件进行海量信息处理，已经日益成为当前程序员笔试面试中一个新的亮点。

海量信息，即大规模数据，随着互联网技术的发展，互联网上的信息越来越多，如何从海量信息中提取有用信息成为当前互联网技术发展必须面对的问题。

针对海量数据的处理，可以使用的方法非常多，常见的方法有Hash法、Bitmap法、Bloom filter法、数据库优化法、倒排索引法、外排序法、Trie数、堆、双层桶法以及MapReduce法。下面就逐个讲解。

Hash法

Hash法一般被称为散列，它是一种映射关系，即给定一个数据元素，其关键字为key，按一个确定的散列函数计算出hash(key)，把hash(key)作为关键字key对应元素的存储地址，再进行数据元素的插入和检索操作。简而言之，散列函数就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

散列表是具有固定大小的数组，散列函数是用于关键字与存储地址之间的一种映射关系，但是不能保证每个元素的关键字与函数值是一一对应的，因为极有可能出现对应于不同的元素，却计算出了相同的函数值，冲突指的就是两个关键字映射到同一个存储地址的情况。

散列函数一般应具有一下几个特点：

  • 运算应该尽可能简单
  • 函数的值域必须在散列表的范围内
  • 尽可能地减少冲突

针对散列函数的这些特点，在构建散列表时，不仅要设定一个好的散列函数，而且还要设定一种处理冲突的方法。常用的散列函数的构建方法一般有以下几种。

散列函数

  1. 直接寻址法：取关键字或关键字的某个线性函数值为散列地址，即h(key)=key 或h(key) = a*key+b，其中a和b均为整型常数，这种散列函数叫做自身函数。例如，有一个人口数字统计表，人的年龄取值范围为1~100,其中年龄作为关键字，散列函数取关键字自身，但这种方法效率低下，时间复杂度为O(1)，空间复杂度为O(n)，n为关键字的个数。

    直接寻址法不会产生冲突，但由于他没有压缩映像，因此当关键字集合很大时，使用这种Hash函数是不可能实现地址编码的散列的。

  2. 取模法：选择一个合适的正整数p，令hash(Key)=Key mod p。p如果选择的是比较大的素数，则效果比较好，一般选取p为TableSize，即散列表的长度。

  3. 数字分析法：设关键字是d位的以r为基的数（例如以10为基的十进制数），且共有n个关键字，则关键字的每个位可能有r个不同的数符出现（即0，1，2…9），但这r个数符在各个位上出现的频率不一样，可能在某些位上分布比较均匀，即每个数符出现的次数接近于n/r，而在另一些位上分布不均匀。因此可选取其中分布比较均匀的那些位，重新组成新的数，用其作散列地址。
    这种方法比较简单、直观，但是需要预先知道每个关键字的情况，这就限制了它的使用范围。

  4. 折叠法：将关键字分成位数为t的几个部分（最后一部分的位数可能小于t），然后把各部分按位对其进行相加，将所得的和舍弃进位，留下t位作为散列地址。当关键字位数很多，而且关键字中每位数字分布比较均匀时，采用折叠法比较合适。

  5. 平方取中法：这是一种较常见的方法，将关键字进行平方运算，然后从结果的中间取出若干位（位数与散列地址的位数相同），将其作为散列地址。

  6. 除留余数法：除留余数法是一种比较常用的散列函数，其主要原理是取关键字除以某个数p（p不大于散列表的长度）的余数作为散列地址，即Hash(key)=key%p，使用该方法时，选取合适的p值也很重要，一般要求p<=TableSize，且接近或等于TableSize，p一般选取质数。

  7. 随机数法：选择一个随机函数，然后用关键字key的随机函数值作为散列地址，即Hash(key)=random(key)，其中random()为随机函数。当关键字的长度不相等时，采用这种方法比较合适。

在构造散列表的过程中，不管使用什么样的散列函数，冲突都是不可能完全避免的，所以解决冲突是构造散列表的一个必不可少的过程。解决冲突的以主要途径就是当一个关键字映射到散列表中的某一个地址，且该地址上已有关键字时，再为该关键字寻找新的存储地址，常用的解决冲突办法有以下几种：

Hash冲突解决办法

  1. 开放地址法：开放地址法的基本思想就是当地址发生冲突时，在散列表中再按照某种方法继续探测其他的存储地址，直到找到空闲的地址为止，该过程可描述为H(key) = (H(key)+d) mod m) (m=1,2...k,k<=m-1)，其中H(key)为关键字key的直接散列地址，m为散列表长度，d为每次再探测时的地址增量。

    采用这种方法时，首先计算出关键字的直接散列地址，即H(key)，若该直接散列地址上已经有其他的关键字了，则继续查看地址为[H(key)+d]的存储地址，判断其是否为空，如此反复，直到找到空闲的存储地址为止，然后将关键字key存放到该地址。

    增量d可以有不同的取法，常用的有以下3种：

    • d = 1，2，3，…，m-1，称为线性探测再散列。
    • d = 12，-12，22，-22，…，-k（k<=m/2），称为二次探测再散列。
    • d = 伪随机序列，称为伪随机再散列。

    注意：对于利用开放地址法处理冲突所产生的散列表中，删除一个元素时不能直接删除，因为这样将会影响其他具有相同地址的元素的查找地址，所以，通常采用设定一个特殊的标志的方法表示该元素已被删除。

  2. 链地址法:链地址法解决冲突的主要思想是：若散列表空间为[0,m-1]，则设置一个由m个指针组成的一维数组CH[m]，然后在寻找关键字散列地址的过程中，所有散列地址为i的数据元素都插入到头指针为CH[i]的链表中。这种方法比较适合于冲突比较严重的情况下使用，例如，设有8个元素{a,b,c,d,e,f,g,h}，采用某种散列函数得到的地址为：{0,2,4,1,0,8,7,2}，当散列表长度为10时，采用链地址法解决冲突的散列表如图所示。

  3. 再散列法：当发生冲突时，使用第二个、第三个散列函数计算地址，直到无冲突为止，但这种方法的缺点就是计算时间会大幅增加。

  4. 建立一个公共溢出区：假设散列函数的值域为[0,m-1]，则设向量HashTable[0…m-1]为基本表，另外设立存储空间向量OverTable[0…v]用于存储发生冲突的记录。

Hash主要是用来进行“快速存取”，在O(1)时间复杂度里就可以查找到目标元素，或者判断其是否存在。Hash数据结构里的数据对外是杂乱无序的，因此其具体存储位置及各个存储元素位置之间的相互关系是无法得知的，但是却可以在常数时间里判断元素位置及存在与否，在处理海量数据的过程中，使用Hash方法一般可以快速存取、统计某些数据、将大量数据进行分类，例如提取某日访问网站次数最多的IP地址等。

Bit-map法

Bit-map法的基本原理是使用位数组来表示某些元素是否存在，例如从8位电话号码中查重复号码，本法适用于海量数据的快速查找、判重、删除等。

具体而言，Bit-map法的结果是生成一个N位长的串，每位上以“1”或“0”表示需要排序的集合中的数，例如集合为{2,7,4,9,1,10}，则生成一个10位的串，将第2,7,4,9,1,10位置置为“1”，其余位置置为“0”，当把串中所有位置都置完后，排序也自动完成了，上例中用Bit-map法排序后的结果为1101001011。

Bit-map法排序的时间复杂度是O(n)，比一般的排序都快，但它是以空间换时间的（需要一个N位的串），而且有一些限制，即数据状态不是很多，例如排序前集合大小最好已知，而且集合中元素的最大重复次数必须已知。

Bit-map法的作用巨大，除了判断数据是否重复以外，也经常使用本法来判断集合中某个数据是否存在。

Bloom Filter法

在日常生活中，很多地方都会遇到类似这样的问题：在设计计算机软件系统时，经常需要判断一个元素是否在一个集合中；在字处理软件中，需要检查一个英语单词是否拼写正确等。

针对这些问题，最直接的解决办法就是将集合中的全部元素都存储在计算机中，每当遇到一个新元素时，将它和集合中的元素直接逐个进行比较即可。这种做法虽然能够准确无误的完成任务，但存在一个问题，就是比较次数太多，效率极其低下，当数据量巨大时，例如在海量数据信息处理中，效率低的问题就凸显出来了，例如邮箱总是需要过滤垃圾邮件，一个办法就是记录下那些发邮件的E-mail地址，可是由于那些发送者还会不断的再注册新的地址，如果使用散列表，每存储一亿个E-mail地址，一般每个E-mail地址需要占用16B，所以一共需要1亿*16B，大约1.6GB的内存，除非是超级计算机，一般服务器是无法存储如此海量信息的。

Bloom Filter正是解决这种问题的有效办法，它是一种空间效率和时间效率都很高的随机数据结构，可用来检测一个元素是否属于一个集合。但它同样带来的问题就是牺牲了正确率。当它判断某元素不属于这个集合时，该元素一定不属于这个集合；当它判断某个元素属于这个集合时，该元素不一定属于这个集合。所以Bloom Filter法适用于对低错误率可以容忍的场合。

Bloom Filter的基本原理是位数组与Hash函数的联合使用。首先Bloom Filter是一个包含了m位的位数组，数组的每一位都初始化为0；其次，定义k个不同的Hash函数，每个函数都可以将集合中的元素映射到位数组的某一位。当向集合中差入一个元素时，根据k个Hash函数可以得到位数组中的k个位，将这些位置置为1。

如果查询某个元素是否属于集合，那么根据k个Hash函数可以得到位数组中的k个位，查看这k个位中的值，如果有的位不为1，那么该元素肯定不在此集合中；如果这k个位的值全部为1，那么该元素可能在此集合中。在插入其它元素时，可能会将这些位置置为1，这样就产生了错误。

下面是一个实例：

所以使用Bloom Filter法的难点是如何根据输入元素个数n，来确定位数组m的大小以及Hash函数。当函数个数k=(ln2)*(m/n)时错误率最小，在错误率不大于E的情况下，m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些，因为还要保证位数组里至少一半为0，所以m应该>=nlg(1/E)*lge，m大概就是nlg(1/E)的1.44倍(lg表示以2为底的对数)。

假设E为0.01，即错误率为1%，则此时m应该大约为n的13倍。这样k大约是8个（m与n的单位不同，m的单位是bit，n的单位是个数）。通常单个元素的长度有很多bit，所以若使用Bloom Filter法，内存上通常都是节省的。

Bloom Filter的优点是具有很好的空间效率和时间效率。它的插入和查询时间都是以常数，另外，它不保存元素本身，具有良好的安全性。然而这些都是以牺牲正确率为代价的。当插入的元素越多，错判“元素属于这个集合的概率”就越大。另外Bloom Filter只能插入元素，不能删除元素，因为多个元素的散列结果可能会共用Bloom Filter结构中的同一个位，如果删除元素，就可能会影响多个元素的检测。

数据库优化法

互联网上的数据一般都被存储在数据库中，很多情况下，人们并非对这些海量数据本身感兴趣，而是需要从这些海量数据中提取出对自己有用的信息，例如从数据中获取访问最多的页面信息等，这就涉及了数据的查询技术等相关内容。常见的数据库优化方法有如下几种：

  • 数据分区：进行海量数据的查询优化，其中一种重要的方式就是如何有效的存储并降低需要处理的数据规模，所以可对海量数据进行分区操作以提高效率，不同的数据库有不同的分区方式，不过处理机制却大致相同。例如将不同的数据存于不同的文件组下，不同的文件组存于不同的磁盘分区下，这样讲数据分散开，减小磁盘I/O，减小系统负荷，还可以将日志、索引等放于不同的分区下。
  • 索引：索引一般可以加速数据的检索速度，加速表与表之间的链接，提高性能，所以在对海量数据进行处理时，考虑到信息量较大，应该对表建立索引，包括在主键上建立聚簇索引，将聚合索引建立在日期列上等。索引的优点很多，但是对于索引的建立，还需要考虑到实际情况，而不是对每一个列建立一个索引。
  • 缓存机制：当数据量增加时，一般的处理工具都要考虑到缓存问题，缓存大小设置的好差也关系到数据处理的成败，例如，在处理2亿条数据聚合操作时，缓存设置为100000条/Buffer可行。
  • 加大虚存：由于系统资源有限，而需要处理的数据量非常大，因此当内存不足时，可以通过增加虚拟内存来解决。
  • 分批处理：由于需要处理的信息量巨大，可以对海量数据进行分批处理，然后再对处理后的数据进行合并操作，分而治之，这样有利于小数据量的处理，不至于面对大数据量带来的问题。
  • 使用临时表或中间表：数据量增加时，处理中要考虑提前汇总。这样做的目的是化整为零，大表变小表，分块处理完成后，再利用一定的规则进行合并，处理过程中临时表的使用和中间结果的保存都非常重要，如果对于超海量的数据，大表处理不了，只能拆分为多个小表。如果处理过程中需要多步汇总操作，可按汇总步骤一步一步来。
  • 优化查询语句：查询语句的性能对查询效率的影响非常大，在对SQL语句的编写过程中，例如减少关联，少用或不用游标，设计好高效的数据库表结构都十分重要。
  • 使用视图
  • 使用存储过程
  • 用排序来取代非顺序存取
  • 使用采样数据进行数据挖掘

倒排序索引法

倒排序索引是目前搜索引擎公司对搜索引擎最常用的存储方式，也是搜索引擎的核心内容，在搜索引擎的实际应用中，有时需要按照关键字的某些值查找记录，索引是按照关键字建立索引，这个索引就被称为倒排序索引。

倒排序索引也常被称为反向索引、置入档案或反向档案，它本质是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射，它是文档检索系统中最常用的数据结构，有两种不同的反向索引形式：

  • 第一种形式是一条记录的水平反向索引包含每个引用单词的文档的列表
  • 第二种形式是一个单词的水平反向索引还又包含每个单词在一个文档中的位置。

第二种形式提供了更多的兼容性，但是需要更多的时间和空间来创建。

例如，对于如下内容，一般情况下可以采用矩阵的方式来存储：

1
2
3
D1 : The GDP increased.
D2 : The text is this.
D3 : My name is.

采用矩阵的方式存储的具体表示见表：
而根据表中的信息，就能得到下面的倒排序索引：

1
2
3
4
5
6
The : {D1,D2};
GDP : {D1};
increased : {D1};
Text : {D2};
is : {D2,D3};
Name : {D3}.

通过比较发现，采用倒排序索引比采用矩阵的方式节省很多的空间。

与正向索引相比，倒排序索引的优点是在处理复杂的多关键字查询时，可在倒排序表中先完成查询的并、交等逻辑运算，得到结果后再对记录进行存取，这样把对记录的查询转换为地址集合的运算，不必对每个记录随机存取，从而提高查询速度。所以倒排序索引一般被应用于文档检索系统，查询哪些文件包含了某关键字。

外排序法

当排序的对象数目特别多时，在内存中不能一次处理，必须把他们以文件的形式存放于外存，排序时再把他们一部分一部分的调入内存进行处理，这种方式就是外排序法。

外排序是相对内排序而言的，它是大文件的排序，待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要内存和外部存储器之间进行多次数据交换，以达到对整个文件进行排序的目的。一般采用归并排序的等方式实现外排序，主要分成两个步骤：第一步，生成若干初始归并段，也能被称为文件预处理，把含有n个记录的文件，按内存大小划分为若干长度为L的子文件，然后分别将子文件调入内存，采用有效的内存排序方法排序后送回外存；第二步，进行多路归并，即对这些初始归并段进行多遍归并，使得有序的归并逐渐扩大，最后在外存上形成整个文件的单一归并段，也就是完成了文件的外排序。

外排序适用于大数据的排序以及去重复，但外排序也存在着很大的缺陷，就是它会消耗大量的I/O，效率不会很高。

Trie树

Trie又称字典树或键树，它是一种用于快速字符串检索到多叉树结构，其原理是利用字符串的公共前缀来减少时空开销，即以空间换时间，从而达到提高程序效率的目的。Trie树的典型应用是用于统计和排序大量的字符串，所以经常被搜索引擎系统用于统计估计文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比散列表高。

Trie树一般具有3个基本特性：

  • 根结点不包含字符，除根节点外每一个结点都只包含一个字符。
  • 从根节点到某一结点，路径上经过字符连接起来，为该结点对应的字符串。
  • 每个结点的所有子结点包含的字符都不同。
    Tried树可以利用字符串的公共前缀来节约存储空间，下图该Trie树保存了6个字符串：how,hi,her,hello,so,see。

Trie树适用于数据量大、重复多，但是数据种类小可以放入内存的情况，例如已知n（n很大）个由小写字母构成的平均长度为10的单词，判断其中是否存在某个字符串是另一个字符串的前缀子串。

堆

堆是一种树形数据结构，每个结点都有一个值，通常所说的堆，一般是指二叉堆。在堆中，以大顶堆为例，堆的根节点的值最大，且根节点的两个子树也是以恶搞大顶堆，基于以上特点，堆适用于海量数据求前N大或前N小数问题，其中N一般比较小。

在海量数据中，堆的作用见下表：

双层桶法

双层桶不是一种数据结构，而是一种算法思想，类似于分治思想。因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。

本文以桶排序进行分析，桶排序的基本思想是把[0,1)划分为n个大小相同的子区间，每一子区间是一个桶，然后将n个记录分配到各个桶中。因为关键字序列是均匀分布在[0,1)上的，所以一般不会有很多个记录落入同一个桶中。桶排序的平均时间复杂度是O(n)，最坏的情况仍有可能是O(n²)，一般只适用于关键字取值比较小的情况，否则所需桶的数目m太多导致浪费存储空间和计算时间。

一般桶排序适用于寻找第k大的数，寻找中位数，寻找不重复或重复的数字等情况，例如：

  • 在一个文件中有10G个整数，乱序排列，要求找出中位数，内存限制为2G。
  • 现在有一个0~30000的随机数生成器，请根据这个随机数生成器，设计一个抽奖范围是0~35000彩票中奖号码列表，其中要包含20000个中奖号码。