Paxos算法的大概过程
• 安全性：
– 最后只能决定出一个值，不能是多个值 – 最后决定的值必须某一个节点提出来的值，不能是 一个没有意义的值 – 一个值只有被确定之后才能够被节点以及外界所获 知
• 活跃性：
– 最终这组节点会决定出一个值
• Paxos算法：
– 是一个多轮的过程，每一轮都通过自己本地的状态 以及消息来决定下一步的工作 – 关键：在提出建议之前首先去了解一下系统的状况 （通过发消息），然后才提建议（要么是新建议， 要么是老建议），从而不去破坏系统可能决定的状
内容
• 数据存储技术 • 数据分析技术
– 大规模平台下的数据分析编程模型 – 基于编程模型的数据查询与优化
• 开源平台技术发展
分布式系统处理的关注点
• • • • • 功能方面：易用性 性能方面：扩展性 分布式容错：可用性，出错容忍 正确性方面：一致性 安全性：访问控制，加密解密，入侵
云计算架构与大数据分析层次
Step 1: Prepare
Proposer 1 PREPARE j Proposer 2
(a) A proposer selects a proposal number n and sends a PREPARE PREPARE k request with number n to a majority of acceptors.
数据的统计与查询
SQL, MatLab, R
数据分析编程
C, Java
数据的存储
FS文件系统，数据库存储
大数据处理的总体架构
数据的统计与查询

LINQ, HIVE, Pig Latin
数据分析编程
MapReduce, Dryad, Piccolo
数据的存储
分布式文件系统GFS 分布式Dynamo存储 分布式BigTable存储，分布式数据库
主要包括开发的平台 • 包括大数据处理的平台例如MapReduce， Dryad，Pregel等，大数据平台需要存储 平台的支持 • 构建应用的平台，实际上是从原先的构造 网络应用程序平台（如LAMP，J2EE等） 衍生的云平台
主要包括将物理硬件虚拟化的平台 • 主机虚拟化：通过虚拟机的方式能够提供软件 方式的虚拟硬件，提高灵活性 • 网络虚拟化：通过虚拟网络，对虚拟机集群进 行隔离 • 存储虚拟化：提供面向对象的存储
• 分析上述各个方法的优缺点
分布式环境下的K-V存储
• 需要做的额外问题是如何将K定位到某个节点 中
• 方法：直接使用哈希？
– 问题：扩展以及缩小的时候所需要移动的数据 – 解决办法：使用一致性哈希
• 哈希方法带来的问题
– 不能进行range的检索 – 方法：进行排序
• 排序方法带来的问题
– 需要存储元数据
主要是使用云计算的方式构建具体的应用，如 电子邮件，办公软件等，不作为平台的选型
将软件作为服务 SaaS (Software as a Service) 将平台作为服务 PaaS (Platform as a Service) 将基础设施作为服务 IaaS (Infrastructure as a Service)
• 核心问题：如何在一个分布式环境下的多
分布式算法的讨论
• Paxos算法达到一个目的，在一组机器内部 获得一个一致的协定，即确定一个值 • 算法需要保证安全性以及活跃性（能够得 出结果） • 前提条件：每一个参与协议的节点都只能 根据自己的内部状态以及别人传入的消息 进行下一步的工作 • 安全性safety：坏的事情永远永远不要发生 • 活跃性liveness：好的事情会最终会发生 （无法定出一个时间的期限，因为消息会
数据存储的格式
• 没有任何格式的文件数据，任意的二进制 流 • 键值对数据，Key-Value Pair • 结构化的数据，组织成数据表格 • 分布式环境下的研究问题 大数据研究中的重点
– 可靠性 – 扩展性 – 安全性
K-V数据的存储
• 在本地中的存储方式
– 哈希表 – 日志 – 顺序表（B树，B+树，排序表等）
Acceptor
Acceptor
Acceptor
k>j
Step 2: Promise
Proposer 1 Proposer 2
• PROMISE n – Acceptor will accept proposals only numbered n or higher
PROMISE j PROMISE k PROMISE k Acceptor
大数据处理的模式
系统结构，方法以及发展趋势
大数据处理的关注对象
• • • • • • 网页数据 各种日志 电信，电信，信令数据 用电数据 政府经济统计数据 社保，银行数据
大数据处理的应用
• • • • • 搜索引擎，网页排序 电信掉线率分析 用户的兴趣点分析，输入法 数据审计 智能翻译
大数据处理的架构思路
• Proposer 1 is ineligible because a quorum has voted for a higher number than j
(b) If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered proposal (if any) that it has accepted.
如何构造一个稳固的分布式系统
• 使用副本状态机 • 什么是副本状态机Replicated State Machine • 副本状态机的容错能力 • 副本状态机的构造基础
– 每一步转换都需要系统中的成员同意，采取一 致行动 – 状态转换时确定性的 – 必须要考虑网络出错，节点出错，消息丢失， 消息延迟，消息乱序的问题