如何应对海量数据时代的挑战

Bertha 。 2022-06-10 04:25 375阅读 0赞

# 如何应对海量数据时代的挑战？ #

大数据的浪潮有多迅猛？IDC在2006年估计全世界产生的数据量是0.18ZB（1ZB=100万PB），而今年这个数字已经提升了一个数量级，达到1.8ZB，差不多对应全世界每个人一块100多GB的硬盘。这种增长还在加速，预计2015年将达到近8ZB。目前IT系统的存储能力远远不足，就更不用说深入地挖掘和分析了。  
在本文中，百度首席科学家威廉•张、Teradata首席客户官周俊凌、Yahoo!北京全球软件研发中心架构师韩轶平、SAP中国区企业信息管理咨询资深顾问杜韬等四位业内专家，将分享他们在应对海量数据挑战方面的见解和经验。

<table style="width:200px"> 
 <tbody> 
 <tr> 
 <td><img src="http://articles.csdn.net/uploads/allimg/110804/2_110804185454_1.jpg" alt=""></td> 
 <td><img src="http://articles.csdn.net/uploads/allimg/110804/2_110804185503_1.jpg" alt=""></td> 
 <td><img src="http://articles.csdn.net/uploads/allimg/110804/2_110804185511_1.jpg" alt=""></td> 
 <td><img src="http://articles.csdn.net/uploads/allimg/110804/2_110804185518_1.jpg" alt=""></td> 
 </tr> 
 <tr> 
 <td>Teradata首席客户官周俊凌</td> 
 <td>百度首席科学家威廉•张</td> 
 <td>Yahoo!北京全球软件研发中心架构师韩轶平</td> 
 <td>SAP中国区企业信息管理咨询资深顾问杜韬</td> 
 </tr> 
 </tbody> 
</table>

**您所在企业的数据量现在达到了什么规模？  
威廉•张：**这个问题比较容易回答。百度不是一个产品，不仅有搜索引擎，还包括很多社区产品和媒体产品，所以这个数字大概是数百个PB，每天处理的数据大约有几十个PB。我是差不多四年半前加入百度的，所以我比较清楚地记得那时候的规模。与那时相比，现在的数据规模成长比较惊人，大概是那时的500~1000倍。  
数据量大并不可怕，问题是要实时处理数据，因为任何的时延都会使服务失去一些优势，从而导致商业经济的下降。我们所做的策略都是针对实时性的，而且今天互联网用户的需求更加实时化，比如说微博、团购、秒杀。  
**周俊凌：**从IDC的数据统计报告来看，数据增长是非常快的。相对于具体的数据量，Teradata更关注数据发展的趋势，并大量投入研究这种发展趋势，包括BI方面的变化和增长模式，这个模式对于我们非常有价值，通过研究这种模式，包括每分钟、每秒钟交易量有多大等这些数据的发掘和建模，数据科学家进行研究和探讨，把这些技术应用到生产系统里面，对企业发挥作用。  
**韩轶平：**Yahoo!的主要云计算平台Hadoop现在有34个集群，总数超过3万台机器，最大的集群是4000台左右，总存储容量超过100PB。这个数量级可以说并不大，主要原因在于我们最近将很多精力放在处理用户隐私性和数据安全性上，因为按照欧盟的规定，Yahoo!不能存储超过一年的数据，所以我们的应对措施就是：不保存原始数据，但做很深入的数据挖掘，挖掘出真正蕴含的有价值的信息，把这些信息保存下来。  
**杜韬：**SAP作为企业级应用提供商，更关注客户的数据量，而我们的客户有许多数据密集型企业，比如电信、金融、政府、零售等，数据量级从几个TB到数百TB。SAP在德国总部的数据中心有3万台服务器，数据量大概是15PB，主要为客户提供服务。我们正在帮助客户将内部应用迁移到我们的数据中心服务平台，这也意味着越来越多的客户数据会存在我们这儿。  
  
  
**面对大数据，您是怎样进行处理分析的？  
杜韬：**一方面在数据中心，我们使用了标准的虚拟化以及分布式存储；另一方面，我们推出了内存计算技术，用以应对数据应用和分析的挑战。传统的架构存在很大的瓶颈，磁盘读取是以毫秒，而内存读取则是纳秒。因此，我们将以前需要在应用层做的计算分析，比如预测分析或者大量运算，都放到内存里操作，从而实现性能提升，帮助用户充分利用数据。  
**韩轶平：**对Yahoo!的情况，我想分三个部分来说明：数据采集、数据存储和数据处理。  
在数据采集方面，我们建立了一个遍布Yahoo!几个数据中心、几十万台机器的实时搜集数据系统，该系统特点是一个主干道负责把数据经过过滤、清理以后，进行整合，并且在高可靠性的情况下，把它放到Hadoop平台。虽然相对来说精度很高、效果很好，但速度会慢一些。为了满足威廉•张所说实时性的需求，还有一个旁路系统，旁路系统在秒级能够把数据汇到主干道上，这是数据采集的部分。  
在数据存储方面，基本上以HDFS为核心。在数据处理方面，主要技术是Hadoop、MapReduce以及我们自己开发的Pig。目前，我们有超过一半数据处理引擎是用Pig完成的。  
**周俊凌：**Teradata一直在持续创新传统的企业级数据仓库产品线，在对接大数据时代的同时，继续传统的BI领域，包括提高数据处理的能力，从而更容易适应大数据管理。例如，通过数据访问频率高低确认数据温度，进行数据压缩，适应大数据的分析要求，使数据管理更容易。  
我们有适应超高规模数据容量要求的硬件平台产品Teradata 1000，可以压缩35PB的数据。特别适用一些结构性数据和非结构性数据的分析，同时开发了很多能够进行数据统计和分析的软件包，包括将Hadoop等架构整合到Teradata数据仓库之中，可以基于目前的Teradata企业级数据仓库接口使用。  
我们提供基于云的架构，能够使用Amazon EC2，为客户提供安全的存储产品，用来存储公司防火墙以外的、存储在云端的数据。我们刚刚收购了Aster Data公司，它有一些非常好的工具，适用于Hadoop、MapReduce的一些应用。  
**威廉•张：**各互联网企业在云计算技术方面的应用都差不多，比如说百度也用了Hadoop，我提几个比较有特点的地方。  
第一个是大搜索，即不仅是把网页抓过来，建立极其庞大的索引，而且为了使数据做到准实时或者更快速的更新，进行一些优化，比如根据地域分布和重要性分布，放在南方或者北方的机房里，主要还是根据数据应用制订的策略。另外就是采用数据流技术。  
第二个是机器学习算法。在科技领域里，机器学习以前更多的是对一台服务器内存里的数据进行高复杂的计算，可能要跑很长时间。而在百度，机器学习应用于所有地方，比如判断用户需求，从用户行为反馈中得到我们应该推荐什么样的内容、匹配什么样的广告等，时效性非常高。可以称得上是增量型、大规模的机器学习方法。  
此外，互联网应用要继续发展，最关键还是找到更有价值的数据，即不管数据来自何方，都要按照价值来决定如何处理它。  
**您怎样看待层出不穷的NoSQL技术？  
杜韬：**我一直认为，存在的就是合理的，NoSQL的产生和演进也是因为我们现有的应用需求所导致。当前在大并发量、海量数据的高效读写等方面，对关系型数据库提出了更高的要求，而NoSQL在这方面有独特的价值和优势。  
当然，这并不是说NoSQL的出现就代表着关系型数据库的世界末日，因为对于一些应用，特别是企业级应用，对于事务的一致性以及读写的实时性等各方面有很高的要求，而关系型数据库在这些年的发展中积累了自己的优势。  
因此，我很认同NoSQL是“Not Only SQL”的说法，相信在未来关系型数据库和NoSQL会并存甚至是相互融合。  
**韩轶平：**NoSQL是一个很宽泛的概念。在Yahoo!，虽然NoSQL说得不多，但用的NoSQL工具非常多，我们的Key-Value数据库等各种各样的系统，都属于NoSQL框架。至于说NoSQL和SQL之间的关系，因为很多场合需要ACID，也就需要NoSQL的东西，而NoSQL之所以会出现，就像我经常说的“上帝是公平的”，当有一个需求出现时必须放弃另一个东西。我们的很多需求，比如大数据量、高分布性，当有了这些需求以后另一个需求可能成为新的瓶颈。事实上，对我们来说，互联网行业在很多应用中并不需要一致性。当把需求放宽时，自然能够满足另一些需求。  
  
  
**怎样挖掘数据中的价值？  
威廉•张：**我举一个直观的匹配广告的例子，它包括两类数据：一类是广告库，即广告内容信息和广告客户信息，这类信息很适合于传统数据库；另一类信息是用户看到广告之后的一切行为，经历了日积月累，可能会有几百万亿的用户行为。这两种数据可以相结合，经过机器学习算法就能产生价值。显然，第二种信息更重要，因为它能给用户提供想要的信息，比如搜索一个词，可以利用所有用户在他之前、在他之后的群体智能、群体行为，判定哪一类的信息最重要、最优质，哪一类信息可能是作弊信息，然后经过反馈机制，把最好的内容提供给用户，甚至推荐相关的一些搜索、查询信息。总而言之，对任何企业来说，数据是命根子；对云计算来说，数据处理就是云数据中心或者云计算存在的理由。  
**韩轶平：**我们工作之余经常开玩笑说：从数据中能挖出的东西，不一定是钱，更重要的是用户体验，对互联网公司来说，数据就是一切。  
Yahoo!不仅仅是搜索引擎，也有很多在美国各领域中排名第一的网站。我们做的很多工作，比如新闻网站信息，都是根据新闻的相关性和大家的兴趣推荐的，我们希望根据每一个用户自己的兴趣，甚至每一个用户此时此刻的兴趣，进行推荐。Yahoo!新闻的推荐系统，是把Yahoo!所有的数据搜集起来，用户在Yahoo!搜索上的所有行为都搜集到一起，做深度挖掘和个性化，对每一个用户都进行分析和推荐，没有这些数据我们不可能为客户提供体验，数据对我们来说就是一切。  
**杜韬：**既然各位是从互联网的角度来看数据的价值，那么我就从企业的角度来分享一下。  
智能电网现在欧洲已经做到了终端，也就是所谓的智能电表。在德国，为了鼓励利用太阳能，会在家庭安装太阳能，除了卖电给你，当你的太阳能有多余电的时候还可以买回来。通过电网收集每隔五分钟或十分钟收集一次数据，收集来的这些数据可以用来预测客户的用电习惯等，从而推断出在未来2~3个月时间里，整个电网大概需要多少电。有了这个预测后，就可以向发电或者供电企业购买一定数量的电。因为电有点像期货一样，如果提前买就会比较便宜，买现货就比较贵。通过这个预测后，可以降低采购成本。  
另一个例子更偏我个人的兴趣。丹•布朗的《失落的秘符》一书讲到，如果把很多人的精神集中在一个点，能够移动物体。当然这个我们无从考证，但我们在网上搜索关键词、敏感词时，就可以判断出某件事情的公众态度。有一些新的业务模式，比如做一个网络广告投放评估公司，利用这样的技术评估网络广告的效果，我觉得也许是未来的业务价值产生点。  
**海量数据时代对企业和技术人员带来了哪些挑战？  
韩轶平：**以前我们都说自己是软件工程师，我们这个行业也经常被叫做软件行业，但我认为我们是真正的Information Technology行业。对大多数人来说，现在最重要的一点是转变观念，从Code/Program观念转变成Data观念，在做任何设计和开发时，要把Data放在第一位。  
**杜韬：**海量数据一直在增长，但是我们应该想办法控制下来，未来的趋势应该放在怎样缩小海量数据上，而不是任凭它扩张。此外，海量数据时代对中国来说是一次引领世界IT业的机会。  
**周俊凌：**在云计算时代，业务数据与云紧密结合在一起，提供业务开发的能力，我们从中学到了很多新的东西，有一些东西不再是自己去存储和开发，而是都放在云里面存储。技术产品推向市场的方式与以往相比，发生了很大变化。云的这样一种环境也给数据库提供商带来很多技术上的挑战，例如如何保证存储的安全性，包括身份识别的健全。这关系到数据的存储地方，例如现在发货的数据都是放在全球任何一个地方，不是放在某一个国家里面，这就带来关于数据主权的问题，可能有一些国家和政府不允许把数据放在国家某些地方，这都是一些挑战，需要从技术上解决安全等问题。  
  
  
**威廉•张：**这里我浅谈一下两点感受。  
首先，数据管理是DBA的一项重要本领，而高校的计算机专业教育里没有特别重视数据程序员，并没有数据管理员；其次，MapReduce并不是一个新概念，早在30~40年前当计算机能力还超小的时候，函数式编程语言就出现了，但至今大学里还没有开设MapReduce或者类似数据处理的课程，也基本上没有人听过这些东西。

未来将所有人的生活经验数据放在云里，这个大概可以实现，但如果解决不好数据安全性问题的话，那么距离最终的实现就会很远。我期待云计算变成云知识、云智能，而不仅仅是计算的工具。建立数据整合分享是云计算成功的必要和充分条件。

**前言**  
  
    本博客内曾经整理过有关海量数据处理的10道面试题（[十道海量数据处理面试题与十个方法大总结][Link 1]），此次除了重复了之前的10道面试题之后，重新多整理了7道。仅作各位参考，不作它用。  
    同时，程序员编程艺术系列将重新开始创作，第十一章以后的部分题目来源将取自下文中的17道海量数据处理的面试题。因为，我们觉得，下文的每一道面试题都值得重新思考，重新深究与学习。再者，编程艺术系列的前十章也是这么来的。若您有任何问题或建议，欢迎不吝指正。谢谢。  
**第一部分、十五道海量数据处理面试题**  
**1. 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？**  
    方案1：可以估计每个文件安的大小为50G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

1.  遍历文件a，对每个url求取![0_1313302192BLP4.gif][]，然后根据所取得的值将url分别存储到1000个小文件（记为![0_13133022154fL9.gif][]）中。这样每个小文件的大约为300M。
2.  遍历文件b，采取和a相同的方式将url分别存储到1000小文件中（记为![0_13133022364Qoo.gif][]）。这样处理后，所有可能相同的url都在对应的小文件（![0_1313302261MhJ0.gif][]）中，不对应的小文件不可能有相同的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：

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

1.  顺序读取10个文件，按照hash(query)%10的结果将query写入到另外10个文件（记为![0_1313302290jETe.gif][]）中。这样新生成的文件每个的大小大约也1G（假设hash函数是随机的）。
2.  找一台内存在2G左右的机器，依次对![0_1313302310ww2H.gif][]用hash\_map(query, query\_count)来统计每个query出现的次数。利用快速/堆/归并排序按照出现次数进行排序。将排序好的query和对应的query\_cout输出到文件中。这样得到了10个排好序的文件（记为![0_1313302329UNN0.gif][]）。
3.  对![0_1313302350l5vC.gif][]这10个文件进行归并排序（内排序与外排序相结合）。

方案2：  
    一般query的总量是有限的，只是重复的次数比较多而已，可能对于所有的query，一次性就可以加入到内存了。这样，我们就可以采用trie树/hash\_map等直接来统计每个query出现的次数，然后按出现次数做快速/堆/归并排序就可以了。  
方案3：  
    与方案1类似，但在做完hash，分成多个文件后，可以交给多个文件来处理，采用分布式的架构来处理（比如MapReduce），最后再进行合并。  
**3. 有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。**  
    方案1：顺序读文件中，对于每个词x，取 ![0_1313302374j4KX.gif][]，然后按照该值存到5000个小文件（记为 ![0_1313302392OZOo.gif][]）中。这样每个文件大概是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：  
][2.5_Bitmap_00_01_01_10_10_bitmap_01_ _2_ _6. _100_TOP10_ _1_]

1.  在每台电脑上求出TOP10，可以采用包含10个元素的堆完成（TOP10小，用最大堆，TOP10大，用最小堆）。比如求TOP10大，我们首先取前10个元素调整成最小堆，如果发现，然后扫描后面的数据，并与堆顶元素比较，如果比堆顶元素大，那么用该元素替换堆顶，然后再调整为最小堆。最后堆中的元素就是TOP10大。
2.  求出每台电脑上的TOP10后，然后把这100台电脑上的TOP10组合起来，共1000个数据，再利用上面类似的方法求出TOP10就可以了。

（更多可以参考： **第三章、寻找最小的k个数**，以及 [第三章续、**Top K算法问题**的实现][Top K]）  
**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个元素的最小堆完成。复杂度为O(100w\*lg100)。
 *      方案2：采用快速排序的思想，每次分割之后只考虑比轴大的一部分，知道比轴大的一部分在比100多的时候，采用传统排序算法排序，取前100个。复杂度为O(100w\*100)。
 *      方案3：采用局部淘汰法。选取前100个元素，并排序，记为序列L。然后一次扫描剩余的元素x，与排好序的100个元素中最小的元素比，如果比这个最小的要大，那么把这个最小的元素删除，并把x利用插入排序的思想，插入到序列L中。依次循环，知道扫描了所有的元素。复杂度为O(100w\*100)。

**13. 寻找热门查询：**  
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复读比较高，虽然总数是1千万，但是如果去除重复和，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。  
(1) 请描述你解决这个问题的思路；  
(2) 请给出主要的处理流程，算法，以及算法的复杂度。  
    方案1：采用trie树，关键字域存该查询串出现的次数，没有出现为0。最后用10个元素的最小推来对出现频率进行排序。  
**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个实数 ![0_131330271622QP.gif][]，求着n个实数在实轴上向量2个数之间的最大差值，要求线性的时间算法。  
方案1：最先想到的方法就是先对这n个数据进行排序，然后一遍扫描即可确定相邻的最大间隙。但该方法不能满足线性时间的要求。故采取如下方法：

1.  找到n个数据中最大和最小数据max和min。
2.  用n-2个点等分区间\[min, max\]，即将\[min, max\]等分为n-1个区间（前闭后开区间），将这些区间看作桶，编号为![0_1313303205157b.gif][]，且桶i 的上界和桶i+1的下届相同，即每个桶的大小相同。每个桶的大小为：![0_1313303279I00N.gif][]。实际上，这些桶的边界构成了一个等差数列（首项为min，公差为![0_1313303418777s.gif][][），且认为将min放入第一个桶，将max放入第n-1个桶。][min_max_n-1]
3.  [将n个数放入n-1个桶中：将每个元素x *分配到某个桶（编号为index），其中![0_13133034380u54.gif][]，并求出分到每个桶的最大最小数据。*][min_max_n-1]
4.  [*最大间隙：除最大最小数据max和min以外的n-2个数据放入n-1个桶中，由抽屉原理可知至少有一个桶是空的，又因为每个桶的大小相同，所以最大间隙不会在同一桶中出现，一定是某个桶的上界和气候某个桶的下界之间隙，且该量筒之间的桶（即便好在该连个便好之间的桶）一定是空桶。也就是说，最大间隙在桶i的上界和桶j的下界之间产生j>=i+1。一遍扫描即可完成。*][min_max_n-1]

[***16. 将多个集合合并成没有交集的集合**  
    给定一个字符串的集合，格式如：**![0_1313305615kcCG.gif][]**。要求将其中交集不为空的集合合并，要求合并完成的集合之间无交集，例如上例应输出![0_1313305694rVyP.gif][]。*  
][min_max_n-1]

> (1) 请描述你解决这个问题的思路；  
> (2) 给出主要的处理流程，算法，以及算法的复杂度；  
> (3) 请描述可能的改进。  
>

方案1：采用并查集。首先所有的字符串都在单独的并查集中。然后依扫描每个集合，顺序合并将两个相邻元素合并。例如，对于 ![0_1313305723D1k5.gif][]，首先查看aaa和bbb是否在同一个并查集中，如果不在，那么把它们所在的并查集合并，然后再看bbb和ccc是否在同一个并查集中，如果不在，那么也把它们所在的并查集合并。接下来再扫描其他的集合，当所有的集合都扫描完了，并查集代表的集合便是所求。复杂度应该是O(NlgN)的。改进的话，首先可以记录每个节点的根结点，改进查询。合并的时候，可以把大的和小的进行合，这样也减少复杂度。  
**17. 最大子序列与最大子矩阵问题**  
数组的最大子序列问题：给定一个数组，其中元素有正，也有负，找出其中一个连续子序列，使和最大。  
    方案1：这个问题可以动态规划的思想解决。设b *表示以第i个元素a结尾的最大子序列，那么显然![0_1313305860szjU.gif][]。基于这一点可以很快用代码实现。  
最大子矩阵问题：给定一个矩阵（二维数组），其中数据有大有小，请找一个子矩阵，使得子矩阵的和最大，并输出这个和。  
    方案2：可以采用与最大子序列类似的思想来解决。如果我们确定了选择第i列和第j列之间的元素，那么在这个范围内，其实就是一个最大子序列问题。如何确定第i列和第j列可以词用暴搜的方法进行。  
  
**第二部分、海量数据处理之Bti-map详解***

[    Bloom Filter已在上一篇文章**海量数据处理之Bloom Filter详解**][min_max_n-1]中予以详细阐述，本文接下来着重阐述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(如下图：)

> > > ![0_1313301884r8Im.gif][]  
> > >

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

> >        ![0_1313301894Tg2K.gif][]  
> >

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

> > > ![0_1313301902884F.gif][]

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

1.  //定义每个Byte中有8个Bit位   \#include ＜memory.h＞   \#define BYTESIZE 8   **void** SetBit(**char** \*p, **int** posi)   \{       **for**(**int** i=0; i ＜ (posi/BYTESIZE); i++)       \{           p++;       \}          \*p = \*p|(0x01＜＜(posi%BYTESIZE));//将该Bit位赋值1       **return**;   \}      **void** BitMapSortDemo()   \{       //为了简单起见，我们不考虑负数       **int** num\[\] = \{3,5,2,10,6,12,8,14,9\};          //BufferLen这个值是根据待排序的数据中最大值确定的       //待排序中的最大值是14，因此只需要2个Bytes(16个Bit)       //就可以了。       **const****int** BufferLen = 2;       **char** \*pBuffer = **new****char**\[BufferLen\];          //要将所有的Bit位置为0，否则结果不可预知。       memset(pBuffer,0,BufferLen);       **for**(**int** i=0;i＜9;i++)       \{           //首先将相应Bit位上置为1           SetBit(pBuffer,num*);  * *    \}        //输出排序结果      **for**(**int** i=0;i＜BufferLen;i++)//每次处理一个字节(Byte)      \{          **for**(**int** j=0;j＜BYTESIZE;j++)//处理该字节中的每个Bit位          \{              //判断该位上是否是1，进行输出，这里的判断比较笨。              //首先得到该第j位的掩码（0x01＜＜j），将内存区中的              //位和此掩码作与操作。最后判断掩码是否和处理后的              //结果相同              **if**((\*pBuffer&(0x01＜＜j)) == (0x01＜＜j))              \{                  printf("%d ",i\*BYTESIZE + j);              \}          \}          pBuffer++;      \}  \}    **int** \_tmain(**int** argc, \_TCHAR\* argv\[\])  \{      BitMapSortDemo();      **return** 0;  \}  *

*可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下  
**基本原理及要点**  
使用bit数组来表示某些元素是否存在，比如8位电话号码  
**扩展**  
Bloom filter可以看做是对bit-map的扩展（关于Bloom filter，请参见：[海量数据处理之**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，都是一样的道理。  
  
整理自：*

1.  [http://www.cnblogs.com/youwang/archive/2010/07/20/1781431.html][http_www.cnblogs.com_youwang_archive_2010_07_20_1781431.html]
2.  [http://blog.redfox66.com/post/2010/09/26/mass-data-4-bitmap.aspx][http_blog.redfox66.com_post_2010_09_26_mass-data-4-bitmap.aspx]

<table> 
 <tbody> 
 <tr> 
 <td> 
 <table> 
 <tbody> 
 <tr> 
 <td>usidc5</td> 
 <td align="right">2011-08-20 22:59</td> 
 </tr> 
 <tr> 
 <td colspan="2"> 导读：Yahoo CTO Raymie Stata是领导海量数据分析引擎的关键人物。IBM和Hadoop将更多的精力专注在海量数据上，海量数据正在潜移默化的改变企业和IT部门。 <img src="http://articles.csdn.net/uploads/allimg/110818/79_110818100924_1.jpg" alt=""> 越来越多的大企业的数据集以及创建需要的一切技术，包括存储、网络、分析、归档和检索等，这些被认为是海量数据。这些大量信息直接推动了存储、服务器以及安全的发展。同时也是给IT部门带来了一系列必须解决的问题。 信息技术研究和分析的公司Gartner认为海量数据处理应该是将大量的不同种类以及结构化和非结构化的数据通过网络汇集到处理器和存储设备之中，并伴随着将这些数据转换为企业的商业报告。 海量数据处理的三个主要因素：大容量数据、多格式数据和速度 大容量数据（TB级、PB级甚至EB级）：人们和机器制造的越来越多的业务数据对IT系统带来了更大的挑战，数据的存储和安全以及在未来访问和使用这些数据已成为难点。 多格式数据：海量数据包括了越来越多不同格式的数据，这些不同格式的数据也需要不同的处理方法。从简单的电子邮件、数据日志和信用卡记录，再到仪器收集到的科学研究数据、医疗数据、财务数据以及丰富的媒体数据（包括照片、音乐、视频等）。 速度：速度是指数据从端点移动到处理器和存储的速度。 Kusnetzky集团的分析师Dan Kusnetzky在其博客表示“简单的说，大数据是指允许组织创建、操作和管理的庞大的数据集和存储设施工具”。这是否意味着将来将会出现比TB和PB更大的数据集吗？供应商给出的回应是“会出现”。 他们也许会说“你需要我们的产品来管理和组织利用大规模的数据，只是想想繁杂大量的维护动态数据集带来的麻烦就使人们头疼“。此外海量数据的另外一个价值是它可以帮助企业在适当的时机作出正确决策。 <img src="http://articles.csdn.net/uploads/allimg/110818/79_110818101534_1.jpg" alt=""> 从历史上看，数据分析软件面对当今的海量数据已显得力不从心，这种局面正在悄然转变。新的海量数据分析引擎已经出现。如Apache的Hadoop、LexisNexis的HPCC系统和1010data（托管、海量数据分析的平台供应商）的以云计算为基础的分析服务。 101data的高级副总裁Tim Negris表示海量数据的收集以及存放和利用海量数据实际上完全是两回事。在做任何事前需要大量（准备数据）的工作是像Oracle和大多数数据库厂商所面临的难题之一。我们正是要消除这个难题，并把数据直接交到分析师的手中。Hadoop和HPCC系统做到了这一点。这三个平台都着眼于海量数据并提供支持。 开源的Hadoop已经在过去5年之中证明了自己是市场中最成功的数据处理平台。目前Cloudera的首席执行官和Apache基金会的Doug Cutting是Hadoop的创始人，他曾在Yahoo工作过。 Hadoop将海量数据分解成较小的更易访问的批量数据并分发到多台服务器来分析（敏捷是一个重要的属性，就像你更容易消化被切成小块的食物）Hadoop再处理查询。 “Gartner和IDC的分析师认为海量数据的处理速度和处理各种数据的能力都是Hadoop吸引人们的地方”。Cloudera的产品副总裁Charles Zedlewski说到。 在Cutting和他的Yahoo团队提出Hadoop项目之后，在Yahoo IT系统测试并广泛使用了很多年。随后他们将Hadoop发布到开源社区，这使得Hadoop逐渐产品化。 在Cutting和Yahoo在开发、测试并内部运行代码时，他们了解到使用起来还是很复杂的。这导致他们马上意识到如果在未来提供周边服务（例如提供直观的用户界面、定制部署和附加功能软件）可赚取更多的资金。 <img src="http://articles.csdn.net/uploads/allimg/110818/79_110818101516_1.jpg" alt=""> 在2009年Cloudera作为一家独立公司开始运营，公司产品采用开源并产品化Hadoop分析引擎和Cloudera企业版（Cloudera Enterprise整合了更多的工具，包括Hive、HBase、Sqoop、Oozie、Flume、Avro、Zookeeper、Pig和Cloudera Desktop）。 Cloudera得到了大量投资者的青睐，这其中包括VMware的创始人和前首席执行官Diane Greene、Flickr的联合创始人Caterina Fake、MySQL前首席执行官Marten Mickos、Linkedln总裁Jeff Weiner和Facebook CFO Gideon Yu。 自从Cloudera成立以来，只有少数的顶级公司和初创公司免费提供他们基于Hadoop开放源代码架构制作的自己的版本。 这是一场真正的企业科技的竞争。就像在一场接力赛中，所有选手都必须使用同一种类型的接力棒（Hadoop的代码）。企业竞争主要集中在处理数据的速度、敏捷性和创造性上。这场竞争是迫使大多数企业在海量数据分析市场有所作为最有效的方法。 IBM提供了基于Hadoop的InfoSphere BigInsights（IBM InfoSphere BigInsights 是用于分析和虚拟化海量数据的软件和服务，这款新产品由 Apache Hadoop 提供技术支持。）基本版和企业版。但公司有更大的计划。 IBM CEO Sam Palmisano表示IBM正在将新一代数据分析作为公司的研发重点，IBM在此项目上投资了1亿美元。IBM院士和计算机科学研究室主任Laura Haas表示IBM实验室的研究远远超出了海量数据的范围，并已经着手”Exadata“分析研究。Watson就是IBM在数据海量数据研究的成果，Watson将用于更多用途，包括卫生保健、科学研究等。 其他Hadoop版本 MapR发布了一个分布式文件系统和MapReduce引擎，MapR还与存储和安全的领导厂商EMC合作向客户提供了Greenplum HD企业版Hadoop存储组件 。EMC Hadoop的另一个独特之处在于它没有采用官方版本的Apache代码，而是采用Facebook的Hadoop代码，后者在可扩展性和多站点部署上进行了优化。 另一家厂商 Platform Computing，Platform提供了与Apache Hadoop MapReduce编程模型完全兼容的分布式分析平台，并支持多种分布式文件系统。 <img src="http://articles.csdn.net/uploads/allimg/110818/79_110818101706_1.jpg" alt=""> SGI（Silicon Graphics International ）提供基于SGI Rackable和CloudRack服务器产品实施服务的Hadoop优化解决方案。 戴尔也开始出售预装该开源数据处理平台的服务器。 该产品成本随支持选项不同而异，基础配置价格在11.8万美元至12.4万美元之间，包含为期一年的Cloudera支持和更新，6个PowerEdge C2100服务器（2个管理节点，1个边缘节点和3个从站节点，以及6个戴尔PowerConnect 6248交换机）。 替代品浮出水面。包括1010data的云服务、LexusNexis公司的Risk，该系统在10年间帮助LexusNexis公司分析大量的客户数据，并在金融业和其他重要的行业中应用。LexusNexis最近还宣布要在开源社区分享其核心技术以替代Hadoop。LexisNexis公司发布一款开源的数据处理方案，该技术被称为HPCC系统。 HPCC可以管理、排序并可在几秒钟内分上亿条记录。HPCC提供两种数据处理和服务的方式——Thor Data Refinery Cluster和Roxy Rapid Data Delivery Cluster。Escalante表示如此命名是因为其能像Thor(北欧神话中司雷、战争及农业的神)一样解决困难的问题，Thor主要用来分析和索引大量的Hadoop数据。而Roxy则更像一个传统的关系型数据库或数据仓库，甚至还可以处理Web前端的服务。 LexisNexis CEO James Peck表示我们认为在当下这样的举动是对的，同时我们相信HPCC系统会将海量数据处理提升到更高高度。 <img src="http://articles.csdn.net/uploads/allimg/110818/79_110818102510_1.jpg" alt=""> 在2011年6月Yahoo和硅谷风险投资公司Benchmark Capital周二联合宣布，他们将联合成立一家名为Hortonworks的新公司，接管被广泛应用的数据分析软件Hadoop的开发工作。 据一些前Yahoo员工透露，从商业角度来看Hortonworks将保持独立运营，并发展其自身的商业版。 在转型时期，Yahoo CTO Raymie Stata成为关键人物，他将负责公司所有IT项目的发展。Stata表示相对于Yahoo，在Hortonworks我们会投入更多的精力在Hadoop的工作和相关技术上，我们认为应加大对Hadoop的投资。我们会将一些关键人员指派到Hortonworks公司，但这既不是裁员也不是分拆。这是在加大对Hadoop的投入。Yahoo将继续为Hadoop的发展做出更大的贡献。 Stata解释说，Yahoo一直有一个梦想，就是将Hadoop变为大数据分析软件的行业标准。但是这必须将Hadoop商业化。Stata表示创建Hortonworks的主要原因是因为Yahoo已经看到了未来企业分析（感谢Hadoop 6年以来的发展）的未来，并知道该怎样去做。我们看到海量数据分析将很快成为企业非常普遍的需求。 我们将Hadoop部署在企业之中，我不认为所有人都否定这样的解决方案。我们要通过Hadoop为我们的股东创造价值。如果某一天Hadoop成为海量数据处理的行业标准，这将是对我们最好的奖赏。（李智/译） </td> 
 </tr> 
 </tbody> 
 </table> </td> 
 </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
 <tr> 
 <td> 
 <table> 
 <tbody> 
 <tr> 
 <td>usidc5</td> 
 <td align="right">2011-10-25 09:21</td> 
 </tr> 
 <tr> 
 <td colspan="2"> 毫无疑问，世界上所有关注开发技术的人都意识到“大数据”对企业商务所蕴含的潜在价值，其目的都在于解决在企业发展过程中各种业务数据增长所带来的痛苦。 现实是，许多问题阻碍了大数据技术的发展和实际应用。 因为一种成功的技术，需要一些衡量的标准。现在我们可以通过几个基本要素来衡量一下大数据技术，这就是——流处理、并行性、摘要索引和可视化。 谁会用到大数据呢？ 一年前，大数据技术的一些主要用户是大型Web企业，例如Facebook和雅虎，它们需要分析点击流数据。但是今天，“大数据技术已经超出了Web，是要是有大量数据需要处理的企业都有可能用到它。”例如银行、公用事业机构、情报部门等都在搭乘大数据这辆车。 实际上，一些大数据技术已经被一些拥有很前卫技术的企业在使用了，比如受社交媒体推动而需要创建相应Web服务的企业。它们对于大数据项目的贡献非常重要。 而在其他垂直行业中，有些企业正在意识到，它们基于信息服务的价值定位要比它们先前想象的要大得多，所以大数据技术很快就吸引了这些企业的注意。再加上硬件和软件成本的下降，这些企业发现它们已经处在了一场企业大转型机遇的完美风暴中。 大数据处理的应对三大挑战：大容量数据、多格式数据和速度 大容量数据（TB级、PB级甚至EB级）：人们和机器制造的越来越多的业务数据对IT系统带来了更大的挑战，数据的存储和安全以及在未来访问和使用这些数据已成为难点。 多格式数据：海量数据包括了越来越多不同格式的数据，这些不同格式的数据也需要不同的处理方法。从简单的电子邮件、数据日志和信用卡记录，再到仪器收集到的科学研究数据、医疗数据、财务数据以及丰富的媒体数据（包括照片、音乐、视频等）。 速度：速度是指数据从端点移动到处理器和存储的速度。 大数据技术涵盖哪些内容？ 一、流处理 伴随着业务发展的步调，以及业务流程的复杂化，我们的注意力越来越集中在“数据流”而非“数据集”上面。 决策者感兴趣的是紧扣其组织机构的命脉，并获取实时的结果。他们需要的是能够处理随时发生的数据流的架构，当前的数据库技术并不适合数据流处理。 <img src="http://articles.csdn.net/uploads/allimg/111024/2_111024223918_1.jpg" alt=""> 例如，计算一组数据的平均值，可以使用一个传统的脚本实现。但对于移动数据平均值的计算，不论是到达、增长还是一个又一个的单元，有更高效的算法。如果你想构建数据仓库，并执行任意的数据分析、统计，开源的产品R或者类似于SAS的商业产品就可以实现。但是你想创建的是一个数据流统计集，对此逐步添加或移除数据块，进行移动平均计算，而且数据库不存在或者尚不成熟。 数据流周边的生态系统有欠发达。换言之，如果你正在与一家供应商洽谈一个大数据项目，那么你必须知道数据流处理对你的项目而言是否重要，并且供应商是否有能力提供。 二、并行化 大数据的定义有许多种，以下这种相对有用。“小数据”的情形类似于桌面环境，磁盘存储能力在1GB到10GB之间，“中数据”的数据量在100GB到1TB之间，“大数据”分布式的存储在多台机器上，包含1TB到多个PB的数据。 <img src="http://articles.csdn.net/uploads/allimg/111024/2_111024224159_1.JPG" alt=""> 如果你在分布式数据环境中工作，并且想在很短的时间内处理数据，这就需要分布式处理。 并行处理在分布式数据中脱颖而出，Hadoop是一个分布式/并行处理领域广为人知的例子。Hadoop包含一个大型分布式的文件系统，支持分布式/并行查询。 三、摘要索引 摘要索引是一个对数据创建预计算摘要，以加速查询运行的过程。摘要索引的问题是，你必须为要执行的查询做好计划，因此它有所限制。 数据增长飞速，对摘要索引的要求远不会停止，不论是长期考虑还是短期，供应商必须对摘要索引的制定有一个确定的策略。 四、数据可视化 <img src="http://articles.csdn.net/uploads/allimg/111024/2_111024224927_1.jpg" alt=""> 可视化工具有两大类。 探索性可视化描述工具可以帮助决策者和分析师挖掘不同数据之间的联系，这是一种可视化的洞察力。类似的工具有Tableau、TIBCO和QlikView，这是一类。 叙事可视化工具被设计成以独特的方式探索数据。例如，如果你想以可视化的方式在一个时间序列中按照地域查看一个企业的销售业绩，可视化格式会被预先创建。数据会按照地域逐月展示，并根据预定义的公式排序。供应商Perceptive Pixel就属于这一类。 五、生态系统战略 许多最大最成功的公司都花费大量资金构建围绕它们产品的生态系统。这些生态系统被产品特性和商务模型所支持，并与合作伙伴的产品和技术协同工作。如果一个产品没有一个富有战略的生态系统，是很难适应客户的要求的。 </td> 
 </tr> 
 </tbody> 
 </table> </td> 
 </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
 <tr> 
 <td> 
 <table> 
 <tbody> 
 <tr> 
 <td>usidc5</td> 
 <td align="right">2011-11-18 22:23</td> 
 </tr> 
 <tr> 
 <td colspan="2">当数据以成百上千TB不断增长的时候，我们需要一种独特技术来应对这种前所未有的挑战。 大数据分析迎来大时代 全球各行各业的组织机构已经意识到，最准确的商务决策来自于事实，而不是凭空臆想。这也就意味着，他们需要在内部交易系统的历史信息之外，采用基于数据分析的决策模型和技术支持。互联网点击数据、传感数据、日志文件、具有丰富地理空间信息的移动数据和涉及网络的各类评论，成为了海量信息的多种形式。 极具挑战性的是，传统的数据库部署不能处理数TB数据，也不能很好的支持高级别的数据分析。在过去十几年中，大规模并行处理（MPP）平台和列存储数据库开启了新一轮数据分析史上的革命。而且近年来技术不断发展，我们开始看到，技术升级带来的已知架构之间的界限变得更加模糊。更为重要的是，开始逐步出现了处理半结构化和非结构化信息的NoSQL等平台。 <img src="http://articles.csdn.net/uploads/allimg/111118/0932336252-0.jpg" alt=""> 大数据分析迎来大时代 本文中，我们将向大家介绍迄今为止，包括EMC的Greenplum、Hadoop和MapReduce等提供大数据分析的产品。此外，惠普前段时间收购实时分析平台Vertica、IBM独立的基于DB2智能分析系统和Netezza的相关产品。当然，也有微软的Parallel Data Warehouse、SAP旗下公司Sybase的Sybase IQ数据仓库分析工具等。下面，就让我们来了解业界大数据分析的这十二大产品： 1.模块化EMC Appliance处理多种数据类型 2010年EMC收购了Greenplum，随后，利用EMC自身存储硬件和支持复制与备份功能的Greenplum大规模并行处理（MPP）数据库，推出了EMC Greenplum Data Computing Appliance (DCA)。通过与SAS和MapR等合作伙伴，DCA扩大了对Greenplum的数据库支持 。 <img src="http://articles.csdn.net/uploads/allimg/111118/09323350H-1.jpg" alt=""> 支持大数据分析的EMC Appliance 今年5月，EMC推出了自己的Hadoop软件工具，而且该公司还承诺，今年秋季发布的模块化DCA将支持Greenplum SQL/关系型数据库，Hadoop部署也能在同样的设备上得到支持。借助Hadoop，EMC能够解决诸如网络点击数据、非结构数据等真正大数据分析的困难。模块化的DCA也能够在同样的设备上支持长期保留的高容量的存储模块，从而满足监测需求。 2.Hadoop和MapReduce提炼大数据 Hadoop是一个开放源码的分布式数据处理系统架构，主要面向存储和处理结构化、半结构化或非结构化、真正意义上的大数据（通常成百上千的TB甚至PB级别数据）应用。网络点击和社交媒体分析应用，正在极大地推动应用需求。Hadoop提供的MapReduce（和其他一些环境）是处理大数据集理想解决方案。 MapReduce能将大数据问题分解成多个子问题，将它们分配到成百上千个处理节点之上，然后将结果汇集到一个小数据集当中，从而更容易分析得出最后的结果。 <img src="http://articles.csdn.net/uploads/allimg/111118/0932335S0-2.jpg" alt=""> MapReduce结构图 Hadoop可以运行在低成本的硬件产品之上，通过扩展可以成为商业存储和数据分析的替代方案。它已经成为很多互联网巨头，比如AOL、eHarmony（美国在线约会网站）、易趣、Facebook、Twitter和Netflix大数据分析的主要解决方案。也有更多传统的巨头公司比如摩根大通银行，也正在考虑采用这一解决方案。 3.惠普Vertica电子商务分析 今年二月被惠普收购的Vertica，是能提供高效数据存储和快速查询的列存储数据库实时分析平台。相比传统的关系数据库，更低的维护和运营成本，就可以获得更快速的部署、运行和维护。该数据库还支持大规模并行处理（MPP）。在收购之后，惠普随即推出了基于x86硬件的HP Vertica。通过MPP的扩展性可以让Vertica为高端数字营销、电子商务客户（比如AOL、Twitter、 Groupon）分析处理的数据达到PB级。 <img src="http://articles.csdn.net/uploads/allimg/111118/09323351V-3.jpg" alt=""> 惠普Vertica实时分析平台 其实，早在惠普收购之前，Vertica就推出有包括内存、闪存快速分析等一系列创新产品。它是首个新增Hadoop链接支持客户管理关系型数据的产品之一，也是首个基于云部署风险的产品平台之一。目前，Vertica支持惠普的云服务自动化解决方案。 4.IBM提供运维和分析数据仓库 去年，IBM推出了基于DB2的Smart Analytic System（图中左侧），那么它为何还要收购另外的Netezza方案平台呢？因为前者是具备高扩展性企业数据仓库的平台，可以支持成千上万的用户和各类应用操作。比如，呼叫中心通常拥有大量的雇员需要快速回拨客户的历史通话记录。Smart Analytic System提供了整合信息的DB2数据库，预配置Cognos BI软件模块，可以在IBM Power System（RISC或者X86架构）上运行。 <img src="http://articles.csdn.net/uploads/allimg/111118/112_111118092313_1.jpg" alt=""> Smart Analytic System及Netezza Netezza致力于为数字化营销公司、电信、和其他挖掘成百上千TB甚至PB级别数据的公司，提供高可扩展分析应用的解决方案。IBM的Netezza TwinFin数据仓库设备，支持大规模并行处理，可以在一天时间内部署完毕。Netezza支持多种语言和方式进行数据库分析，其中包括Java、C、C++、Python和MapReduce。与此同时，它还支持如SAS，IBM SPSS使用的矩阵操作方法和R编程语言。IBM Netezza最近增加了一个高容量长期存档设备以满足更多要求。 5.Infobright减少DBA工作量和查询时间 Infobright列存储数据库，旨在为数十TB级别数据提供各类分析服务。而这一块也正是甲骨文和微软SQL Server的核心市场之一。InfoBright还表示，建立在MySQL基础之上的数据库也提供了另外一种选择，它专门针对分析应用、低成本简化劳动力工作、交付高性能的服务进行设计。 列存储数据库能够自动创建索引，而且无需进行数据分区和DBA调整。相比传统数据库，它可以减少90%的人工工作量，而且由 于其采用高数据压缩，在数据库许可和存储等方面的开支也可以减少一半。 <img src="http://articles.csdn.net/uploads/allimg/111118/093233AS-5.jpg" alt=""> Knowledge Grid查询引擎 InfoBright最新的4.0版本产品，新增了一个DomainExpert的功能。企业用户可以借此忽略不断重复的那些数据，比如邮箱地址 、URL和IP地址。与此同时，公司还可以增加与呼叫记录、业务交易或者地理位置信息相关的数据。Kowledge Grid查询引擎则可以帮助过滤那些静态数据而只关注那些变化的数据。也就是说，它可以帮助节省数据查询的时间，因为那些无关的数据无需进行解压缩和筛选。 6.Kognitio提供三倍速度和虚拟多维数据集 Kognitio是一家本身不生产硬件产品的数据库厂商，它看到了客户对快速部署的广泛兴趣和市场需求，推出了在惠普、IBM硬件产品上预配置有WX2数据库的Lakes、Rivers和Rapids解决方案。 Lakes能够以低成本、10TB数据存储和每个模块48个运算核心提供大容量存储服务。电信或金融服务公司，可以使用这种配置来扫描大量的分支结构的各种信息记录。Rivers则提供了容量和速度之间的平衡，预配置为2.5TB存储容量，它的每个模块拥有48个运算核心。而追求查询性能的Rapids，其预配置提供有96个运算核心，每个模块仅仅为1.5TB。该产品方案主要针对金融公司在算法交易或者其他高性能要求方面的需求。 <img src="http://articles.csdn.net/uploads/allimg/111118/0932332I8-6.jpg" alt=""> Kognitio基于内存运算的数据仓库和数据分析 今年， Kognitio新增了一个虚拟化OLAP风格的Pablo分析引擎。它提供了灵活的、为企业用户进行分析的解决方案。用户可升级选用WX2构建一个虚拟多维数据集。因此，WX2数据库中任何一个维度的数据都可在内存中用于快速分析。这种分析的前端接口是我们常见的Microsoft Excel。 7.微软SQL Server新增PDW功能 今年年初微软发布的SQL Server R2 Parallel Data Warehouse（PDW，并行数据仓库），一改以往SQL Server部署时间需要花 费两年半时间的历史，它可以帮助客户扩展部署数百TB级别数据的分析解决方案。支持这一产品的包括有合作伙伴惠普的硬件平台。发布之初，虽然微软官网提供有让利折扣，但PDW售价仍超过13000美元/TB（用户和硬件访问量）。 <img src="http://articles.csdn.net/uploads/allimg/111118/0932334396-7.jpg" alt=""> SQL Server PDW 和很多产品一样，PDW使用了大规模并行处理来支持高扩展性，但微软进入这一市场实属“姗姗来迟”，而且在一定程度上说，数据仓库分析和内存分析计算市场落下了后腿。目前，微软寄希望于其整体数据库平台在市场上带来的差异化竞争力。这意味着，所有沿袭了基于微软平台的数据和数据管理，将被广泛应用在信息集成领域——Reporting and Analysis Services，而这一切都基于SQL Server数据库。 微软在今年10月12日通过推出Apache Hadoop和相关的SQL Azure Hadoop服务，宣布进入大数据领域。Azure服务将在2011年底亮相，而相应的本地配套软件要在明年上半年推出，现在也不清楚微软是否会与其他硬件合作伙伴或者相关大数据设备厂商合作。 8.甲骨文讲述Engineered Systems的故事 甲骨文表示，Exadata（图中左侧）是迄今以来发布的产品中最为成功的产品，自从2008年推出以来，已经拥有超过1000名客户。而engineered system使得甲骨文11g数据库，可以支持基于X86的数据处理和磁盘存储层，其闪存缓存也使得可以实现超快速查询处理。 它既可应用在任意事务环境中，也可以应用在数据仓库（但不能同时进行）。Exadata的混合柱状压缩能够实现列存储数据库的某些高效率特点，提供高达10:1的压缩比，而大部分行存储数据库的平均压缩比为4:1。 甲骨文在9月通过宣布Oracle SuperCluster（图中右侧），扩展了engineered systems产品家族。它采用了最新的Sun Sparc T-4芯片。SuperCluster支持全机架/半机架配置，而且用户可以在半机架容量基础上进行扩容。满额配置提供有1200个CPU线程，4TB内存，97TB至198TB磁盘存储，8.66TB闪存。 <img src="http://articles.csdn.net/uploads/allimg/111118/093233N43-8.jpg" alt=""> 甲骨文大数据分析系统设施 甲骨文声称，SuperCluster事务处理和数据仓库性能相比传统服务器架构能分别带来10倍和50倍速度提升。但作为一个专有的Unix机器，甲骨文想通过SuperCluster，在面向x86硬件的数据仓库部署迁移大潮中力挽狂澜。甲骨文的Exadata和Exalogic都基于x86架构而且运行Linux系统。 在十月召开的Oracle OpenWorld中，甲骨文宣布将新增一个分布式pache Hadoop软件和相关的大数据设备。甲骨文也计划推出一个独立的基于开源BerkeleyDB产品的NoSQL。 9.ParAccel大打列存储、MPP和数据库分析组合拳 ParAccel是ParAccel Analytic Database（PADB）的开发厂商——提供快速、选择性查询和列存储数据库，并基于大规模并行处理优势特点的产品。该公式表示，其平台支持一系列针对各种复杂、先进应用的工作负载报告和分析。 <img src="http://articles.csdn.net/uploads/allimg/111118/09323360L-9.jpg" alt=""> ParAccel大数据解决方案 内置的分析算法可以为分析师提供高级数学运算、数据统计、和数据挖掘等各种功能，同时，它还提供一个开放的API，可以扩展数据库的各种数据处理能力和第三方分析应用。 Table functions被用来传送和接收第三方和采用C、C++等编写的定制算法的数据结果。ParAccel与Fuzzy Logix——一家提供各种描述统计学、统计实验模拟和模式识别功能库功能的服务商。此外， Table functions还支持MapReduce和广泛应用在金融服务的700多种分析技术。 10.Sybase推进IQ列存储数据库 SAP旗下的Sybase是列存储数据库管理系统的首批厂商，而且目前仍然是拥有2000多个客户的畅销厂商。今年夏天推出了Sybase IQ 15.3版本，该版本产品能够处理更多数据和更多数据类型，也能胜任更多查询，当然这主要得益于其包含了一个名叫PlexQ 的大规模并行处理功能。 基于MPP大规模并行处理的PlexQ分布式查询平台，通过将任务分散到网格配置中的多台计算机，加速了高度复杂的查询。有报道说，它能提供比现有的IQ部署快12倍的交付能力。 <img src="http://articles.csdn.net/uploads/allimg/111118/112_111118092736_1.jpg" alt=""> Sybase IQ 为了支持不同的分析，15.3版本的产品增加了分布式处理功能，来执行PlexQ网格中跨CPU的查询服务。为了确保实现最快速度的查询，PlexQ包含了一个逻辑服务器——让管理员对PlexQ网格的物理服务器组成虚拟群集，以便优化分析工作负载、用户需求和应用程序。 Sybase IQ和其他大多数的支持MPP功能的产品之间区别主要在于，它采用了全共享的方式。全共享的缺点是CPU会争相访问共享存储（通常是SAN），而这会降低查询性能。不过Sybase坚持认为，从优化查询的角度来说全共享会更加灵活，因为所有的CPU 都会访问所有的数据。所以，我们可以对某个特定的查询尽可能多（或者少）地分配计算资源。 11.Teradata从EDWs跨入大规模分析领域 一旦成为企业级数据仓库（EDW）的宣传者，近年来Teradata就已经放松了扩展Teradata数据库产品家族的步伐。该公司的高性能、高容量产品被广泛采用和复制，因为其中包括了很多企业工作量管理的功能模块，包括虚拟OLAP（三维立体式）分析模型 。 Teradata在数据库分析领域不断推陈出新，但在结构化数据、半结构化数据和大部分非结构化数据领域几乎没有很大成果。这也就是为什么该公司要收购Aster Data——一家提供SQL-MapReduce框架的公司。MapReduce处理拥有广泛的市场需求，因为存在着大量的互联网点击数据、传感数据和社交媒体内容。 <img src="http://articles.csdn.net/uploads/allimg/111118/09323352S-11.jpg" alt=""> Teradata平台产品家族 Teradata日前宣布了一项Aster Data MapReduce产品的计划，它建立在以往产品同样的硬件平台之上，而且在Teradata和Aster Data之间新增了两种集成方法。通过收购，Teradata打破了在数据仓储业被认为最广泛、最具扩展性的界限。 12.1010data提供基于云计算大数据分析 正如标题所说，1010data能够提供基于云计算的大数据分析平台。很大数据库平台供应商提供基于云的沙箱测试和开发环境， 但1010data的管理数据库服务，主要针对将整个工作负载迁移到云的全过程。 该服务支持一种提供“丰富而又高级的内置分析功能”，其中包括有预测分析。其一大卖点是服务包括了数据建模和设计、信息集成和数据转换。 <img src="http://articles.csdn.net/uploads/allimg/111118/093233O63-12.jpg" alt=""> 1010data提供基于云计算大数据分析 其客户包括有对冲基金、全球各大银行、证券交易商，零售商和包装消费品公司。 何谓大数据？ 大数据，也就是国外常说的Big Data。IBM把大数据概括成了三个V，即大量化（Volume）、多样化（Variety）和快速化（Velocity）。这些特点也反映了大数据所潜藏的价值（Value），我们也可以认为，四个V高度概括了大数据的基本特征。 <img src="http://articles.csdn.net/uploads/allimg/111118/0932332604-13.jpg" alt=""> 业界比较一致对大数据的定义是：大数据是指无法在一定时间内用常规软件工具对其内容进行抓取、管理和处理的数据集合。 </td> 
 </tr> 
 </tbody> 
 </table> </td> 
 </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
 <tr> 
 <td> 
 <table> 
 <tbody> 
 <tr> 
 <td>usidc5</td> 
 <td align="right">2012-02-17 16:48</td> 
 </tr> 
 <tr> 
 <td colspan="2">导读：和许多新兴的网站一样，著名的轻博客服务Tumblr在急速发展中面临了系统架构的瓶颈。每天5亿次浏览量，峰值每秒4万次请求，每天3TB新的数据存储，超过1000台服务器，这样的情况下如何保证老系统平稳运行，平稳过渡到新的系统，Tumblr正面临巨大的挑战。近日，HighScalability网站的Todd Hoff采访了该公司的分布式系统工程师Blake Matheny，撰文系统介绍了网站的架构，内容很有价值。我们也非常希望国内的公司和团队多做类似分享，贡献于社区的同时，更能提升自身的江湖地位，对招聘、业务发展都好处多多。欢迎通过@CSDN云计算的微博向我们投稿。 以下为译文的第一部分。第二部分点这里。（括号内小号字为CSDN编辑所注）： Tumblr每月页面浏览量超过150亿次，已经成为火爆的博客社区。用户也许喜欢它的简约、美丽，对用户体验的强烈关注，或是友好而忙碌的沟通方式，总之，它深得人们的喜爱。 每月超过30%的增长当然不可能没有挑战，其中可靠性问题尤为艰巨。每天5亿次浏览量，峰值每秒4万次请求，每天3TB新的数据存储，并运行于超过1000台服务器上，所有这些帮助Tumblr实现巨大的经营规模。 创业公司迈向成功，都要迈过危险的迅速发展期这道门槛。寻找人才，不断改造基础架构，维护旧的架构，同时要面对逐月大增的流量，而且曾经只有4位工程师。这意味着必须艰难地选择应该做什么，不该做什么。这就是Tumblr的状况。好在现在已经有20位工程师了，可以有精力解决问题，并开发一些有意思的解决方案。 Tumblr最开始是非常典型的LAMP应用。目前正在向分布式服务模型演进，该模型基于Scala、HBase、Redis（著名开源K-V存储方案）、Kafka（Apache项目，出自LinkedIn的分布式发布-订阅消息系统）、Finagle（由Twitter开源的容错、协议中立的RPC系统），此外还有一个有趣的基于Cell的架构，用来支持Dashboard（CSDN注：Tumblr富有特色的用户界面，类似于微博的时间轴）。 Tumblr目前的最大问题是如何改造为一个大规模网站。系统架构正在从LAMP演进为最先进的技术组合，同时团队也要从小的创业型发展为全副武装、随时待命的正规开发团队，不断创造出新的功能和基础设施。下面就是Blake Matheny对Tumblr系统架构情况的介绍。 网站地址 http://www.tumblr.com/ 主要数据 &nbsp;&nbsp;&nbsp;&nbsp;每天5亿次PV（页面访问量） &nbsp;&nbsp;&nbsp;&nbsp;每月超过150亿PV &nbsp;&nbsp;&nbsp;&nbsp;约20名工程师 &nbsp;&nbsp;&nbsp;&nbsp;峰值请求每秒近4万次 &nbsp;&nbsp;&nbsp;&nbsp;每天超过1TB数据进入Hadoop集群 &nbsp;&nbsp;&nbsp;&nbsp;MySQL/HBase/Redis/memcache每天生成若干TB数据 &nbsp;&nbsp;&nbsp;&nbsp;每月增长30% &nbsp;&nbsp;&nbsp;&nbsp;近1000硬件节点用于生产环境 &nbsp;&nbsp;&nbsp;&nbsp;平均每位工程师每月负责数以亿计的页面访问 &nbsp;&nbsp;&nbsp;&nbsp;每天上传大约50GB的文章，每天跟帖更新数据大约2.7TB（CSDN注：这两个数据的比例看上去不太合理，据Tumblr数据科学家Adam Laiacano在Twitter上解释，前一个数据应该指的是文章的文本内容和元数据，不包括存储在S3上的多媒体内容） 软件环境 &nbsp;&nbsp;&nbsp;&nbsp;开发使用OS X，生产环境使用Linux（CentOS/Scientific） &nbsp;&nbsp;&nbsp;&nbsp;Apache &nbsp;&nbsp;&nbsp;&nbsp;PHP, Scala, Ruby &nbsp;&nbsp;&nbsp;&nbsp;Redis, HBase, MySQL &nbsp;&nbsp;&nbsp;&nbsp;Varnish, HAProxy, nginx &nbsp;&nbsp;&nbsp;&nbsp;memcache, Gearman（支持多语言的任务分发应用框架）, Kafka, Kestrel（Twitter开源的分布式消息队列系统）, Finagle &nbsp;&nbsp;&nbsp;&nbsp;Thrift, HTTP &nbsp;&nbsp;&nbsp;&nbsp;Func——一个安全、支持脚本的远程控制框架和API &nbsp;&nbsp;&nbsp;&nbsp;Git, Capistrano（多服务器脚本部署工具）, Puppet, Jenkins 硬件环境 &nbsp;&nbsp;&nbsp;&nbsp;500台Web服务器 &nbsp;&nbsp;&nbsp;&nbsp;200台数据库服务器（47 pool，20 shard） &nbsp;&nbsp;&nbsp;&nbsp;30台memcache服务器 &nbsp;&nbsp;&nbsp;&nbsp;22台Redis服务器 &nbsp;&nbsp;&nbsp;&nbsp;15台Varnish服务器 &nbsp;&nbsp;&nbsp;&nbsp;25台HAproxy节点 &nbsp;&nbsp;&nbsp;&nbsp;8台nginx服务器 &nbsp;&nbsp;&nbsp;&nbsp;14台工作队列服务器（Kestrel + Gearman） 架构 &nbsp;&nbsp;&nbsp;&nbsp;1. 相对其他社交网站而言，Tumblr有其独特的使用模式： &nbsp;&nbsp;&nbsp;&nbsp;每天有超过5千万篇文章更新，平均每篇文章的跟帖又数以百计。用户一般只有数百个粉丝。这与其他社会化网站里少数用户有几百万粉丝非常不同，使得Tumblr的扩展性极具挑战性。 &nbsp;&nbsp;&nbsp;&nbsp;按用户使用时间衡量，Tumblr已经是排名第二的社会化网站。内容的吸引力很强，有很多图片和视频，文章往往不短，一般也不会太长，但允许写得很长。文章内容往往比较深入，用户会花费更长的时间来阅读。 &nbsp;&nbsp;&nbsp;&nbsp;用户与其他用户建立联系后，可能会在Dashboard上往回翻几百页逐篇阅读，这与其他网站基本上只是部分信息流不同。 &nbsp;&nbsp;&nbsp;&nbsp;用户的数量庞大，用户的平均到达范围更广，用户较频繁的发帖，这些都意味着有巨量的更新需要处理。 &nbsp;&nbsp;&nbsp;&nbsp;2. Tumblr目前运行在一个托管数据中心中，已在考虑地域上的分布性。 &nbsp;&nbsp;&nbsp;&nbsp;3. Tumblr作为一个平台，由两个组件构成：公共Tumblelogs和Dashboard &nbsp;&nbsp;&nbsp;&nbsp;公共Tumblelogs与博客类似（此句请Tumblr用户校正），并非动态，易于缓存 &nbsp;&nbsp;&nbsp;&nbsp;Dashboard是类似于Twitter的时间轴,用户由此可以看到自己关注的所有用户的实时更新。与博客的扩展性不同，缓存作用不大，因为每次请求都不同，尤其是活跃的关注者。而且需要实时而且一致，文章每天仅更新50GB，跟帖每天更新2.7TB，所有的多媒体数据都存储在S3上面。 &nbsp;&nbsp;&nbsp;&nbsp;大多数用户以Tumblr作为内容浏览工具，每天浏览超过5亿个页面，70%的浏览来自Dashboard。 &nbsp;&nbsp;&nbsp;&nbsp;Dashboard的可用性已经不错，但Tumblelog一直不够好，因为基础设施是老的，而且很难迁移。由于人手不足，一时半会儿还顾不上。 老的架构 Tumblr最开始是托管在Rackspace上的，每个自定义域名的博客都有一个A记录。当2007年Rackspace无法满足其发展速度不得不迁移时，大量的用户都需要同时迁移。所以他们不得不将自定义域名保留在Rackspace，然后再使用HAProxy和Varnish路由到新的数据中心。类似这样的遗留问题很多。 开始的架构演进是典型的LAMP路线： 最初用PHP开发，几乎所有程序员都用PHP 最初是三台服务器：一台Web，一台数据库，一台PHP 为了扩展，开始使用memcache，然后引入前端cache，然后在cache前再加HAProxy，然后是MySQL sharding（非常奏效） 采用“在单台服务器上榨出一切”的方式。过去一年已经用C开发了两个后端服务：ID生成程序和Staircar（用Redis支持Dashboard通知） Dashboard采用了“扩散-收集”方式。当用户访问Dashboard时将显示事件，来自所关注的用户的事件是通过拉然后显示的。这样支撑了6个月。由于数据是按时间排序的，因此sharding模式不太管用。 新的架构 由于招人和开发速度等原因，改为以JVM为中心。目标是将一切从PHP应用改为服务，使应用变成请求鉴别、呈现等诸多服务之上的薄层。 这其中，非常重要的是选用了Scala和Finagle。 在团队内部有很多人具备Ruby和PHP经验，所以Scala很有吸引力。 Finagle是选择Scala的重要因素之一。这个来自Twitter的库可以解决大多数分布式问题，比如分布式跟踪、服务发现、服务注册等。 转到JVM上之后，Finagle提供了团队所需的所有基本功能（Thrift, ZooKeeper等），无需再开发许多网络代码，另外，团队成员认识该项目的一些开发者。 Foursquare和Twitter都在用Finagle，Meetup也在用Scala。 应用接口与Thrift类似，性能极佳。 团队本来很喜欢Netty（Java异步网络应用框架，2月4日刚刚发布3.3.1最终版），但不想用Java，Scala是不错的选择。 选择Finagle是因为它很酷，还认识几个开发者。 之所以没有选择Node.js，是因为以JVM为基础更容易扩展。Node的发展为时尚短，缺乏标准、最佳实践以及大量久经测试的代码。而用Scala的话，可以使用所有Java代码。虽然其中并没有多少可扩展的东西，也无法解决5毫秒响应时间、49秒HA、4万每秒请求甚至有时每秒40万次请求的问题。但是，Java的生态链要大得多，有很多资源可以利用。 内部服务从C/libevent为基础正在转向Scala/Finagle为基础。 开始采用新的NoSQL存储方案如HBase和Redis。但大量数据仍然存储在大量分区的MySQL架构中，并没有用HBase代替MySQL。HBase主要支持短地址生产程序（数以十亿计）还有历史数据和分析，非常结实。此外，HBase也用于高写入需求场景，比如Dashboard刷新时一秒上百万的写入。之所以还没有替换HBase，是因为不能冒业务上风险，目前还是依靠人来负责更保险，先在一些小的、不那么关键的项目中应用，以获得经验。MySQL和时间序列数据sharding（分片）的问题在于，总有一个分片太热。另外，由于要在slave上插入并发，也会遇到读复制延迟问题。 此外，还开发了一个公用服务框架： 花了很多时间解决分布式系统管理这个运维问题。 为服务开发了一种Rails scaffolding，内部用模板来启动服务。 所有服务从运维的角度来看都是一样的，所有服务检查统计数据、监控、启动和停止的方式都一样。 工具方面，构建过程围绕SBT（一个Scala构建工具），使用插件和辅助程序管理常见操作，包括在Git里打标签，发布到代码库等等。大多数程序员都不用再操心构建系统的细节了。 200台数据库服务器中，很多是为了提高可用性而设，使用的是常规硬件，但MTBF（平均故障间隔时间）极低。故障时，备用充足。 为了支持PHP应用有6个后端服务，并有一个小组专门开发后端服务。新服务的发布需要两到三周，包括Dashboard通知、Dashboard二级索引、短地址生成、处理透明分片的memcache代理。其中在MySQL分片上耗时很多。虽然在纽约本地非常热，但并没有使用MongoDB，他们认为MySQL的可扩展性足够了。 Gearman用于会长期运行无需人工干预的工作。 可用性是以达到范围（reach）衡量的。用户能够访问自定义域或者Dashboard吗？也会用错误率。 历史上总是解决那些最高优先级的问题，而现在会对故障模式系统地分析和解决，目的是从用户和应用的角度来定成功指标。（后一句原文似乎不全） 最开始Finagle是用于Actor模型的，但是后来放弃了。对于运行后无需人工干预的工作，使用任务队列。而且Twitter的util工具库中有Future实现，服务都是用Future（Scala中的无参数函数，在与函数关联的并行操作没有完成时，会阻塞调用方）实现的。当需要线程池的时候，就将Future传入Future池。一切都提交到Future池进行异步执行。 Scala提倡无共享状态。由于已经在Twitter生产环境中经过测试，Finagle这方面应该是没有问题的。使用Scala和Finagle中的结构需要避免可变状态，不使用长期运行的状态机。状态从数据库中拉出、使用再写回数据库。这样做的好处是，开发人员不需要操心线程和锁。 22台Redis服务器，每台的都有8-32个实例，因此线上同时使用了100多个Redis实例。 Redis主要用于Dashboard通知的后端存储。 所谓通知就是指某个用户like了某篇文章这样的事件。通知会在用户的Dashboard中显示，告诉他其他用户对其内容做了哪些操作。 高写入率使MySQL无法应对。 通知转瞬即逝，所以即使遗漏也不会有严重问题，因此Redis是这一场景的合适选择。 这也给了开发团队了解Redis的机会。 使用中完全没有发现Redis有任何问题，社区也非常棒。 开发了一个基于Scala Futures的Redis接口，该功能现在已经并入了Cell架构。 短地址生成程序使用Redis作为一级Cache，HBase作为永久存储。 Dashboard的二级索引是以Redis为基础开发的。 Redis还用作Gearman的持久存储层，使用Finagle开发的memcache代理。 正在缓慢地从memcache转向Redis。希望最终只用一个cache服务。性能上Redis与memcache相当。 （先到这里吧，敬请期待下篇，包括如何用Kafaka、Scribe、Thrift实现内部活动流，Dashboard的Cell架构，开发流程和经验教训等精彩内容。） 翻译：包研，张志平，刘江；审校：刘江</td> 
 </tr> 
 </tbody> 
 </table> </td> 
 </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
 <tr> 
 <td> 
 <table> 
 <tbody> 
 <tr> 
 <td>usidc5</td> 
 <td align="right">2012-02-21 10:52</td> 
 </tr> 
 <tr> 
 <td colspan="2">如今Apache Hadoop已成为大数据行业发展背后的驱动力。Hive和Pig等技术也经常被提到，但是他们都有什么功能，为什么会需要奇怪的名字（如Oozie，ZooKeeper、Flume）。 Hadoop带来了廉价的处理大数据（大数据的数据容量通常是10-100GB或更多，同时数据种类多种多样，包括结构化、非结构化等）的能力。但这与之前有什么不同？ 现今企业数据仓库和关系型数据库擅长处理结构化数据，并且可以存储大量的数据。但成本上有些昂贵。这种对数据的要求限制了可处理的数据种类，同时这种惯性所带的缺点还影响到数据仓库在面对海量异构数据时对于敏捷的探索。这通常意味着有价值的数据源在组织内从未被挖掘。这就是Hadoop与传统数据处理方式最大的不同。 本文就重点探讨了Hadoop系统的组成部分，并解释各个组成部分的功能。 MapReduce——Hadoop的核心 <img src="http://articles.csdn.net/uploads/allimg/120220/79_120220163456_1.jpg" alt=""> Google的网络搜索引擎在得益于算法发挥作用的同时，MapReduce在后台发挥了极大的作用。MapReduce框架成为当今大数据处理背后的最具影响力的“发动机”。除了Hadoop，你还会在MapReduce上发现MPP（Sybase IQ推出了列示数据库）和NoSQL（如Vertica和MongoDB）。 MapReduce的重要创新是当处理一个大数据集查询时会将其任务分解并在运行的多个节点中处理。当数据量很大时就无法在一台服务器上解决问题，此时分布式计算优势就体现出来。将这种技术与Linux服务器结合可获得性价比极高的替代大规模计算阵列的方法。Yahoo在2006年看到了Hadoop未来的潜力，并邀请Hadoop创始人Doug Cutting着手发展Hadoop技术，在2008年Hadoop已经形成一定的规模。Hadoop项目再从初期发展的成熟的过程中同时吸纳了一些其他的组件，以便进一步提高自身的易用性和功能。 HDFS和MapReduce <img src="http://articles.csdn.net/uploads/allimg/120220/79_120220163657_1.png" alt=""> 以上我们讨论了MapReduce将任务分发到多个服务器上处理大数据的能力。而对于分布式计算，每个服务器必须具备对数据的访问能力，这就是HDFS（Hadoop Distributed File System）所起到的作用。 HDFS与MapReduce的结合是强大的。在处理大数据的过程中，当Hadoop集群中的服务器出现错误时，整个计算过程并不会终止。同时HFDS可保障在整个集群中发生故障错误时的数据冗余。当计算完成时将结果写入HFDS的一个节点之中。HDFS对存储的数据格式并无苛刻的要求，数据可以是非结构化或其它类别。相反关系数据库在存储数据之前需要将数据结构化并定义架构。 开发人员编写代码责任是使数据有意义。Hadoop MapReduce级的编程利用Java APIs，并可手动加载数据文件到HDFS之中。 Pig和Hive <img src="http://articles.csdn.net/uploads/allimg/120220/79_120220163944_1.png" alt=""> 对于开发人员，直接使用Java APIs可能是乏味或容易出错的，同时也限制了Java程序员在Hadoop上编程的运用灵活性。于是Hadoop提供了两个解决方案，使得Hadoop编程变得更加容易。 •Pig是一种编程语言，它简化了Hadoop常见的工作任务。Pig可加载数据、表达转换数据以及存储最终结果。Pig内置的操作使得半结构化数据变得有意义（如日志文件）。同时Pig可扩展使用Java中添加的自定义数据类型并支持数据转换。 •Hive在Hadoop中扮演数据仓库的角色。Hive添加数据的结构在HDFS（hive superimposes structure on data in HDFS），并允许使用类似于SQL语法进行数据查询。与Pig一样，Hive的核心功能是可扩展的。 Pig和Hive总是令人困惑的。Hive更适合于数据仓库的任务，Hive主要用于静态的结构以及需要经常分析的工作。Hive与SQL相似促使其成为Hadoop与其他BI工具结合的理想交集。Pig赋予开发人员在大数据集领域更多的灵活性，并允许开发简洁的脚本用于转换数据流以便嵌入到较大的应用程序。Pig相比Hive相对轻量，它主要的优势是相比于直接使用Hadoop Java APIs可大幅削减代码量。正因为如此，Pig仍然是吸引大量的软件开发人员。 改善数据访问：HBase、Sqoop以及Flume <img src="http://articles.csdn.net/uploads/allimg/120220/79_120220164225_1.png" width="700" alt=""> Hadoop核心还是一套批处理系统，数据加载进HDFS、处理然后检索。对于计算这或多或少有些倒退，但通常互动和随机存取数据是有必要的。HBase作为面向列的数据库运行在HDFS之上。HBase以Google BigTable为蓝本。项目的目标就是快速在主机内数十亿行数据中定位所需的数据并访问它。HBase利用MapReduce来处理内部的海量数据。同时Hive和Pig都可以与HBase组合使用，Hive和Pig还为HBase提供了高层语言支持，使得在HBase上进行数据统计处理变的非常简单。 但为了授权随机存储数据，HBase也做出了一些限制：例如Hive与HBase的性能比原生在HDFS之上的Hive要慢4-5倍。同时HBase大约可存储PB级的数据，与之相比HDFS的容量限制达到30PB。HBase不适合用于ad-hoc分析，HBase更适合整合大数据作为大型应用的一部分，包括日志、计算以及时间序列数据。 获取数据与输出数据 Sqoop和Flume可改进数据的互操作性和其余部分。Sqoop功能主要是从关系数据库导入数据到Hadoop，并可直接导入到HFDS或Hive。而Flume设计旨在直接将流数据或日志数据导入HDFS。 Hive具备的友好SQL查询是与繁多数据库的理想结合点，数据库工具通过JDBC或ODBC数据库驱动程序连接。 负责协调工作流程的ZooKeeper和Oozie <img src="http://articles.csdn.net/uploads/allimg/120220/79_120220165708_1.jpg" alt=""> 随着越来越多的项目加入Hadoop大家庭并成为集群系统运作的一部分，大数据处理系统需要负责协调工作的的成员。随着计算节点的增多，集群成员需要彼此同步并了解去哪里访问服务和如何配置，ZooKeeper正是为此而生的。 而在Hadoop执行的任务有时候需要将多个Map/Reduce作业连接到一起，它们之间或许批次依赖。Oozie组件提供管理工作流程和依赖的功能，并无需开发人员编写定制的解决方案。 Ambari是最新加入Hadoop的项目，Ambari项目旨在将监控和管理等核心功能加入Hadoop项目。Ambari可帮助系统管理员部署和配置Hadoop，升级集群以及监控服务。还可通过API集成与其他的系统管理工具。 Apache Whirr是一套运行于云服务的类库（包括Hadoop），可提供高度的互补性。Whirr现今相对中立，当前支持Amazon EC2和Rackspace服务。 机器学习：Mahout <img src="http://articles.csdn.net/uploads/allimg/120220/79_120220165930_1.jpg" alt=""> 各类组织需求的不同导致相关的数据形形色色，对这些数据的分析也需要多样化的方法。Mahout提供一些可扩展的机器学习领域经典算法的实现，旨在帮助开发人员更加方便快捷地创建智能应用程序。Mahout包含许多实现，包括集群、分类、推荐过滤、频繁子项挖掘。 使用Hadoop 通常情况下，Hadoop应用于分布式环境。就像之前Linux的状况一样，厂商集成和测试Apache Hadoop生态系统的组件，并添加自己的工具和管理功能。（李智/编译）</td> 
 </tr> 
 </tbody> 
 </table> </td> 
 </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
 <tr> 
 <td> 
 <table> 
 <tbody> 
 <tr> 
 <td>usidc5</td> 
 <td align="right">2012-03-22 16:54</td> 
 </tr> 
 <tr> 
 <td colspan="2"> 
 <div> 
 越来越多的应用涉及到大数据，不幸的是所有大数据的属性，包括数量，速度，多样性等等都是描述了数据库不断增长的复杂性。那么大数据给我们带来了什么好处呢？大数据最大的好处在于能够让我们从这些数据中分析出很多智能的，深入的，有价值的信息。 
 </div> 
 <div> 
 下面我总结了分析大数据的5个方面。 
 </div> 1. Analytic Visualizations（可视化分析） 
 <div> 
 不管是对数据分析专家还是普通用户，数据可视化是数据分析工具最基本的要求。可视化可以直观的展示数据，让数据自己说话，让观众听到结果。 
 </div> 2. Data Mining Algorithms（数据挖掘算法） 
 <div> 
 可视化是给人看的，数据挖掘就是给机器看的。集群、分割、孤立点分析还有其他的算法让我们深入数据内部，挖掘价值。这些算法不仅要处理大数据的量，也要处理大数据的速度。 
 </div> 3. Predictive Analytic Capabilities（预测性分析能力） 
 <div> 
 数据挖掘可以让分析员更好的理解数据，而预测性分析可以让分析员根据可视化分析和数据挖掘的结果做出一些预测性的判断。 
 </div> 4. Semantic Engines（语义引擎） 
 <div> 
 我们知道由于非结构化数据的多样性带来了数据分析的新的挑战，我们需要一系列的工具去解析，提取，分析数据。语义引擎需要被设计成能够从“文档”中智能提取信息。 
 </div> 5. Data Quality and Master Data Management（数据质量和数据管理） 
 <div> 
 数据质量和数据管理是一些管理方面的最佳实践。通过标准化的流程和工具对数据进行处理可以保证一个预先定义好的高质量的分析结果。 
 </div> 
 <div> 
 假如大数据真的是下一个重要的技术革新的话，我们最好把精力关注在大数据能给我们带来的好处，而不仅仅是挑战。 
 </div> </td> 
 </tr> 
 </tbody> 
 </table> </td> 
 </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
 <tr> 
 <td> 
 <table> 
 <tbody> 
 <tr> 
 <td>usidc5</td> 
 <td align="right">2012-03-22 19:53</td> 
 </tr> 
 <tr> 
 <td colspan="2">一、什么是Bloom Filter &nbsp;&nbsp;&nbsp;&nbsp;Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。 &nbsp;&nbsp;&nbsp;&nbsp;有人可能想知道它的中文叫法，倒是有被译作称布隆过滤器。该不该译，译的是否恰当，由诸君品之。下文之中，如果有诸多公式不慎理解，也无碍，只作稍稍了解即可。 1.1、集合表示和元素查询 
 <div> 
 
 </div> 
 <div> 
 
 </div> &nbsp;&nbsp;&nbsp;&nbsp;下面我们具体来看Bloom Filter是如何用位数组表示集合的。初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0。 
 <div> 
 <img src="https://p-blog.csdn.net/images/p_blog_csdn_net/jiaomeng/275417/o_bf1.jpg" alt=""> 
 </div> &nbsp;&nbsp;&nbsp;&nbsp;为了表达S={x1, x2,…,xn}这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1（1≤i≤k）。注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位，即第二个“1“处）。&nbsp;&nbsp; 
 <div> 
 <img src="https://p-blog.csdn.net/images/p_blog_csdn_net/jiaomeng/275417/o_bf2.jpg" alt=""> 
 </div> &nbsp;&nbsp;&nbsp;&nbsp;在判断y是否属于这个集合时，我们对y应用k次哈希函数，如果所有hi(y)的位置都是1（1≤i≤k），那么我们就认为y是集合中的元素，否则就认为y不是集合中的元素。下图中y1就不是集合中的元素（因为y1有一处指向了“0”位）。y2或者属于这个集合，或者刚好是一个false positive。 
 <div> 
 <img src="https://p-blog.csdn.net/images/p_blog_csdn_net/jiaomeng/275417/o_bf3.jpg" alt=""> 
 </div> 
 <div> 
 
 </div> 
 <div> 
 
 </div> 1.2、错误率估计 
 <div> 
 
 </div> 
 <div> 
 
 </div> &nbsp;&nbsp;&nbsp;&nbsp;前面我们已经提到了，Bloom Filter在判断一个元素是否属于它表示的集合时会有一定的错误率（false positive rate），下面我们就来估计错误率的大小。在估计之前为了简化模型，我们假设kn&lt;m且各个哈希函数是完全随机的。当集合S={x1, x2,…,xn}的所有元素都被k个哈希函数映射到m位的位数组中时，这个位数组中某一位还是0的概率是： 
 <div> 
 <img src="https://p-blog.csdn.net/images/p_blog_csdn_net/jiaomeng/275417/o_bf4.jpg" alt=""> 
 </div> &nbsp;&nbsp;&nbsp;&nbsp;其中1/m表示任意一个哈希函数选中这一位的概率（前提是哈希函数是完全随机的），(1-1/m)表示哈希一次没有选中这一位的概率。要把S完全映射到位数组中，需要做kn次哈希。某一位还是0意味着kn次哈希都没有选中它，因此这个概率就是（1-1/m）的kn次方。令p = e-kn/m是为了简化运算，这里用到了计算e时常用的近似： 
 <div> 
 <img src="https://p-blog.csdn.net/images/p_blog_csdn_net/jiaomeng/275417/o_bf16.JPG" alt=""> 
 </div> 
 <div> 
 
 </div> 令ρ为位数组中0的比例，则ρ的数学期望E(ρ)= p’。在ρ已知的情况下，要求的错误率（false positive rate）为： 
 <div> 
 <img src="https://p-blog.csdn.net/images/p_blog_csdn_net/jiaomeng/275417/o_bf5.jpg" alt=""> 
 </div> (1-ρ)为位数组中1的比例，(1-ρ)k就表示k次哈希都刚好选中1的区域，即false positive rate。上式中第二步近似在前面已经提到了，现在来看第一步近似。p’只是ρ的数学期望，在实际中ρ的值有可能偏离它的数学期望值。M. Mitzenmacher已经证明[2] ，位数组中0的比例非常集中地分布在它的数学期望值的附近。因此，第一步的近似得以成立。分别将p和p’代入上式中，得： &nbsp;&nbsp; 
 <div> 
 <img src="https://p-blog.csdn.net/images/p_blog_csdn_net/jiaomeng/275417/o_bf6.jpg" alt=""> 
 </div> 
 <div> 
 <img src="https://p-blog.csdn.net/images/p_blog_csdn_net/jiaomeng/275417/o_bf7.jpg" alt=""> 
 </div> 相比p’和f’，使用p和f通常在分析中更为方便。 
 <div> 
 
 </div> 
 <div> 
 
 </div> 1.3、最优的哈希函数个数 
 <div> 
 
 </div> 
 <div> 
 
 </div> &nbsp;&nbsp;&nbsp;&nbsp;既然Bloom Filter要靠多个哈希函数将集合映射到位数组中，那么应该选择几个哈希函数才能使元素查询时的错误率降到最低呢？这里有两个互斥的理由：如果哈希函数的个数多，那么在对一个不属于集合的元素进行查询时得到0的概率就大；但另一方面，如果哈希函数的个数少，那么位数组中的0就多。为了得到最优的哈希函数个数，我们需要根据上一小节中的错误率公式进行计算。 &nbsp;&nbsp;&nbsp;&nbsp;先用p和f进行计算。注意到f = exp(k ln(1 − e−kn/m))，我们令g = k ln(1 − e−kn/m)，只要让g取到最小，f自然也取到最小。由于p = e-kn/m，我们可以将g写成 
 <div> 
 <img src="https://p-blog.csdn.net/images/p_blog_csdn_net/jiaomeng/275417/o_bf8.jpg" alt=""> 
 </div> &nbsp;&nbsp;&nbsp;&nbsp;根据对称性法则可以很容易看出当p = 1/2，也就是k = ln2· (m/n)时，g取得最小值。在这种情况下，最小错误率f等于(1/2)k≈ (0.6185)m/n。另外，注意到p是位数组中某一位仍是0的概率，所以p = 1/2对应着位数组中0和1各一半。换句话说，要想保持错误率低，最好让位数组有一半还空着。 &nbsp;&nbsp;&nbsp;&nbsp;需要强调的一点是，p = 1/2时错误率最小这个结果并不依赖于近似值p和f。同样对于f’ = exp(k ln(1 − (1 − 1/m)kn))，g’ = k ln(1 − (1 − 1/m)kn)，p’ = (1 − 1/m)kn，我们可以将g’写成 
 <div> 
 <img src="https://p-blog.csdn.net/images/p_blog_csdn_net/jiaomeng/275417/o_bf9.jpg" alt=""> 
 </div> 同样根据对称性法则可以得到当p’ = 1/2时，g’取得最小值。 
 <div> 
 
 </div> 
 <div> 
 
 </div> 1.4、位数组的大小 
 <div> 
 
 </div> 
 <div> 
 
 </div> &nbsp;&nbsp;&nbsp;&nbsp;下面我们来看看，在不超过一定错误率的情况下，Bloom Filter至少需要多少位才能表示全集中任意n个元素的集合。假设全集中共有u个元素，允许的最大错误率为є，下面我们来求位数组的位数m。 &nbsp;&nbsp;&nbsp;&nbsp;假设X为全集中任取n个元素的集合，F(X)是表示X的位数组。那么对于集合X中任意一个元素x，在s = F(X)中查询x都能得到肯定的结果，即s能够接受x。显然，由于Bloom Filter引入了错误，s能够接受的不仅仅是X中的元素，它还能够є (u - n)个false positive。因此，对于一个确定的位数组来说，它能够接受总共n + є (u - n)个元素。在n + є (u - n)个元素中，s真正表示的只有其中n个，所以一个确定的位数组可以表示 
 <div> 
 <img src="https://p-blog.csdn.net/images/p_blog_csdn_net/jiaomeng/275417/o_bf10.jpg" alt=""> 
 </div> 个集合。m位的位数组共有2m个不同的组合，进而可以推出，m位的位数组可以表示 &nbsp;&nbsp; 
 <div> 
 <img src="https://p-blog.csdn.net/images/p_blog_csdn_net/jiaomeng/275417/o_bf11.jpg" alt=""> 
 </div> 个集合。全集中n个元素的集合总共有 &nbsp;&nbsp; 
 <div> 
 <img src="https://p-blog.csdn.net/images/p_blog_csdn_net/jiaomeng/275417/o_bf12.jpg" alt=""> 
 </div> 个，因此要让m位的位数组能够表示所有n个元素的集合，必须有 &nbsp;&nbsp; 
 <div> 
 <img src="https://p-blog.csdn.net/images/p_blog_csdn_net/jiaomeng/275417/o_bf13.jpg" alt=""> 
 </div> 即： &nbsp;&nbsp; 
 <div> 
 <img src="https://p-blog.csdn.net/images/p_blog_csdn_net/jiaomeng/275417/o_bf14.jpg" alt=""> 
 </div> 上式中的近似前提是n和єu相比很小，这也是实际情况中常常发生的。根据上式，我们得出结论：在错误率不大于є的情况下，m至少要等于n log2(1/є)才能表示任意n个元素的集合。 上一小节中我们曾算出当k = ln2· (m/n)时错误率f最小，这时f = (1/2)k= (1/2)mln2 / n。现在令f≤є，可以推出 
 <div> 
 <img src="https://p-blog.csdn.net/images/p_blog_csdn_net/jiaomeng/275417/o_bf15.jpg" alt=""> 
 </div> 这个结果比前面我们算得的下界n log2(1/є)大了log2e≈ 1.44倍。这说明在哈希函数的个数取到最优时，要让错误率不超过є，m至少需要取到最小值的1.44倍。 
 <div> 
 
 </div> 
 <div> 
 
 </div> 1.5、概括 
 <div> 
 
 </div> 
 <div> 
 
 </div> &nbsp;&nbsp;&nbsp;&nbsp;在计算机科学中，我们常常会碰到时间换空间或者空间换时间的情况，即为了达到某一个方面的最优而牺牲另一个方面。Bloom Filter在时间空间这两个因素之外又引入了另一个因素：错误率。在使用Bloom Filter判断一个元素是否属于某个集合时，会有一定的错误率。也就是说，有可能把不属于这个集合的元素误认为属于这个集合（False Positive），但不会把属于这个集合的元素误认为不属于这个集合（False Negative）。在增加了错误率这个因素之后，Bloom Filter通过允许少量的错误来节省大量的存储空间。 &nbsp;&nbsp;&nbsp;&nbsp;自从Burton Bloom在70年代提出Bloom Filter之后，Bloom Filter就被广泛用于拼写检查和数据库系统中。近一二十年，伴随着网络的普及和发展，Bloom Filter在网络领域获得了新生，各种Bloom Filter变种和新的应用不断出现。可以预见，随着网络应用的不断深入，新的变种和应用将会继续出现，Bloom Filter必将获得更大的发展。 二、适用范围 &nbsp;&nbsp;&nbsp;&nbsp;可以用来实现数据字典，进行数据的判重，或者集合求交集 三、基本原理及要点 
 <div> 
 &nbsp;&nbsp;&nbsp;&nbsp;对于原理来说很简单，位数组+k个独立hash函数。将hash函数对应的值的位数组置1，查找时如果发现所有hash函数对应位都是1说明存在，很明显这 个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter，用一个counter数组代替位数组，就可以支持删除了。 
 </div> 
 <div> 
 
 </div> 
 <div> 
 &nbsp;&nbsp;&nbsp;&nbsp;还有一个比较重要的问题，如 何根据输入元素个数n，确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况 下，m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些，因为还要保证bit数组里至少一半为0，则m应 该&gt;=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。 
 </div> 
 <div> 
 
 </div> 
 <div> 
 举个例子我们假设错误率为0.01，则此时m应大概是n的13倍。这样k大概是8个。 
 </div> 
 <div> 
 
 </div> 
 <div> 
 &nbsp;&nbsp;&nbsp;&nbsp;注意这里m与n的单位不同，m是bit为单位，而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。 
 </div> 
 <div> 
 
 </div> 四、扩展 
 <div> 
 &nbsp;&nbsp;&nbsp;&nbsp;Bloom filter将集合中的元素映射到位数组中，用k（k为哈希函数个数）个映射位是否全1表示元素在不在这个集合中。Counting bloom filter（CBF）将位数组中的每一位扩展为一个counter，从而支持了元素的删除操作。Spectral Bloom Filter（SBF）将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。 
 </div> 
 <div> 
 
 </div> 五、问题实例 
 <div> 
 &nbsp;&nbsp;&nbsp;&nbsp;给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。如果是三个乃至n个文件呢？ 
 </div> 
 <div> 
 
 </div> 
 <div> 
 根据这个问题我们来计算下内存的占用，4G=2^32大概是40亿*8大概是340亿，n=50亿，如果按出错率0.01算需要的大概是650亿个bit。 现在可用的是340亿，相差并不多，这样可能会使出错率上升些。另外如果这些urlip是一一对应的，就可以转换成ip，则大大简单了。 
 </div> </td> 
 </tr> 
 </tbody> 
 </table> </td> 
 </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
 <tr> 
 <td> 
 <table> 
 <tbody> 
 <tr> 
 <td>usidc5</td> 
 <td align="right">2012-03-22 19:54</td> 
 </tr> 
 <tr> 
 <td colspan="2">前言 &nbsp;&nbsp; 一般而言，标题含有“秒杀”，“史上最全/最强”等词汇的往往都脱不了哗众取宠之嫌，但进一步来讲，如果读者读罢此文，却无任何收获，那么，我也甘愿背负这样的罪名，:-)，同时，此文可以看做是对这篇文章：十道海量数据处理面试题与十个方法大总结的一般抽象性总结。 &nbsp;&nbsp;&nbsp;&nbsp;毕竟受文章和理论之限，本文摒弃绝大部分的细节，只谈方法/模式论，且注重用最通俗最直白的语言阐述相关问题。最后，有一点必须强调的是，全文行文是基于面试题的分析基础之上的，具体实践过程中，还是得具体情况具体分析，且场景也远比本文所述的任何一种场景复杂得多。 &nbsp;&nbsp;&nbsp;&nbsp;OK，若有任何问题，欢迎随时不吝赐教。谢谢。 何谓海量数据处理？ &nbsp;&nbsp; 所谓海量数据处理，其实很简单，海量，海量，何谓海量，就是数据量太大，所以导致要么是无法在较短时间内迅速解决，要么是数据太大，导致无法一次性装入内存。 &nbsp;&nbsp;&nbsp;&nbsp;那解决办法呢?针对时间，我们可以采用巧妙的算法搭配合适的数据结构，如Bloom filter/Hash/bit-map/堆/数据库或倒排索引/trie/，针对空间，无非就一个办法：大而化小：分而治之/hash映射，你不是说规模太大嘛，那简单啊，就把规模大化为规模小的，各个击破不就完了嘛。 &nbsp;&nbsp;&nbsp;&nbsp;至于所谓的单机及集群问题，通俗点来讲，单机就是处理装载数据的机器有限(只要考虑cpu，内存，硬盘的数据交互)，而集群，机器有多辆，适合分布式处理，并行计算(更多考虑节点和节点间的数据交互)。 &nbsp;&nbsp;&nbsp;&nbsp;再者，通过本blog内的有关海量数据处理的文章，我们已经大致知道，处理海量数据问题，无非就是： 分而治之/hash映射 + hash统计 + 堆/快速/归并排序； Bloom filter/Bitmap； Trie树/数据库/倒排索引； 外排序； 分布式处理之hadoop/mapreduce。 &nbsp;&nbsp;&nbsp;&nbsp;本文接下来的部分，便针对这5种方法模式结合对应的海量数据处理面试题分别具体阐述。 密匙一、分而治之/hash映射 + hash统计 + 堆/快速/归并排序 1、海量日志数据，提取出某日访问百度次数最多的那个IP。 &nbsp;&nbsp;&nbsp;&nbsp;既然是海量数据处理，那么可想而知，给我们的数据那就一定是海量的。针对这个数据的海量，我们如何着手呢?对的，无非就是分而治之/hash映射 + hash统计 + 堆/快速/归并排序，说白了，就是先映射，而后统计，最后排序： 分而治之/hash映射：针对数据太大，内存受限，智能是：把大文件化成(取模映射)小文件，即16字方针：大而化小，各个击破，缩小规模，逐个解决 hash统计：当大文件转化了小文件，那么我们便可以采用常规的hashmap(ip，value)来进行频率统计。 堆/快速排序：统计完了之后，便进行排序(可采取堆排序)，得到次数最多的IP。 &nbsp;&nbsp; 具体而论，则是： “首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最大的IP中，找出那个频率最大的IP，即为所求。”--十道海量数据处理面试题与十个方法大总结。 &nbsp;&nbsp;&nbsp;&nbsp;但如果数据规模比较小，能一次性装入内存呢?比如下面的这道题，题目中说，虽然有一千万个Query，但是由于重复度比较高，因此事实上只有300万的Query，每个Query255Byte，因此我们可以考虑把他们都放进内存中去，而现在只是需要一个合适的数据结构，在这里，Hash Table绝对是我们优先的选择。OK，请看第2题： 2、搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。 &nbsp;&nbsp;&nbsp;&nbsp;假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。 前面说了，数据比较小，摒弃分而治之/hash映射的方法，直接上hash统计，然后排序。So， hash统计先对这批海量数据预处理(维护一个Key为Query字串，Value为该Query出现次数的HashTable，即hashmap(Query，Value)，每次读取一个Query，如果该字串不在Table中，那么加入该字串，并且将Value值设为1；如果该字串在Table中，那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内用Hash表完成了统计； 堆排序：第二步、借助堆这个数据结构，找出Top K，时间复杂度为N‘logK。即借助堆结构，我们可以在log量级的时间内查找和调整/移动。因此，维护一个K(该题目中是10)大小的小根堆，然后遍历300万的Query，分别和根元素进行对比所以，我们最终的时间复杂度是：O（N） + N'*O（logK），（N为1000万，N’为300万）。 &nbsp;&nbsp;&nbsp;&nbsp;别忘了这篇文章中所述的堆排序思路：“维护k个元素的最小堆，即用容量为k的最小堆存储最先遍历到的k个数，并假设它们即是最大的k个数，建堆费时O（k），并调整堆（费时O（logk））后，有k1&gt;k2&gt;...kmin（kmin设为小顶堆中最小元素）。继续遍历数列，每次遍历一个元素x，与堆顶元素比较，若x&gt;kmin，则更新堆（用时logk），否则不更新堆。这样下来，总费时O（k*logk+（n-k）*logk）=O（n*logk）。此方法得益于在堆中，查找等各项操作时间复杂度均为logk。”--第三章、寻找最小的k个数。 &nbsp;&nbsp;&nbsp;&nbsp;当然，你也可以采用trie树，关键字域存该查询串出现的次数，没有出现为0。最后用10个元素的最小推来对出现频率进行排序。 &nbsp;&nbsp;&nbsp;&nbsp;由上面这两个例题，分而治之 + hash统计 + 堆/快速排序这个套路，我们已经开始有了屡试不爽的感觉。下面，再拿几道再多多验证下。请看第3题： 3、有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。 &nbsp;&nbsp; 又是文件很大，又是内存受限，咋办?还能怎么办呢?无非还是 分而治之/hash映射：顺序读文件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个小文件（记为x0,x1,...x4999）中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M。 hash统计：对每个小文件，采用trie树/hash_map等统计每个文件中出现的词以及相应的频率。 堆/归并排序：取出出现频率最大的100个词（可以用含100个结点的最小堆），并把100个词及相应的频率存入文件，这样又得到了5000个文件。最后就是把这5000个文件进行归并（类似与归并排序）的过程了。 4、有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。 &nbsp;&nbsp; 直接上： hash映射：顺序读取10个文件，按照hash(query)%10的结果将query写入到另外10个文件（记为）中。这样新生成的文件每个的大小大约也1G（假设hash函数是随机的）。 hash统计：找一台内存在2G左右的机器，依次对用hash_map(query, query_count)来统计每个query出现的次数。注：hash_map(query,query_count)是用来统计每个query的出现次数，不是存储他们的值，出现一次，则count+1。 堆/快速/归并排序：利用快速/堆/归并排序按照出现次数进行排序。将排序好的query和对应的query_cout输出到文件中。这样得到了10个排好序的文件（记为）。对这10个文件进行归并排序（内排序与外排序相结合）。 &nbsp;&nbsp;&nbsp;&nbsp; 除此之外，此题还有以下两个方法： &nbsp;&nbsp;&nbsp;&nbsp;方案2：一般query的总量是有限的，只是重复的次数比较多而已，可能对于所有的query，一次性就可以加入到内存了。这样，我们就可以采用trie树/hash_map等直接来统计每个query出现的次数，然后按出现次数做快速/堆/归并排序就可以了。 &nbsp;&nbsp;&nbsp;&nbsp;方案3：与方案1类似，但在做完hash，分成多个文件后，可以交给多个文件来处理，采用分布式的架构来处理（比如MapReduce），最后再进行合并。 5、 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？ &nbsp;&nbsp;&nbsp;&nbsp;可以估计每个文件安的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。 分而治之/hash映射：遍历文件a，对每个url求取，然后根据所取得的值将url分别存储到1000个小文件（记为）中。这样每个小文件的大约为300M。遍历文件b，采取和a相同的方式将url分别存储到1000小文件中（记为）。这样处理后，所有可能相同的url都在对应的小文件（）中，不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。 hash统计：求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。 &nbsp;&nbsp;&nbsp;&nbsp;OK，此第一种方法：分而治之/hash映射 + hash统计 + 堆/快速/归并排序，再看最后三道题，如下： &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;8、怎么在海量数据中找出重复次数最多的一个？ &nbsp;&nbsp;&nbsp;&nbsp;方案1：先做hash，然后求模映射为小文件，求出每个小文件中重复次数最多的一个，并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求（具体参考前面的题）。 9、上千万或上亿数据（有重复），统计其中出现次数最多的钱N个数据。 &nbsp;&nbsp;&nbsp;&nbsp;方案1：上千万或上亿的数据，现在的机器的内存应该能存下。所以考虑采用hash_map/搜索二叉树/红黑树等来进行统计次数。然后就是取出前N个出现次数最多的数据了，可以用第2题提到的堆机制完成。 10、一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。 &nbsp;&nbsp;&nbsp;&nbsp;方案1：这题是考虑时间效率。用trie树统计每个词出现的次数，时间复杂度是O(n*le)（le表示单词的平准长度）。然后是找出出现最频繁的前10个词，可以用堆来实现，前面的题中已经讲到了，时间复杂度是O(n*lg10)。所以总的时间复杂度，是O(n*le)与O(n*lg10)中较大的哪一个。 &nbsp;&nbsp;&nbsp;&nbsp;接下来，咱们来看第二种方法，Bitmap。 密匙二：Bloom filter/Bitmap 关于什么是Bloom filter，请参看此文：海量数据处理之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应该&gt;=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中的最小值来近似表示元素的出现频率。 　　问题实例：给你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，则大大简单了。 &nbsp;&nbsp;&nbsp;&nbsp;同时，上文的第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（注意会有一定的错误率）。 &nbsp;&nbsp;&nbsp;&nbsp;至于什么是Bitmap，请看此文：<a href="http://blog.csdn.net/v_july_v/article/details/6685962" rel="nofollow">http://blog.csdn.net/v_july_v/article/details/6685962</a>。下面关于Bitmap的应用，直接上题，如下第6、7道： 6、在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数。 &nbsp;&nbsp;&nbsp;&nbsp;方案1：采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存2^32 * 2 bit=1 GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。 &nbsp;&nbsp;&nbsp;&nbsp;方案2：也可采用与第1题类似的方法，进行划分小文件的方法。然后在小文件中找出不重复的整数，并排序。然后再进行归并，注意去除重复的元素。 7、腾讯面试题：给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？ &nbsp;&nbsp;&nbsp;&nbsp;方案1：oo，申请512M的内存，一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。 密匙三、Trie树/数据库/倒排索引 Trie树 　　适用范围：数据量大，重复多，但是数据种类小可以放入内存 　　基本原理及要点：实现方式，节点孩子的表示方式 　　扩展：压缩实现。 　　问题实例： 　　1).有10个文件，每个文件1G，每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query的频度排序。 　　2).1000万字符串，其中有些是相同的(重复),需要把重复的全部去掉，保留没有重复的字符串。请问怎么设计和实现？ 　　3).寻找热门查询：查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个，每个不超过255字节。 &nbsp;&nbsp;&nbsp;&nbsp;更多有关Trie树的介绍，请参见此文：从Trie树（字典树）谈到后缀树。 数据库索引 　　适用范围：大数据量的增删改查 　　基本原理及要点：利用数据的设计实现方法，对海量数据的增删改查进行处理。 倒排索引(Inverted index) 　　适用范围：搜索引擎，关键字查询 　　基本原理及要点：为何叫倒排索引？一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。 　以英文为例，下面是要被索引的文本： &nbsp;&nbsp;&nbsp;&nbsp;T0 = "it is what it is" &nbsp;&nbsp;&nbsp;&nbsp;T1 = "what is it" &nbsp;&nbsp;&nbsp;&nbsp;T2 = "it is a banana" 我们就能得到下面的反向文件索引： &nbsp;&nbsp;&nbsp;&nbsp;"a":&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{2} &nbsp;&nbsp;&nbsp;&nbsp;"banana": {2} &nbsp;&nbsp;&nbsp;&nbsp;"is":&nbsp;&nbsp;&nbsp;&nbsp; {0, 1, 2} &nbsp;&nbsp;&nbsp;&nbsp;"it":&nbsp;&nbsp;&nbsp;&nbsp; {0, 1, 2} &nbsp;&nbsp;&nbsp;&nbsp;"what":&nbsp;&nbsp; {0, 1} 　检索的条件"what","is"和"it"将对应集合的交集。 　　正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中，文档占据了中心的位置，每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词，而反向索引则是单词指向了包含它的文档，很容易看到这个反向的关系。 　　扩展： 　　问题实例：文档检索系统，查询那些文件包含了某单词，比如常见的学术论文的关键字搜索。 &nbsp;&nbsp;&nbsp;&nbsp;关于倒排索引的应用，更多请参见：第二十三、四章：杨氏矩阵查找，倒排索引关键词Hash不重复编码实践，及第二十六章：基于给定的文档生成倒排索引的编码与实践。 密匙四、外排序 　　适用范围：大数据的排序，去重 　　基本原理及要点：外排序的归并方法，置换选择败者树原理，最优归并树 　　扩展： 　　问题实例： 　　1).有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词。 　　这个数据具有很明显的特点，词的大小为16个字节，但是内存只有1m做hash有些不够，所以可以用来排序。内存可以当输入缓冲区使用。 &nbsp;&nbsp;&nbsp;&nbsp;关于多路归并算法及外排序的具体应用场景，请参见此文：第十章、如何给10^7个数据量的磁盘文件排序。 密匙五、分布式处理 Mapreduce &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;适用范围：数据量大，但是数据种类小可以放入内存 　　基本原理及要点：将数据交给不同的机器去处理，数据划分，结果归约。 　　扩展： 　　问题实例： 　　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)？ &nbsp;&nbsp;&nbsp;&nbsp;更多具体阐述请参见：从Hadhoop框架与MapReduce模式中谈海量数据处理，及MapReduce技术的初步了解与学习。 参考文献 十道海量数据处理面试题与十个方法大总结； 海量数据处理面试题集锦与Bit-map详解； 十一、从头到尾彻底解析Hash表算法； 海量数据处理之Bloom Filter详解； 从Trie树（字典树）谈到后缀树； 第三章、寻找最小的k个数； 第十章、如何给10^7个数据量的磁盘文件排序； 第二十三、四章：杨氏矩阵查找，倒排索引关键词Hash不重复编码实践； 第二十六章：基于给定的文档生成倒排索引的编码与实践； 从Hadhoop框架与MapReduce模式中谈海量数据处理。 后记 &nbsp;&nbsp;&nbsp;&nbsp;经过上面这么多海量数据处理面试题的轰炸，我们依然可以看出这类问题是有一定的解决方案/模式的，所以，不必将其神化。当然，这类面试题所包含的问题还是比较简单的，若您在这方面有更多实践经验，欢迎随时来信与我不吝分享：<a href="mailto:zhoulei0907@yahoo.cn" rel="nofollow">zhoulei0907@yahoo.cn</a>。 &nbsp;&nbsp;&nbsp;&nbsp;不过，相信你也早就意识到，若单纯论海量数据处理面试题，本blog内的有关海量数据处理面试题的文章已涵盖了你能在网上所找到的70~80%。但有点，必须负责任的敬告大家：无论是这些海量数据处理面试题也好，还是算法也好，7、80%的人不是倒在这两方面，而是倒在基础之上，所以，无论任何时候，基础最重要，没了基础，便什么都不是。最后，推荐国外一面试题网站：<a href="http://www.careercup.com/" rel="nofollow">http://www.careercup.com/</a>。 &nbsp;&nbsp;&nbsp;&nbsp;OK，本文若有任何问题，欢迎随时不吝留言，评论，赐教，谢谢。完。</td> 
 </tr> 
 </tbody> 
 </table> </td> 
 </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
 <tr> 
 <td> 
 <table> 
 <tbody> 
 <tr> 
 <td>usidc5</td> 
 <td align="right">2012-04-10 22:47</td> 
 </tr> 
 <tr> 
 <td colspan="2">大数据，非结构化数据，半结构化数据。数据存在于所有的技术资讯里面。贯穿于绝大部分的组织中；需要全新的手段来保持竞争力；来更好的服务客户；并将产品更快的推向市场。 Gartner预测，企业数据将在五年内增加800%，其中80%是非结构化的。来自团体，社区，以及社交网络的非业务数据会成为这种趋势中的大部分。 根据IBM对1500名CEO的调查，大部分的CEO表示他们组织有大量的数据，但是鲜有人能够将这些数据化为实际行动，制定计划，导致机会的流失。 尤其令人不安的是，公司无法有效的管理从社会媒体以及企业里面的客户信息。一份Coveo最近对100名客户管理人员的调查表明，85%的人认为管理非结构化的内容将决定他们以后可以更有效和高效的服务客户。 洞察力和知识有助于理解数据 组织混淆的数据，信息和知识。数据是无用的，除非与其他数据相结合，以创建信息。知识是人类面临复杂情况下采取行动的能力，集体的知识被称为一个组织最重要的部分。 其实我们每天都在实践管理非结构化数据，只是我们不知道 互联网上的搜索可以提供我们正在寻找的任何信息。由于互联网上的信息大多是均匀的，它并不会很难收集和处理，并且有强大的搜索引擎帮我们做。然而，在企业内部的异构信息环境，增加了信息整合和连接的复杂性，要做到信息的实时，统一，虚拟和现实的集成很难。 重要的是，结构化和非结构化数据必须提供便于人际互动的接口：让员工，客户和合作伙伴意识到这一点，为了探索新思路，新的人际关系和新的方法来拓展业务，所有的这一切归功于释放潜在的知识。并不是取代现有的技术，而是利用所有的系统。</td> 
 </tr> 
 </tbody> 
 </table> </td> 
 </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
 <tr> 
 <td> 
 <table> 
 <tbody> 
 <tr> 
 <td>usidc5</td> 
 <td align="right">2012-04-24 10:51</td> 
 </tr> 
 <tr> 
 <td colspan="2">现今我们已经进入了大数据时代，因为创新的数据管理技术的诞生，使得组织可以对所有的数据类型进行分析。这也使得企业每天都能够发掘出新的商业机会。 随着互联网技术的发展，当今网络中每天都在产生海量的信息，这其中包括半结构化和非结构化的数据。组织可以通过对海量信息的分析了解到他们客户真正需要的以及为什么需要的原因。但新的商业模式的真实成本还尚未被人们充分认识。 数据格式的多样化 <img src="http://articles.csdn.net/uploads/allimg/120423/79_120423172449_1.jpg" width="700" alt=""> 从IT角度来看，信息结构类型大致经历了三次浪潮。必须注意这一点，新的浪潮并没取代旧浪潮，它们仍在不断发展，三种数据结构类型一直存在，只是其中一种结构类型往往主导于其他结构： 结构化信息——这种信息可以在关系数据库中找到，多年来一直主导着IT应用。这是关键任务OLTP系统业务所依赖的信息，另外，还可对结构数据库信息进行排序和查询； 半结构化信息——这是IT的第二次浪潮，包括电子邮件，文字处理文件以及大量保存和发布在网络上的信息。半结构化信息是以内容为基础，可以用于搜索，这也是谷歌存在的理由； 非结构化信息——该信息在本质形式上可认为主要是位映射数据。数据必须处于一种可感知的形式中（诸如可在音频、视频和多媒体文件中被听或被看）。许多大数据都是非结构化的，其庞大规模和复杂性需要高级分析工具来创建或利用一种更易于人们感知和交互的结构。 市场的领导者们对存储的多格式数据进行分析不止获得竞争的优势。通过对数据的分析使得他们可以更深入的洞察客户的行为模式，这直接影响到他们的业务。 两个特定的行业——电信和零售已经在数据仓库解决方案投入巨资。随着时间的推移，电信和零售两大行业通过对累积的大量客户事务和互动数据研究以确定关键的性能指标。例如每年的收入、每个客户通过网络获取促销信息所导致花费以及销售的高峰。 然而随着数据的激增，即使是市场的领导者也无法承受，传统的数据仓库已无法存储和管理PB级规模的原始详细数据。企业往往将数据备份到离线的磁带上，但这并不容易访问。业务的挑战无处不在，例如当圣诞节恰逢星期六时，企业就需要对7年前（恰逢圣诞节也是周六）的数据进行分析以便了解特定的模式。将大量的历史数据导入数据仓库不仅极具挑战性，同时成本也是非常昂贵的。 两大创新促进大数据发展 <img src="http://articles.csdn.net/uploads/allimg/120423/79_120423173554_1.jpg" alt=""> 两个关键因素正在企业级规模大数据管理和分析中发挥作用。首先是网络创新，包括Facebook、Google、Yahoo已开发出一种大规模可扩展的存储和计算架构以管理大数据。Hadoop框架以低成本的硬件处理大型数据集，这使得处理PB级规模数据的成本大幅降低。 其次管理大数据的技术需求已经从不同的市场领域发展为日益增加的需求以及跨越多个部门的独特需求。随着越来越多的终端设备连接成千上万的移动应用，管理PB级规模数据的通信运营商预计数据将会有10-100倍的增长，这也迫使用户向4G或LTE网络转移。智能电网也受到大数据的影响，世界各地的城市都在加入新的“数字化电网”。金融服务机构看到交易和期权数据100%的复合增长，这导致金融机构最少将数据存储7年。 在未来的3到5年，大数据已经成为私人和公共组织的战略关键。事实上，在未来5年预计有50%的大数据项目会在Hadoop框架下运行。 目前的状况是传统的数据仓库的扩展性不佳，同时写入数据速度已经无法跟上数据产生的速度。而专门涉及的数据仓库在处理结构化数据时非常有效，但扩展硬件时的成本较高。 在大数据领域，Hadoop的低成本和高扩展性是其关键因素。例如一个处理PB级规模数据的Hadoop集群（125到250节点）的费用大约为100万美元，而每个节点每年的费用为4000美元。这对于企业级数据仓库的花费（1000万-1亿美元）来说只是一小部分。这样看来Hadoop似乎是一个不错的解决方案。问题是企业如何利用Hadoop并将其作为关键业务的核心技术。然后，现有设施与大数据生态系统的整合的整体经营真正成本的关键。 由于大数据的规模，如Yahoo的Hadoop系统共有50000节点和200PB的数据，管理这些数据需要更多的额外的存储能力。许多Web 2.0组织运行Hadoop完全依赖数据冗余。但如果企业是银行或通信行业就必须遵守基于标准的安全性、灾难恢复性和高可用性。Hadoop发展到今天也面临诸多的问题，面对这些挑战，Hadoop必须引入更复杂的数据管理和技术资源。 大数据时代催生数据科学家 <img src="http://articles.csdn.net/uploads/allimg/120423/79_120423173915_1.jpg" alt=""> 在部署Hadoop处理大数据表面的背后，对开源平台的创新也催生了“数据科学家”这一新兴职业。数据科学家本质上更像是统计学家，他们有能力设计和利用MapReduce框架。Google的Hal Varian表示未来10年数据科学家将变成性感的工作，许多人认为我是在开玩笑，回过头来看，在20世纪90年代谁会猜到计算机工程师会成为性感的工作。 前LinkedIn数据科学家DJ Patil表示数据科学家是具备独特技能的。Bitly首席科学家Hilary Mason表达同样的观点，他认为数据科学家是融合数学、算法，并可从大数据中寻求问题答案的人。而现任LinkedIn首席数据科学家Monica Rogati认为数据科学家是黑客和分析师组成的混合体，他们通过数据发现本质。 纽约时报研发实验室的成员Jake Porway表示数据科学家绝对是罕见的全才。数据科学家除了具备编程的能力外还需将各种来源的数据管理并利用统计学挖掘出蕴藏在内部的信息。 Kaggle总裁兼首席科学家Jeremy Howard认为一个伟大的数据科学家应具备创新、坚韧、好奇、深厚技术这四项素质。具备数据收集、数据改写、可视化、机器学习、计算机编程等技术的数据科学家使数据驱动决策并主导产品。他们更喜欢用数据说话。 MapReduce与现有设施的整合 <img src="http://articles.csdn.net/uploads/allimg/120423/79_120423173621_1.jpg" alt=""> MapReduce是一种处理大型及超大型数据集并生成相关的执行的编程模型。其主要思想是从函数式编程语言里借来的，同时也包含了从矢量编程语言里借来的特性。MapReduce将整个任务分解成成百甚至上千块小任务，然后发送到计算机集群中。 为了整合MapReduce，多数企业需要开发一个基于全新技术的基础架构，而对于技术人员的投资成本将很快超过对基础设施的投资成本。此外，为了充分利用现有的数据仓库和商业智能的基础设施，企业需要将现有的工具和技能与Hadoop加以整合。 大数据带来了巨大的商业利益，但隐形成本和复杂性是现今发展的障碍。Hadoop应进一步朝着提高可靠性和易于使用的方面进行完善。Apache是Hadoop发展的主要贡献者。未来对以下两个方面的的改进将改变易用性和成本。 ●在Hadoop框架下充分利用SQL和现有的BI工具。 ●压缩数据，这不仅会降低对存储需求，还会降低对节点的数量，并简化基础设施。 如果不改善这两个功能，大数据技能学习将需要更多的时间和成本。虽然大数据带来的好处显而易见，但CIO和CTO现在必须重新审视大数据的成本了。（李智/编译）</td> 
 </tr> 
 </tbody> 
 </table> </td> 
 </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
 <tr> 
 <td>usidc5</td> 
 <td align="right">2012-05-29 15:27</td> 
 </tr> 
 <tr> 
 <td colspan="2">美国国家超级计算应用中心(National Center for Supercomputing Applications)正计划推出一个包含380PB磁带存储容量和由17000个SATA驱动器组成的25PB在线磁盘存储的存储基础设施。 这个大规模存储基础设施将用于支持世界上最大的超级计算机之一，被称为Blue Waters。由美国国家科学基金会(NFS)委托制造的Blue Waters预计峰值性能将达到11.5 petaflops，虽然NFS对其的要求是提供1 petaflop的应用程序持续计算能力。 美国伊利诺伊大学运行的NCSA已经与Cray公司签署了一份合同来建设这个超级计算机，该系统将运行一个Lustre并行文件系统，到其后端存储的吞吐量将超过1TB每秒。 Blue Waters项目将创造一个1 petaflop超级计算机来处理现实世界科学和工程应用。其中，这台超级计算机将帮助人类理解宇宙大爆炸后宇宙是如何演化的，帮助预测飓风和龙卷风的形成，并在新材料的设计中在原子水平上发挥重要作用。 这台超级计算机将包含超过235个使用380000个AMD Opteron 6200系列X82处理器的Cray XE6机柜，和超过30个最新推出的Cray XK6超级计算机(拥有3000个NVIDIA CPU)未来版本的机柜。该系统将包含来自19万个内存DIMM的1.5PB聚合内存。 为了支持所有这些计算能力，NCSA使用Cray Sonexion存储系统部署了25PB磁盘存储。Sonexion原本被称为Zyratex存储阵列，该系统通过40Gbps以太网从Extreme Networks提供高达1TBps聚合带宽。 “我们一直努力与网络供应商合作，以确保他们准备好迎接40千兆以太网，”NCSA负责存储和网络工程的高级技术项目经理Michelle Butler表示，“我们并不是第一个使用40Gbps以太网的，但是现在使用这个以太网的人并不多。” Butler表示，使用40Gbit以太网网络的关键是将管道分成多个10Gbps以太网通道的能力，使NCSA将架构分散到多个端口。该以太网将被用于连接75台主机。 Butler表示，NCSA还选择了DataDirect Network的SFA 12K存储阵列提供100GBps存储性能来卸载数据到“近线”磁带库系统。该磁带子系统可扩展到500PB容量。 她表示：“该子系统能够卸载每秒万亿字节的文件系统，所以我们需要一个非常大的磁带基础设施来进行卸载。” <img src="http://articles.csdn.net/uploads/allimg/120528/1I6154G6-0.jpg" alt=""> 正在建设中的Blue Waters超级计算机 在主存储后面是四个Spectra Logic 17-frame T-Finity磁带库，磁带库将拥有366个240MB/sec 的IBM TS1140企业级磁带驱动器。该磁带库将提供高达每小时2.2PB的聚合读/写率。 Butler表示：“我们实际上评估了LTO-5或LTO-6和TS1140，我们并没有指定何种磁带驱动器、何种库或者其他任何东西。我们希望让供应商自由地向我们提供多种解决方案。” Butler表示，NCSA选择IBM磁带驱动器，而没有选择更流行的中级LTO驱动器，因为它们提供优越的性能。TS1140提供240MB每秒的吞吐量，LTO驱动器提供140MB每秒。 在意见请求书中，Butler的团队给存储供应商列出了10到15个要求。除此之外，它们还规定磁带库必须要符合一定面积，不能超过一定电力和冷却要求，并且应该满足某种可靠性和性能目标。 Butler表示，磁带库聚合吞吐量的目标是100GB/sec，目前，大约为89.5GB/sec。 Cray超级计算机通过Mellanox IS5000 InfiniBand交换机和ConnectX InfiniBand适配器连接到磁带库。交换机使用InfiniBand QDR协议，提供高达每个lane 8Gbps吞吐量和高达12个I/O lane。Butler表示，她想要使用更高带宽版本的InfiniBand， FDR，但是Cray的系统不支持。 InfiniBand FDR提供每个lane 13.6 Gbps吞吐量和高达12个I/O lane。 虽然NCSA可以从很多企业级磁盘存储供应商中选择产品用于超级计算机中，Butler及其团队感觉如果所有产品都来自于Cray的话，他们将会得到更好的支持。 “Lustre，如你所知，并不好维护，所以我们想要与特定供应商合作，使用其软件硬件，并有一个设备来进行故障转换等，自2003年以来，我们就一直运行Lustre，”Butler表示，“所以我理解Cray公司试图为我们简化我们的系统。”</td> 
 </tr> 
 </tbody> 
</table>

在过去几年，一种新兴的大型数据存储机制正吞噬大数据存储市场。这种存储解决方案与传统的RDBMS有显著的区别，它们被称之为NoSQL。  
在NoSQL世界中有以下关键的成员，包括  
●Google BigTable、HBase、Hypertable  
●Amazon Dynamo、Voldemort、Cassendra、Riak  
●Redis  
●CouchDB、MongoDB  
而这些解决方案又有一些共同的特点  
●基于键-值存储  
●系统运行在海量的普通机器上  
●数据在经过分区和复制后分布在集群中  
●放宽对数据一致性的要求（因为CAP定理）。  
选择NoSQL的重要标准就是要看CAP（Consistency、Availability和Partition Tolerance），也就是我们所说的一致性、可用性和分区容忍性。但CAP原则要求在分布式系统只能选择一致性、可用性和分区容忍性其中的两项。  
本文旨在提取这些解决方案背后的共同的技术，以便更深入的了解应用程序设计的意义。本文并不会对这些解决方案作比较，也不会建议使用某一款产品。  
**API模型**  
底层的数据模型可以被看作为一个大的Hashtable（键/值存储）  
API访问基本形式：  
get(key)：提取给定键的对应值  
put(key，value) ：新建或更新给定键的对应值  
delete(key)：删除键及其关联值  
在服务器环境利用更高级的API执行用户自定义的函数  
execute(key, operation, parameters) ：调用操作给定键对应的值，值具有特殊数据（例如List、Set、Map等）  
mapreduce(keyList, mapFunc, reduceFunc) ：对范围内的键调用MapReduce  
**机器布局**  
![79_120614164514_1.png][]  
底层基础设施由大量（成百上千）廉价的、普通的、不可靠的机器通过网络组成。每台机器为一个单独的物理节点（PN）。在每个PN软件配置相同，但CPU、内存、硬盘等会有所不同。每个PN根据不同的硬件配置运行不同数目的虚拟节点。  
**数据分区**  
![79_120614164631_1.png][]  
由于整个Hashtable分布在众多VN之中，我们需要一种能够将每个键映射到对应VN的方法。一种行之有效的方法是：partition = key mod (total\_VNs)。这种方案的缺点是当我们改变VN的数量时，现有键的所有权将发生巨大的变化，这导致全部的数据需要重新再分配。所以多数大型存储使用被称为“consistent hashing”的技术将键所有权变更的影响最小化。  
在“consistent hashing”方法中，键空间是有限的，且分布在一个环上。虚拟节点的ID也从相同的键空间中分配。对于任意键，如果从该键沿着环顺时针移动，遇到了第一个虚拟节点就是它的所属节点。当某一节点崩溃时，他所属的所有键都将顺时针的移动到相邻的节点。因此，重新分配键的情况只发生在崩溃节点的相邻节点中，而所有其他的节点仍保持原有的键值。  
**数据复制**  
![79_120614164648_1.png][]  
为了从单个并不可靠的资源来提供更高的可靠性，迫使我们需要复制数据分区。  
复制不仅提高了数据的可靠性，同时将工作负载分布到多个副本还有助于提升性能。  
只读请求可以分发到任何副本，而更新的要求却具有挑战性。因为需要任职协调各个副本的更新。  
**成员变动**  
![79_120614164755_1.png][]  
请注意，虚拟节点可以随时加入和离开而不影响环的运作网络。  
**当心节点加入到网络**  
1.新加入的节点将示意自身的存在，并将其ID通知其他重要的节点。  
2.所有相邻（左边或右边）节点将调整键的所有权以及副本成员的信息，这将通过同步完成。  
3.新加入的节点开始从其相邻的节点并行、异步的批量复制数据。  
4.副本成员的变更异步传播到其他节点  
**当现有节点脱离网络时（例如崩溃）**  
![79_120614164913_1.png][]  
1.崩溃的节点不再回应Gossip消息，因此相邻的节点也会得知此情况。  
2.相邻节点更新成员信息，同时异步复制数据。  
**客户端的一致性**  
一旦我们拥有相同数据的多个副本，就必须考虑如何同步他们，这样在客户端看来数据才能使一致的。  
1.严格的一致性：从语义上看相当只存在一个数据副本，任何更新看上去都是实时发生的。  
2.读取已写内容的一致性：允许客户端立刻看到自身所做的更新，但无法看到其他客户端的更新  
3.会话一致性：对于客户端在同一会话作用域发出的请求，提供读取已写内容一致性。  
4.单调读一致性：保证时间的单调性，保证客户端在未来的请求中只读区比当前更新的数据。  
5.最终一致性：提供最低限度的保证。在更新过程中客户端将看到不一致的视图。当并发访问同一数据几率非常小的时候，此模型效果可以得到保证。  
同时取决采用何种一致性模型需要安排两种机制  
●客户端请求如何让分发到副本  
●副本如何传播以及应用更新  
围绕着如何实现这两方面。出现了许多模型，各有不同的权衡取舍。  
**矢量时钟**  
![79_120614165213_1.png][]  
矢量时钟是一种时间戳机制，透过矢量时钟我们可以推到更新之前的因果关系。首先，每个副本都持有矢量时钟。假设副本i的时钟是Vi。Vi*是副本根据特定规则更新矢量时钟之后的逻辑时钟。*   
*●当副本i执行了一则内部操作，副本i的时钟加1。  
●当副本i向副本j发送一则消息，副本i首先把自己的时钟Vi加1，并将自己的矢量时钟Vi附加到消息中发送出去。  
●当副本j收到来自副本i的消息，首先自增其时钟Vj\[j\]，然后合并其时钟及消息所附的时钟Vm。即Vj\[k\] = max (Vj\[k\], Vm\[k\])。  
于是可以定义偏序关系，Vi > Vj，当且仅当对于所有的k，Vi\[k\] >= Vj\[k\]。根据这样的偏序关系，我们就可以推导出更新之间的因果关系。其背后原理如下  
●内部操作的效果可在同一节点上立即看到。  
●接到消息之后，接收节点得知发送节点在消息发送之时的情况。情况不仅包括发送节点上发生的事情，还包括发送节点所知的所有其他节点上发生的事情。  
●Vi反映了节点i上发生最后一次内部操作的时间。Vi\[k\] = 6意味着副本i已经知道副本k在他的逻辑时钟6时刻的情况。  
**MapReduce的执行过程**  
![79_120614165300_1.png][]  
分布式存储架构同样适合分布式的处理，例如对一个键列表执行Map/Reduce操作情况。  
系统将Map和Reduce函数推送给全部的节点。Map函数分布到键所属的各个副本上处理，然后Map函数的输出被转交给Reduce函数去执行聚合操作。  
**对删除的处理**  
![79_120614165458_1.png][]  
在多主复制系统中，用矢量时钟时间戳去判定因果序，需要非常小心处理“删除”的情况。以免丢失掉删除对象关联的时间戳信息，否则根本无法推到何时执行删除。因此，通常需要将删除当作一种特殊的更新来处理，把对象标记为删除，但仍然保留元数据、时间戳信息。当经过足够长的时间，并确信所有节点都已经对该对象标记为删除之后，才能通过垃圾回收已删除对象的空间。（Шевченко/编译）*

[Link 1]: http://blog.csdn.net/v_JULY_v/archive/2011/03/26/6279498.aspx
[0_1313302192BLP4.gif]: http://hi.csdn.net/attachment/201108/14/0_1313302192BLP4.gif
[0_13133022154fL9.gif]: /images/20220610/ca6a5d7d27ae4a81af36e3331e8a14d3.png
[0_13133022364Qoo.gif]: http://hi.csdn.net/attachment/201108/14/0_13133022364Qoo.gif
[0_1313302261MhJ0.gif]: /images/20220610/044972cc822e4d34937f084088fa5b91.png
[0_1313302290jETe.gif]: /images/20220610/1c02e286b6fb4b0885e88fedaf5024e3.png
[0_1313302310ww2H.gif]: http://hi.csdn.net/attachment/201108/14/0_1313302310ww2H.gif
[0_1313302329UNN0.gif]: /images/20220610/0a1388e845ee4d4a9b33b7654ea61d5c.png
[0_1313302350l5vC.gif]: /images/20220610/4a71b036c88b45c88488fb57f0afb645.png
[0_1313302374j4KX.gif]: http://hi.csdn.net/attachment/201108/14/0_1313302374j4KX.gif
[0_1313302392OZOo.gif]: /images/20220610/21f0d889d28246de9ba26f1a6b39213d.png
[2.5_Bitmap_00_01_01_10_10_bitmap_01_ _2_ _6. _100_TOP10_ _1_]: http://images.cnblogs.com/cnblogs_com/youwang/WindowsLiveWriter/1340f2e6fa8e_D5D1/clip_image020_2.png
[Top K]: http://blog.csdn.net/v_JULY_v/archive/2011/05/08/6403777.aspx
[0_131330271622QP.gif]: /images/20220610/b553ad7a5f784debae2c7c6fa9b0c426.png
[0_1313303205157b.gif]: http://hi.csdn.net/attachment/201108/14/0_1313303205157b.gif
[0_1313303279I00N.gif]: http://hi.csdn.net/attachment/201108/14/0_1313303279I00N.gif
[0_1313303418777s.gif]: /images/20220610/5f662736a84a4b528da2e113b620c617.png
[min_max_n-1]: http://images.cnblogs.com/cnblogs_com/youwang/WindowsLiveWriter/1340f2e6fa8e_D5D1/clip_image050_2.png
[0_13133034380u54.gif]: /images/20220610/5e030ed242954f1aac4752b9c14b26e6.png
[0_1313305615kcCG.gif]: http://hi.csdn.net/attachment/201108/14/0_1313305615kcCG.gif
[0_1313305694rVyP.gif]: /images/20220610/1c2a7dd400cb4d04a9293c100792ca1c.png
[0_1313305723D1k5.gif]: /images/20220610/4e1e9815fdf649738dd7178ff04f3a22.png
[0_1313305860szjU.gif]: /images/20220610/82e5734fa3a2410f86bd8aa326398389.png
[0_1313301884r8Im.gif]: /images/20220610/b83cf3d58b094bcdb9c3d3f582a6dcc4.png
[0_1313301894Tg2K.gif]: /images/20220610/9289ffa4c8994d9eb4c9bf469160cea2.png
[0_1313301902884F.gif]: /images/20220610/9663772ef8bc4f74a0e20615abd55350.png
[Bit_2_3_4_5_7_BitMap_ view plain]: http://blog.redfox66.com/wp-content/uploads/2010/09/image_thumb_2.png
[Bloom filter]: http://blog.csdn.net/v_july_v/article/details/6685894
[http_www.cnblogs.com_youwang_archive_2010_07_20_1781431.html]: http://www.cnblogs.com/youwang/archive/2010/07/20/1781431.html
[http_blog.redfox66.com_post_2010_09_26_mass-data-4-bitmap.aspx]: http://blog.redfox66.com/post/2010/09/26/mass-data-4-bitmap.aspx
[79_120614164514_1.png]: /images/20220610/22eb598e7d824071833ddfc661c5fb2d.png
[79_120614164631_1.png]: /images/20220610/07704b7b91d84a6fb4adba005a59a0d0.png
[79_120614164648_1.png]: /images/20220610/927ad57175d74e7d83c73aca19c1ce0c.png
[79_120614164755_1.png]: /images/20220610/23939c1f495742a5a283c6528ed0abce.png
[79_120614164913_1.png]: /images/20220610/4739b64fe22c4af88aa84b5990a9d7ff.png
[79_120614165213_1.png]: /images/20220610/70c2ebaa4a3c49198dc199d3cad6ca7f.png
[79_120614165300_1.png]: /images/20220610/3b58724104a24455b9970ecb8dbf8fb6.png
[79_120614165458_1.png]: /images/20220610/76a0438cbce24a179edb1afa6a15e254.png