妩媚人生 http://www.5may.net/ 云计算与大规模数据并行处理技术黄宜华南京大学计算机科学与技术系软件新技术国家重点实验室妩媚人生 http://www.5may.net/ 妩媚人生 http://www.5may.net/

妩媚人生 http://www.5may.net/
云计算与大规模数据并行处理技术黄宜华南京大学计算机科学与技术系软件新技术国家重点实验室妩媚人生妩媚人生

主要内容第一部分：云计算技术简介简要介绍云计算及其主要特点，云计算发展背景与现状，云计算的关键技术第二部分：MapReduce大规模数据并行处理技术简要介绍Google和Hadoop MapReduce大规模数据并行处理技术第三部分：大规模数据并行处理技术研究与应用介绍大规模数据并行处理技术研究，主要讨论大规模数据并行算法研究、大规模数据索引查询技术、以及Hadoop改进和优化技术研究妩媚人生妩媚人生

第一部分云计算技术妩媚人生妩媚人生

云计算技术简介什么是云计算？ Cloud Computing, Utility Computing, Service Computing…… 通过集中式远程计算资源池，以按需分配方式，为终端用户提供强大而廉价的计算服务能力工业化部署、商业化运作的大规模计算能力一种新的、可商业化的计算和服务模式计算能力像水电煤气一样，按需分配使用资源池物理上对用户透明就像在云端一样妩媚人生妩媚人生

云计算的主要特点透明的云端计算服务 “无限”多的计算资源，强大的计算能力按需分配，弹性伸缩，取用方便，成本低廉资源共享，降低企业IT基础设施建设维护费用应用部署快速而容易软件/应用功能更新方便快捷节省能源，绿色环保集计算技术之大成，具有很强的技术性、工程型特点妩媚人生

云计算的分类按云计算服务层面进行分类 SaaS：Software as a Service 提供各种应用软件服务 PaaS：Platform as a Service 提供软件支撑平台服务 IaaS：Infrastructure as a Service 提供接近于裸机(物理机或虚拟机)的计算资源和基础设施服务妩媚人生妩媚人生

云计算的分类按云计算服务层面进行分类云计算应用服务软件 SaaS 如腾讯云词典云计算应用云计算软件支撑平台 PaaS 如Google AppEng 云计算硬件平台 IaaS 如Amazon EC2 妩媚人生妩媚人生

云计算的分类按云计算系统类型进行分类美国联邦云计算战略报告中，定义了4中云：公用云：提供面向社会大众、公共群体的云计算服务如Amazon云平台，Google AppEng 公有云有很多优点，但最大的一个缺点是难以保证数据的私密性私有云：提供面向应用行业/组织内的云计算服务如政府机关、移动通信、学校等内部使用的云平台私有云可较好地解决数据私密性问题，对移动通信、公安等数据私密性要求特别高的企业或机构，建设私有云将是一个必然的选择妩媚人生

云计算的分类按云计算系统类型进行分类社区云：提供面向社团组织内用户使用的云计算平台如美国航天局(NASA) Nebula云平台为NASA内的研究人员提供快速的IT访问服务混合云：包含以上2种以上云计算类型的混合式云平台妩媚人生妩媚人生

云计算发展背景云计算技术的争议反方：云计算是业界的商业性行为正方：云计算是计算技术的重大发展趋势个人认为：云计算技术有其发展的必然性和必要性妩媚人生妩媚人生

云计算发展背景 “天下大势，合久必分，分久必合” “否定之否定，螺旋式上升” 07-现在: 云计算集中分散 95-06: 互联网/网格/集群 80-90’s: 个人计算机, 人手一台 60-70’s: 大型机(mainframe), 集中式、终端用户共享妩媚人生

云计算发展背景应用需求背景大粒度应用系统的规模越来越大应用系统数据量越来越大中国移动全国每天的电话短信通联记录数据达到 500TB；而中国移动一个流量最大的省每天的通联记录数据可达到65TB 阿里巴巴电子商务平台日处理数据量将达到500TB 百度存储 PB数据，每日处理10-100PB；存储1千-1万亿网页，索引亿网页 2009年eBays数据仓库，一个有2PB用户数据，另一个6.5PB用户数据包含170TB记录且每天增长150GB 个记录 Facebook：2.5PB用户数据，每天增加15TB 仅2011年，全世界产生1.8ZB（1.8万亿GB）数据，相当于每位美国人每分钟写3条Twitter，不停地写 2.7万年 YouTube每分钟有13h视频上传，每天数据10TB相当于好莱坞每周发行57000部电影妩媚人生

云计算发展背景应用需求背景大粒度应用系统的规模越来越大超大的计算量和计算复杂度用SGI工作站进行电影渲染时，每帧一般需要1～2小时一部2小时的电影渲染需要： 2小时x3600秒x24帧x(1~2小时)/24小时=20~40年! 特殊场景每帧可能需要60个小时(影片“星舰骑兵”中数千只蜘蛛爬行的场面),用横向4096象素分辨率进行渲染时，如果以每帧60个小时的速度，则1秒的放映量（24帧）需要60天的渲染时间,1分钟则需要100年！妩媚人生

云计算发展背景应用需求背景小粒度应用系统资源重复、无法共享企业内大量的小粒度应用系统需要添置独立的硬件资源，但忙闲不均，忙时资源不够，闲时资源空置，资源无法相互调配和共享，造成资源和资金浪费淘宝网案例：后台设置约15万台服务器，服务于不同的应用系统；而不同应用系统的负载不同，忙闲不均；据淘宝测算，如能在不同应用间合理调配计算资源，大约可省去2/3 约10万台服务器，以每台3万元计算，约可节省30亿元！妩媚人生

云计算发展背景技术发展背景贯穿整个计算机技术发展历史的两条主线：计算能力角度：不断追求计算性能提升无论是微处理器还是巨型机，近20年性能提高3千多倍使用角度：不断追求易用性和灵活性可获得性、易用性、可扩展性和灵活性不断提升妩媚人生妩媚人生

不断追求计算性能提升 Intel 微处理器每秒 1千8百亿次浮点运算！近20年性能提高3千多倍妩媚人生

巨型机：中国天河一号，2010年底世界TOP500强第1名每秒2千5百多万亿次浮点运算，近20年性能提高3千多倍亿亿千万亿百万亿十万亿万亿千亿百亿十亿亿妩媚人生

不断追求方便性和灵活性 TOP500系统体系结构演化向量机=>SMP =>MPP=>Cluster Cluster以高获得性、高可扩展性优势成为发展主流妩媚人生

云计算发展背景妩媚人生云计算发展背景技术发展背景虽然新的计算技术在易用性和灵活性上有不断提高，但仍然存在很大不足：计算能力仍取决于硬件计算资源，计算能力不够时，需要不断增加硬件资源；空闲时，硬件资源闲置浪费，不能共享；计算能力的获取和使用上仍然存在较大的制约。云计算正是一种解决这一问题的新的计算服务模式，其基本思路是集中计算资源提供巨大的计算能力的同时，提供使用上的方便性和灵活性妩媚人生

云计算发展背景技术发展背景云计算是诸多计算技术发展成熟与自然进化的产物计算机虚拟化技术、大规模并行计算、分布式存储、面向服务构架、公用服务计算等诸多技术广泛应用计算机系统规模和处理能力迅速扩大技术发展成熟与自然进化的结果妩媚人生妩媚人生

云计算发展背景 “云计算”的概念在2006年由Google公司正式提出但最初的思想雏形可追溯到更早的时间 “The computation and the data and so forth are in the servers. … We call it cloud computing.” (Erick Schmidt, 2006) “computation may someday be organized as a public utility” (John McCarthy, 1960) 妩媚人生妩媚人生

云计算发展背景妩媚人生云计算发展意义云计算出现的意义，可与20世纪电力工业的变革相比 20世纪初电力工业变革的几项关键技术发电容量大幅提升交流电的出现 (1888) 电表的发明和使用 (1894) 20世纪初私有电厂向公共电力服务转化过程 1900: 美国有5万多个私有小型电厂，3千6百个中心电站 1907: 40%并入了公共电力服务系统 1920: 70%并入了公共电力服务系统 1930: 80%~90%并入了公共电力服务系统妩媚人生

云计算发展背景云计算发展意义云计算的一个重要目标是，把计算能力变成像水电等公用服务一样，随用随取，按需使用。故此也有人把云计算称为“Utility Computing” 这里Utility不是效用、实用的意思，在英文里Utility有一个专门的含义，专指类似于水电煤气的公用服务，故Utility Computing应译为“公用服务计算” 妩媚人生妩媚人生

云计算发展背景云计算发展意义 2011年2月8日美国奥巴马总统签署了联邦云计算战略报告，制定该报告的目的： The Federal Government’s current Information Technology (IT) environment is characterized by low asset utilization, a fragmented demand for resources, duplicative systems, environments which are difficult to manage, and long procurement lead times.These inefficiencies negatively impact the Federal Government’s ability to serve the American public. Cloud computing has the potential to play a major part in addressing these inefficiencies and improving government service delivery. The cloud computing model can significantly help agencies grappling with the need to provide highly reliable, innovative services quickly despite resource constraints. 美国联邦政府部门计划用全部的800亿美元IT预算中的200亿作为云计算平台开发建设的费用。美国联邦云计算战略报告，2011/2/8 妩媚人生

云计算发展背景妩媚人生云计算发展意义美国联邦云计算战略报告认为： Cloud is a fundamental shift in IT Cloud computing enables IT systems to be scalable and elastic. End users do not need to determine their exact computing resource requirements upfront.I nstead, they provision computing resources as required, on-demand.Using cloud computing services, a Federal agency does not need to own data center infrastructure to launch a capability that serves millions of users Cloud computing can significantly improve public sector IT A number of government agencies are adopting cloud technologies and are realizing considerable benefits. For instance, NASA Nebula, through a community cloud, gives researchers access to IT services relatively inexpensively in minutes.Prior to adopting this approach, it would take researchers months to procure and configure comparable IT resources and significant management oversight to monitor and upgrade systems. Applying cloud technologies across the entire Federal Government can yield tremendous benefits in efficiency, agility, and innovation. 妩媚人生

云计算发展现状与趋势业界云计算技术的发展自2006年Google公司提出云计算技术的概念后，全球 IT著名企业纷纷予以极大关注，并投入了巨大力量进行云计算技术的研究开发。妩媚人生妩媚人生

Google Cloud Infrastructure (Google AppEngine，PaaS型公用云平台)
GFS master Google Cloud Infrastructure Scheduler Chubby Google AppEngine Node BigTable Server Node User … MapReduce Framework Node Node Scheduler slave GFS Google AppEngine提供了一种PaaS类型的云计算服务平台，用户可租用该平台的计算资源，并使用AppEngine提供的各种应用开发和支撑软件平台开发和部署自己的应用软件 Linux 妩媚人生

Amazon Elastic Computing Cloud (Amazon EC2，IaaS型公用云平台)
SQS EBS EC2 EBS EC2 User EBS EC2 EBS EC2 SimpleDB Developer S3 Amazon EC2提供了一种IaaS类型的云计算服务平台，在该平台上用户可部署自己的系统软件，完成应用软件的开发和发布。 SQS: Simple Queue Service EC2: Running Instance of Virtual Machines EBS: Elastic Block Service, Providing the Block Interface, Storing Virtual Machine Images S3: Simple Storage Service, SOAP, Object Interface SimpleDB: Simplified Database 妩媚人生

Amazon Elastic Computing Cloud 租用案例 2007年，美国纽约时报租用Amazon云计算平台，用于将年纽约时报的1100万篇报刊文章转换为PDF文件,供读者上网免费访问。共租用了100个EC2节点，运行了24小时，处理了4TB的报刊原始扫描图像，生成了1.5TB的PDF文件。每节点每小时费用为10美分，整个计算任务仅花费了240美元(100节点 x 24小时 x $0.10)！如果用自己的服务器，将需要数月和多得多的费用！妩媚人生妩媚人生

Microsoft Cloud Services (Window Azure，私有云平台管理和服务软件)
30 Microsoft Cloud Services (Window Azure，私有云平台管理和服务软件) Slide objectives: Define the Microsoft Services Platform in a clear and repeatable way. Speaking Points: [Build-out the slide starting at the bottom] So what is Microsoft providing for the cloud? Applications provided as services Microsoft has had a number applications that we’ve exposed to both user’s and organizations. For instance, today we have applications like Windows Live and Office Live that are operated as services. Within the last year we have also launched new online service versions of key products. This includes Exchange Online, SharePoint Online, and Dynamics CRM Online. These online applications provided as services enable IT organizations to rapidly use service-based versions of Microsoft products, without installing, configuring, and managing these products themselves. As part of providing SharePoint, for example, as a service, the SharePoint team had to think about a lot of issues such as: Scalability, redundancy, and availability Provisioning and billing Access Control and federation of identities with existing on-premises systems Extensibility – how do you let organizations customize and change an application running in a scalable, multi-tenant environment. We believe that these are common issues that we can address with a Cloud Platform. This is where the Azure Services Platform comes in. The Azure Services Platform is a comprehensive hosted platform for your applications & services. It enables a wide range of scenarios ranging from running your application code in Microsoft’s data centers to consuming programmable, web-based services from your applications. We are effectively building a comprehensive and coherent platform for the cloud, just as Windows & the .NET Framework provides a comprehensive and coherent platform for managed code. We are building a comprehensive services platform to help organizations take advantage of cloud computing and services. The Azure Services Platform consists of two layers of services: Windows Azure At the base layer we have Windows Azure. Windows Azure provides the core data center and infrastructure as well as compute, basic storage, and management services. Effectively, Windows Azure allows you to run your code in Microsoft’s data center. Developer Services The Azure Services Platform also provides a set of higher-level developer services including SQL Services, .NET Services, and Live Services. These higher-level services are programmable components, often exposed through standard SOAP or open REST-based endpoints, which can be consumed from within your applications. Your application can be running in Windows Azure and take advantage of these services or run on-premises or with a hosting provider. These services can also be mixed and matched to compose applications. In fact, you can selectively choose to just use certain services such as the .NET Services independent from the rest of the Azure Services Platform. Some of the services are designed more for business application scenarios and others are designed more for personal or consumer-centric scenarios. However, these services collectively will work together. These developer services include three primary categories: SQL Services – which are designed to provide the capabilities of SQL Server in the cloud .NET Services – which extend the key capabilities of the .NET Framework to provide flexible business connectivity, orchestration of services, and federated access control for your apps Live Services – which are designed to manage a user’s data and provide new user-centric capabilities to applications. SharePoint Services: Dynamics CRM and SharePoint are two of our most capable and most extensible platforms for business content, collaboration, and rapid solutions. The SharePoint Services and Dynamics CRM services you see on this diagram represent future services we will add to the Azure Services Platform. We will drill into Windows Azure, SQL Services, .NET Services, and Live Services later in this presentation. Notes: Azure™ Services Platform Microsoft SharePoint Services Microsoft Dynamics CRM Services 妩媚人生

IBM 云计算方案 (私有云计算平台管理和服务软件)
提供私有云计算资源管理软件平台，主要负责管理和调度虚拟计算资源，完成资源申请、调度和管理等整个生命周期管理妩媚人生

云计算发展现状与趋势其它国内外IT企业云计算研发除以上几家全球著名的IT企业外，其它著名IT企业如Cisco、HP、EMC、VMWare等，都在大力推进云计算技术和系统研发。国内诸多著名IT企业，如中国移动、中国电信、中国联通、阿里巴巴、腾讯、百度、万网、中兴通信、华为等，也大力推动云计算研发。妩媚人生妩媚人生

中国移动Big Cloud 云计算发展现状目标是建立可为中国移动企业内部进行海量通信数据存储和处理的使用的私有云平台，以及为社会大众和群体使用的公有云平台。妩媚人生

阿里巴巴电子交易云计算平台商品交易平台软件服务平台数据服务平台企业IT服务云计算编程模型与访问接口统一的资源调度服务综合监控计费系统安全高可靠保障机制结构化数据存储非结构化数据存储大规模离线数据处理在线服务分布式计算资源管理大规模低成本数据中心的订制化硬件设计妩媚人生

云计算发展现状与趋势云计算发展趋势云计算将提供一种新的计算模式和服务模式。云计算将是计算技术的一次重大变革，作为今后计算发展的潮流将大大改变现有的计算模式，对计算技术领域本身以及各个应用行业都将带来重大的影响，提供更多的发展机遇通过云计算人们能获得前所未有的强大计算能力，并能按需分配，按需付费，提升了本地计算能力但使用成本低廉，而且还能大幅削减不断升级软硬件系统的费用通过云计算平台强大的计算和存储能力，人们将能完成传统系统所无法完成的计算和处理，开发出更强大的应用功能，提供更多智能化应用妩媚人生

云计算发展现状与趋势云计算发展趋势通过各种个人终端使用云端的计算能力，将大大扩展现有的移动设备的计算能力，提供各种新的增值应用模式云计算与物联网有重要的关联性，作为未来的人机物计算的重要组成部分，云计算关注的是服务器端技术，物联网关注的客户和终端技术妩媚人生妩媚人生

云计算发展现状与趋势云计算发展趋势面向民生工程的政企应用将是云计算的潜在市场，并能带动产业整体发展未来3年，云计算应用将以政府、电信、教育、医疗、金融、石油石化和电力等行业为重点，在中国市场逐步被越来越多的企业和机构采用，市场规模将从2009年的92.23亿元增长到2012年的606.78亿元，年复合增长率达87.4% （来源:赛迪顾问中国云计算产业发展白皮书）妩媚人生妩媚人生

云计算的关键技术主要包括以下关键技术虚拟化技术：虚拟机的安装、设置、调度分配、使用、故障检测与失效恢复等云计算构架技术：研究解决适合于云计算的系统软硬件构架资源调度技术：解决物理或虚拟计算资源的自动化分配、调度、配置、使用、负载均衡、回收等资源管理妩媚人生妩媚人生

云计算的关键技术主要包括以下关键技术并行计算技术：针对大规模数据或复杂计算应用，解决数据或计算任务切分和并行计算算法设计问题海量存储技术：解决大规模数据的分布存储、共享访问、数据备份等问题云安全技术：解决云计算系统的访问安全性、数据安全性（包括数据私密性）等问题此外，还有云计算中心的节能和散热等工程技术问题妩媚人生

云计算的关键技术怎样才算是云计算？云计算概念很热，各级政府部门、很多行业和应用都想搞云计算。大家很热议的问题是：云计算与传统计算系统有什么区别？系统做成什么样才能称得上是云计算系统？妩媚人生妩媚人生

云计算的关键技术怎样才算是云计算？回答这两个问题必须从发展云计算技术的两个根本目的、以及云计算区别于传统计算的特点上来看提高计算能力：集中计算资源，为应用提供强大而廉价的计算能力 => 大规模并行计算能力提高易用性和灵活性：合理调配资源，为应用提供弹性资源分配、资源共享 => 资源虚拟化和弹性调度妩媚人生

云计算的关键技术怎样才算是云计算？因此，个人认为：一个计算系统必须具备以下两个特征才能算是云计算系统（至少具备第一个特征）: 资源虚拟化和弹性调度基于虚拟化和弹性调度，以按需分配方式，为小粒度应用提供计算资源，实现资源共享大规模并行计算服务基于云端的强大而廉价的计算能力，为大粒度应用提供传统计算系统或用户终端所无法完成的计算服务。这些计算能力包括海量数据存储能力、以及大规模并行计算能力。妩媚人生

第二部分 MapReduce 大规模数据并行处理技术
妩媚人生妩媚人生

大规模数据并行处理技术的重要性为什么大规模数据并行处理是云计算核心技术之一？大规模数据处理和行业应用需求日益增加和迫切出现越来越多的超大规模数据处理应用需求，传统系统难以提供足够的存储和计算资源进行处理，云计算平台是最理想的解决方案。调查显示：目前，IT专业人员对云计算中诸多关键技术最为关心的是大规模数据并行处理技术大数据并行处理没有通用和现成的解决方案对于应用行业来说，云计算平台软件、虚拟化软件都不需要自己开发，但行业的大规模数据处理应用软件没有通用的软件，需要针对特定的应用需求专门开发，涉及到诸多并行化算法、索引查询优化技术研究、以及系统的设计实现妩媚人生

大规模数据并行处理技术的重要性为什么大规模数据并行处理是云计算核心技术之一？处理数据的能力大幅落后于数据增长速度磁盘容量增长远远快过存储访问带宽和延迟：80年代中期数十MB到今天1-2TB，增长10万倍，而延迟仅提高2倍，带宽仅提高50倍！海量数据隐含着更准确的事实研究发现：训练数据集越大,数据分类精度越高；大数据集上的简单算法能比小数据集上的复杂算法产生更好的结果妩媚人生妩媚人生

大规模数据并行处理技术的重要性大数据(Big Data)应用需求出现越来越多的大数据应用和行业需求。2008年，在Google 成立10周年之际，《Nature》杂志出版一期专刊专门讨论未来的大数据（Big Data）处理相关的一系列技术问题和挑战。据预计：未来10年，数据量将从数百EB增长到数百ZB量级！妩媚人生

Google大规模数据并行处理技术简介 Google MapReduce Google在2004年提出的一种通用的大规模数据并行计算平台和编程模型和框架 MapReduce发明后，Google大量用于各种海量数据处理，目前Google内部有7千以上的程序基于MapReduce实现，包括其搜索引擎的全部索引处理妩媚人生

什么是MapReduce？ MapReduce三个层面的含义基于集群的高性能并行计算平台(Cluster Infrastructure) 允许用市场上的普通服务器，构成一个包含数百到数千个节点的分布式并行计算集群并行程序开发与运行框架(Software Framework) 提供了一个庞大但设计精良的并行计算软件构架，能自动完成计算任务的并行化处理，自动划分计算数据和计算任务，在集群节点上自动分配和执行子任务以及收集计算结果，将数据分布存储、数据通信、容错处理等并行计算中的很多复杂细节交由系统负责处理，大大减少了软件开发人员的负担并行程序设计模型与方法(Programming Model & Methodology) 借助于函数式语言中的设计思想，提供了一种简便的并行程序设计方法，用Map和Reduce两个函数编程实现基本的并行计算任务，提供了完整的并行编程接口，完成大规模数据处理妩媚人生

MapReduce的基本设计思想典型的流式大数据处理问题的特征大量数据记录/元素进行重复处理对每个数据记录/元素作感兴趣的处理、获取感兴趣的中间结果信息排序和整理中间结果以利后续处理收集整理中间结果产生最终结果输出 Map Reduce 关键思想：借助于Lisp函数式程序设计思想，为大数据处理过程中的两个主要处理操作提供一种抽象机制妩媚人生

MapReduce的基本设计思想 MapReduce三个层面上的基本设计思想如何对付大数据处理：分而治之对相互间不具有计算依赖关系的大数据，实现并行最自然的办法就是采取分而治之的策略上升到抽象模型：Mapper与Reducer MapReduce借鉴了Lisp函数式语言中的思想，用Map和Reduce两个函数提供了高层的并行编程抽象模型，程序员只需描述需要“做什么” (what to do),不需要关心具体“怎么做”（How to do) 上升到统一构架：为程序员隐藏系统层细节对于具体的“怎么做”的问题，MapReduce提供了一个统一的计算框架，为程序员隐藏了数据存储访问、数据块划分、计算节点调度管理、数据通信、结果收集、容错处理、负载均衡、性能优化等诸多低层细节，交由系统负责处理，因而大大减轻了程序员进行并行编程时的负担妩媚人生

MapReduce的基本设计思想大数据任务划分和并行计算模型大数据计算任务任务划分子任务子任务子任务子任务 …… 结果合并计算结果妩媚人生

MapReduce的基本设计思想 Map和Reduce操作的抽象描述 MapReduce借鉴了函数式程序设计语言Lisp中的思想，定义了如下的Map和Reduce两个抽象的编程接口，由用户去编程实现: map: (k1; v1)  [(k2; v2)] 输入：键值对(k1; v1)表示的数据处理：文档数据记录(如文本文件中的行，或数据表格中的行)将以“键值对”形式传入map函数；map函数将处理这些键值对，并以另一种键值对形式输出处理的一组键值对中间结果[(k2; v2)] 输出：键值对[(k2; v2)]表示的一组中间数据妩媚人生妩媚人生

MapReduce的基本设计思想 Map和Reduce操作的抽象描述 reduce: (k2; [v2])  [(k3; v3)] 输入：由map输出的一组键值对[(k2; v2)] 将被进行合并处理将同样主键下的不同数值合并到一个列表[v2] 中，故reduce的输入为(k2; [v2]) 处理：对传入的中间结果列表数据进行某种整理或进一步的处理,并产生最终的某种形式的结果输出[(k3; v3)] 。输出：最终输出结果[(k3; v3)] 妩媚人生妩媚人生

Barrier：Aggregation and Shuffle
MapReduce的基本设计思想基于Map和Reduce的并行计算模型海量数据存储 …… 数据划分 Map 初始kv 键值对中间结果 (k1,val) (k2,val) (k3,val) Barrier：Aggregation and Shuffle Reduce (k1,values) (k2,values) (k3,values) 计算结果 (K1,val) (K2,val) (K3,val) 妩媚人生

MapReduce的基本设计思想基于Map和Reduce的并行计算模型各个map函数对所划分的数据并行处理，从不同的输入数据产生不同的中间结果输出各个reduce也各自并行计算，各自负责处理不同的中间结果数据集合进行reduce处理之前,必须等到所有的map函数做完，因此, 在进入reduce前需要有一个同步障(barrier);这个阶段也负责对map的中间结果数据进行收集整理(aggregation & shuffle) 处理,以便reduce更有效地计算最终结果最终汇总所有reduce的输出结果即可获得最终结果妩媚人生妩媚人生

MapReduce并行处理示例文档词频统计WordCount 设有4组原始文本数据： Text 1: the weather is good Text 2: today is good Text 3: good weather is good Text 4: today has good weather 传统的串行处理方式(Java)： String[] text = new String[] { “hello world”, “hello every one”, “say hello to everyone in the world” ｝; HashTable ht = new HashTable(); for(i=0; i<3; ++i) { StringTokenizer st = new StringTokenizer(text[i]); while (st.hasMoreTokens()) { String word = st.nextToken(); if(!ht.containsKey(word)) { ht.put(word, new Integer(1)); } else { int wc = ((Integer)ht.get(word)).intValue() +1;// 计数加1 ht.put(word, new Integer(wc)); } for (Iterator itr=ht.KeySet().iterator(); itr.hasNext(); ) { String word = (String)itr.next(); System.out.print(word+ “: ”+ (Integer)ht.get(word)+“; ”); 输出： good: 5; has: 1; is: 3; the: 1; today: 2; weather: 3 妩媚人生

MapReduce并行处理示例文档词频统计WordCount Map处理示例设使用4个map节点： map节点1: 输入：(text1, “the weather is good”) 输出：(the, 1), (weather, 1), (is, 1), (good, 1) map节点2: 输入：(text2, “today is good”) 输出：(today, 1), (is, 1), (good, 1) map节点3: 输入：(text3, “good weather is good”) 输出：(good, 1), (weather, 1), (is, 1), (good, 1) map节点4: 输入：(text3, “today has good weather”) 输出：(today, 1), (has, 1), (good, 1), (weather, 1) 妩媚人生

MapReduce并行处理示例完整的MapReduce并行处理模型和过程海量数据存储 …… 数据划分 Map 初始kv 键值对中间结果 (the, 1) (weather, 1) (is, 1) (good, 1) Combiner (today, 1) (has, 1) (good, 2) Barrier (good, 1) (good,2) (good,1) Partitioner (is, 1) (has, 1) (weather, 1) (the, 1) (today, 1) (today,1) Reduce (good, 5) (is, 3) (has, 1) (weather, 3) (the, 1) (today, 2) 计算结果妩媚人生

MapReduce并行处理示例文档词频统WordCount Reduce处理示例设使用3个Reduce节点: reduce节点1: 输入：(good, 1), (good, 1), (good, 2), (good, 1) 输出：(good, 5) reduce节点2: 输入：(has, 1), (is,1), (is,1), (is, 1), 输出：(has, 1), (is, 3) reduce节点3: 输入：(the, 1), (today, 1), (today, 1) (weather, 1), (weather,1), (weather, 1) 输出：(the, 1), (today, 2), (weather, 3) 输出： good: 5 is: 3 has:1 the:1 today:2 weather: 3 妩媚人生

MapReduce并行处理示例文档词频统WordCount MapReduce程序实现 MapReduce伪代码(实现Map和Reduce两个函数)： Class Mapper method map(String input_key, String input_value): // input_key: text document name // input_value: document contents for each word w in input_value: EmitIntermediate(w, "1"); Class Reducer method reduce(String output_key, Iterator intermediate_values): // output_key: a word // output_values: a list of counts int result = 0; for each v in intermediate_values: result += ParseInt(v); Emit(output_key，result); 妩媚人生

提供统一的计算框架主要需求和目标：实现自动并行化计算为程序员隐藏系统层细节需要考虑的细节技术问题：如何管理和存储数据？如何划分数据？如何调度计算任务并分配map和reduce节点？如果节点间需要共享或交换数据怎么办？如何考虑数据通信和同步？如何掌控节点的执行完成情况？如何收集中间和最终的结果数据？节点失效如何处理？如何恢复数据？如何恢复计算任务？节点扩充后如何保证原有程序仍能正常运行并保证系统性能提升？问题：我们能把这些细节和复杂性都交给系统去负责处理吗？妩媚人生

提供统一的计算框架答案：MapReduce之前的并行计算方法都未能做到但MapReduce做到了！ MapReduce提供一个统一的计算框架，可完成：计算任务的划分和调度数据的分布存储和划分处理数据与计算任务的同步结果数据的收集整理(sorting, combining, partitioning,…) 系统通信、负载平衡、计算性能优化处理计算和存储节点出错检测和失效恢复妩媚人生妩媚人生

MapReduce的主要设计思想与特点向“外”横向扩展，而非向“上”纵向扩展（Scale “out”, not “up”）即MapReduce集群的构筑选用价格便宜、易于扩展的大量低端商用服务器，而非价格昂贵、不易扩展的高端服务器（SMP）低端服务器市场与高容量Desktop PC有重叠的市场，因此，由于相互间价格的竞争、可互换的部件、和规模经济效应，使得低端服务器保持较低的价格基于TPC-C在2007年底的性能评估结果,一个低端服务器平台与高端的共享存储器结构的服务器平台相比,其性价比大约要高4 倍;如果把外存价格除外,低端服务器性价比大约提高12倍对于大规模数据处理，由于有大量数据存储需要，显而易见，基于低端服务器的集群远比基于高端服务器的集群优越，这就是为什么MapReduce并行计算集群会基于低端服务器实现 * Cite from Jimmy Lin, University of Maryland, Data-Intensive Text processing with MapReduce 妩媚人生

MapReduce的主要设计思想与特点失效被认为是常态（Assume failures are common） MapReduce集群中使用大量的低端服务器(Google目前在全球共使用百万台以上的服务器节点),因此，节点硬件失效和软件出错是常态，因而：一个良好设计、具有容错性的并行计算系统不能因为节点失效而影响计算服务的质量，任何节点失效都不应当导致结果的不一致或不确定性；任何一个节点失效时，其它节点要能够无缝接管失效节点的计算任务；当失效节点恢复后应能自动无缝加入集群，而不需要管理员人工进行系统配置 MapReduce并行计算软件框架使用了多种有效的机制，如节点自动重启技术，使集群和计算框架具有对付节点失效的健壮性，能有效处理失效节点的检测和恢复。妩媚人生

MapReduce的主要设计思想与特点把计算向数据迁移 Moving processing to the data 传统高性能计算系统通常有很多处理器节点与一些外存储器节点相连，如用区域存储网络(SAN,Storage Area Network)连接的磁盘阵列，因此，大规模数据处理时外存文件数据I/O访问会成为一个制约系统性能的瓶颈。为了减少大规模数据并行计算系统中的数据通信开销，代之以把数据传送到处理节点(数据向处理器或代码迁移)，应当考虑将处理向数据靠拢和迁移。 MapReduce采用了数据/代码互定位的技术方法，计算节点将首先将尽量负责计算其本地存储的数据,以发挥数据本地化特点(locality),仅当节点无法处理本地数据时，再采用就近原则寻找其它可用计算节点，并把数据传送到该可用计算节点。妩媚人生

MapReduce的主要设计思想与特点顺序处理数据、避免随机访问数据 Process data sequentially and avoid random access 大规模数据处理的特点决定了大量的数据记录不可能存放在内存、而只可能放在外存中进行处理。磁盘的顺序访问和随即访问在性能上有巨大的差异例：100亿(1010)个数据记录(每记录100B,共计1TB)的数据库更新1%的记录(一定是随机访问)需要1个月时间；而顺序访问并重写所有数据记录仅需1天时间！ MapReduce设计为面向大数据集批处理的并行计算系统，所有计算都被组织成很长的流式操作，以便能利用分布在集群中大量节点上磁盘集合的高传输带宽。妩媚人生

MapReduce的主要设计思想与特点为应用开发者隐藏系统层细节 Hide system-level details from the application developer 软件工程实践指南中，专业程序员认为之所以写程序困难，是因为程序员需要记住太多的编程细节(从变量名到复杂算法的边界情况处理)，这对大脑记忆是一个巨大的认知负担,需要高度集中注意力而并行程序编写有更多困难，如需要考虑多线程中诸如同步等复杂繁琐的细节，由于并发执行中的不可预测性，程序的调试查错也十分困难；大规模数据处理时程序员需要考虑诸如数据分布存储管理、数据分发、数据通信和同步、计算结果收集等诸多细节问题 MapReduce提供了一种抽象机制将程序员与系统层细节隔离开来，程序员仅需描述需要计算什么(what to compute), 而具体怎么去做(how to compute)就交由系统的执行框架处理，这样程序员可从系统层细节中解放出来，而致力于其应用本身计算问题的算法设计妩媚人生

MapReduce的主要设计思想与特点平滑无缝的可扩展性 Seamless scalability 主要包括两层意义上的扩展性：数据扩展和系统规模扩展理想的软件算法应当能随着数据规模的扩大而表现出持续的有效性，性能上的下降程度应与数据规模扩大的倍数相当在集群规模上，要求算法的计算性能应能随着节点数的增加保持接近线性程度的增长绝大多数现有的单机算法都达不到以上理想的要求；把中间结果数据维护在内存中的单机算法在大规模数据处理时很快失效；从单机到基于大规模集群的并行计算从根本上需要完全不同的算法设计奇妙的是，MapReduce几乎能实现以上理想的扩展性特征。多项研究发现基于MapReduce的计算性能可随节点数目增长保持近似于线性的增长妩媚人生

Google MapReduce框架和关键技术 MapReduce BigTable GFS Chubby 并行数据处理MapReduce Google分布式文件系统GFS(Google File System) 结构化数据表BigTable 分布式锁管理Chubby 用市场上的普通服务器，构建了非常可靠的大规模并行计算集群！妩媚人生

Google MapReduce的基本工作原理
1.有一个待处理的大数据，被划分为大小相同的数据块(如64MB),及与此相应的用户作业程序 2.系统中有一个负责调度的主节点(Master),以及数据Map和Reduce工作节点(Worker) 3.主节点为作业程序寻找和配备可用的Map节点，并将程序和数据传送给map节点 4.主节点也为作业程序寻找和配备可用的Reduce节点，并将程序传送给Reduce节点 6.每个Map节点处理读取的数据块,并做一些数据整理工作(combining, sorting等)并将中间结果存放在本地；同时通知主节点计算任务完成并告知中间结果数据存储位置 5.主节点启动每个Map节点执行程序，每个map节点尽可能读取本地或本机架的数据进行计算 7.主节点等所有Map节点计算完成后,开始启动Reduce节点运行；Reduce节点从主节点掌握的中间结果数据位置信息读取这些数据 8.Reduce节点计算结果汇总输出到一个结果文件即获得整个处理结果妩媚人生 Cite from Dean and Ghemawat (OSDI 2004)

失效检测和恢复处理主节点失效主节点中会周期性地设置检查点(checkpoint)，检查整个计算作业的执行情况，一旦某个任务失效，可以从最近有效的检查点开始重新执行，避免从头开始计算的时间浪费。工作节点失效工作节点失效是很普遍发生的，主节点会周期性地给工作节点发送检测命令，如果工作节点没有回应，这认为该工作节点失效，主节点将终止该工作节点的任务并把失效的任务重新调度到其它工作节点上重新执行妩媚人生

带宽优化问题大量的键值对数据在传送给Reduce节点时会引起较大的通信带宽开销。解决方案每个Map节点处理完成的中间键值队将由Combiner做一个合并压缩，即把那些键名相同的键值对归并为一个键名下的一组数值。 (good, 1) (weather, 1) (is, 1) (good, 2) (weather, 1) (is, 1) combiner 妩媚人生

计算优化问题 Reduce节点必须要等到所有Map节点计算计算才能开始执行，因此，如果有一个计算量大、或者由于某个问题导致很慢结束的Map节点，则会成为严重的“拖后腿者”。解决方案把一个Map计算任务让多个Map节点同时做，取最快完成者的计算结果。根据Google的测试，使用了这个冗余Map节点计算方法以后，计算任务性能提高40%多！妩媚人生

用数据分区解决数据相关性问题问题一个Reduce节点上的计算数据可能会来自多个Map节点，因此，为了在进入Reduce节点计算之前，需要把属于一个Reduce节点的数据归并到一起。解决方案在Map阶段进行了Combine以后，可以根据一定的策略对Map输出的中间结果进行分区(partition)，这样即可解决以上数据相关性问题避免Reduce计算过程中的数据通信。例如：有一个巨大的数组,其最终结果需要排序,每个Map节点数据处理好后,为了避免在每个Reduce节点本地排序完成后还需要进行全局排序,我们可以使用一个分区策略如:(d%R),d为数据大小，R为Reduce节点的个数，则可根据数据的大小将其划分到指定数据范围的Reduce节点上,每个Reduce将本地数据拍好序后即为最终结果妩媚人生

分布式文件系统GFS工作原理 Google GFS的基本构架
Google GFS是一个基于分布式集群的大型分布式文件系统，为MapReduce计算框架提供低层数据存储和数据可靠性支撑； GFS是一个构建在分布节点本地文件系统之上的一个逻辑上文件系统，它将数据存储在物理上分布的每个节点上，但通过 GFS将整个数据形成一个逻辑上整体的文件。 MapReduce Applications Google MapReduce Google GFS …… 妩媚人生

分布式文件系统GFS工作原理 Google GFS的基本构架廉价本地磁盘分布存储各节点本地分布式存储数据，优点是不需要采用价格较贵的集中式磁盘阵列，容量可随节点数增加自动增加多数据自动备份解决可靠性采用廉价的普通磁盘，把磁盘数据出错视为常态，用自动多数据备份存储解决数据存储可靠性问题为上层的MapReduce计算框架提供支撑 GFS作为向上层MapReduce执行框架的底层数据存储支撑，负责处理所有的数据自动存储和容错处理，因而上层框架不需要考虑低层的数据存储和数据容错问题妩媚人生

分布式文件系统GFS工作原理 Google GFS的基本构架和工作原理 GFS Master：保存GFS文件系统的三种元数据：命名空间(Name Space),即整个分布式文件系统的目录结构 Chunk与文件名的映射表 Chunk副本的位置信息，每一个Chunk默认有3个副本 GFS Master GFS ChunkServer：用来保存大量实际数据的数据服务器；每个数据块缺省划分为64MB 妩媚人生 Cite from Ghemawat et al. (SOSP 2003)

开源的Hadoop MapReduce 在Google发表了文章后，Doug Cutting，2004年，开源项目 Lucene( 搜索索引程序库)和Nutch(搜索引擎)的创始人，发现 MapReduce正是其所需要的解决大规模分布数据处理的重要技术，因而模仿Google MapReduce，基于Java设计出了称为 Hadoop的开源MapReduce，该项目成为Apache下最重要项目 Hadoop目前最新版本是0.23.0, 11/11/2010 Yahoo是 Hadoop联盟中最大的支持者，目前大量使用了 Hadoop集群 Yahoo! Hadoop集群(引自Yahoo）妩媚人生

Hadoop MapReduce的基本工作原理
数据存储与计算节点构架 namenode job submission node namenode daemon jobtracker tasktracker tasktracker tasktracker datanode daemon datanode daemon datanode daemon Linux file system Linux file system Linux file system … … … slave node slave node slave node 妩媚人生

Hadoop MapReduce的基本工作原理
对等于Google MapReduce 中的Master 对等于Google MapReduce 中的Worker 妩媚人生

Hadoop MapReduce的基本工作原理 Hadoop MapReduce程序执行过程妩媚人生

Hadoop的分布式文件系统HDFS HDFS基本构架对等于GFS Master HDFS NameNode 应用程序 HDFS客户端文件名或数据块号数据块号，数据块位置对等于GFS ChunkServer DataNode 数据妩媚人生

大规模数据并行技术培训、教学和平台建设 Google技术培训 2009年12月Google在清华大学举办的 MapReduce技术培训班妩媚人生

大规模数据并行技术培训、教学和平台建设课程建设 2009年参加了 Google公司 MapReduce技术培训班，后与Google公司签约在Google资助下开设了 “MapReduce大规模数据并行处理”课程，是目前为止江苏省唯一开设该课程的教师和院系妩媚人生

大规模数据并行技术培训、教学和平台建设教材出版 2011年7月合著编写《实战Hadoop》，有关Hadoop技术第一本具有原著性质的书籍， 456页，9月电子工业出版出版发行。妩媚人生

大规模数据并行技术培训、教学和平台建设 5.1 简介 114 5.2 复合键值对的使用 115 5.2.1 把小的键值对合并成大的键值对 115 5.2.2 巧用复合键让系统完成排序 117 5.3 用户定制数据类型 123 5.3.1 hadoop 内置的数据类型 123 5.3.2 用户自定义数据类型的实现 124 5.4 用户定制输入/输出格式 126 5.4.1 hadoop 内置的数据输入格式和recordreader 126 5.4.2 用户定制数据输入格式与recordreader 127 5.4.3 hadoop 内置的数据输出格式与recordwriter 133 5.4.4 用户定制数据输出格式与recordwriter 134 5.4.5 通过定制数据输出格式实现多集合文件输出 134 5.5 用户定制partitioner 和combiner 137 5.5.1 用户定制partitioner 137 5.5.2 用户定制combiner 139 5.6 组合式mapreduce 计算作业 141 5.6.1 迭代mapreduce 计算任务 141 5.6.2 顺序组合式mapreduce 作业的执行 142 5.6.3 具有复杂依赖关系的组合式mapreduce 作业的执行 144 5.6.4 mapreduce 前处理和后处理步骤的链式执行 145 5.7 多数据源的连接 148 5.7.1 基本问题数据示例 149 5.7.2 用datajoin 类实现reduce 端连接 150 5.7.3 用全局文件复制方法实现map 端连接 158 5.7.4 带map 端过滤的reduce 端连接 162 5.7.5 多数据源连接解决方法的限制 162 5.8 全局参数/数据文件的传递与使用 163 5.8.1 全局作业参数的传递 163 5.8.2 查询全局mapreduce 作业属性 166 5.8.3 全局数据文件的传递 167 5.9 关系数据库的连接与访问 169 5.9.1 从数据库中输入数据 169 5.9.2 向数据库中输出计算结果 170 《实战Hadoop》第1 章神奇的大象—hadoop 第2 章 HDFS—不怕故障的海量存储第3 章分久必合—MapReduce 第4 章一张无限大的表—HBase 第5 章更上一层楼—MapReduce 进阶第6 章 Hive—飞进数据仓库的小蜜蜂第7 章 Pig—一头什么都能吃的猪第8 章 Facebook 的女神—cassandra 第9 章 Chukwa—收集数据的大乌龟第10 章一统天下—Zookeeper 第11 章综合实战1—打造一个搜索引擎第12 章综合实战2—生物信息学应用第13 章综合实战3—移动通信信令监测与查询第14 章高枕无忧—Hadoop 容错妩媚人生

大规模数据并行技术培训、教学和平台建设购建高性能MapReduce并行计算集群 2011年1月和10月共斥资100万建成南京大学第一台专用于科研的高性能MapReduce 并行计算集群 81台DELL高性能机架式服务器构成其中80台服务器每台包含： 2路4核Intel Xeon 5620, 2.4GHz 24GB内存 4TB硬盘整个集群总计： 332个处理器核 1000GB内存 162TB硬盘存储量千兆以太网交换机,背板带宽184Gbps 妩媚人生

第三部分大规模数据并行处理技术研究与应用
第三部分大规模数据并行处理技术研究与应用妩媚人生妩媚人生

大规模数据处理的主要研究内容大规模数据处理的主要研究问题数据存储 + 数据传输 + 数据处理具体可包括以下主要技术问题：海量数据存储管理技术海量数据压缩与传输技术大规模数据并行算法海量数据索引和查询技术 Hadoop系统改进与优化研究大规模数据并行处理应用以下主要讨论后3项内容妩媚人生

大规模数据并行算法基本算法各种全局数据相关性小、能适当划分数据的计算任务，如：分布式排序分布式GREP(文本匹配查找) 关系代数操作如：选择，投影，求交集、并集，连接，成组，聚合… 矩阵向量相乘、矩阵相乘词频统计(word count)，词频重要性分析(TF-IDF) 单词同现关系分析典型的应用如从生物医学文献中自动挖掘基因交互作用关系文档倒排索引 …… 妩媚人生

大规模数据并行算法复杂算法或应用 Web搜索引擎网页爬取、倒排索引、网页排序、搜索算法 Web访问日志分析分析和挖掘用户在Web上的访问、购物行为特征、以定制个性化用户界面或投放用户感兴趣的产品广告数据/文本统计分析如科技文献引用关系分析和统计、专利文献引用分析和统计图算法并行化宽度优先搜索(最短路径问题，可克服Dijkstra串行算法的不足)，最小生成树，子树搜索、比对 Web链接图分析算法PageRank，垃圾邮件连接分析妩媚人生

大规模数据并行算法复杂算法或应用聚类(clustering) 文档聚类、图聚类、其它数据集聚类相似性比较分析算法字符序列、文档、图、数据集相似性比较分析基于统计的文本处理最大期望(EM)统计模型，隐马可夫模型(HMM)，…… 机器学习监督学习、无监督学习、分类算法（决策树、SVM…) 数据挖掘统计机器翻译生物信息处理 DNA序列分析比对算法Blast：双序列比对、多序列比对生物网络功能模块(Motif)查找和比对广告推送与推荐系统 …… 妩媚人生

大规模数据并行算法机器学习与数据挖掘算法 Stanford大学研究小组研究了基于多核构架、自行设计的轻量级MapReduce框架的各种机器学习算法, 发现计算性能可随处理器核数增长保持近似于线性的增长 Cheng-Tao Chu et.al , MapReduce for Machine Learning on Multicore, 2006 妩媚人生

大规模数据并行算法中国移动通信数据挖掘 China Mobile looks to data warehousing and mining of this data to extract insights for improving marketing operations, network optimization, and service optimization. Some typical applications include Analyzing user behavior Predicting customer churn Analyzing service association Analyzing network quality of service (QOS) Analyzing signaling data Filtering 原来使用由著名供应商提供的专用的商业数据挖掘系统，但该系统的单服务器构架严重限制了大数据量挖掘处理。一个分支机构使用了8 核、32 GB 内存、一个磁盘阵列的Unix服务器，但仅能处理1.4百万个用户的行为数据，或者仅仅本分支机构10%的用户数据,而且处理时间很长妩媚人生

大规模数据并行算法中国移动通信数据挖掘然后他们基于Hadoop重新做了一个数据挖掘系统 Datanode/TaskTracker —单路 4核 Xeon 2.5 GHz CPU, 8 GB RAM, 4 x 250 GB SATA disks Namenode/JobTracker —双路 2核 AMD Opteron 2.6 GHz CPU, 16 GB RAM, 4 x 146 GB SAS 价格比较 1/5的价格 10倍数据时的速度比较一个数量级的性能提升妩媚人生

大规模数据并行算法海量数据挖掘算法研究发现：大数据隐含着更准确的事实信息检索、自然语言理解和机器学习的三个要素：数据，特征，与算法 2001, Banko and Brill 发表了一篇自然语言领域的经典研究论文，探讨训练数据集大小对分类精度的影响，发现数据越大，精度越高；更有趣的发现是，他们发现当数据不断增长时，不同算法的分类精度趋向于相同，使得小数据集时不同算法在精度上的差别基本消失！结论引起争论：算法不再要紧，数据更重要！不再需要研究复杂算法，找更多数据就行了！妩媚人生

大规模数据并行算法海量数据隐含着更准确的事实 2001年,一个基于事实的简短问答研究, 如提问:Who shot Abraham Lincoln？在很大的数据集时,只要使用简单的模式匹配方法,找到在“shot Abraham Lincoln”前面的部分即可快速得到准确答案：John Wilkes Booth 2007, Brants et al. 描述了一个基于2万亿个单词训练数据集的语言模型，比较了当时最先进的Kneser-Ney smoothing 算法与他们称之为“stupid backoff “ (简单退避)的简单算法,最后发现,后者在小数据集时效果不佳，但在大数据集时，该算法最终居然产生了更好的语言模型！结论：大数据集上的简单算法能比小数据集上的复杂算法产生更好的结果！妩媚人生

大规模数据并行算法机器学习与数据挖掘算法中科院计算所智能信息重点实验室何清教授进行了基于MapReduce的K-Means聚类、分类、和关联规则挖掘等海量数据挖掘并行算法、以及常用的数据统计分析算法的研究；并基于这些算法开发了一个并行分布式数据挖掘工具平台PDMiner，其中大规模数据存储在HDFS上，且通过MapReduce实现各种并行数据预处理和数据挖掘算法。 Parallel K-means clustering based on MapReduce Zhao, Weizhong (Key Laboratory of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Sciences, China); Ma, Huifang; He, Qing Source: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), v 5931 LNCS, p , 2009, Cloud Computing - First International Conference, CloudCom 2009, Proceedings Parallel implementation of classification algorithms based on mapreduce He, Qing (Key Laboratory of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Sciences, Beijing , China); Zhuang, Fuzhen; Li, Jincheng; Shi, Zhongzhi Source: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), v 6401 LNAI, p , 2010, Rough Set and Knowledge Technology - 5th International Conference, RSKT 2010, Proceedings The high-activity parallel implementation of data preprocessing based on mapreduce He, Qing (Key Laboratory of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Sciences, Beijing , China); Tan, Qing; Ma, Xudong; Shi, Zhongzhi Source: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), v 6401 LNAI, p , 2010, Rough Set and Knowledge Technology - 5th International Conference, RSKT 2010, Proceedings 妩媚人生

大规模数据并行算法机器学习与数据挖掘算法中科院深圳先进技术研究院高性能数据挖掘重点实验室，在海量数据挖掘技术研究方面进行了大量的研究工作：高性能数据挖掘算法及服务平台交互式可视化数据挖掘非规范数据挖掘海量时空数据分析与挖掘海量图数据分析与挖掘妩媚人生妩媚人生

大规模数据并行算法机器学习与数据挖掘算法本研究组进行了基于MapReduce的频繁项集挖掘算法研究 PSON: A Parallelized SON Algorithm with MapReduce for Mining Frequent Sets Tao Xiao, Shuai Wang, Chunfeng Yuan, Yihua Huang The Fourth International Symposium on Parallel Architectures, Algorithms and Programming (PAAP 2011)， Tianjin，Dec. 9-11, 2011 妩媚人生妩媚人生

Background Transaction database is ubiquitous and of large scale Supermarkets and online shops record transactions each day Their sizes can reach TBs or PBs easily Mining frequent sets from transaction database is fundamental and important Many data mining methods are based on frequent sets mining Many serial algorithms have been developed Finding frequent sets is a computation-intensive task For m items, the number of distinct itemsets can be up to 2m It’s desirable if it can be parallelized SON algorithm is naturally to be parallelized with MapReduce 妩媚人生

Transaction and Itemsets What is transaction and itemsets ? A transaction is composed of an id and a set of items There are 4 transactions in the figure above The first transaction (T100) has 3 items, {I1, I2, I5} is an itemset The length of {I1, I2, I5} is 3, so it is called a 3-itemsets An itemset, whose length is k, is referred as a k-itemset 妩媚人生

Frequent sets Suppose I is an itemset consisting of items from the transaction database D Let N be the number of transactions D Let M be the number of transactions that contain all the items of I M /N is referred to as the support of I in D Example Here, N = 4, let I = {I1, I2}, than M = 2 because I = {I1, I2} is contained in transactions T100 and T400 so the support of I is 0.5 (2/4 = 0.5) If sup(I) is no less that an user-defined threshold, then I is referred to as a frequent itemset Goal of frequent sets mining To find all frequent k-itemsets from a transaction database (k = 1, 2, 3, ....) 枚举计算的时间复杂度是：O(2n*N*t), n是Item的总数，N是Transaction总数，t是每个Transaction平均包含的Item数妩媚人生

Apriori Algorithm* A classic frequent sets mining algorithm Needs multiple passes over the database In the first pass, all frequent 1-itemsets are discovered In each subsequent pass, frequent (k+1)-itemsets are discovered, with the frequent k-itemsets found in the previous pass as the seed (referred to as candidate itemsets) Repeat until no more frequent itemsets can be found * R. Agrawal, R. Srikant, “Fast algorithms for mining association rules,” in proceedings of the 20th International Conference on Very Large Data Bases, Santiago, Chile, August 29-September 1, 1994 妩媚人生

SON Algorithm* Basic idea Divide the whole database into several non-overlapping partitions For each partition, discover all the frequent itemsets for it (referred to as local frequent itemsets) Merge all the local frequent itemsets from all the partitions (referred to as global candidate itemsets) Remove those that are not actually frequent in the whole database, generating global frequent itemsets Lemma An itemset that is not local frequent in any of the partitions cannot be global frequent A global frequent itemset must appear as local frequent in at least one of the partitions * A. Savasere, E. Omiecinski, and S. Navathe, “An efficient algorithm for mining association rules in large databases,” in proceedings of the 21st VLDB Conference Zurich, Swizerland, 1995 妩媚人生

PSON: Parallelized SON Algorithm Motivation to Parallelize SON Processing one partition doesn’t need any information from any other partition Each partition can be processed concurrently SON is naturally suitable for parallelization Preparing data Store the transaction database into DFS The whole database will be automatically divided into several non-overlapping chunks Chunks correspond to the partitions in SON Map tasks Each chunk is processed by one mapper node to find local frequent itemsets for that chunk Reduce tasks Local frequent itemsets of the same length are processed by one reduce node Each node counts for each global candidate itemset it receives Thus decides which are global frequent itemsets Run two MapReduce jobs to generate all frequent itemsets 1st job: generate all global candidate itemsets 2nd job: identify global frequent itemsets from global candidate itemsets 妩媚人生

The 1st MapReduce Job Map phase Each map node takes in one partition and generates local frequent itemsets for that partition using Apriori algorithm. For each local frequent itemset F, emits key-value pair <F, 1>. Here, the value 1 is only to indicate that F is a local frequent itemset for that partition. Shuffle and Sort phase The same local frequent itemsets are sent to one reduce node. Reduce phase Each reduce node emits one and only one key-value pair <F, 1> to DFS Finally Merging all the pairs in DFS gives us all global candidate itemsets 妩媚人生

The 2nd MapReduce Job Assumption Each node is given a full duplicate of the global candidate itemsets generated by the 1st MapReduce job beforehand Map phase Each map node counts for each of the global candidate itemsets in the partition the map node is assigned Then emits pairs like <C, v> where C is a global candidate itemset and v is the count of it in that partition Shuffle and Sort phase Each global candidate itemset and its counts in all the partitions are sent to one reduce node Reduce phase For each global candidate itemset C, reduce node adds up all the associative counts for C and emits only the actual global frequent itemsets to DFS 妩媚人生

Experimental Results The transaction database size varies from 6GB to 60GB，with the number of transactions varies from 1 million to 500 billion Conclusion: When the size of the database reaches a threshold of hundreds of GB, PSON can finish running in an acceptable period of time，achieving a good performance in scale-up 妩媚人生

Experimental Results Number of running nodes varies from 2 to 18 Conclusion: PSON can achieve a good performance in speed-up 妩媚人生

大规模数据并行算法重复文档检测算法（Duplicate Document Detection）本研究组进行了重复文档检测算法研究问题：搜索引擎的结果中包含大量重复文档链接 Numerous copies of web documents(1.7%-7%) creating a serious problem for search engines: enlarge the space to store indexhttp:// increase the cost of crawling, ranking, clustering… unbeneficial information on the first page in search result 妩媚人生

大规模数据并行算法重复文档检测算法（Duplicate Document Detection）妩媚人生

Algorithms “State-of-the-art” Comparing only the some of the tokens (shingles) rather than the entire documents (proposed by Andrei Z. Broder, 1997) Using random projection to reduce the dimension of feature vectors. (proposed by Charikars,2002) A novel similar detection algorithm(called I-Match) which considering the collections statistic (proposed by Chowdhury,2002) Employing the concept analysis on data reduction algorithm. (proposed by Ahmad M.Hasnah,2006) Employing the crawl logs or web server logs instead of probing page contents to mine the dust (proposed by Ahmad M.Hasnah,2007) 妩媚人生妩媚人生

Algorithm Details —shingles（叠瓦式算法）
Definitions. Shingle: a contiguous subsequence of w tokens contained in document D. e.g. , D=(a, rose, is, a, rose, is, a, rose), w=4, then 4-shingles ={(a, rose, is , a),(rose, is, a ,rose),(is, a, rose, is),…} Resemblance: resemblance of two documents , is defined as: = Theories. , Let 𝜋 be chosen at random from . Then ∪ Di 是所有文档中的shingles的全集合{s0,s1,s2,s3,…,sn}。Sn是该集合的全排列，π 是其中一个任选的排列，π(Di)是文档Di的shingles按该排列排序的集合，min{π(Di)}即为排在最前面的那个shingle; 当取足够多的排列数时，文档D1和D2的相似度可用概率Pr(min{π(D1)} = min{π(D2)}) 来近似表示。妩媚人生

Algorithm Details —shingles
Problem1: It is impossible to choose and represent permutaion at random in . Sketch. Choose a set of t independent random permutations (For instance we take t=100). For each document D, we store a sketch, which is the list: Then we can estimate resemblance of by . 问题是，对于一个巨大的文档集合， Sn中的shingles数量巨大，排列数更大，实际处理时根本无法表示并尝试所有的shingle的排列。为此，采用抽样方法抽取一个小数量的(t个)排列，然后对文档D，用这个抽样排列集合获取t个最前shingle，以此大大缩减的shingle集合代表整个文档，完成最终的相似度的计算。妩媚人生

Solution to problem1. min-wise independent: we say that hash function is min-wise independent if for any set X and any ,when h is chosen at random in : Ithe elements of any fixed set X have an equal chance to become the minimum element of the image of X under . H 进一步，真实处理时，基于上述shingle排列进行计算不现实，为此，用一个散列函数值代替每一个排列，求解min{π(D)}（最前shingle）的计算可用求解最小散列值min{h(D)}来代替，以此将大大简化计算。妩媚人生

Answer to Qustion1. Universal Hashing: Let the universe to be hashed be , pick a prime , then where a, b are randomly chosen integers which are less than . 为了减少散列函数值碰撞，采用上述散列函数。妩媚人生妩媚人生

Conclusion. Get the shingles set of each documents. e.g. Chose t(for instance we chose t=100) min-wise independent (universal hashing) functions Compute Compute similarity: . 妩媚人生妩媚人生

改进的重复文档检测算法问题：中文与英文有很大区别，处理中文文档时，原有的英文瓦片划分方法直接适用于中文时效果不佳，故进行中文分词预处理并提取关键字妩媚人生

重复文档检测算法并行化实现 Hadoop实验集群环境结点个数：12 主节点处理器：Intel(R) Xeon(R) CPU 2.8GHz 主节点内存：32G 从节点处理器： Intel(R) Quad Core E5620 Xeon(R) , 2.4GHz 从节点内存：24G 实验数据网页个数：160, 203 网站个数：137 网站类型：新闻，军事，财经，社交，小说，团购，体育，手机，汽车，旅游… 爬取工具：Nutch1.2 重复网页定义如下：不同网站下内容完全一样或者主题内容相同的网页。如：某一新闻网站的网页转载了其他新闻网站上的新闻页面，则这两个网页视为重复；相同网站下内容完全一样的网页，除了以下部分：时间戳、信息编号、网站访问量统计、服务器名称、响应时间和URL。信息编号不同但其它内容相同的重复网页如：视频网站下电视剧各集的网页；URL不同但其它内容相同的重复网页如：网站在各省的域名不一样，而首页内容是一样的；进入到同一网站的登陆界面。不满足以上条件的网页视为非重复网页。妩媚人生

重复文档检测并行化算法实现步骤第一步使用中文分词算法将文档分割成一个个单词Term 第二步计算每个Term的TF-IDF权重第三步选取TF-IDF权重最高的若干个（如10个）Term作为文档的Keywords 过滤TF-IDF权重低于阈值的Term，保留权重高于阈值的Term 第四步使用Shingling方法和散列函数对选取出高阀值Term计算后进一步筛选出若干个（100）Terms，以代表整个文档第五步将Keywords相同的文档对视为可能的候选重复文档对第六步基于压缩后文档内容，比较候选文档对的相似性，相似性高于阈值的视为重复文档对妩媚人生

第三步MapReduce 计算过程对每个文档,根据计算好的各单词的TF-IDF值，选取TF-ITF值最大的n个单词作为文档关键词，用以预选出候选重复文档对；再筛选出高于一定阀值的单词以代表整个文档 Web Document Terms with TF-IDF value mapper mapper mapper <{D3, 0.2}, t1> <{D1, 0.6}, t4> <{D3, 0.6}, t7> <{D2, 0.4}, t2> <{D3, 0.9}, t5> <{D1, 0.3}, t8> <{D1, 0.7}, t3> <{D2, 0.3}, t6> <{D2, 0.8}, t9> Shuffle and Sort: aggregate by document and sort by TF-IDF value Get Top n terms as the keywords of each document and filter out the terms whose TF-IDF values are less than the threshold reducer reducer reducer <{D1, 0.7}, t3> <{D2, 0.8}, t9> <{D3, 0.9}, t5> <{D1, 0.6}, t4> <{D2, 0.4}, t2> <{D3, 0.6}, t7> <{D1, 0.3}, t8> <{D2, 0.3}, t6> <{D3, 0.2}, t1> 妩媚人生

对每个文档选取出的高阀值单词，计算并选取t(如100)个散列值最小的单词
第四步MapReduce计算过程对每个文档选取出的高阀值单词，计算并选取t(如100)个散列值最小的单词 Web Document Terms whose TF-IDF value is larger than threshold Chose a universal hash function H at random. mapper mapper mapper <{D1, H(t1)} t1> <{D2, H(t4)}, t4> <{D3, H(t7)}, t7> <{D1, H(t2)}, t2> <{D2, H(t5)}, t5> <{D3, H(t8)}, t8> <{D1, H(t3)}, t3> <{D2, H(t6)}, t6> <{D3, H(t9)}, t9> Remain top t terms which have minimum hash values in each reducer. Shuffle and Sort: aggregate by document and sort by hash value reducer reducer reducer <{D1, H(t3)}, t3> <{D2, H(t5)}, t5> <{D3, H(t8)}, t8> <{D1, H(t2)}, t2> <{D2, H(t6)}, t6> <{D3, H(t7)}, t7> <{D1, H(t1)} t1> <{D2, H(t4)}, t4> <{D3, H(t9)}, t9> 妩媚人生

基于选取好的n个关键字单词，计算并输出包含相同单词的文档对，作为候选的重复文档对
第五步MapReduce 计算过程基于选取好的n个关键字单词，计算并输出包含相同单词的文档对，作为候选的重复文档对 Web Documents with their keywords mapper mapper mapper <D1, k1> <D4,k3> <D7, k2> <D2, k2> <D5, k1> <D8, k1> Shuffle and Sort: aggregate by keywords of each document reducer reducer reducer output all pairs of documents which share same keywords <k1, D1> <K2, D2> <K3, D4> <K1, D5> <K2, D7> <K1, D8> 妩媚人生

对每个候选的重复文档对，用每个文档所筛选出的t个单词，具体计算其文档对的相似度，若相似度超过一定阀值，即确定为重复文档对
第六步MapReduce 计算过程对每个候选的重复文档对，用每个文档所筛选出的t个单词，具体计算其文档对的相似度，若相似度超过一定阀值，即确定为重复文档对 Document pairs which share the same keywords mapper mapper Content1 = GetContent(D1); Content2 = GetContent(D2); S = GetSimilarity(Content1,Content2); If(S>threshold) Emit(<{D1,D2},NullWritable>); Content3 = GetContent(D3); Content4 = GetContent(D4); S = GetSimilarity(Content3,Content4); If(S>threshold) Emit(<{D3,D5},NullWritable>); Shuffle and Sort: aggregate by keywords of each document reducer reducer <D1,D2> <D3, D4> 妩媚人生

算法结果比较其中改进算法利用TF-IDF权重提取网页内容的关键字。关键字不同的网页对将会视为非重复网页过滤掉，然后采用Shingling算法进行比较算法 Shingling算法改进算法重复网页对的个数 682, 786 1, 055 准确性(抽样检查) < 0.1 0.94 召回率(抽样检查) 0.23 0.32 运行时间 8min37s 29min13s 妩媚人生妩媚人生

算法结果比较基于中文分词的改进算法实验结果以字符为单位，采用固定长度切割的改进算法结果以分词单元为单位，采用固定长度切割的改进算法结果
切割长度 2 3 4 5 重复对的个数 10, 770 2, 477 1, 742 1, 291 准确性(抽样检查) 0.22 0.78 0.82 0.87 召回率(抽样检查) 0.34 0.32 0.35 0.29 运行时间 32min46s 39min04s 40min55s 45min22s 以字符为单位，采用固定长度切割的改进算法结果切割长度 1 2 3 4 重复对的个数 52, 416 2, 156 1, 290 1, 055 准确性(抽样检查) 0.16 0.89 0.91 0.94 召回率(抽样检查) 0.34 0.21 0.32 运行时间 17min34s 22min20s 27min46 29min13s 以分词单元为单位，采用固定长度切割的改进算法结果妩媚人生

大规模数据并行算法大规模基因序列比对算法基于MapReduce 的基因序列比对算法BLAST的研究显示,无论基于虚拟机还是非虚拟机MapReduce，随着处理器数目的增加都能实现近似于线性的性能增长 Andréa Matsunaga et.al. CloudBLAST: Combining MapReduce and Virtualization on Distributed Resources for Bioinformatics Applications. 2008 妩媚人生

大规模数据并行算法大规模长基因序列比对算法本研究组进行了基于MapReduce的大规模基因序列比对并行化算法研究 Parallization of BLAST with MapReduce Xiaoliang Yang, Chunfeng Yuan, Yihua Huang The Fourth International Symposium on Parallel Architectures, Algorithms and Programming (PAAP 2011)， Tianjin，Dec. 9-11, 2011 妩媚人生妩媚人生

基因序列比对问题背景 With the rapid development of next-generation high-throughput genomic sequencing technologies in recent years, the amount of sequence data is growing rapidly The purpose of BLAST is to prodict the function of unknown gene sequences by comparing with gene sequences with known functions in database It is slow to use the standard BLAST (Basic Local Alignment Search Tool) to deal with the increasing demands of sequence alignment on big sequence databases An alignment example 妩媚人生

基因序列比对问题背景 MapReduce is currently the most successful approach for massive data parallel processing on large clusters The BLAST algorithm is both data-intensive and computation-intensive 一个未知功能的待比对序列，需要与数据库中数十万已知基因序列逐一比对，这是一个非常耗时的计算工作 Existing implementations for parallelizing BLAST, such as mpiBLAST, GPU-BLAST, CloudBLAST, lack of good scalability or fault-tolerance 妩媚人生妩媚人生

基因比对处理方法 2.用查询序列中的单词片段到已知基因序列中比较，找到两个相邻的单词片段匹配 3.以此为基础，向序列两侧扩展，找到一个最高分的匹配串 1. 划分单词片段 4.当这个最高分匹配串达到一定的分值时，触发一个对查询序列与已知基因序列进行精确匹配比较的过程，该过程用动态规划方法完成 1-3步进行初步的筛选，快速过滤掉大量不可能匹配的序列，以此大大减少比对数量，第4步对筛选出的可能匹配的序列进行精确比对妩媚人生

基因比对并行化算法 MapReduce BLAST overview （1）由查询序列构造单词列表；（2）从单词列表构造一个扫描器
（3）利用Hadoop的Distributed Cache将查询序列和扫描器发送到每个节点上，然后启动MapReduce Job进行序列比对；（4）在Map阶段，每个map task从Distributed Cache文件中读取查询序列并加载扫描器，然后在本地的数据块上扫描单词匹配（word hit）；满足two-hit条件的匹配会被保留下来进行扩展；（5）在每个节点上，扫描完成后，对保留下来的单词匹配先后做精确匹配扩展和允许空位的扩展（动态规划方法） MapReduce BLAST overview 妩媚人生

基因比对并行化算法实验结果 The running time grows nearly linearly as the query length increases The running time scales nearly linearly as the size of the sequence database increases A set of queries were aligned with sequence databases of different sizes Fragments of increasing length from a 95kb neucleoside sequence were aligned with the 16GB nt sequence database. 妩媚人生

基因比对并行化算法实验结果 The running time of searching a sequence database dropped quickly as the number of compute nodes increases. Four nucleoside sequences of 1kbp, 2kbp, 5kbp, and 10kbp in length respectively were aligned with the 16GB nt database on different cluster configurations(3 to 19 nodes, 24 to 152 CPU cores). 妩媚人生

大规模数据并行算法网页排名图算法PageRank PageRank是一种由搜索引擎根据网页之间相互的超链接计算的网页排名技术 PageRank是Google用于用来标识网页的等级或重要性的一种方法；其级别从1到10级，PR值越高说明该网页越受欢迎（越重要） PageRank基本思想从许多优质的网页链接过来的网页，必定还是优质网页。一个网页要想拥有较高的PR值的条件：有很多网页链接到它有高质量的网页链接到它妩媚人生

PageRank的随机浏览模型假定一个上网者从一个随机的网页开始浏览上网者不断点击当前网页的链接开始下一次浏览但是，上网者最终厌倦了，开始了一个随机网页的浏览随机上网者访问一个新网页的概率就等于这个网页的 PageRank值。这个模型更加接近于用户的行为妩媚人生妩媚人生

随机浏览模型的图表示设定任意两个顶点之间都有直接通路在每个顶点处以概率d按原来蓝色方向转移（即按照网页上的超链跳转浏览），以概率1-d按红色方向转移（即随机进入一个新的网页地址开始浏览）妩媚人生

随机浏览模型的表示与计算由于网页数目巨大，网页之间的连接关系的邻接矩阵是一个很大的稀疏矩阵。采用邻接表来表示网页之间的连接关系。随机浏览模型的PageRank公式：以上公式是递归定义的，因此需要通过迭代计算得到所有节点最终的PageRank值妩媚人生

用MapReduce实现PageRank
n1 [n2, n4] n2 [n3, n5] n3 [n4] n4 [n5] n5 [n1, n2, n3] Map n2 n4 n3 n5 n4 n5 n1 n2 n3 n1 n2 n2 n3 n3 n4 n4 n5 n5 Reduce n1 [n2, n4] n2 [n3, n5] n3 [n4] n4 [n5] n5 [n1, n2, n3] 妩媚人生

用MapReduce实现PageRank
Phase1: GraphBuilder 建立网页之间的超链接图 Phase2: PageRankIter 迭代计算各个网页的PageRank值 Phase3: RankViewer 按PageRank值从大到小输出妩媚人生妩媚人生

Phase1：GraphBuilder 原始数据集：维基百科各网页间的链接信息。文本文件，共11.2G。每行包含一个网页名，及其所链接的全部网页名 GraphBuilder目标：分析原始数据，建立各个网页之间的链接关系。 Map：逐行分析原始数据, 输出<URL ,(PR_init, link_list)> 其中网页的URL作为key, PageRank初始值（PR_init）和网页的出度列表一起作为value,以字符串表示value，用特定的符号将二者分开。 Reduce: 输出<URL, (PR_init, link_list)> 该阶段的Reduce不需要做任何处理妩媚人生

Phase2：PageRankIter PageRankIer：迭代计算PR值，直到PR值收敛或迭代预定次数。 Map对上阶段的 <URL, (cur_rank, link_list)>产生两种<key, value>对： For each u in link_list, 输出 <u, cur_rank/|link_list|> 其中u代表当前URL所链接到网页ID，并作为key； Cur_rank为当前URL的PageRank值， |link_list|为当前URL的出度数量， , cur_rank/|link_list|作为value。同时在迭代过程中，传递每个网页的链接信息<URL, link_list> 在迭代过程中，必须保留网页的局部链出信息，以维护图的结构。妩媚人生

Phase2：PageRankIter Reduce 对 Map输出的<URL, url_list> 和多个 <URL, val>做如下处理：其中<URL, url_list> 为当前URL的链出信息； <URL, val>为当前URL的链入网页对其贡献的PageRank值计算所有val的和，并乘上d，在加上常数(1-d) /N得到new_rank。输出 (URL, (new_rank, url_list))。迭代计算公式： PR(A) = (1-d) /N+ d (PR(T1)/C(T1) PR(Tn)/C(Tn)) 妩媚人生

Phase2：PageRankIter PageRankIter伪代码妩媚人生

Phase3：Rankviewer PageRankViewer：将最终结果排序输出。 PageRankViewer从最后一次迭代的结果读出文件，并将文件名和其PR值读出，并以PR值为key网页名为value，并且以PR值从大到小的顺序输出。排序过程中可以采用框架自身的排序处理，重载key的比较函数，使其经过shuffle和sort后反序（从大到小）输出 public static class DecFloatWritable extends FloatWritable { … @Override public int compareTo(Object o) { return -super.compareTo(o); } 妩媚人生

PageRank迭代终止条件可选的终止条件：各网页的PageRank值不再改变各网页的PageRank值排序不再变化迭代至固定次数妩媚人生妩媚人生

迭代MapReduce的处理 public class PageRankDriver { private static int times = 10; public static void main(String args[]) throws Exception String[] forGB = {"", args[1]+"/Data0"}; forGB[0] = args[0]; GraphBuilder.main(forGB); String[] forItr = {"Data","Data"}; for (int i=0; i<times; i++) { forItr[0] = args[1]+"/Data"+(i); forItr[1] = args[1]+"/Data"+(i+1); PageRankIter.main(forItr); } String[] forRV = {args[1]+"/Data"+times, args[1]+"/FinalRank"}; PageRankViewer.main(forRV); 也可以使用org.apache.hadoop.util.ProgramDriver 妩媚人生

海量数据索引和查询技术海量数据存储和查询的主要技术问题无论是结构化还是半结构化/非结构化数据，由于数据量巨大，传统的关系数据库已经难以胜任，在存储能力和查询性能上都难以满足海量数据存储和查询管理的需求。因此，需要针对具体的应用，研究海量数据的索引和查询技术。妩媚人生妩媚人生

海量数据索引和查询技术全文检索文档倒排索引和检索技术本研究组进行了基于Hadoop 的全文检索文档倒排索引和检索系统的研究开发,为南大小百合开发了全文检索系统。妩媚人生

全文检索的系统的体系结构 Documents Query document acquisition (e.g., web crawling) online offline Representation Function Representation Function Query Representation Document Representation Index Comparison Function Hits 妩媚人生

简单的文档倒排算法 doc1： one fish two fish 倒排索引： one: doc1, doc3 fish: doc1, doc2 two: doc1 red: doc2, doc3 blue: doc2 bird: doc3 解释一下term,documents doc2： red fish blue fish doc3： one red bird 基于以上索引的搜索结果： fish  doc1, doc2 red  doc2, doc3 red fish  doc2 妩媚人生

带词频属性的文档倒排算法如果考虑单词在每个文档中出现的词频、位置、对应Web文档的URL等诸多属性，则前述简单的倒排算法就不足以有效工作。我们把每个单词对应的文档ID、单词词频、位置等诸多信息称为postings 解释一下term,documents 妩媚人生

带词频属性的文档倒排算法一个倒排索引由大量的postings list构成一个postings list由多个posting构成(按doc id排序) 一个postings list与一个term关联一个posting 包含一个document id和属性信息，属性信息载有term在document中出现情况相关的信息(e.g. term frequency, positions, term properties)，同时还有对应Web文档到其URL的映射doc_idURL 解释一下term frequency 妩媚人生

带词频属性的文档倒排算法 Map和Reduce实现伪代码 1: class Mapper 2: procedure Map(docid n, doc d) 3: H ← new AssociativeArray 4: for all term t ∈ doc d do 5: H{t} ← H{t} + 1 6: for all term t ∈ H do 7: Emit(term t, posting <n, H{t}>) 1: class Reducer 2: procedure Reduce(term t, postings [<n1, f1>, <n2, f2>…]) 3: P ← new List 4: for all posting <a, f> ∈ postings [<n1, f1>, <n2, f2>…] do 5: Append(P, <a, f>) 6: 7: Emit(term t; postings P) 妩媚人生

带词频属性的文档倒排算法 A simple example posting(docid, tf) 妩媚人生

带词频属性的文档倒排算法倒排索引数据二级索引倒排索引数据量甚至超过了原始文档大小，数据量太大，需要压缩 Source file size Inverted index file size 48M 72.5M 182M 240M 703M 828M 妩媚人生妩媚人生

带词频属性的文档倒排算法倒排索引数据二级索引全文检索时，由于每个单词下的Postings数据不等长，因此检索时需要扫描整个倒排索引表，检索效率太低，需要建立二级索引提高查询效率二级索引将为每个单词建立一个等长索引项，并依据单词顺序排序，因此，检索时可用两分查找法实现快速的查找定位 Source file size Inverted index file size Second-Level Index file size 48.1M 72.5M 2.375M 182M 240M 5.17M 703M 828M 10.5M 妩媚人生

海量数据索引和查询技术大规模移动电话通联记录索引和查询技术移动电话通联记录（CDR）数据量巨大，关系数据库已经越来越难以承受和胜任大量电话记录的管理和查询处理，为此，需要考虑基于Hadoop的分布式CDR数据存储和查询技术。例如，在移动电话公司内部，最常使用的查询是依据电话号码（一个指定号码或者一个屏蔽了最后4位数字的万字段号码查询），加上其他查询信息（如局向、拨打或接受时间等）。为此提高查询速度，我们可以基于电话号码建立专门的快速查询索引表，然后使用两分快速查找方法，即可快速查询到指定号码的CDR数据记录。妩媚人生

海量数据索引和查询技术大规模移动电话通联记录索引和查询技术 CDR两级查询索引基于电话号码的等长二级索引表，可以进行快速的两分查找定位一级索引表中的offset包含其他查询信息，定位到指定号码后，可进行基于其他信息（局向、日期等）的进一步查询处理妩媚人生

海量数据索引和查询技术大规模移动电话通联记录索引和查询技术 CDR两级查询索引 20亿个号码的CDR电话记录最多只需要比较大约31次即可完成! 妩媚人生

Hadoop系统改进与优化研究面向实时数据查询的Hadoop系统改进和优化大规模数据的在线实时查询处理在使用MapReduce完成查询计算时，难以达到秒级的时间相应原因：MapReduce作业初始化需要花费10多秒的常数时间因此，需要考虑改进和优化现有的Hadoop MapReduce计算框架，使其能够满足实时数据查询应用需求可能的解决方案： MapReduce作业执行机制的定制化改造：即为特定的查询任务，采用把数据和程序在系统中预先布置的办法，避免常规的作业提交后的初始化过程采用基于内存或SDD的数据缓存机制，减少MapReduce作业执行时读写硬盘的I/O时间开销妩媚人生

Hadoop系统改进与优化研究面向实时数据查询的Hadoop系统改进和优化可能的解决方案：采用基于内存或SDD的数据缓存机制，减少MapReduce作业执行时读写硬盘的I/O时间开销 Berkeley大学进行了基于内存的集群计算优化技术研究，提出了一个基于内存缓存的抽象程序执行机制RDD(Resilient Distributed Datasets)，面向迭代执行的应用程序，优化后比常规 Hadoop计算性能提高10倍以上 Spark: Cluster Computing withWorking Sets Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, Ion Stoica. University of California, Berkeley，2010 Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauley, Michael J. Franklin, Scott Shenker, Ion Stoica. University of California, Berkeley， 2011 妩媚人生

大规模数据并行处理应用大规模数据处理将可以应用于各种需要处理海量数据的行业和应用电信数据信息处理与挖掘电网数据信息处理与挖掘大规模基因序列分析比对 Web信息挖掘多媒体数据并行化处理．．．．．．妩媚人生妩媚人生

移动信令监测云计算系统信令共享平台信令数据订阅网络管理实时跟踪信令数据采集系统信令数据合成信令数据存储查询分析应用增值扩展应用实时跟踪系统管理计算资源存储资源网络资源中国移动私有云资源池妩媚人生

中国移动私有云资源池订单管理界面实时跟踪界面查询界面网络管理界面系统管理界面订阅订单管理 Web服务程序
客户端信令数据处理软件层数据层系统软件层硬件平台层订单管理界面实时跟踪界面查询界面网络管理界面系统管理界面 CDR合成信令数据订阅实时跟踪信令数据查询分析网络管理系统管理应用系统订阅订单管理 Web服务程序并行查询任务分发拓扑管理配置管理 KPI统计信令数据输出模块协议分析订阅数据发送 KPI分析查询 CDR 查询专题查询报表生成告警预警管理安全管理 CDR合成实时业务跟踪订阅数据过滤基于Zookeeper的索引、计算、查询并行计算任务负载均衡调度与单点容错控制网络指标监视用户管理信令解析关联分析 KPI 统计专题计算查询索引创建自系统网管其它系统管理负载均衡数据分发数据库访问接口 HDFS访问接口 HBase接口 Hadoop编程接口移动云存储系统 Hadoop综合分析云计算软件平台 Web 服务器 Apache HBase Map Reduce Zoo keeper Sybase ASE HDFS Web服务器云存储集群 CDR合成处理集群综合分析计算集群接口与管理服务器妩媚人生中国移动私有云资源池

公安警务云计算系统 SaaS 云应用系统层指挥调度图像监控交通疏导反电信诈骗云搜索 …… 共享服务构件层 Web服务集成访问接口统一用户管理服务 GIS服务关联查询服务统一消息服务比对服务数据抽取集成数据挖掘服务安全服务 …… 共享数据资源云应用系统数据资源应用数据层警务业务信息资源库公安管理行业信息库机关企业信息资源库指挥调度数据图像监控数据交通疏导数据反电信诈骗数据云搜索数据 …… …… PaaS 云平台支撑系统软件层 Web访问接口 Web服务编程接口数据库访问接口其他存储访问接口 HDFS访问接口 HBase接口 MapReduce编程接口 Web 服务器基于SOA的Web服务支撑环境云存储系统 Hadoop大规模数据并行计算系统 HBase MapReduce 并行计算执行框架关系数据库其他存储系统 HDFS IaaS 虚拟化与云计算管理虚拟化管理资源用户管理资源配置管理资源调度管理资源状况监控计算资源池存储资源池 …… 硬件基础设施层妩媚人生数据库/Web服务器/负载均衡服务器网络设备云存储/灾备设备大规模数据并行计算集群

谢谢！ Q&A 妩媚人生妩媚人生

妩媚人生 http://www.5may.net/ 云计算与大规模数据并行处理技术黄宜华南京大学计算机科学与技术系软件新技术国家重点实验室妩媚人生 http://www.5may.net/ 妩媚人生 http://www.5may.net/

Similar presentations

Presentation on theme: "妩媚人生 http://www.5may.net/ 云计算与大规模数据并行处理技术黄宜华南京大学计算机科学与技术系软件新技术国家重点实验室妩媚人生 http://www.5may.net/ 妩媚人生 http://www.5may.net/"— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

妩媚人生 http://www.5may.net/ 云 计 算 与 大规模数据并行处理技术 黄 宜 华 南 京 大 学 计算机科学与技术系 软件新技术国家重点实验室 妩媚人生 http://www.5may.net/ 妩媚人生 http://www.5may.net/

Similar presentations

Presentation on theme: "妩媚人生 http://www.5may.net/ 云 计 算 与 大规模数据并行处理技术 黄 宜 华 南 京 大 学 计算机科学与技术系 软件新技术国家重点实验室 妩媚人生 http://www.5may.net/ 妩媚人生 http://www.5may.net/"— Presentation transcript:

Similar presentations

About project

反馈

妩媚人生 http://www.5may.net/ 云计算与大规模数据并行处理技术黄宜华南京大学计算机科学与技术系软件新技术国家重点实验室妩媚人生 http://www.5may.net/ 妩媚人生 http://www.5may.net/

Presentation on theme: "妩媚人生 http://www.5may.net/ 云计算与大规模数据并行处理技术黄宜华南京大学计算机科学与技术系软件新技术国家重点实验室妩媚人生 http://www.5may.net/ 妩媚人生 http://www.5may.net/"— Presentation transcript: