分布式系统原理 刘杰

分布式系统原理 刘杰 讲的很基础 很详细 适合新手入门24.6工程投影3725日忐技术2.51数据库系统日志技术简述…252 Redo Log与Chck412.5.3 No Undo/No Redo log.2.54工程投影….4426两阶段提交协议2.6.1问题背景…452.6.2流程描述452.6.3异常处埋………······:···*472.6.4协议分析…27基于MVCC的分布式事务27MVCC简介502.7.2分布式MVCC…512.73⊥程投影5228 Paxos协议28.1简介28.2协议描述….5328.3实例2.84竞争及活锁.2.8.5协议推导…286程投影·+““+“*+++“+“+“+··+++“““·+·“““29CAP埋论…2.9.1定义292CAP理论的意义66293协议分析663参考资料前言半年前,冋学提出希望学习分布式系统的相关知识,然而笔者发觉缺少一份既有一定理论内容又贴近工程实践,既深入浅出又较为全面的学习资料。为此,笔者尝试对自己在学习、开发分布式系统过程中获得的一些理论与实践进行总结,进而催生了写作木文的想法。分布式系统理论体系非常庞大,涉及知识面也非常广博,由于笔者的肽浅,本文精心选择了部分在程实中应用广泛、简单有效的分布式理论、算法、协议加以介绍。全文分为两大部分,第一部分介绍了分冇式系统的一些基本概念并框定了本文的问题模型和问题域,作为后续章节的基础。第二部分介绍了一些分布式系统的理论,在介绍这些理论时,注重引入实例并加以应用,同时将这些理论投影到真实的系统中在原本的写作计划中,本文还有第三部分的内容。第三部将分析若干有代表性的分布式系统着重分析第二部分中的理论是如何被综合运用在这些真实的分布式系统中的。在具体写作时,笔者将这部分的内容拆解到第二章各节的“工程投影”中,简要分析了第二章的理论是如何体现在各个典型分布式系统中的。即便如此,笔者觉得后续可以再作一篇《典型分布式系统分析》,从各个系统的角度横向分析这些系统的特点开发分布式系统需要多方面的知识、技能与经验。受限于作者的能力,本文将讨论的重点集中在分布式层面的协议和算法设计,开发分布式系统所需要的其他方面的知识与技术则不在本文的讨论范围。最后,感谢李海磊先生、吴学林先生对笔者学习、实饯分布式系统给了的大力指导;感谢梁建平先生、徐朋先生对木文提出的诸多宝贵意见和建议。2012年5月1概念1.1模型一些经典的分布式系统的资料对分布式系统的全貌做了比较详细的介绍[1I2]。为了控制规模,在开始讨论分布式系统的协议、原理与设计之前,首先给出在本文中研究的分布式系统在分布式层面的基本问题模型。后续所有的讨论都限定在这个模型的范围内,超过模型范围的内容则不在本文中讨论。本文尽量精简分布式系统模型是为了控制问题的规模。图例○带存储的状态节点匚无状态节点宕机节点■■■>网络通信完全网络分化界限图1-1本文的分布式系统模型1.1.1节点节点是指一个可以独立按照分布式协议完成一组逻辑的程序个体。在具体的工程项目中,一个节点往往是一个操作系统上的进程。在本文的模型中,认为节点是一个完整的、不可分的整体,如果某个程序进程实际上由若干相对独立部分构成,则在模型中可以将一个进程划分为多个节点。本文不考虑拜占庭问题,即认为节点始终按照约定的分布式协议上作。图1-1中以矩形和椭圆形衣示了节点。1.2通信节点与节点之间是完仝独立、相工隔离的,节点之间传递信息的唯一方式是通过不可靠的网络进行通信。即一个节点可以向其他节点通过网络发送消息,但发送消息的节点无法确认消息是否被接收节点完整正确收到。在1.1.4.2节,将重点讨论这种网络通信异常的问题。图1-1中以带箭头的育线表示了消息通信,其中某些节点间使用双箭头表示网终双向可达,而某些节点间只有单箭头表示网络单向可达,而某些节点间没有箭头表示网络完全不可达。1.1.3存储节点可以通过将数据写入与节点在同·台杌器的本地仔储设备保存数据。通常的存储设备有磁盘、SSD等。存储、读取数据的节点称为有状态的节点,反之称为无状态的节点。如果某个节点A存储数据的方式是将数据通过网络发送到另一个节点B,由节点B负责将数据存储到节点B的本地存储设备,那么不能认为节点A是有状态的节点,而只有节点B是有状态的节点。图1-1中以矩形节点表小无状态节点,以椭圆形节点表小有状态节点1.1.4异常分布式系统核心问题之一就是处理各种异常( failure)情况。本节着重讨论在本文范围内系统会遇到的各种异常1.1.41机器宕机机器宕机是最常见的异常之一。在大型集群中每日宕机发生的概率为千分之一左右。在实践中台宕机的机器恢复的时间通常认为是24小时,一般需要人工介入重启机器。宕机造成的后果通常为该机器上节点不能正常工作。假设节点的工作流程是三个独立原子的步骤,宕机造成的后果是节点可能在处理完某个步骤后不再继续处理后续步骤。由于本文不考虑拜占庭问题,认为不会出现执行完第一个步骤后跳过第二个步骤而执行第三个步骤的情况。宕机是一个完全随机的事件,在本文中,认为在任何时刻都可能发生宕机,从而造成某些协议流程无法完成。当发生宕机时,节点无法进入正常⊥作的状态,称之为“不可用”( unavailable)状态。机器重启后,机器上的节点可以重新启动,但节点将失去所有的内存信息。在某些分布式系统中,节点可以通过读取本地存储设备中的信息或通过读取其他节点数据的方式恢复内存信息,从而恢复到某一宕机前的状态,进而重新进入正常二作状态、即“可用”( availab)状态。而另些分布式系统中的某些无状态节点则无需读取读取任何信息就可以立刻重新“可用”。使得节点在宕札后从“不可用”到可用”的过程称为宕札恢复。图1-1中虚线节点表示宕机的节点。1.1.42网络异常网络异常是力一类常见的异常形式。在1.1.2中已经定义,节点间通过不可靠的网络进行通信。本节定义了本文范畴内的各种网络异常。1.142.1消息丢失消息丟失是最常见的网终异常。对于常见的P网络来说,网络层不保证数据报文( IP fragment的可靠传递,在发生网络拥塞、路由变动、设备异常等情况时,都可能发生发送的数据丢失。由于网络数据丢失的异常存在,直接决定了分布式系统的协议必须能处理网络数据丢失的情况依据网络质量的不同,网络消息丢失的概率也不同,甚至可能出现在一段时间内某些节点之间的网络消息完全丢失的情况。如果某些节点的直接的网络通信止常或丢包率在合理范围内,而某些节点之间始终无法正常通信,则称这种特殊的网终异常为“网终分化”( network partition)。络分化是一类常见的网络异常,尤其当分布式系统部署在多个机房之间时。图1-1中,用虚线分割了两片节点,这两片节点之间彼此完全无法通信,即出现了“终分化”例1.1:某分布式系统部署于两个机房,机房间使用内部独立光纤链路。由于机房间的光纤链路交割调整,两个机房间通信中断,期间,各机房内的节点相互通信正常。更为严重的是,所有的英特网用户都可以正常访问两个机房内对外服务节点。本文后续将讨论出现这种严重的网络分化时,对分布式系统的设计带来的巨大挑战。1.1.422消息乱序消息乱序是指节点发送的网络消息有一定的概率不是按照发送时的顺序依次到达目的节点。通常由于网终的存储转发机制、路由不确定性等问题,网络报文乱序也是一种常见的网终异常。这就要求设计分布式协议时,考虑使用序列号等机制处理网络消息的乱序问题,使得无效的、过期的网络消息不影响系统的正确性1.1.4.2.3数据错误网络上传输的数据有可能发生比特错误,从而造成数据错误。通常使用一定的校验码机制可以较为简单的检查出网终数据的错误,从而丢弃错误的数据。1.1424不可靠的TCPTCP协议为应用层提供了可靠的、面向连接的传输服务。TCP协议是最优秀的传输层协议之其设计初衷就是在不可靠的网络之上建立可靠的传输服务。TCP协议通过为传输的每一个字节设置顺序递增的序列号,由接收方在收到数据后按序列号重组数据并发送确认信息,当发现数据包丢失时,TCP协议重传丢失的数据包,从而TCP协议解决了网终数据包丢失的问题和数据包乱序问题。TCP协议为每个TCP数据段(以太网上通常最人为1460字节)使用32位的校验和从而检査数据错误问题。TCP协议通过设置接收和发送窗口的杋制极人的提高了传输性能,解决了网络传输的时延与吞吐问题。TCP协议最为复杂而巧妙的是其几十年来不断改进的拥寒控制算法,使得TCP可以动态感知底层链路的带宽加以合理使用并与其他TCP链接分享带宽( TCP friendly)。上述种种使得TCP协议成为一个在通常情况下非常可靠的协议,然而在分布式系统的协议设计中不能认为所有网络通信都基于TCP协议则通信就是可靠的。一方面,TCP协议保证」TCP协以栈之间的可靠的传输,但无法倮证两个上层应用之间的可靠通信。通常的,当某个应用层程序通过TCP的系统调用发送一个网络消息时,即使TCP系统调用返回成功,也仅仅只能意味着该消息被本机的TCP协议栈接受,一般这个消息是被放入」TCP协议栈的缓冲区中。再退一步讲,即使目的机器的TCP协议栈后续也正常收到了该消息,并发送了确认数据包,也仅仅意味着消息达到了对方机器的协议栈,而不能认为消息被目标应用程序进程接收到并止确处理了ε当发送过程中出现宕札等异常时,TCP办议栈缓冲区中的消息有可能被丟失从而无法被目标节点正确处理。更有甚者,在网终中断前,某数据包已经被目标进程正确处理,之后网络立刻中断,由于接收方的TCP协议栈发送的确认薮据包始终被丟失,发送方的TCP协议栈乜有可能告知发送进程发送失败。另一方面,TCP协议只能保证同一个TCP链接内的网络消息不乱序,TCP链接之间的网络消息顺序则无法保证。但在分布式系统中,一个节点向另一个节点发送数据,有可能是先后使用多个TCP链接发送,也有可能是同时并发多个TCP链接发送,那么发送进程不能认为先调用TCP系统调用发送的消息就一定会先于后发送的消息到达对方节点并被处理由上述分析,在设计分布系统的网络协议时即使使用TCP协议,也依旧要考虑网络异常,不能简单的认为使用TCP协议后通信就是可靠的。另方面,如果完全放弃使用TCP协议,使用UDP协议加自定义的传输控制机制,则会使得系统设计复尔。尤其是要设计、实现个像TCP那样优秀的拥塞控制机制是非常困难的1.143分布式系统的三态由于网络异常的存在,分布式系统中请求结果存在“三态”的概念。在单机系统中,我们调用个函数实现一个功能,则这个函数要么成功、要么失败,只要不发生宕机其执行的结果是确定的。然而在分布式系统中,如果某个节点向另一个节点发起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成功执行:但如果节点Δ成功的向节点B发送了请求消息,且节点B也成功的执行∫该请求,但节点B发向节点A的结果消息被网终丢失∫或者节点B在执行完该操作后立刻宕机没有能够发出结果消息,从而造成从节点A看来请求超时。所以一旦发生超时,请求方是无法获知RPC的执行结果的。图1-2给出了撅作成功但超时的例子。ClientServerClientRPC请求请求网络异常成功处理请求成功处理请求一k-发送RPC响应失贩sever宕机图1-2RPC执行成功但超时的例子一个非常易于理解的例子是在网上银行进行转账操作,当系统超时,页面提示:“如果系统长时间未返回,请检查账户余额以确认交易是否成功分布式系统一般需要区别对待RPC的“成功”“失败”、“超时”三种状态。当出现“超时”时可以通过发起读取数据的操作以验证RPC是否成功(例如银行系统的做法)。另一种简单的做法是,设计分布式协议吋将执行步骤设计为可重试的,即具有所谓的“幂等性”。例如覆盖写就是·种常见的幂等性操作,因为重复的覆盖写最终的结果都相等。如果使用可重试的设计,当出现“失败”和“超时”时,一律重试操作直到“成功”。这样,即使超时的操作实际上凵经成功了,重试操作也不会对正确性造成影响,从而简化了设计。后续本文中,如果说明“不成功”即指“失败”或“超时”两种状态之一。如果说明“失败”则表示收到了明确的“失败”消息。1.1.44存储数据丢失数据丟失指节点存储的数据不可被读取或读取出的数据错误。数据丢失是另一类常见的异常尤其是使用机械硬馄做存储介质时,硬囧损坏的概率较大。对于有状态节点来说,数据丢失意味着状态丢失,通常只能从其他节点读取、恢复存储的状态1.14.5无法归类的异常在工程实践中,大量异常情况是无法预先可知的,更可恶的是这些异常往往是“半死不活”的状态。例如,磁盘枚障会导致I操作缓慢,从而有可能使得进程运行速度非常慢,“缓慢”是异常吗?如果慢的超过某种程度,则对系统会造成影响。更有甚者,几十秒进程非常慢甚至完全阻塞住,又几十秒恢复了,如此交替。又例如网络不稳定时也会引起“半死不活”异常,例如网络发生严重拥塞时约等于网络不通,过一会儿又恢复,恢复后又拥塞,如此交替。对于这些极端的无法预先归类的异常,需要在具体的项目中,通过长期的工程实践调整应对。1.14.6异常处理的原则在设计、推导、验证分布式系统的协议、流程时,最重要的工作之一就是思考在执行流程的每个步骤时一旦发生各种异常的情况下系统的处理方式及造成的影响。例1.2:某分布式协议实现一个echo功能,即由节点A向节点B发送一个消息,内容是一个整数,节点B收到后返回相同的消息。节点A发送的消息每次递増加1。节点A的处理流程为1.向节点B发送一个消息,消息内容为当前需要发送的整数2.等待接收从节点B发回的响应消息3.若B发回的消息等于当前需要发送的整数,a)将当前需要发送的整数加1;b)否则返回1;上述简单的流程可能遇到各种异常且不能正确处理:第一、当前需要发送的整数没有持久化,在上述流程中,一旦节点A宕机,节点A无法继续上述流程。第二、节点B一旦宕机,节点A不公收到响应消息,流稈将卡在第二步无法进行下去。第三、若A发给B或B发回A的消息有一个丢失,节点A也不会收到响应消息。在本节中,不讨论如何修改这个流程以处理上述异常,举这个例子是为了说明异常分析的基本方法。被大量工程实饯所检验过的异常处理黄金原则是:任何在设计阶段考虐到的异常情况一定会在系统实际运行中发生,但在系统实际运行遇到的异常却很有可能在设计时未能考虑,所以,除非需求抬标允许,在系统设计时不能放过任何异常情况。工程中常常容易岀问题的一种思眳是认为某种异常岀现的概率非常小以至于可以忽略不计。这种思路的错误在于只注意到了单次异常事件发生的概率,而忽略了样本的大小。即使单次异常概率非常小,由于系统规模和运行时间的作用,事件样本将是一个非常大的值,从而使得异常事件实际发生的概率变大。例如,某系统中某种异常每天发生的概率为103,但系统每天处理的请求数为10次,每次请求都要执行有异常风险的流程,那么系统每天发生这和异常的概率就为1-(110-9)10°=10%。