云计算核心算法(一) 云计算 （第三版） 第 10 章 CLOUD COMPUTING Third Edition 主编：刘鹏 教授 电子工业出版社《云计算(第三版)》配套课件 云计算 （第三版） CLOUD COMPUTING Third Edition 第 10 章 云计算核心算法(一) 主编：刘鹏 教授

云计算的红宝书 微信扫描二维码 关注云计算头条 电子工业出版社《云计算(第三版)》配套课件 本套PPT下载地址：http://www.chinacloud.cn/list.aspx?cid=20 云计算的红宝书 书籍购买地址：http://weidian.com/item.html?itemID=1469775685&p=-1 （包邮且有刘鹏教授亲笔签名） 微信扫描二维码 关注云计算头条

刘 鹏 教授、博导、学科带头人，清华大学博士。现任中国云计算专家咨询委员会秘书长、中国信息协会大数据分会副会长、工业与信息化部云计算研究中心专家。 主持完成科研项目25项，发表论文80余篇，出版专业书籍15本。获部级科技进步二等奖4项、三等奖4项。主编了国内第一本云计算教材《云计算》和第一本云计算编程书籍《实战Hadoop》。创办了知名的中国云计算（chinacloud.cn）和中国大数据（thebigdata.cn）网站。 曾率队夺得2002 PennySort国际计算机排序比赛冠军，两次夺得全国高校科技比赛最高奖，并三次夺得清华大学科技比赛最高奖。 荣获“全军十大学习成才标兵”（排名第一）、南京“十大杰出青年”、江苏省“333高层次人才培养工程”中青年科学技术带头人、清华大学“学术新秀”等称号。

云计算的基础技术是集群技术，支撑集群高效协同工作需要一系列资源和任务调度算法，良好的调度算法可以提高集群处理能力，有效分配资源，加速作业进度。 三种核心算法 Paxos算法 DHT算法 Gossip协议 解决分布式系统中信息一致性问题 解决分布式网络的应用层选路问题 解决分布式环境下信息高效分发问题

10.1 Paxos算法 10.2 DHT算法 10.3 Gossip协议

Paxos算法解决的问题是一个分布式系统如何就某个value（决议）达成一致。

10.1 Paxos算法 10.1.1 Paxos 算法背景知识 10.1.2 Paxos 算法详解 10.1.3 Paxos 算法举例

10.1 Paxos算法 Paxos 算法背景知识 1 processor可以担任三个角色“proposer”、“accepter”和“learner”中的一个或多个角色。 2 proposal和value： proposal一般译为“提案”，value一般译为“决议”。 3 proposer可以propose（提出）proposal； accepter可以accept（接受）proposal 4 各个processor之间信息的传递可以延迟、丢失，但是在这个算法中假设传达到的信息都是正确的

10.1 Paxos算法 10.1.1 Paxos 算法背景知识 10.1.2 Paxos 算法详解 10.1.3 Paxos 算法举例

10.1 Paxos算法 Paxos 算法详解 1 2 3 Paxos算法的核心是，只要满足下面三个条件就能保证数据的一致性： 一个value只有在被proposer 提出之后才可以被choose； 2 每次只有一个value被choose； 3 value只有被choose之后才能被learners所获取。

10.1 Paxos算法 Paxos 算法详解 对一个proposal的提出和接受做一个系统的描述，这个过程分为请求和提出两个阶段。 proposer选择一个编号n，并向accepter多数派发出一个prepare请求 请求 阶段 如果accepter接受到的prepare所带有的编号n比它之前所做出过回应的prepare请求的编号都要高，则该accepter回应proposer一个promise 如果proposer收到了accepter多数派对它所发出的prepare请求所做的回应，则它发出带有proposal的accept请求，proposal = (num,value)，value为回应所带回的proposal的value值 提出 阶段 如果accepter接受到一个accept请求，如果该accepter之前没有对任何编号大于n的prepare请求做出过promise，则接受该proposal

10.1 Paxos算法 Paxos 算法详解 p1 a1 a2 a3 PR PR：prepare request（假设p1到a3的PR丢失） a1和a2是第一次接受到prepare请求，所以返回promise（不带回proposal），此时p1收到了a1和a2的promise，但是根据提出阶段的proposer必须接受来自多数派的promise才可以提出accept 请求，因此不会出现先前例子中的情况。

10.1 Paxos算法 10.1.1 Paxos 算法背景知识 10.1.2 Paxos 算法详解 10.1.3 Paxos 算法举例

10.1 Paxos算法 Paxos 算法举例 步骤一 S1选定编号1（假设第一个命令编号为1），向集合database={s2, s3, s4, s5}的一个多数派子集发送Prepare Request（PR） S2（Accepter） S3（Accepter） S4（Accepter） S5（Accepter） S1（Proposer） Prepare Request

10.1 Paxos算法 Paxos 算法举例 步骤二 如果通信顺利，所有的多数派都收到了PR S2（Accepter） S3（Accepter） S4（Accepter） S5（Accepter） S1（Proposer） Promise Proposal 如果通信部分失败导致接受到PR的节点不构成多数派则S1重复步骤1（PR编号递增）

10.1 Paxos算法 Paxos 算法举例 步骤三 S1接收到多数派的Paromise，向集合database发出带有第一个SQL命令（这里的SQL命令就是之前的value）的Proposal，编号为1，因为Promise没有带回Proposal所以这里的SQL命令没有限制。

10.1 Paxos算法 Paxos 算法举例 步骤四 通信顺利 接收Proposal 决议产生 S2（Accepter） S1（Proposer） SQL 构成多数派 通信失败 决议不产生 不构成多数派

10.1 Paxos算法 Paxos 算法举例 步骤五 重复以上操作，注意Proposal、Prepare以及Promise的编号递增，以及Promise根据情况带回Proposal。

10.1 Paxos算法 10.2 DHT算法 10.3 Gossip协议

10.2 DHT算法 Client/Server计算模式（即客户—服务器计算模式）主要应用于小规模的网络环境。 大部分的计算都集中在服务器端，因而引起负载的不平衡。即所谓的“服务器端的计算瓶颈”，而客户机端则存在资源浪费的情况。 集中式计算模式对用户的隐私以及数据安全也将存在不可能解决的难题。

10.2 DHT算法 P2P计算模式是一种非集中计算模式。

10.2 DHT算法 P2P按照拓扑结构的不同可以分为三种： 这种模式必须有中央服务器。当系统中节点数增多时，中央服务器就成为系统的瓶颈。 集中式拓扑模式 分布式非结构化拓扑模式 在非结构化P2P系统中，信息搜索的算法难免会带有一定的盲目性。 分布式结构化拓扑模式 由于用户预先知道应该搜索哪些节点，避免了非结构化P2P系统中使用的泛洪式查找，提高了信息搜索的效率。

10.2 DHT算法 10.2.1 DHT原理介绍 10.2.2 Chord中DHT的具体实现 10.2.3 Pastry中DHT的具体实现 10.2.4 CAN中DHT的具体实现 10.2.5 Tapestry中DHT的具体实现

10.2 DHT算法 DHT原理介绍 应用层 DHT层 网络层 DHT分布式哈希表采用Hash函数加速了查找速度和增强了安全性，而且便于管理，同时不会占用太多的网络带宽 事件通知 网络存储 其他应用 应用层 DHT DHT层 TCP/IP 网络层 DHT技术的基本概念

10.2 DHT算法 DHT原理介绍 应用层 DHT Node 通过DHT层的LookUp(Key)操作，可以把应用层的数据均匀分布在网络的各个节点内，这种方法使下层网络完全不受中心控制 应用层 DHT Node Insert（Key，data） LookUp（Key） … … DHT应用层的接口

10.2 DHT算法 DHT原理介绍 所有的DHT路由算法都主要包括三个方面: 第一方面 第二方面 第三方面 DHT的散列值空间的描述 路由发现算法 即如何进行散列 即散列后的信息如何决定其存储的节点位置 即对散列值进行查询时节点如何高效地路由到存储目标信息的节点

百度排名首位的大数据资料和交流中心

百度排名首位的云计算资料和交流中心

终生免费的智能硬件大数据托管平台 扫一扫，进入万物云

终生免费的环境大数据共享平台 扫一扫，进入环境云

高校Hadoop教学科研 一揽子解决方案 云创大数据 给您一步到位的解决方案！ 了解详情 云计算、大数据时代，社会亟需相关人才！而高校缺平台、缺人才、缺经验！怎么办？ 云创大数据 给您一步到位的解决方案！ 建设一个Hadoop实验平台 一套开源的Hadoop一体机和开发环境，详细的指导书籍和实验设计。 培养一支云计算师资队伍 来自云计算高手的系列培训， 早在2010年就培训了全国第一批云计算师资力量。 营造一个大数据科研环境 为科研提供技术支持，与大数据应用相结合，让科研迈上新台阶。

知名微信公众号推荐 学习云计算必须关注的公众号 刘鹏看未来 云计算头条 中国大数据 云创大数据 眼光决定成败，与刘鹏教授看未来。 微信号：lpoutlook 微信号： chinacloudnj 眼光决定成败，与刘鹏教授看未来。 刘鹏，清华博士，《云计算》作者。 资源丰富、分析深入、更新及时的云计算知识共享平台。 中国大数据 云创大数据 微信号： cStor_cn 微信号： cstorbigdata 国内大数据龙头企业。提供领先的云存储、云数据库、云视频、云传输产品和解决方案。 分享大数据技术，剖析大数据案例，讨论大数据话题。

运用云计算，精彩你生活 优秀免费云计算应用推荐 支持安卓和苹果 支持安卓和苹果 暂时仅有安卓版本

谢谢观看 云计算 （第三版） 第 10 章 CLOUD COMPUTING Third Edition 主编：刘鹏 教授 电子工业出版社《云计算(第三版)》配套课件 云计算 （第三版） CLOUD COMPUTING Third Edition 第 10 章 谢谢观看 主编：刘鹏 教授