分布式系统原理介绍 - 刘杰 - 百度.pdf

发布时间：2022-06-13 发布人：admin 分类：说明书资料大小：3.15M 资料格式：pdf 举报版权申诉

cab936e7-3fbe-436e-9caf-3dc479ba5d3f.pdf-第1页.png

第1页 / 共72页

cab936e7-3fbe-436e-9caf-3dc479ba5d3f.pdf-第2页.png

第2页 / 共72页

cab936e7-3fbe-436e-9caf-3dc479ba5d3f.pdf-第3页.png

第3页 / 共72页

cab936e7-3fbe-436e-9caf-3dc479ba5d3f.pdf-第4页.png

第4页 / 共72页

cab936e7-3fbe-436e-9caf-3dc479ba5d3f.pdf-第5页.png

第5页 / 共72页

cab936e7-3fbe-436e-9caf-3dc479ba5d3f.pdf-第6页.png

第6页 / 共72页

cab936e7-3fbe-436e-9caf-3dc479ba5d3f.pdf-第7页.png

第7页 / 共72页

cab936e7-3fbe-436e-9caf-3dc479ba5d3f.pdf-第8页.png

第8页 / 共72页

前言

1 概念

1.1 模型

1.1.1 节点

1.1.2 通信

1.1.3 存储

1.1.4 异常

1.1.4.1 机器宕机

1.1.4.2 网络异常

1.1.4.2.1 消息丢失

1.1.4.2.2 消息乱序

1.1.4.2.3 数据错误

1.1.4.2.4 不可靠的TCP

1.1.4.3 分布式系统的三态

1.1.4.4 存储数据丢失

1.1.4.5 无法归类的异常

1.1.4.6 异常处理的原则

1.2 副本

1.2.1 副本的概念

1.2.2 副本一致性

1.3 衡量分布式系统的指标

1.3.1 性能

1.3.2 可用性

1.3.3 可扩展性

1.3.4 一致性

2 分布式系统原理

2.1 数据分布方式

2.1.1 哈希方式

2.1.2 按数据范围分布

2.1.3 按数据量分布

2.1.4 一致性哈希

2.1.5 副本与数据分布

2.1.6 本地化计算

2.1.7 数据分布方式的选择

2.1.8 工程投影

2.2 基本副本协议

2.2.1 中心化副本控制协议

2.2.2 primary-secondary协议

2.2.2.1 数据更新基本流程

2.2.2.2 数据读取方式

2.2.2.3 primary副本的确定与切换

2.2.2.4 数据同步

2.2.3 去中心化副本控制协议

2.2.4 工程投影

2.2.4.1 GFS中的Primary-Secondary协议

2.2.4.2 PNUTS中的Primary-Secondary协议

2.2.4.3 Niobe中的Primary-Secondary协议

2.2.4.4 Dynamo/Cassandra的去中心化副本控制协议

2.2.4.5 Chubby/Zookeeper的副本控制协议

2.2.4.6 Megastore的副本控制协议

2.2.4.7 其他系统的副本控制协议

2.3 Lease机制

2.3.1 基于lease的分布式cache系统

2.3.2 lease机制的分析

2.3.3 基于lease机制确定节点状态

2.3.4 lease的有效期时间选择

2.3.5 工程投影

2.3.5.1 GFS中的Lease

2.3.5.2 Niobe中的Lease

2.3.5.3 Chubby与Zookeeper中的Lease

2.3.5.4 间接使用Lease

2.4 Quorum机制

2.4.1 约定

2.4.2 Write-all-read-one

2.4.3 Quorum定义

2.4.4 读取最新成功提交的数据

2.4.5 基于Quorum机制选择primary

2.4.6 工程投影

2.4.6.1 GFS中的Quorum

2.4.6.2 Dynamo中的Quorum

2.4.6.3 Zookeeper中的Quorum

2.4.6.4 Mola*/Armor*中的Quorum

2.4.6.5 Big Pipe*中的Quorum

2.5 日志技术

2.5.1 数据库系统日志技术简述

2.5.2 Redo Log与Check point

2.5.2.1 问题模型

2.5.2.2 Redo Log

2.5.2.3 Check point

2.5.3 No Undo/No Redo log

2.5.4 工程投影

2.6 两阶段提交协议

2.6.1 问题背景

2.6.2 流程描述

2.6.3 异常处理

2.6.3.1 宕机恢复

2.6.3.1.1 协调者宕机恢复

2.6.3.1.2 参与者宕机恢复

2.6.3.2 响应超时

2.6.3.2.1 协调者在WAIT状态超时

2.6.3.2.2 协调者在COMMIT或ABORT状态超时

2.6.3.2.3 参与者在INIT状态超时

2.6.3.2.4 参与者在READY状态超时

2.6.4 协议分析

2.7 基于MVCC的分布式事务

2.7.1 MVCC简介

2.7.2 分布式MVCC

2.7.3 工程投影

2.7.3.1 Megastore中的MVCC

2.7.3.2 Doris*中的MVCC

2.8 Paxos协议

2.8.1 简介

2.8.2 协议描述

2.8.2.1 节点角色

2.8.2.2 流程描述

2.8.3 实例

2.8.3.1 基本例子

2.8.3.2 批准的Value无法改变

2.8.3.3 一种不可能出现的状态

2.8.3.4 节点异常

2.8.4 竞争及活锁

2.8.5 协议推导

2.8.6 工程投影

2.8.6.1 Chubby中的Paxos

2.8.6.2 Zookeeper中的Paxos

2.8.6.3 Megastore中的Paxos

2.9 CAP理论

2.9.1 定义

2.9.2 CAP理论的意义

2.9.3 协议分析

2.9.3.1 Lease机制

2.9.3.2 Quorum机制

2.9.3.3 两阶段提交协议

2.9.3.4 Paxos协议

3 参考资料

分布式系统原理介绍刘杰

目录前言 ................................................................................................................................................................. 1 1 概念 ............................................................................................................................................................. 2 1.1 模型 .................................................................................................................................................. 2 1.1.1 节点 ....................................................................................................................................... 2 1.1.2 通信 ....................................................................................................................................... 2 1.1.3 存储 ....................................................................................................................................... 2 1.1.4 异常 ....................................................................................................................................... 3 1.2 副本 .................................................................................................................................................. 8 1.2.1 副本的概念 ........................................................................................................................... 8 1.2.2 副本一致性 ........................................................................................................................... 8 1.3 衡量分布式系统的指标 .................................................................................................................. 9 1.3.1 性能 ....................................................................................................................................... 9 1.3.2 可用性 ................................................................................................................................... 9 1.3.3 可扩展性 ............................................................................................................................... 9 1.3.4 一致性 ................................................................................................................................. 10 2 分布式系统原理 ....................................................................................................................................... 11 2.1 数据分布方式 ................................................................................................................................ 11 2.1.1 哈希方式 ............................................................................................................................. 11 2.1.2 按数据范围分布 ................................................................................................................. 13 2.1.3 按数据量分布 ..................................................................................................................... 14 2.1.4 一致性哈希 ......................................................................................................................... 14 2.1.5 副本与数据分布 ................................................................................................................. 16 2.1.6 本地化计算 ......................................................................................................................... 18 2.1.7 数据分布方式的选择 ......................................................................................................... 18 2.1.8 工程投影 ............................................................................................................................. 18 2.2 基本副本协议 ................................................................................................................................ 20 2.2.1 中心化副本控制协议 ......................................................................................................... 20 2.2.2 primary-secondary 协议 ....................................................................................................... 20 2.2.3 去中心化副本控制协议 ..................................................................................................... 23 2.2.4 工程投影 ............................................................................................................................. 24 2.3 Lease 机制....................................................................................................................................... 26 2.3.1 基于 lease 的分布式 cache 系统 ........................................................................................ 26 2.3.2 lease 机制的分析 ................................................................................................................. 28 2.3.3 基于 lease 机制确定节点状态 ........................................................................................... 29 2.3.4 lease 的有效期时间选择 ..................................................................................................... 30 2.3.5 工程投影 ............................................................................................................................. 30 2.4 Quorum 机制................................................................................................................................... 33 2.4.1 约定 ..................................................................................................................................... 33 2.4.2 Write-all-read-one ................................................................................................................ 33 2.4.3 Quorum 定义 ........................................................................................................................ 34 2.4.4 读取最新成功提交的数据 ................................................................................................. 35 2.4.5 基于 Quorum 机制选择 primary ........................................................................................ 36

2.4.6 工程投影 ............................................................................................................................. 37 2.5 日志技术 ........................................................................................................................................ 41 2.5.1 数据库系统日志技术简述 ................................................................................................. 41 2.5.2 Redo Log 与 Check point ..................................................................................................... 41 2.5.3 No Undo/No Redo log .......................................................................................................... 43 2.5.4 工程投影 ............................................................................................................................. 44 2.6 两阶段提交协议 ............................................................................................................................ 45 2.6.1 问题背景 ............................................................................................................................. 45 2.6.2 流程描述 ............................................................................................................................. 45 2.6.3 异常处理 ............................................................................................................................. 47 2.6.4 协议分析 ............................................................................................................................. 49 2.7 基于 MVCC 的分布式事务 .......................................................................................................... 50 2.7.1 MVCC 简介 ......................................................................................................................... 50 2.7.2 分布式 MVCC .................................................................................................................... 51 2.7.3 工程投影 ............................................................................................................................. 52 2.8 Paxos 协议 ...................................................................................................................................... 53 2.8.1 简介 ..................................................................................................................................... 53 2.8.2 协议描述 ............................................................................................................................. 53 2.8.3 实例 ..................................................................................................................................... 55 2.8.4 竞争及活锁 ......................................................................................................................... 58 2.8.5 协议推导 ............................................................................................................................. 59 2.8.6 工程投影 ............................................................................................................................. 61 2.9 CAP 理论 ........................................................................................................................................ 66 2.9.1 定义 ..................................................................................................................................... 66 2.9.2 CAP 理论的意义 ................................................................................................................. 66 2.9.3 协议分析 ............................................................................................................................. 66 3 参考资料 ................................................................................................................................................... 69

前言半年前，同学提出希望学习分布式系统的相关知识，然而笔者发觉缺少一份既有一定理论内容、又贴近工程实践，既深入浅出又较为全面的学习资料。为此，笔者尝试对自己在学习、开发分布式系统过程中获得的一些理论与实践进行总结，进而催生了写作本文的想法。分布式系统理论体系非常庞大，涉及知识面也非常广博，由于笔者的肤浅，本文精心选择了部分在工程实践中应用广泛、简单有效的分布式理论、算法、协议加以介绍。全文分为两大部分，第一部分介绍了分布式系统的一些基本概念并框定了本文的问题模型和问题域，作为后续章节的基础。第二部分介绍了一些分布式系统的理论，在介绍这些理论时，注重引入实例并加以应用，同时将这些理论投影到真实的系统中。在原本的写作计划中，本文还有第三部分的内容。第三部将分析若干有代表性的分布式系统，着重分析第二部分中的理论是如何被综合运用在这些真实的分布式系统中的。在具体写作时，笔者将这部分的内容拆解到第二章各节的“工程投影”中，简要分析了第二章的理论是如何体现在各个典型分布式系统中的。即便如此，笔者觉得后续可以再作一篇《典型分布式系统分析》，从各个系统的角度横向分析这些系统的特点。开发分布式系统需要多方面的知识、技能与经验。受限于作者的能力，本文将讨论的重点集中在分布式层面的协议和算法设计，开发分布式系统所需要的其他方面的知识与技术则不在本文的讨论范围。最后，感谢李海磊先生、吴学林先生对笔者学习、实践分布式系统给予的大力指导；感谢梁建平先生、徐鹏先生对本文提出的诸多宝贵意见和建议。 2012 年 5 月 1

1 概念 1.1 模型一些经典的分布式系统的资料对分布式系统的全貌做了比较详细的介绍[1][2]。为了控制规模，在开始讨论分布式系统的协议、原理与设计之前，首先给出在本文中研究的分布式系统在分布式层面的基本问题模型。后续所有的讨论都限定在这个模型的范围内，超过模型范围的内容则不在本文中讨论。本文尽量精简分布式系统模型是为了控制问题的规模。 A 图例带存储的状态节点无状态节点宕机节点网络通信完全网络分化界限 A A 1.1.1 节点图 1-1 本文的分布式系统模型节点是指一个可以独立按照分布式协议完成一组逻辑的程序个体。在具体的工程项目中，一个节点往往是一个操作系统上的进程。在本文的模型中，认为节点是一个完整的、不可分的整体，如果某个程序进程实际上由若干相对独立部分构成，则在模型中可以将一个进程划分为多个节点。本文不考虑拜占庭问题，即认为节点始终按照约定的分布式协议工作。图 1-1 中以矩形和椭圆形表示了节点。 1.1.2 通信节点与节点之间是完全独立、相互隔离的，节点之间传递信息的唯一方式是通过不可靠的网络进行通信。即一个节点可以向其他节点通过网络发送消息，但发送消息的节点无法确认消息是否被接收节点完整正确收到。在 1.1.4.2 节，将重点讨论这种网络通信异常的问题。图 1-1 中以带箭头的直线表示了消息通信，其中某些节点间使用双箭头表示网络双向可达，而某些节点间只有单箭头表示网络单向可达，而某些节点间没有箭头表示网络完全不可达。 1.1.3 存储节点可以通过将数据写入与节点在同一台机器的本地存储设备保存数据。通常的存储设备有磁 2

盘、SSD 等。存储、读取数据的节点称为有状态的节点，反之称为无状态的节点。如果某个节点 A 存储数据的方式是将数据通过网络发送到另一个节点 B，由节点 B 负责将数据存储到节点 B 的本地存储设备，那么不能认为节点 A 是有状态的节点，而只有节点 B 是有状态的节点。图 1-1 中以矩形节点表示无状态节点，以椭圆形节点表示有状态节点。 1.1.4 异常分布式系统核心问题之一就是处理各种异常(failure)情况。本节着重讨论在本文范围内系统会遇到的各种异常。 1.1.4.1 机器宕机机器宕机是最常见的异常之一。在大型集群中每日宕机发生的概率为千分之一左右。在实践中，一台宕机的机器恢复的时间通常认为是 24 小时，一般需要人工介入重启机器。宕机造成的后果通常为该机器上节点不能正常工作。假设节点的工作流程是三个独立原子的步骤，宕机造成的后果是节点可能在处理完某个步骤后不再继续处理后续步骤。由于本文不考虑拜占庭问题，认为不会出现执行完第一个步骤后跳过第二个步骤而执行第三个步骤的情况。宕机是一个完全随机的事件，在本文中，认为在任何时刻都可能发生宕机，从而造成某些协议流程无法完成。当发生宕机时，节点无法进入正常工作的状态，称之为“不可用”(unavailable)状态。机器重启后，机器上的节点可以重新启动，但节点将失去所有的内存信息。在某些分布式系统中，节点可以通过读取本地存储设备中的信息或通过读取其他节点数据的方式恢复内存信息，从而恢复到某一宕机前的状态，进而重新进入正常工作状态、即“可用”(available)状态。而另一些分布式系统中的某些无状态节点则无需读取读取任何信息就可以立刻重新“可用”。使得节点在宕机后从“不可用”到 “可用”的过程称为宕机恢复。图 1-1 中虚线节点表示宕机的节点。 1.1.4.2 网络异常网络异常是另一类常见的异常形式。在 1.1.2 中已经定义，节点间通过不可靠的网络进行通信。本节定义了本文范畴内的各种网络异常。 1.1.4.2.1 消息丢失消息丢失是最常见的网络异常。对于常见的 IP 网络来说，网络层不保证数据报文(IP fragment) 的可靠传递，在发生网络拥塞、路由变动、设备异常等情况时，都可能发生发送的数据丢失。由于网络数据丢失的异常存在，直接决定了分布式系统的协议必须能处理网络数据丢失的情况。依据网络质量的不同，网络消息丢失的概率也不同，甚至可能出现在一段时间内某些节点之间 3

的网络消息完全丢失的情况。如果某些节点的直接的网络通信正常或丢包率在合理范围内，而某些节点之间始终无法正常通信，则称这种特殊的网络异常为“网络分化”(network partition)。网络分化是一类常见的网络异常，尤其当分布式系统部署在多个机房之间时。图 1-1 中，用虚线分割了两片节点，这两片节点之间彼此完全无法通信，即出现了“网络分化”。例 1.1：某分布式系统部署于两个机房，机房间使用内部独立光纤链路。由于机房间的光纤链路交割调整，两个机房间通信中断，期间，各机房内的节点相互通信正常。更为严重的是，所有的英特网用户都可以正常访问两个机房内对外服务节点。本文后续将讨论出现这种严重的网络分化时，对分布式系统的设计带来的巨大挑战。 1.1.4.2.2 消息乱序消息乱序是指节点发送的网络消息有一定的概率不是按照发送时的顺序依次到达目的节点。通常由于 IP 网络的存储转发机制、路由不确定性等问题，网络报文乱序也是一种常见的网络异常。这就要求设计分布式协议时，考虑使用序列号等机制处理网络消息的乱序问题，使得无效的、过期的网络消息不影响系统的正确性。 1.1.4.2.3 数据错误网络上传输的数据有可能发生比特错误，从而造成数据错误。通常使用一定的校验码机制可以较为简单的检查出网络数据的错误，从而丢弃错误的数据。 1.1.4.2.4 不可靠的 TCP TCP 协议为应用层提供了可靠的、面向连接的传输服务。TCP 协议是最优秀的传输层协议之一，其设计初衷就是在不可靠的网络之上建立可靠的传输服务。TCP 协议通过为传输的每一个字节设置顺序递增的序列号，由接收方在收到数据后按序列号重组数据并发送确认信息，当发现数据包丢失时，TCP 协议重传丢失的数据包，从而 TCP 协议解决了网络数据包丢失的问题和数据包乱序问题。 TCP 协议为每个 TCP 数据段（以太网上通常最大为 1460 字节）使用 32 位的校验和从而检查数据错误问题。TCP 协议通过设置接收和发送窗口的机制极大的提高了传输性能，解决了网络传输的时延与吞吐问题。TCP 协议最为复杂而巧妙的是其几十年来不断改进的拥塞控制算法，使得 TCP 可以动态感知底层链路的带宽加以合理使用并与其他 TCP 链接分享带宽（TCP friendly）。上述种种使得 TCP 协议成为一个在通常情况下非常可靠的协议，然而在分布式系统的协议设计中不能认为所有网络通信都基于 TCP 协议则通信就是可靠的。一方面，TCP 协议保证了 TCP 协议栈之间的可靠的传输，但无法保证两个上层应用之间的可靠通信。通常的，当某个应用层程序通过 TCP 的系统调用发送一个网络消息时，即使 TCP 系统调用返回成功，也仅仅只能意味着该消息被本机的 TCP 协议栈接受，一般这个消息是被放入了 TCP 协议栈的缓冲区中。再退一步讲，即使目的机器的 TCP 协议栈后续也正常收到了该消息，并发送了确认数据包，也仅仅意味着消息达到了对方 4

机器的协议栈，而不能认为消息被目标应用程序进程接收到并正确处理了。当发送过程中出现宕机等异常时，TCP 协议栈缓冲区中的消息有可能被丢失从而无法被目标节点正确处理。更有甚者，在网络中断前，某数据包已经被目标进程正确处理，之后网络立刻中断，由于接收方的 TCP 协议栈发送的确认数据包始终被丢失，发送方的 TCP 协议栈也有可能告知发送进程发送失败。另一方面，TCP 协议只能保证同一个 TCP 链接内的网络消息不乱序，TCP 链接之间的网络消息顺序则无法保证。但在分布式系统中，一个节点向另一个节点发送数据，有可能是先后使用多个 TCP 链接发送，也有可能是同时并发多个 TCP 链接发送，那么发送进程不能认为先调用 TCP 系统调用发送的消息就一定会先于后发送的消息到达对方节点并被处理。由上述分析，在设计分布系统的网络协议时即使使用 TCP 协议，也依旧要考虑网络异常，不能简单的认为使用 TCP 协议后通信就是可靠的。另一方面，如果完全放弃使用 TCP 协议，使用 UDP 协议加自定义的传输控制机制，则会使得系统设计复杂。尤其是要设计、实现一个像 TCP 那样优秀的拥塞控制机制是非常困难的。 1.1.4.3 分布式系统的三态由于网络异常的存在，分布式系统中请求结果存在“三态”的概念。在单机系统中，我们调用一个函数实现一个功能，则这个函数要么成功、要么失败，只要不发生宕机其执行的结果是确定的。然而在分布式系统中，如果某个节点向另一个节点发起 RPC(Remote procedure call)调用，即某个节点 A 向另一个节点 B 发送一个消息，节点 B 根据收到的消息内容完成某些操作，并将操作的结果通过另一个消息返回给节点 A，那么这个 RPC 执行的结果有三种状态：“成功”、“失败”、“超时（未知）”，称之为分布式系统的三态。如果请求 RPC 的节点 A 收到了执行 RPC 的节点 B 返回的消息，并且消息中说明执行成功，则该 RPC 的结果为“成功”。如果请求 RPC 的节点 A 收到了执行 RPC 的节点 B 返回的消息，并且消息中说明执行失败，则该 RPC 的结果为“失败”。但是，如果请求 RPC 的节点 A 在给定的时间内没有收到执行 RPC 的节点 B 返回的消息，则认为该操作“超时”。对于超时的请求，我们无法获知该请求是否被节点 B 成功执行了。这是因为，如果超时是由于节点 A 发向节点 B 的请求消息丢失造成的，则该操作肯定没有被节点 B 成功执行；但如果节点 A 成功的向节点 B 发送了请求消息，且节点 B 也成功的执行了该请求，但节点 B 发向节点 A 的结果消息被网络丢失了或者节点 B 在执行完该操作后立刻宕机没有能够发出结果消息，从而造成从节点 A 看来请求超时。所以一旦发生超时，请求方是无法获知 RPC 的执行结果的。图 1-2 给出了操作成功但超时的例子。 5

分享到：

赞收藏

资料库

分布式系统原理介绍 - 刘杰 - 百度.pdf

相关推荐

课程资源

热门标签

最新资料