精华内容
下载资源
问答
  • 教你如何迅速秒杀掉:99%的海量数据处理面试题

    万次阅读 多人点赞 2012-03-22 12:51:07
    教你如何迅速秒杀掉:99%的海量数据处理面试题作者:July出处:结构之法算法之道blog前言 一般而言,标题含有“秒杀”,“99%”,“史上最全/最强”等词汇的往往都脱不了哗众取宠之嫌,但进一步来讲,如果读者读罢...

          教你如何迅速秒杀掉:99%的海量数据处理面试题

    本文经过大量细致的优化后,收录于我的新书《编程之法:面试和算法心得》第六章中,新书目前已上架京东/当当


    作者:July
    出处:结构之法算法之道blog



    前言

       一般而言,标题含有“秒杀”,“99%”,“史上最全/最强”等词汇的往往都脱不了哗众取宠之嫌,但进一步来讲,如果读者读罢此文,却无任何收获,那么,我也甘愿背负这样的罪名 :-),同时,此文可以看做是对这篇文章:十道海量数据处理面试题与十个方法大总结的一般抽象性总结。

        毕竟受文章和理论之限,本文将摒弃绝大部分的细节,只谈方法/模式论,且注重用最通俗最直白的语言阐述相关问题。最后,有一点必须强调的是,全文行文是基于面试题的分析基础之上的,具体实践过程中,还是得具体情况具体分析,且各个场景下需要考虑的细节也远比本文所描述的任何一种解决方法复杂得多。

        OK,若有任何问题,欢迎随时不吝赐教。谢谢。



    何谓海量数据处理?

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

        那解决办法呢?针对时间,我们可以采用巧妙的算法搭配合适的数据结构,如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内此篇文章
    • 关于红黑树,请参看blog内系列文章
    • 关于hash_map的具体应用:请看这里,关于hash_set:请看此文

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



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

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

    1、海量日志数据,提取出某日访问百度次数最多的那个IP。
        既然是海量数据处理,那么可想而知,给我们的数据那就一定是海量的。针对这个数据的海量,我们如何着手呢?对的,无非就是分而治之/hash映射 + hash统计 + 堆/快速/归并排序,说白了,就是先映射,而后统计,最后排序:
    1. 分而治之/hash映射:针对数据太大,内存受限,只能是:把大文件化成(取模映射)小文件,即16字方针:大而化小,各个击破,缩小规模,逐个解决
    2. hash_map统计:当大文件转化了小文件,那么我们便可以采用常规的hash_map(ip,value)来进行频率统计。
    3. 堆/快速排序:统计完了之后,便进行排序(可采取堆排序),得到次数最多的IP。

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

        关于本题,还有几个问题,如下:

          1、Hash取模是一种等价映射,不会存在同一个元素分散到不同小文件中的情况,即这里采用的是mod1000算法,那么相同的IP在hash取模后,只可能落在同一个文件中,不可能被分散的。因为如果两个IP相等,那么经过Hash(IP)之后的哈希值是相同的,将此哈希值取模(如模1000),必定仍然相等。
          2、那到底什么是hash映射呢?简单来说,就是为了便于计算机在有限的内存中处理big数据,从而通过一种映射散列的方式让数据均匀分布在对应的内存位置(如大数据通过取余的方式映射成小树存放在内存中,或大文件映射成多个小文件),而这个映射散列方式便是我们通常所说的hash函数,设计的好的hash函数能让数据均匀分布而减少冲突。尽管数据映射到了另外一些不同的位置,但数据还是原来的数据,只是代替和表示这些原始数据的形式发生了变化而已。

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

    2、寻找热门查询,300万个查询字符串中统计最热门的10个查询

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

        解答:由上面第1题,我们知道,数据大则划为小的,如如一亿个Ip求Top 10,可先%1000将ip分到1000个小文件中去,并保证一种ip只出现在一个文件中,再对每个小文件中的ip进行hashmap计数统计并按数量排序,最后归并或者最小堆依次处理每个小文件的top10以得到最后的结。

        但如果数据规模比较小,能一次性装入内存呢?比如这第2题,虽然有一千万个Query,但是由于重复度比较高,因此事实上只有300万的Query,每个Query255Byte,因此我们可以考虑把他们都放进内存中去(300万个字符串假设没有重复,都是最大长度,那么最多占用内存3M*1K/4=0.75G。所以可以将所有字符串都存放在内存中进行处理),而现在只是需要一个合适的数据结构,在这里,HashTable绝对是我们优先的选择。

        所以我们放弃分而治之/hash映射的步骤,直接上hash统计,然后排序。So,针对此类典型的TOP K问题,采取的对策往往是:hashmap + 堆。如下所示:

    1. hash_map统计:先对这批海量数据预处理。具体方法是:维护一个Key为Query字串,Value为该Query出现次数的HashTable,即hash_map(Query,Value),每次读取一个Query,如果该字串不在Table中,那么加入该字串,并且将Value值设为1;如果该字串在Table中,那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内用Hash表完成了统计;
    2. 堆排序:第二步、借助堆这个数据结构,找出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,则更新堆(x入堆,用时logk),否则不更新堆。这样下来,总费时O(k*logk+(n-k)*logk)=O(n*logk)。此方法得益于在堆中,查找等各项操作时间复杂度均为logk。”--第三章续、Top K算法问题的实现
        当然,你也可以采用trie树,关键字域存该查询串出现的次数,没有出现为0。最后用10个元素的最小推来对出现频率进行排序。

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

    1. 分而治之/hash映射:顺序读文件中,对于每个词x,取hash(x)%5000,然后按照该值存到5000个小文件(记为x0,x1,...x4999)中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小,还可以按照类似的方法继续往下分,直到分解得到的小文件的大小都不超过1M。
    2. hash_map统计:对每个小文件,采用trie树/hash_map等统计每个文件中出现的词以及相应的频率。
    3. 堆/归并排序:取出出现频率最大的100个词(可以用含100个结点的最小堆)后,再把100个词及相应的频率存入文件,这样又得到了5000个文件。最后就是把这5000个文件进行归并(类似于归并排序)的过程了。
    4、海量数据分布在100台电脑中,想个办法高效统计出这批数据的TOP10。
        如果每个数据元素只出现一次,而且只出现在某一台机器中,那么可以采取以下步骤统计出现次数TOP10的数据元素:
    1. 堆排序:在每台电脑上求出TOP10,可以采用包含10个元素的堆完成(TOP10小,用最大堆,TOP10大,用最小堆,比如求TOP10大,我们首先取前10个元素调整成最小堆,如果发现,然后扫描后面的数据,并与堆顶元素比较,如果比堆顶元素大,那么用该元素替换堆顶,然后再调整为最小堆。最后堆中的元素就是TOP10大)。
    2. 求出每台电脑上的TOP10后,然后把这100台电脑上的TOP10组合起来,共1000个数据,再利用上面类似的方法求出TOP10就可以了。
        但如果同一个元素重复出现在不同的电脑中呢,如下例子所述:


        这个时候,你可以有两种方法:
    • 遍历一遍所有数据,重新hash取摸,如此使得同一个元素只出现在单独的一台电脑中,然后采用上面所说的方法,统计每台电脑中各个元素的出现次数找出TOP10,继而组合100台电脑上的TOP10,找出最终的TOP10。
    • 或者,暴力求解:直接统计统计每台电脑中各个元素的出现次数,然后把同一个元素在不同机器中的出现次数相加,最终从所有数据中找出TOP10。
    5、有10个文件,每个文件1G,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。要求你按照query的频度排序。

       方案1:直接上:

    1. hash映射:顺序读取10个文件,按照hash(query)%10的结果将query写入到另外10个文件(记为a0,a1,..a9)中。这样新生成的文件每个的大小大约也1G(假设hash函数是随机的)。
    2. hash_map统计:找一台内存在2G左右的机器,依次对用hash_map(query, query_count)来统计每个query出现的次数。注:hash_map(query,query_count)是用来统计每个query的出现次数,不是存储他们的值,出现一次,则count+1。
    3. 堆/快速/归并排序:利用快速/堆/归并排序按照出现次数进行排序,将排序好的query和对应的query_cout输出到文件中,这样得到了10个排好序的文件(记为)。最后,对这10个文件进行归并排序(内排序与外排序相结合)。根据此方案1,这里有一份实现:https://github.com/ooooola/sortquery/blob/master/querysort.py
         除此之外,此题还有以下两个方法:
        方案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。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

    1. 分而治之/hash映射遍历文件a,对每个url求取,然后根据所取得的值将url分别存储到1000个小文件(记为这里漏写个了a1)中。这样每个小文件的大约为300M遍历文件b,采取和a相同的方式将url分别存储到1000小文件中(记为)。这样处理后,所有可能相同的url都在对应的小文件()中,不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可
    2. hash_set统计:求每对小文件中相同的url时,可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url,看其是否在刚才构建的hash_set中,如果是,那么就是共同的url,存到文件里面就可以了。

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

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

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

    8、上千万或上亿数据(有重复),统计其中出现次数最多的前N个数据。

        方案:上千万或上亿的数据,现在的机器的内存应该能存下。所以考虑采用hash_map/搜索二叉树/红黑树等来进行统计次数。然后利用堆取出前N个出现次数最多的数据。

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

        方案1:如果文件比较大,无法一次性读入内存,可以采用hash取模的方法,将大文件分解为多个小文件,对于单个小文件利用hash_map统计出每个小文件中10个最常出现的词,然后再进行归并处理,找出最终的10个最常出现的词。
        方案2:通过hash取模将大文件分解为多个小文件后,除了可以用hash_map统计出每个小文件中10个最常出现的词,也可以用trie树统计每个词出现的次数,时间复杂度是O(n*le)(le表示单词的平准长度),最终同样找出出现最频繁的前10个词(可用堆来实现),时间复杂度是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 树。更多请待后续实验论证。

    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)。

        接下来,咱们来看第二种方法,双层捅划分。


    密匙二、多层划分

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

    问题实例:

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

    14、5亿个int找它们的中位数。

    1. 思路一:这个例子比上面那个更明显。首先我们将int划分为2^16个区域,然后读取数据统计落到各个区域里的数的个数,之后我们根据统计结果就可以判断中位数落到那个区域,同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。
      实际上,如果不是int是int64,我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域,然后确定区域的第几大数,在将该区域分成2^20个子区域,然后确定是子区域的第几大数,然后子区域里的数的个数只有2^20,就可以直接利用direct addr table进行统计了。
    2.   思路二@绿色夹克衫:同样需要做两遍统计,如果数据存在硬盘上,就需要读取2次。
      方法同基数排序有些像,开一个大小为65536的Int数组,第一遍读取,统计Int32的高16位的情况,也就是0-65535,都算作0,65536 - 131071都算作1。就相当于用该数除以65536。Int32 除以 65536的结果不会超过65536种情况,因此开一个长度为65536的数组计数就可以。每读取一个数,数组中对应的计数+1,考虑有负数的情况,需要将结果加32768后,记录在相应的数组内。
      第一遍统计之后,遍历数组,逐个累加统计,看中位数处于哪个区间,比如处于区间k,那么0- k-1的区间里数字的数量sum应该<n/2(2.5亿)。而k+1 - 65535的计数和也<n/2,第二遍统计同上面的方法类似,但这次只统计处于区间k的情况,也就是说(x / 65536) + 32768 = k。统计只统计低16位的情况。并且利用刚才统计的sum,比如sum = 2.49亿,那么现在就是要在低16位里面找100万个数(2.5亿-2.49亿)。这次计数之后,再统计一下,看中位数所处的区间,最后将高位和低位组合一下就是结果了。

    密匙三:Bloom filter/Bitmap

    Bloom filter

    关于什么是Bloom filter,请参看blog内此文:

      适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集
      基本原理及要点:
      对于原理来说很简单,位数组+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中的最小值来近似表示元素的出现频率。

       可以看下上文中的第6题:

    “6、给你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的应用,可以看下上文中的第13题,以及另外一道新题:

    “13、在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树

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

    1. 上面的第2题:寻找热门查询:查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个,每个不超过255字节。
    2. 上面的第5题:有10个文件,每个文件1G,每个文件的每一行都存放的是用户的query,每个文件的query都可能重复。要你按照query的频度排序。
    3. 1000万字符串,其中有些是相同的(重复),需要把重复的全部去掉,保留没有重复的字符串。请问怎么设计和实现?
    4. 上面的第8题:一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词。其解决方法是:用trie树统计每个词出现的次数,时间复杂度是O(n*le)(le表示单词的平准长度),然后是找出出现最频繁的前10个词。

        更多有关Trie树的介绍,请参见此文:从Trie树(字典树)谈到后缀树

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

    倒排索引(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"将对应集合的交集。

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

        关于倒排索引的应用,更多请参见:


    密匙五、外排序

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

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


    密匙六、分布式处理之Mapreduce

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

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

    1. The canonical example application of MapReduce is a process to count the appearances of each different word in a set of documents:
    2. 海量数据分布在100台电脑中,想个办法高效统计出这批数据的TOP10。
    3. 一共有N个机器,每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中数(median)?

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

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

        至此,六种处理海量数据问题的模式/方法已经阐述完毕。据观察,这方面的面试题无外乎以上一种或其变形,然题目为何取为是:秒杀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个数?请读者思考。更多海里数据处理面试题,请参见此文第一部分:http://blog.csdn.net/v_july_v/article/details/6685962



    参考文献

    1. 十道海量数据处理面试题与十个方法大总结
    2. 海量数据处理面试题集锦与Bit-map详解
    3. 十一、从头到尾彻底解析Hash表算法
    4. 海量数据处理之Bloom Filter详解
    5. 从Trie树(字典树)谈到后缀树
    6. 第三章续、Top K算法问题的实现
    7. 第十章、如何给10^7个数据量的磁盘文件排序
    8. 从B树、B+树、B*树谈到R 树
    9. 第二十三、四章:杨氏矩阵查找,倒排索引关键词Hash不重复编码实践
    10. 第二十六章:基于给定的文档生成倒排索引的编码与实践
    11. Hadhoop框架与MapReduce模式中谈海量数据处理
    12. 第十六~第二十章:全排列,跳台阶,奇偶排序,第一个只出现一次等问题
    13. http://blog.csdn.net/v_JULY_v/article/category/774945
    14. STL源码剖析第五章,侯捷著;
    15. 2012百度实习生招聘笔试题:http://blog.csdn.net/hackbuteer1/article/details/7542774
    16. Redis/MongoDB绝佳站点:http://blog.nosqlfan.com/
    17. 国外一面试题网站:http://www.careercup.com/


    后记

        经过上面这么多海量数据处理面试题的轰炸,我们依然可以看出这类问题是有一定的解决方案/模式的,所以,不必将其神化。然这类面试题所包含的问题还是比较简单的,若您在这方面有更多实践经验,欢迎在本文评论下与大家不吝分享
        不过,相信你也早就意识到,若单纯论海量数据处理面试题,本blog内的有关海量数据处理面试题的文章已涵盖了你能在网上所找到的70~80%。但有点,必须负责任的敬告大家:无论是这些海量数据处理面试题也好,还是算法也好,面试时70~80%的人不是倒在这两方面,而是倒在基础之上(诸如语言,数据库,操作系统,网络协议等等),所以,无论任何时候,基础最重要,没了基础,便什么都不是
        最后,推荐几个求职/算法/刷题的相关课程,包括LeetCode直播刷题等等,感兴趣的可以看下:https://www.julyedu.com/category/index/1
        OK,本文若有任何问题,欢迎随时不吝留言,评论,赐教,谢谢。完。

    重大消息:我的新书《编程之法:面试和算法心得》终于在2015年10月14日起上架开卖了!京东抢购地址http://item.jd.com/11786791.html。京东、当当、亚马逊等各大网店均已有现货销售。

    展开全文
  • 数据的存储及应用体系是企业生态运转的中枢神经,数据湖已经成为海量数据存储与分析的重要承载方式。 在汹涌而至的信息化浪潮下,大数据技术不断更新迭代,数据管理工具得到飞速发展,相关概念也随之而生。数据湖...

    简介: 在云计算和大数据时代,基于数据开展生产、运营、决策成为常态,根据Gartner报道,2019年数据基建方面的采购费用飙升到660亿美元,占据基础架构类软件费用的24%。数据的存储及应用体系是企业生态运转的中枢神经,数据湖已经成为海量数据存储与分析的重要承载方式。

    在汹涌而至的信息化浪潮下,大数据技术不断更新迭代,数据管理工具得到飞速发展,相关概念也随之而生。数据湖(Data Lake)概念自2011年被推出后,其概念定位、架构设计和相关技术都得到了飞速发展和众多实践,数据湖也从单一数据存储池概念演进为支撑高效、安全、稳定企业级数据应用的下一代基础数据平台。

     

    wp1.png

     

    此次发布的《数据湖应用实践白皮书》涵盖了数据湖的定义与架构、数据湖核心组件与方案介绍、数据湖构建方案、应用实践等内容,希望为用户提供新的洞察。

     

    wp2.png

     

    通过阅读本书,包括开发者、IT运维人员、企业数字化管理者等可以全面了解阿里云基于云原生技术的企业级数据湖解决方案和相关产品,也能明晰传统数据仓库和数据湖的差异。 

     

    wp3.png

     

    在云计算和大数据时代,基于数据开展生产、运营、决策成为常态,根据Gartner报道,2019年数据基建方面的采购费用飙升到660亿美元,占据基础架构类软件费用的24%。数据的存储及应用体系是企业生态运转的中枢神经,数据湖已经成为海量数据存储与分析的重要承载方式。

     

    wp4.png

     

    市场调研机构Research and Markets发布的报告显示,2020年,全球数据湖市场的价值为37.4亿美元,预计到2026年将达到176亿美元,在2021年至2026年的预测期间的复合年增长率为29.9%。

     

    wp5.png

     

    云原生时代的到来,引领数据湖进入了“云湖共生”新的阶段。在此背景下,阿里云推出基于云原生技术的企业级数据湖解决方案,该方案采用了存储计算分离架构,存储层基于阿里云对象存储OSS构建,并与阿里云数据湖分析(Data Lake Analytics 简称 DLA)、数据湖构建(Data Lake Formation简称 DLF)、E-MapReduce(简称EMR)、DataWorks(简称DW)等计算引擎无缝对接,且兼容丰富的开源计算引擎生态。

     

    wp6.png

     

    十年踪迹十年心,结合先进的数据科学与机器学习技术,数据湖还能为企业提供预测分析,帮助企业构建、优化训练模型等。希望这本白皮书可以为企业和组织的数字化转型实践提供指引,为相关领域的业务决策者与实践者提供面向行业应用场景的重要参考。

    原文链接

    本文为阿里云原创内容,未经允许不得转载。

    展开全文
  • 海量数据处理技巧

    万次阅读 2018-08-02 20:07:18
    当高性能硬件的普及还跟不上这样的数据大潮时,如何在有限的时空资源内处理海量数据成为了计算机科学以及数理统计等领域最大的挑战。 所谓“数据处理”,在本文中特指通过计算机技术,对海量数据进行存储、统计、...

    数据时代来临,数据量的爆炸式增长是最为显著的特征。当高性能硬件的普及还跟不上这样的数据大潮时,如何在有限的时空资源内处理海量数据成为了计算机科学以及数理统计等领域最大的挑战。

    所谓“数据处理”,在本文中特指通过计算机技术,对海量数据进行存储、统计、查询等操作。我将在下面介绍一些基本的海量数据处理的方法,供大家参考。需要明确的一点是,现实情况复杂多变,所以对于海量数据处理这样大的主题,是不可能用一篇博客就说清楚的。但方法论可以一通百通,我们通过一些已经被无数次实验证明有效的方法,就能大致理解对此类问题的解决思路,之后在面临新的问题时,至少能找到一个大致的方向。

    1. 海量数据处理的困难

    海量数据处理的困难用一句话概括,就是时空资源不够。具体来说,

    • 时间受限:无法在有限时间内,完成针对海量数据的某项处理工作;
    • 空间受限:无法将海量数据一次性读入内存

    对于时间受限的问题,我们一般的解决办法是高效的算法配合恰当的数据结构,比如哈希表,Bloom Filter,堆,倒排索引,tire树);而对于空间受限的问题,一般的解决办法是“大而化小,分而治之”的策略,既然一次性行不通,那就一部分一部分读,每读入一部分可以生成一个小文件,小文件是可以直接读入内存的,我们这样分割大数据之后,再依次处理小文件的数据。

    注意,本文我只介绍对于海量数据执行一些简单的数据处理(比如存储,查重,排序,统计数量等)时的一些通用的方法,至于更复杂的计算,涉及具体算法性能层面的东西,由于世界上算法以千万记,面对不同情况,又有着无数变形,所以不可能总结出来。

    2. 海量数据处理方法归纳

    July的博客 教你如何迅速秒杀掉:99%的海量数据处理面试题 对海量数据处理的方法进行了细致的总结,这篇文章写的非常全面,建议大家一读。但我读完之后,窃以为许多问题和解决思路有所重复,没必要全部都详细探究。为了理清思路、抓重点,我将那篇文章中涉及的问题以及相应方法更加简化地总结为如下7点。

    2.1 哈希映射 + 统计 + 排序

    解决问题:海量数据不能一次性读入内存,而我们需要对海量数据进行的计数、排序等操作
    使用工具:hash函数(hash表);堆

    这种方法是典型的“分而治之”的策略,也是解决空间限制最常用的方法。基本思路可以用下图表示。先借助哈希算法,计算每一条数据的hash值,按照hash值将海量数据分布存储到多个桶中(所谓桶,一般可以用小文件实现)。根据hash函数的唯一性,相同的数据一定在同一个桶中。如此,我们再依次处理这些小文件,最后做合并运算即可(有点类似于Map-Reduce的思想)。


    注:一般用hash函数将数据映射到桶的方法是:

    (35)bucketID=H(mi)  %  n

    其中mi为第i条数据,bucket_ID为桶标号,n为要设置的桶数量。关于桶数量(即小文件数量)设置的基本的原则是:每个小文件的大小比内存限制要小。比如处理1G的大文件,内存限制为1M,那就可以把大文件分成2000个小文件(甚至更多),这样每个小文件的大小约500K(甚至更小),我们就可以轻松读入内存处理了。下面看一些具体的例子:

    问题1 top-k筛选:海量数据存储于多个文件,任何一条数据都可能存在于任何一个文件当中,现需要筛选出现的次数最多的k条数据。
    解决思路

    • 依次遍历这些文件,通过hash映射,将每个文件的每条数据映射到新构造的多个小文件中(设生成了n个小文件);
    • 依次统计每个小文件中出现次数最多的k条数据,构成hash表,hash表中每个键值对的形式为 dataItem: count
    • 利用堆排序,依次遍历这些hash表,在nk条数据中,找出count值最大的k个;

    这里之所以使用堆排序,也是为了能尽可能地提高排序效率。就上例而言,堆排序的时间复杂度为nklog(k)

    问题2 对比查重:现有A和B两个大文件,每个文件都存储着海量数据,要求给出A,B中重复的数据。
    解决思路

    • 遍历A中的所有数据,通过hash映射将他们分布存储在n个小文件中,记为{a1,a2,,an}
    • 遍历B中的所有数据,通过hash映射将他们分布存储在n个小文件中,记为{b1,b2,,bn}
    • 根据hash函数性质可知,A和B中的相同数据一定被映射到序号相同的小文件,所以我们依次比较{ai,bi}即可;
    • 如果问题更进一步,要求返回重复次数最多的k条数据,则可以将对比小文件找到的数据存入hash表,键为数据,值为该数据出现的次数。再用大小为k的堆,排序找出即可。

    2.2 Trie树处理海量字符串数据

    解决问题:当需要处理的是海量字符串数据时,有时Trie树会比直接上面说的hash映射的策略更高效。
    使用工具:Trie树;堆

    Trie树是一种非常强大的处理海量字符串数据的工具。尤其是大量的字符串数据中存在前缀时,Trie树特别好用。Trie树在字典的存储,字符串的查找,求取海量字符串的公共前缀,以及字符串统计等方面发挥着重要的作用。用于存储时,Trie树因为不重复存储公共前缀,节省了大量的存储空间;用于以字符串的查找时,Trie树依靠其特殊的性质,实现了在任意数据量的字符串集合中都能以O(len)的时间复杂度完成查找(len为要检索的字符串长度);在字符串统计中,Trie树能够快速记录每个字符串出现的次数。下面看几个问题实例。

    注:有关Trie树的详细讲解可以参考我之前的博客 Trie树的构建和应用

    问题3 数据去重:一个超大文件(不能直接读入内存),里面包含海量字符串数据,但字符串数据种类有限(可见含有大量重复),现需要对字符串去重。并统计去重后每个字符串出现的次数
    解决思路

    • 将大文件分割成多个小文件,依次遍历每个小文件,读取其中存储的每一个字符串,构建Trie树,并在每一个终止节点记录该节点代表的字符串(即从根节点到该节点的字符组成的字符串)当前出现的次数,解决问题的时间复杂度为O(Nlen),其中N为字符串总数,len为字符串的平均长度;

    • 如果问题更进一步,需要排序,那就再建一个堆,读取Trie树,将字符串依次插入堆,时间复杂度为O(NlenlogN),其中N是去重后字符串的数量;

    至于Trie树在存储,求取公共前缀等方面的应用可以参考我上面给出的博客,这里不再赘述。

    总结一下,Trie树对于海量字符串数据,在数据种类有限(构建的Trie树可以完全读入内存)时,能够使我们轻松的进行存储,查找,计数等工作。

    2.3 Bloom Filter

    解决问题:数据字典的构建;判定目标数据是否存在于一个海量数据集;集合求交
    使用工具:Bloom Filter;hash函数

    以存在性判定为例,Bloom Filter通过对目标数据的映射,能够以O(k)的时间复杂度判定目标数据的存在性,其中k为使用的hash函数个数。这样就能大大缩减遍历查找所需的时间。

    注:有关Bloom Filter树的详细讲解可以参考我之前的博客 Bloom Filter原理与实现,下面我假设你已经知道了Bloom Filter的工作原理。直接看问题4:

    问题4 集合求交:与上面的问题2类似,只不过现在不是A和B两个大文件,而是A, B, C, D….多个大文件。
    解决思路

    • 依次遍历每个大文件中的每条数据,遍历每条数据时,都将它插入Bloom Filter;
    • 如果已经存在,则在另外的集合(记为S)中记录下来;
    • 如果不存在,则插入Bloom Filter;
    • 最后,得到的S即为所有这些大文件中元素的交

    问题5 unsigned int型整数存在性判定:判定一个unsigned int型整数是否在一个大的unsigned int型整数数据集中。
    解决思路

    • 假设unsigned int型整数数据集长度为N,则申请一个大小为512M的数组作为Bloom Filter;
    • 遍历数据集,按照遍历到的整数(记为a)将Bloom Filter的第a位变成1;
    • 检查Bloom Filter中,目标数据所代表的位是0还是1;

    问题5用的其实是一种简化了的Bloom Filter,不再采取hash映射的方式,而是直接根据整数的大小确定要改变的位数,这在某些特殊情况下(比如数据种类不多时)非常有效。

    2.4 多层桶结构

    解决问题:海量数据求取第k大数
    使用工具:hash函数

    多层桶结构其实和最开始我们用hash映射分割大文件的思路是一致的,都是一种“分而治之”的策略。只不过多层桶结构是对有些桶分割之后再分割,构成了一种层次化的结构,它主要应用于一次分割的结果依然不能解决内存限制的情况。比如下面的问题6:

    问题6 求取海量整数的中位数。
    解决思路

    • 依次遍历整数,按照其大小将他们分拣到n个桶中。但是现在出现了一种不好的情况,就是可能有的桶数据量很小,有的则数据量很大,大到内存放不下了;
    • 对于那些太大的桶,我们就再分割成更小的桶,当然分割的准则还是依据数据大小,这样,其实是构成了一种类似于不平衡的多叉树的结构;
    • 根据多叉树第一层的数量统计结果,我们可以知道中位数在哪个节点中,如果该节点还有孩子,就判断在其哪个孩子节点中,直到找到叶子节点,最后找出目标。

    2.5 倒排索引

    这个不详细说了,在文档数据的检索,尤其是关键字查询领域有着极为广泛的应用。其实这个思路也可以推广开来,当存在海量的文件,且每个文件包含的数据种类有限,而我们的任务又是依据数据查文件时,倒排索引都可以排上用场。

    2.6 外排序

    解决问题:海量数据的排序
    实用工具:归并算法

    外排序是经典的排序方法之一,主要是针对大数据不能直接读入内存的情况,通过内存与外存之间的数据交换,实现海量数据排序的。我大致介绍一下外排序的算法思路,详细的解释可以参照博客:排序之外部排序

    问题7 海量数据排序。
    解决思路

    • 依次读取数据,将数据按照大小范围,生成一定数量的“归并段”并写入外存,注意归并段中的数据是排好序的;
    • 对归并段执行归并排序,每两个归并段排序之后的结果作为新的归并段写入外存;
    • 重复执行上一步,知道完全排序完毕,最终的排序结果会存在外存中;

    2.7 MapReduce

    MapReduce是一种计算模型,分为”Map”和”Reduce”两个阶段。

    • Map:将大量数据分割后(或者将困难任务分解后)“各个击破”;
    • Reduce:将“各个击破”的结果按照一定的规律进行合并操作;

    这样做的好处是可以在任务被分解后,可以通过大量机器进行并行计算,从而突破时间或者空间的限制。时间上显然更快,空间上,单个机器只需要处理空间允许的数据量即可。举个简单的例子就是归并排序,我们先将数据集分割成小数据集,使用多个机器排序每个分割后的小数据集(Map),再将处理好的归并段依次归并(Reduce)。

    本文求尽量全面总结海量数据处理的思路,不求对每种思路的深入探讨。因为这些方法要么在我之前的博客中已有详细说明,要么比较通用,网上的介绍很充分。

    不得不说海量数据处理时,面临的问题是千变万化的,所以本文也会持续更新,希望读者们也能不断补充我遗漏的知识。

    展开全文
  • 海量数据的存储 海量数据的计算 大数据处理的主要应用场景 前言:大数据技术诞生之初,就是为了解决海量数据的存储和计算问题。 大数据起源于Google。 Google是当时世界上(尽管目前也是)最大的搜索引擎公司...

    目录

    海量数据的存储

    海量数据的计算

    大数据处理的主要应用场景

    前言:大数据技术诞生之初,就是为了解决海量数据的存储和计算问题。

    大数据起源于Google。

    Google是当时世界上(尽管目前也是)最大的搜索引擎公司,由于互联网时代的到来,Google积累了海量的用户,海量用户意味着海量的数据,谷歌需要将这些数据保存下来,传统的保存数据的方式已经满足不了Google的需求了。

    首先我们需要了解,海量数据的存储面临着三个困难:

    ①:数据能够存储的容量足够大;

    ②:数据的读写速度要足够的快;

    ③:数据要要有可靠性的保证,也即数据备份。

    海量数据的存储

    首先看一个问题:

    当一个仓库无法装载更多的货物的时候,我们如何解决更多的货物的存储问题?

    没错,我们可以扩建仓库,如果我们想存储更多的数据,我们可以不断的升级计算机,通过升级内存,磁盘,CPU等将一台计算机变得更强大,比如商业服务器不够用,升级为小型机,中型机,大型机,甚至超级计算机。以扩建“仓库”的方式来升级存储能力的方式也称作是:“垂直伸缩”,拜摩尔定律所赐,计算机发展的早期,每过一年半,工程师们总能将计算机的性能提升一倍

    倘若升级了计算机之后,依然无法存储待存储的数据,可以使用另外一种垂直伸缩的技术:独立磁盘冗余队列,也即RAID技术,如果本科专业是计算机相关专业,应该都会在教材里面看到该技术,RAID技术有很多种类型,比如RAID1,是在数据写入磁盘的时候,将一份数据同时写入到两块磁盘,任何一块新的磁盘损坏,数据依然是安全的。剩余的其他的RAIDx 读者可以根据兴趣自行了解。

    一言以蔽之:RAIDx 技术能够实现海量数据的存储面临的三个困难。

    但是进入了互联网时代,垂直伸缩的路子有些难走了,一方面是升级计算机带来的成本问题,另一方面由于有些巨头公司(例如Google,Alibaba)即便是世界上最牛X的超级计算机,也无法满足其需求。

    Google作为这个世界技术最牛的公司解决这一问题,责无旁贷。工程师们想:如果扩建仓库遇到了瓶颈,那么就新建更多的仓库,也即一台计算机存储不了如此庞大的数据,那么就用N台,就形成分布式集群,再将RAID运用到分布式服务集群上(其实就是HDFS的思想),如此就解决了海量数据的存储问题。

    这种通过不断添加计算机来提高数据存储能力的方式也称作是“水平伸缩“,垂直伸缩总会遇到天花板,但是水平伸缩理论上却没有尽头!

    海量数据的计算

    当一匹马拉不动车的时候?也即:由数据存储引发的数据计算的问题:

    大数据的鼻祖Google,它存储着几乎全世界所有可访问的网页,数以万亿的规模,消耗的磁盘可达万块,为了将这些文件存储起来,Google开发了GFS(Google 文件系统)将数千台服务器上万块磁盘统一管理起来,然后作为一个文件系统,存储所有这些网页文件。

    Google将这些网页文件存储起来之后,需要构建索引,然后对文件中的单词进行词频统计,然后根据PageRank算法计算网页的排名,也即Google需要对这数万计磁盘上的文件进行计算处理,这并不是一般场景的计算问题。

    我们先来看看一般的计算,也即传统的软件处理模型:

    输入 --> 计算 -->   输出 模型,一个程序给它传入一些数据,或者是程序从文件中读取数据,然后对这些数据进行处理,最后得到输出结果。一个程序能够调度的网络带宽,常常以MB(通常百MB),内存容量以GB(通常几十个GB)来计量,但是在互联网大数据时代,例如一个稍微大一些的互联网企业,需要计算处理的数据常常以PB计算,可以发现,传统的计算处理模型并不能满足大数据场景下的计算要求。也就是说,这么大的数据量,计算机根本算不动!

    一匹马拉不动车的时候,我们想过更换更好的马,商业级的服务器不够用,就升级为小型机,小型机不够用,就升级中型机,实在不行就升级大型机,超级计算机。和前面的海量数据存储遇到一样的问题,光靠升级硬件,是不能够满足像Google这样每天需要处理几十亿用户请求的计算需求的。

    那么应该如何解决呢?

    应该多添加几匹马。

    前面我们提到海量的数据存储于分布式文件系统中,也即存储在分布式服务器集群中,和海量数据的分布式存储的思路一致,海量数据的计算,使用数千台甚至上万台计算机构建大数据处理集群(MapReduce分布式计算框架),利用更多的网络带宽,内存资源 ,CPU核心数去执行计算。

    由于数据量巨大,而按照MapReduce编程框架编写的MR程序较之于数据量却非常的小,所以大数据场景下的计算原则是:移动计算大于移动数据。道理非常简单,因为移动程序更划算。

    大数据处理的主要应用场景

    大数据的主要应用场景是:数据分析,数据挖掘与机器学习。其中数据分析主要使用Hive,Spark-SQL等SQL处理引擎完成,而数据挖掘和机器学习则由专门的框架如TensorFlow等内置了主要的数据挖掘和机器学习的算法。

    在以前,我们在进行数据分析时候,只能针对数据库中的数据进行分析和统计,受到数据量和计算能力的限制也只能对重要的数据(例如财务相关的数据)进行统计,但是大数据技术出现之后,能够存储的数据更多,计算能力也有更大的提升,因此我们可以对记录更多的数据,然后对其计算和分析。

    正是因为对海量数据的存储和计算问题得以解决,才使得很多公司能够更加详解的采集用户的行为数据,形成了数据仓库,因为老板知道,自己的服务器(数据仓库)存的下,也能应付海量数据的计算,这一切都得益于大数据计算。

    由于数据仓库和分布式计算框架的存在,使得数据挖掘也进入了大数据时代。以前,受到存储能力和计算能力的限制,“数据挖掘机”,只能挖掘 ”小小的数据山“,而现在,可以使用更大的数据挖掘机(更好的计算能力),去挖掘更大的数据山(真正海量的数据),如此一来就能够挖掘到更多的数据的价值。比如挖掘到两个商品之间的关系,就可以进行关联分析,最终让用户尽可能的看到想要购买的商品;还可以挖掘到人和人之间的关系,将各自购买过的商品出现在对方的推荐列表中;还能够将每一个人身上不同的特性挖掘出来,形成用户画像,对同一类人推荐可能购买的商品。

    我们知道机器学习实际就是使用数据训练出来一个模型,然后将带输入值输入到该模型中,然后得到该值的输出值。

    在没有大数据的时候,我们受到数据采集,存储,计算能力的限制,只能通过抽样的方式获取小部分数据,无法得到完整的,全局的,细节的规律,有了大数据技术之后,我们能够把全部的历史数据收集起来,统计其规律,进而预测正在发生的事情。这就是大数据时代的机器学习。

    展开全文
  • 尹成老师带你步入python数据分析海量数据营销的殿堂,讲课生动风趣、深入浅出,全套视频内容充实,整个教程以python语言为核心,完整精彩的演练了python数据分析海量数据营销操作流程以及各种精彩的小项目等,非常...
  • Sphinx 实现海量数据的快速查询

    万次阅读 2017-05-22 10:37:32
    说到 Sphinx,就会想到:站内搜索,mysql优化,分词 等等有关搜索海量数据的需求,本文介绍了 sphinx的基本概念、安装、和一个联系动态语言实现大数据海量查询的实例。1. Sphinx的基本概念Sphinx 是一个 全文检索...
  • 海量数据面试题

    万次阅读 2018-04-24 09:01:49
    海量数据面试题1、给个超过100G的logfile, log中存着IP地址, 设计算法找到出现次数最多的IP地址? 第一题:首先我们的思路就是利用哈希进行文件的切分,我们把100G大小的logfile分为1000份,那么下来差不多没一个...
  • 海量数据处理面试题集锦

    万次阅读 多人点赞 2011-08-14 14:07:13
    十七道海量数据处理面试题与Bit-map详解作者:小桥流水,redfox66,July。前言 本博客内曾经整理过有关海量数据处理的10道面试题(十道海量数据处理面试题与十个方法大总结),此次除了重复了之前的10道面试题之后...
  • 海量数据处理

    千次阅读 2016-08-07 22:39:00
    本文转自结构之法算法之道blog1、何谓海量数据处理?所谓海量数据处理,其实很简单,海量,海量,何谓海量,就是数据量太大,所以导致要么是无法在较短时间内迅速解决,要么是数据太大,导致无法一次性装入内存。那...
  • Mysql海量数据处理

    千次阅读 2019-03-02 11:18:49
    一说海量数据有人就说了直接用大数据,那只能说不太了解这块,为此我们才要好好的去讲解一下海量的处理 海量数据的处理分为两种情况 1)表中有海量数据,但是每天不是很快的增长 2)表中有还流量数据,而且每天很...
  • 搭建高可用的、高可靠的Flume数据采集通道,运用阿里云DateHub构建中间缓冲队列并担任数据分发枢纽将数据推送至阿里自主研发的DataWorks对数据进行分层处理,采用MaxCompute作为处理海量数据的方案,将计算结果保存...
  • 海量数据处理方案

    千次阅读 2018-03-17 22:21:28
    什么是海量数据? 正如《逍遥游》中的一句话:北冥有鱼,其名为鲲,鲲之大,一锅炖不下,化而为鸟,其名为鹏,鹏之大,需要两个烧烤架;简单的可以把这里的海量数据理解为这里的鲲鹏 ,数据大到一个服务器存不下,...
  • 什么是海量数据

    千次阅读 2018-04-18 15:37:30
    1.什么是海量数据? 海量数据,顾名思义,数据量一般大得多. 海量数据一般是相对当前计算机处理能力而言 的,今天看来是海量数据,也许随着计算机硬件能力的提升在不久的将来就不算海量数据了.即使是同一时期,...
  • 海量数据处理算法

    千次阅读 2017-08-14 20:00:04
    海量信息即大规模数据,随着互联网技术的发展,...在海量数据中提取信息,不同于常规量级数据中提取信息,在海量信息中提取有用数据,会存在以下几个方面的问题: (1)数据量过大,数据中什么情况都可能
  • 海量数据存储

    千次阅读 2012-09-22 20:16:36
    如何处理海量数据 在实际的工作环境下,许多人会遇到海量数据这个复杂而艰巨的问题,它的主要难点有以下几个方面: 一、数据量过大,数据中什么情况都可能存在。 如果说有10条数据,那么大不了每条...
  • Mysql实现海量海量数据存储查询时,主要有几个关键点,分表,分库,集群,M-S,负载均衡。 其中分库分表是很重要的一点。分库是如何将海量的MySQL数据放到不同的服务器中,分表则是在分库基础上对数据现进行逻辑...
  • 海量数据面试题分析

    千次阅读 2018-07-27 08:34:44
    箴言:无论是这些海量数据处理面试题也好,还是算法也好,面试时,70~80%的人不是倒在这两方面,而是倒在基础之上(诸如语言,数据库,操作系统,网络协议等等),所以,无论任何时候,基础最重要,没了基础,便什么都...
  • 十道海量数据处理面试题与十个方法大总结

    万次阅读 多人点赞 2011-03-26 10:16:00
    海量数据处理:十道面试题与十个海量数据处理方法总结作者:July、youwang、yanxionglu。时间:二零一一年三月二十六日本文之总结:教你如何迅速秒杀掉:99%的海量数据处理面试题。有任何问题,欢迎随时交流、指正。...
  • 海量数据问题总结

    千次阅读 2018-05-11 00:22:42
    本博客已弃用,当时存在一些小细节错误后期也不再修改了 欢迎来我的新博客 前言:在这个用户量爆炸、并发极高的互联网时代,对于如今...海量数据处理能力是一家大公司必须要做得非常硬的一个技术块,这样才能在互...
  • 海量数据处理面试题

    千次阅读 2017-08-16 23:12:44
    何谓海量数据处理? 所谓海量数据处理,无非就是基于海量数据上的存储、处理、操作。何谓海量,就是数据量太大,所以导致要么是无法在较短时间内迅速解决,要么是数据太大,导致无法一次性装入内存。 那解决办法呢...
  • 海量数据找到最大的100个数据

    千次阅读 2019-03-07 16:43:11
    海量数据指的是数据量非常大,亿级的数据。如果是 int 型数据,int型数组占4个字节的内存,1亿个int型数据就得占用近400M的内存,计算机性能差的话很难一次性读入然后排序。所以一般的靠排序来做这道题是很尴尬的。 ...
  • 海量数据的处理与挖掘

    千次阅读 2020-11-04 15:17:14
    海量数据处理与挖掘 1 Hadoop海量数据实现原理 1.1 单点结构 单点结构:也就是一台计算机,对于大数据,高并发来讲,我们所用的计算机的性能是远远不够的。而且单台及计算机对于我们数据来讲也是十分不安全的,当...
  • Java海量数据处理算法

    千次阅读 2019-09-03 23:20:59
    在处理海量数据的过程中,使用hash法一般可以快速存取,统计某些数据,将大量数据进行分类,例如提取某日访问网站次数最多的IP地址等. 常用散列函数的构建方法如下: 直接寻址法 取关键字或关键字的某个线性函...
  • 随着互联网的兴起,越来越多的内容被放到互联网中,从而导致海量数据处理受到更多人的重视,尤其是在百度、腾讯等这些涉及海量数据的公司。下面我们简单谈一下关于海量数据处理的一些常用数据结构。包括哈希、bitmap...
  • 海量数据处理问题

    千次阅读 2017-09-28 17:24:07
    “99%”,“史上最全/最强”等词汇的往往都脱不了哗众取宠之嫌,但进一步来讲,如果读者读罢此文,却无任何收获,那么,我也甘愿背负这样的罪名 :-),同时,此文可以看做是对这篇文章:十道海量数据处理面试题与十个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 54,061
精华内容 21,624
关键字:

海量数据