Presentation is loading. Please wait.

Presentation is loading. Please wait.

妩媚人生 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:

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

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

3 妩媚人生 http://www.5may.net/
第 一 部 分 云计算技术 妩媚人生 妩媚人生

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

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

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

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

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

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

10 妩媚人生 http://www.5may.net/
云计算发展背景 云计算技术的争议 反方:云计算是业界的商业性行为 正方:云计算是计算技术的重大发展趋势 个人认为:云计算技术有其发展的必然性和必要性 妩媚人生 妩媚人生

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

12 妩媚人生 http://www.5may.net/
云计算发展背景 应用需求背景 大粒度应用系统的规模越来越大 应用系统数据量越来越大 中国移动全国每天的电话短信通联记录数据达到 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部电影 妩媚人生

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

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

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

16 妩媚人生 http://www.5may.net/
不断追求计算性能提升 Intel 微处理器 每秒 1千8百亿次 浮点运算! 近20年性能提高3千多倍 妩媚人生

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

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

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

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

21 妩媚人生 http://www.5may.net/
云计算发展背景 “云计算”的概念在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) 妩媚人生 妩媚人生

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

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

24 妩媚人生 http://www.5may.net/
云计算发展背景 云计算发展意义 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 妩媚人生

25 妩媚人生 http://www.5may.net/
云计算发展背景 妩媚人生 云计算发展意义 美国联邦云计算战略报告认为: 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. 妩媚人生

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

27 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 妩媚人生

28 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 妩媚人生

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

30 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 妩媚人生

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

51 妩媚人生 http://www.5may.net/
MapReduce的基本设计思想 大数据任务划分和并行计算模型 大数据计算任务 任务划分 子任务 子任务 子任务 子任务 …… 结果合并 计算结果 妩媚人生

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

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

54 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) 妩媚人生

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

56 妩媚人生 http://www.5may.net/
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 妩媚人生

57 妩媚人生 http://www.5may.net/
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) 妩媚人生

58 妩媚人生 http://www.5may.net/
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) 计算结果 妩媚人生

59 妩媚人生 http://www.5may.net/
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 妩媚人生

60 妩媚人生 http://www.5may.net/
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); 妩媚人生

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

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

63 妩媚人生 http://www.5may.net/
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 妩媚人生

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

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

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

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

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

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

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

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

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

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

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

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

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

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

78 妩媚人生 http://www.5may.net/
开源的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) 妩媚人生

79 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 妩媚人生

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

81 妩媚人生 http://www.5may.net/
Hadoop MapReduce的基本工作原理 Hadoop MapReduce程序执行过程 妩媚人生

82 妩媚人生 http://www.5may.net/
Hadoop的分布式文件系统HDFS HDFS基本构架 对等于GFS Master HDFS NameNode 应用程序 HDFS客户端 文件名或数据块号 数据块号,数据块位置 对等于GFS ChunkServer DataNode 数据 妩媚人生

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

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

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

86 妩媚人生 http://www.5may.net/
大规模数据并行技术培训、教学和平台建设 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 容错 妩媚人生

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

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

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

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

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

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

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

94 妩媚人生 http://www.5may.net/
大规模数据并行算法 中国移动通信数据挖掘 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%的用 户数据,而且处理时间很长 妩媚人生

95 妩媚人生 http://www.5may.net/
大规模数据并行算法 中国移动通信数据挖掘 然后他们基于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倍数据时的速度比较 一个数量级的性能提升 妩媚人生

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

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

98 妩媚人生 http://www.5may.net/
大规模数据并行算法 机器学习与数据挖掘算法 中科院计算所智能信息重点实验室何清教授进行了基于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 妩媚人生

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

100 妩媚人生 http://www.5may.net/
大规模数据并行算法 机器学习与数据挖掘算法 本研究组进行了基于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 妩媚人生 妩媚人生

101 妩媚人生 http://www.5may.net/
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 妩媚人生

102 妩媚人生 http://www.5may.net/
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 妩媚人生

103 妩媚人生 http://www.5may.net/
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数 妩媚人生

104 妩媚人生 http://www.5may.net/
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 妩媚人生

105 妩媚人生 http://www.5may.net/
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 妩媚人生

106 妩媚人生 http://www.5may.net/
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 妩媚人生

107 妩媚人生 http://www.5may.net/
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 妩媚人生

108 妩媚人生 http://www.5may.net/
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 妩媚人生

109 妩媚人生 http://www.5may.net/
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 妩媚人生

110 妩媚人生 http://www.5may.net/
Experimental Results Number of running nodes varies from 2 to 18 Conclusion: PSON can achieve a good performance in speed-up 妩媚人生

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

112 妩媚人生 http://www.5may.net/
大规模数据并行算法 重复文档检测算法(Duplicate Document Detection) 妩媚人生

113 妩媚人生 http://www.5may.net/
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) 妩媚人生 妩媚人生

114 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)}) 来近似表示。 妩媚人生

115 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集合代表整个文档,完成最终的相似度的计算。 妩媚人生

116 Algorithm Details —shingles
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)}来代替,以此将大大简化计算。 妩媚人生

117 Algorithm Details —shingles
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 . 为了减少散列函数值碰撞,采用上述散列函数。 妩媚人生 妩媚人生

118 Algorithm Details —shingles
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: . 妩媚人生 妩媚人生

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

120 妩媚人生 http://www.5may.net/
重复文档检测算法并行化实现 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不同但其它内容相同的重复网页如:网站在各省的域名不一样,而首页内容是一样的; 进入到同一网站的登陆界面。 不满足以上条件的网页视为非重复网页。 妩媚人生

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

122 第三步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> 妩媚人生

123 对每个文档选取出的高阀值单词,计算并选取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> 妩媚人生

124 基于选取好的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> 妩媚人生

125 对每个候选的重复文档对,用每个文档所筛选出的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> 妩媚人生

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

127 算法结果比较 基于中文分词的改进算法实验结果 以字符为单位,采用固定长度切割的改进算法结果 以分词单元为单位,采用固定长度切割的改进算法结果
切割长度 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 以分词单元为单位,采用固定长度切割的改进算法结果 妩媚人生

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

129 妩媚人生 http://www.5may.net/
大规模数据并行算法 大规模长基因序列比对算法 本研究组进行了基于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 妩媚人生 妩媚人生

130 妩媚人生 http://www.5may.net/
基因序列比对问题背景 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 妩媚人生

131 妩媚人生 http://www.5may.net/
基因序列比对问题背景 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 妩媚人生 妩媚人生

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

133 基因比对并行化算法 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 妩媚人生

134 妩媚人生 http://www.5may.net/
基因比对并行化算法实验结果 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. 妩媚人生

135 妩媚人生 http://www.5may.net/
基因比对并行化算法实验结果 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). 妩媚人生

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

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

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

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

140 用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] 妩媚人生

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

142 妩媚人生 http://www.5may.net/
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不需要做任何处理 妩媚人生

143 妩媚人生 http://www.5may.net/
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> 在迭代过程中,必须保留网页的局部链出信息,以维护图的结构。 妩媚人生

144 妩媚人生 http://www.5may.net/
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)) 妩媚人生

145 妩媚人生 http://www.5may.net/
Phase2:PageRankIter PageRankIter伪代码 妩媚人生

146 妩媚人生 http://www.5may.net/
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); } 妩媚人生

147 妩媚人生 http://www.5may.net/
PageRank迭代终止条件 可选的终止条件: 各网页的PageRank值不再改变 各网页的PageRank值排序不再变化 迭代至固定次数 妩媚人生 妩媚人生

148 妩媚人生 http://www.5may.net/
迭代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 妩媚人生

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

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

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

152 妩媚人生 http://www.5may.net/
简单的文档倒排算法 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 妩媚人生

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

154 妩媚人生 http://www.5may.net/
带词频属性的文档倒排算法 一个倒排索引由大量的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 妩媚人生

155 妩媚人生 http://www.5may.net/
带词频属性的文档倒排算法 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) 妩媚人生

156 妩媚人生 http://www.5may.net/
带词频属性的文档倒排算法 A simple example posting(docid, tf) 妩媚人生

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

158 妩媚人生 http://www.5may.net/
带词频属性的文档倒排算法 倒排索引数据二级索引 全文检索时,由于每个单词下的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 妩媚人生

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

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

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

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

163 妩媚人生 http://www.5may.net/
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 妩媚人生

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

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

166 中 国 移 动 私 有 云 资 源 池 订单管理界面 实时跟踪界面 查询 界面 网络管理界面 系统管理界面 订阅订 单管理 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合成处理集群 综合分析计算集群 接口与管理 服务器 妩媚人生 中 国 移 动 私 有 云 资 源 池

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

168 妩媚人生 http://www.5may.net/
谢 谢! Q&A 妩媚人生 妩媚人生


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

Similar presentations


Ads by Google