大数据——应对海量数据挑战方面的见解和经验

Teradata首席客户官周俊凌	百度首席科学家威廉•张	Yahoo!北京全球软件研发中心架构师韩轶平	SAP中国区企业信息管理咨询资深顾问杜韬

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

前言

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

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

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。

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

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

•     方案1：在前面的题中，我们已经提到了，用一个含100个元素的最小堆完成。复杂度为O(100w*lg100)。
•     方案2：采用快速排序的思想，每次分割之后只考虑比轴大的一部分，知道比轴大的一部分在比100多的时候，采用传统排序算法排序，取前100个。复杂度为O(100w*100)。
•     方案3：采用局部淘汰法。选取前100个元素，并排序，记为序列L。然后一次扫描剩余的元素x，与排好序的100个元素中最小的元素比，如果比这个最小的要大，那么把这个最小的元素删除，并把x利用插入排序的思想，插入到序列L中。依次循环，知道扫描了所有的元素。复杂度为O(100w*100)。

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

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

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

表示以第i个元素a结尾的最大子序列，那么显然。基于这一点可以很快用代码实现。
最大子矩阵问题：给定一个矩阵（二维数组），其中数据有大有小，请找一个子矩阵，使得子矩阵的和最大，并输出这个和。
    方案2：可以采用与最大子序列类似的思想来解决。如果我们确定了选择第i列和第j列之间的元素，那么在这个范围内，其实就是一个最大子序列问题。如何确定第i列和第j列可以词用暴搜的方法进行。

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

//定义每个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;
}

1. 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

usidc5 2011-08-20 22:59 导读：Yahoo CTO Raymie Stata是领导海量数据分析引擎的关键人物。IBM和Hadoop将更多的精力专注在海量数据上，海量数据正在潜移默化的改变企业和IT部门。 越来越多的大企业的数据集以及创建需要的一切技术，包括存储、网络、分析、归档和检索等，这些被认为是海量数据。这些大量信息直接推动了存储、服务器以及安全的发展。同时也是给IT部门带来了一系列必须解决的问题。 信息技术研究和分析的公司Gartner认为海量数据处理应该是将大量的不同种类以及结构化和非结构化的数据通过网络汇集到处理器和存储设备之中，并伴随着将这些数据转换为企业的商业报告。 海量数据处理的三个主要因素：大容量数据、多格式数据和速度 大容量数据（TB级、PB级甚至EB级）：人们和机器制造的越来越多的业务数据对IT系统带来了更大的挑战，数据的存储和安全以及在未来访问和使用这些数据已成为难点。 多格式数据：海量数据包括了越来越多不同格式的数据，这些不同格式的数据也需要不同的处理方法。从简单的电子邮件、数据日志和信用卡记录，再到仪器收集到的科学研究数据、医疗数据、财务数据以及丰富的媒体数据（包括照片、音乐、视频等）。 速度：速度是指数据从端点移动到处理器和存储的速度。 Kusnetzky集团的分析师Dan Kusnetzky在其博客表示“简单的说，大数据是指允许组织创建、操作和管理的庞大的数据集和存储设施工具”。这是否意味着将来将会出现比TB和PB更大的数据集吗？供应商给出的回应是“会出现”。 他们也许会说“你需要我们的产品来管理和组织利用大规模的数据，只是想想繁杂大量的维护动态数据集带来的麻烦就使人们头疼“。此外海量数据的另外一个价值是它可以帮助企业在适当的时机作出正确决策。 从历史上看，数据分析软件面对当今的海量数据已显得力不从心，这种局面正在悄然转变。新的海量数据分析引擎已经出现。如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在开发、测试并内部运行代码时，他们了解到使用起来还是很复杂的。这导致他们马上意识到如果在未来提供周边服务（例如提供直观的用户界面、定制部署和附加功能软件）可赚取更多的资金。 在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编程模型完全兼容的分布式分析平台，并支持多种分布式文件系统。 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系统会将海量数据处理提升到更高高度。  在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成为海量数据处理的行业标准，这将是对我们最好的奖赏。（李智/译）

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

usidc5 2011-11-18 22:23 当数据以成百上千TB不断增长的时候，我们需要一种独特技术来应对这种前所未有的挑战。 大数据分析迎来大时代 全球各行各业的组织机构已经意识到，最准确的商务决策来自于事实，而不是凭空臆想。这也就意味着，他们需要在内部交易系统的历史信息之外，采用基于数据分析的决策模型和技术支持。互联网点击数据、传感数据、日志文件、具有丰富地理空间信息的移动数据和涉及网络的各类评论，成为了海量信息的多种形式。 极具挑战性的是，传统的数据库部署不能处理数TB数据，也不能很好的支持高级别的数据分析。在过去十几年中，大规模并行处理（MPP）平台和列存储数据库开启了新一轮数据分析史上的革命。而且近年来技术不断发展，我们开始看到，技术升级带来的已知架构之间的界限变得更加模糊。更为重要的是，开始逐步出现了处理半结构化和非结构化信息的NoSQL等平台。 大数据分析迎来大时代 本文中，我们将向大家介绍迄今为止，包括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的数据库支持 。 支持大数据分析的EMC Appliance 今年5月，EMC推出了自己的Hadoop软件工具，而且该公司还承诺，今年秋季发布的模块化DCA将支持Greenplum SQL/关系型数据库，Hadoop部署也能在同样的设备上得到支持。借助Hadoop，EMC能够解决诸如网络点击数据、非结构数据等真正大数据分析的困难。模块化的DCA也能够在同样的设备上支持长期保留的高容量的存储模块，从而满足监测需求。 2.Hadoop和MapReduce提炼大数据 Hadoop是一个开放源码的分布式数据处理系统架构，主要面向存储和处理结构化、半结构化或非结构化、真正意义上的大数据（通常成百上千的TB甚至PB级别数据）应用。网络点击和社交媒体分析应用，正在极大地推动应用需求。Hadoop提供的MapReduce（和其他一些环境）是处理大数据集理想解决方案。 MapReduce能将大数据问题分解成多个子问题，将它们分配到成百上千个处理节点之上，然后将结果汇集到一个小数据集当中，从而更容易分析得出最后的结果。 MapReduce结构图 Hadoop可以运行在低成本的硬件产品之上，通过扩展可以成为商业存储和数据分析的替代方案。它已经成为很多互联网巨头，比如AOL、eHarmony（美国在线约会网站）、易趣、Facebook、Twitter和Netflix大数据分析的主要解决方案。也有更多传统的巨头公司比如摩根大通银行，也正在考虑采用这一解决方案。 3.惠普Vertica电子商务分析 今年二月被惠普收购的Vertica，是能提供高效数据存储和快速查询的列存储数据库实时分析平台。相比传统的关系数据库，更低的维护和运营成本，就可以获得更快速的部署、运行和维护。该数据库还支持大规模并行处理（MPP）。在收购之后，惠普随即推出了基于x86硬件的HP Vertica。通过MPP的扩展性可以让Vertica为高端数字营销、电子商务客户（比如AOL、Twitter、 Groupon）分析处理的数据达到PB级。 惠普Vertica实时分析平台 其实，早在惠普收购之前，Vertica就推出有包括内存、闪存快速分析等一系列创新产品。它是首个新增Hadoop链接支持客户管理关系型数据的产品之一，也是首个基于云部署风险的产品平台之一。目前，Vertica支持惠普的云服务自动化解决方案。 4.IBM提供运维和分析数据仓库 去年，IBM推出了基于DB2的Smart Analytic System（图中左侧），那么它为何还要收购另外的Netezza方案平台呢？因为前者是具备高扩展性企业数据仓库的平台，可以支持成千上万的用户和各类应用操作。比如，呼叫中心通常拥有大量的雇员需要快速回拨客户的历史通话记录。Smart Analytic System提供了整合信息的DB2数据库，预配置Cognos BI软件模块，可以在IBM Power System（RISC或者X86架构）上运行。 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%的人工工作量，而且由 于其采用高数据压缩，在数据库许可和存储等方面的开支也可以减少一半。 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。该产品方案主要针对金融公司在算法交易或者其他高性能要求方面的需求。 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（用户和硬件访问量）。 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闪存。 甲骨文大数据分析系统设施 甲骨文声称，SuperCluster事务处理和数据仓库性能相比传统服务器架构能分别带来10倍和50倍速度提升。但作为一个专有的Unix机器，甲骨文想通过SuperCluster，在面向x86硬件的数据仓库部署迁移大潮中力挽狂澜。甲骨文的Exadata和Exalogic都基于x86架构而且运行Linux系统。 在十月召开的Oracle OpenWorld中，甲骨文宣布将新增一个分布式pache Hadoop软件和相关的大数据设备。甲骨文也计划推出一个独立的基于开源BerkeleyDB产品的NoSQL。 9.ParAccel大打列存储、MPP和数据库分析组合拳 ParAccel是ParAccel Analytic Database（PADB）的开发厂商——提供快速、选择性查询和列存储数据库，并基于大规模并行处理优势特点的产品。该公式表示，其平台支持一系列针对各种复杂、先进应用的工作负载报告和分析。 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倍的交付能力。 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处理拥有广泛的市场需求，因为存在着大量的互联网点击数据、传感数据和社交媒体内容。 Teradata平台产品家族 Teradata日前宣布了一项Aster Data MapReduce产品的计划，它建立在以往产品同样的硬件平台之上，而且在Teradata和Aster Data之间新增了两种集成方法。通过收购，Teradata打破了在数据仓储业被认为最广泛、最具扩展性的界限。 12.1010data提供基于云计算大数据分析 正如标题所说，1010data能够提供基于云计算的大数据分析平台。很大数据库平台供应商提供基于云的沙箱测试和开发环境， 但1010data的管理数据库服务，主要针对将整个工作负载迁移到云的全过程。 该服务支持一种提供“丰富而又高级的内置分析功能”，其中包括有预测分析。其一大卖点是服务包括了数据建模和设计、信息集成和数据转换。 1010data提供基于云计算大数据分析 其客户包括有对冲基金、全球各大银行、证券交易商，零售商和包装消费品公司。 何谓大数据？ 大数据，也就是国外常说的Big Data。IBM把大数据概括成了三个V，即大量化（Volume）、多样化（Variety）和快速化（Velocity）。这些特点也反映了大数据所潜藏的价值（Value），我们也可以认为，四个V高度概括了大数据的基本特征。 业界比较一致对大数据的定义是：大数据是指无法在一定时间内用常规软件工具对其内容进行抓取、管理和处理的数据集合。

usidc5 2012-02-21 10:52 如今Apache Hadoop已成为大数据行业发展背后的驱动力。Hive和Pig等技术也经常被提到，但是他们都有什么功能，为什么会需要奇怪的名字（如Oozie，ZooKeeper、Flume）。 Hadoop带来了廉价的处理大数据（大数据的数据容量通常是10-100GB或更多，同时数据种类多种多样，包括结构化、非结构化等）的能力。但这与之前有什么不同？ 现今企业数据仓库和关系型数据库擅长处理结构化数据，并且可以存储大量的数据。但成本上有些昂贵。这种对数据的要求限制了可处理的数据种类，同时这种惯性所带的缺点还影响到数据仓库在面对海量异构数据时对于敏捷的探索。这通常意味着有价值的数据源在组织内从未被挖掘。这就是Hadoop与传统数据处理方式最大的不同。 本文就重点探讨了Hadoop系统的组成部分，并解释各个组成部分的功能。 MapReduce——Hadoop的核心 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 以上我们讨论了MapReduce将任务分发到多个服务器上处理大数据的能力。而对于分布式计算，每个服务器必须具备对数据的访问能力，这就是HDFS（Hadoop Distributed File System）所起到的作用。 HDFS与MapReduce的结合是强大的。在处理大数据的过程中，当Hadoop集群中的服务器出现错误时，整个计算过程并不会终止。同时HFDS可保障在整个集群中发生故障错误时的数据冗余。当计算完成时将结果写入HFDS的一个节点之中。HDFS对存储的数据格式并无苛刻的要求，数据可以是非结构化或其它类别。相反关系数据库在存储数据之前需要将数据结构化并定义架构。 开发人员编写代码责任是使数据有意义。Hadoop MapReduce级的编程利用Java APIs，并可手动加载数据文件到HDFS之中。 Pig和Hive 对于开发人员，直接使用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 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 随着越来越多的项目加入Hadoop大家庭并成为集群系统运作的一部分，大数据处理系统需要负责协调工作的的成员。随着计算节点的增多，集群成员需要彼此同步并了解去哪里访问服务和如何配置，ZooKeeper正是为此而生的。 而在Hadoop执行的任务有时候需要将多个Map/Reduce作业连接到一起，它们之间或许批次依赖。Oozie组件提供管理工作流程和依赖的功能，并无需开发人员编写定制的解决方案。 Ambari是最新加入Hadoop的项目，Ambari项目旨在将监控和管理等核心功能加入Hadoop项目。Ambari可帮助系统管理员部署和配置Hadoop，升级集群以及监控服务。还可通过API集成与其他的系统管理工具。 Apache Whirr是一套运行于云服务的类库（包括Hadoop），可提供高度的互补性。Whirr现今相对中立，当前支持Amazon EC2和Rackspace服务。 机器学习：Mahout  各类组织需求的不同导致相关的数据形形色色，对这些数据的分析也需要多样化的方法。Mahout提供一些可扩展的机器学习领域经典算法的实现，旨在帮助开发人员更加方便快捷地创建智能应用程序。Mahout包含许多实现，包括集群、分类、推荐过滤、频繁子项挖掘。 使用Hadoop 通常情况下，Hadoop应用于分布式环境。就像之前Linux的状况一样，厂商集成和测试Apache Hadoop生态系统的组件，并添加自己的工具和管理功能。（李智/编译）

usidc5 2012-03-22 19:53 一、什么是Bloom Filter     Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。     有人可能想知道它的中文叫法，倒是有被译作称布隆过滤器。该不该译，译的是否恰当，由诸君品之。下文之中，如果有诸多公式不慎理解，也无碍，只作稍稍了解即可。 1.1、集合表示和元素查询     下面我们具体来看Bloom Filter是如何用位数组表示集合的。初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0。     为了表达S={x1, x2,…,xn}这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1（1≤i≤k）。注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位，即第二个“1“处）。        在判断y是否属于这个集合时，我们对y应用k次哈希函数，如果所有hi(y)的位置都是1（1≤i≤k），那么我们就认为y是集合中的元素，否则就认为y不是集合中的元素。下图中y1就不是集合中的元素（因为y1有一处指向了“0”位）。y2或者属于这个集合，或者刚好是一个false positive。 1.2、错误率估计     前面我们已经提到了，Bloom Filter在判断一个元素是否属于它表示的集合时会有一定的错误率（false positive rate），下面我们就来估计错误率的大小。在估计之前为了简化模型，我们假设kn<m且各个哈希函数是完全随机的。当集合S={x1, x2,…,xn}的所有元素都被k个哈希函数映射到m位的位数组中时，这个位数组中某一位还是0的概率是：     其中1/m表示任意一个哈希函数选中这一位的概率（前提是哈希函数是完全随机的），(1-1/m)表示哈希一次没有选中这一位的概率。要把S完全映射到位数组中，需要做kn次哈希。某一位还是0意味着kn次哈希都没有选中它，因此这个概率就是（1-1/m）的kn次方。令p = e-kn/m是为了简化运算，这里用到了计算e时常用的近似： 令ρ为位数组中0的比例，则ρ的数学期望E(ρ)= p’。在ρ已知的情况下，要求的错误率（false positive rate）为： (1-ρ)为位数组中1的比例，(1-ρ)k就表示k次哈希都刚好选中1的区域，即false positive rate。上式中第二步近似在前面已经提到了，现在来看第一步近似。p’只是ρ的数学期望，在实际中ρ的值有可能偏离它的数学期望值。M. Mitzenmacher已经证明[2] ，位数组中0的比例非常集中地分布在它的数学期望值的附近。因此，第一步的近似得以成立。分别将p和p’代入上式中，得：     相比p’和f’，使用p和f通常在分析中更为方便。 1.3、最优的哈希函数个数     既然Bloom Filter要靠多个哈希函数将集合映射到位数组中，那么应该选择几个哈希函数才能使元素查询时的错误率降到最低呢？这里有两个互斥的理由：如果哈希函数的个数多，那么在对一个不属于集合的元素进行查询时得到0的概率就大；但另一方面，如果哈希函数的个数少，那么位数组中的0就多。为了得到最优的哈希函数个数，我们需要根据上一小节中的错误率公式进行计算。     先用p和f进行计算。注意到f = exp(k ln(1 − e−kn/m))，我们令g = k ln(1 − e−kn/m)，只要让g取到最小，f自然也取到最小。由于p = e-kn/m，我们可以将g写成     根据对称性法则可以很容易看出当p = 1/2，也就是k = ln2· (m/n)时，g取得最小值。在这种情况下，最小错误率f等于(1/2)k≈ (0.6185)m/n。另外，注意到p是位数组中某一位仍是0的概率，所以p = 1/2对应着位数组中0和1各一半。换句话说，要想保持错误率低，最好让位数组有一半还空着。     需要强调的一点是，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’写成 同样根据对称性法则可以得到当p’ = 1/2时，g’取得最小值。 1.4、位数组的大小     下面我们来看看，在不超过一定错误率的情况下，Bloom Filter至少需要多少位才能表示全集中任意n个元素的集合。假设全集中共有u个元素，允许的最大错误率为є，下面我们来求位数组的位数m。     假设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个，所以一个确定的位数组可以表示 个集合。m位的位数组共有2m个不同的组合，进而可以推出，m位的位数组可以表示     个集合。全集中n个元素的集合总共有     个，因此要让m位的位数组能够表示所有n个元素的集合，必须有     即：     上式中的近似前提是n和єu相比很小，这也是实际情况中常常发生的。根据上式，我们得出结论：在错误率不大于є的情况下，m至少要等于n log2(1/є)才能表示任意n个元素的集合。 上一小节中我们曾算出当k = ln2· (m/n)时错误率f最小，这时f = (1/2)k= (1/2)mln2 / n。现在令f≤є，可以推出 这个结果比前面我们算得的下界n log2(1/є)大了log2e≈ 1.44倍。这说明在哈希函数的个数取到最优时，要让错误率不超过є，m至少需要取到最小值的1.44倍。 1.5、概括     在计算机科学中，我们常常会碰到时间换空间或者空间换时间的情况，即为了达到某一个方面的最优而牺牲另一个方面。Bloom Filter在时间空间这两个因素之外又引入了另一个因素：错误率。在使用Bloom Filter判断一个元素是否属于某个集合时，会有一定的错误率。也就是说，有可能把不属于这个集合的元素误认为属于这个集合（False Positive），但不会把属于这个集合的元素误认为不属于这个集合（False Negative）。在增加了错误率这个因素之后，Bloom Filter通过允许少量的错误来节省大量的存储空间。     自从Burton Bloom在70年代提出Bloom Filter之后，Bloom Filter就被广泛用于拼写检查和数据库系统中。近一二十年，伴随着网络的普及和发展，Bloom Filter在网络领域获得了新生，各种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应 该>=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，则大大简单了。

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

usidc5

2012-05-29 15:27

美国国家超级计算应用中心(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容量。 她表示：“该子系统能够卸载每秒万亿字节的文件系统，所以我们需要一个非常大的磁带基础设施来进行卸载。” 正在建设中的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公司试图为我们简化我们的系统。”

●当副本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的执行过程

分布式存储架构同样适合分布式的处理，例如对一个键列表执行Map/Reduce操作情况。
系统将Map和Reduce函数推送给全部的节点。Map函数分布到键所属的各个副本上处理，然后Map函数的输出被转交给Reduce函数去执行聚合操作。
对删除的处理

在多主复制系统中，用矢量时钟时间戳去判定因果序，需要非常小心处理“删除”的情况。以免丢失掉删除对象关联的时间戳信息，否则根本无法推到何时执行删除。因此，通常需要将删除当作一种特殊的更新来处理，把对象标记为删除，但仍然保留元数据、时间戳信息。当经过足够长的时间，并确信所有节点都已经对该对象标记为删除之后，才能通过垃圾回收已删除对象的空间。