分布式系统基础-State Machine

在研究Raft算法的时候,看到其是使用状态机实现的,于是找了一篇论文,了解了一下状态机.

论文原文为Implementing Fault-Tolerant Services Using the State Machine Approach:A Tutorial.这篇文章是作者在读了论文之后的一些心得,一些体会.所以不会跟论文中那样详细,来证明一些公式.当然,作者的水平有限,理解的跟作者的意思还是有一些差距的,所以,希望读者还是要读原文,防止作者误人子弟.

状态机

顾名思义,状态机就是关于状态的一种机器,其由状态变量以及状态命令组成,状态命令用于改变状态机的状态.状态机的三个组件为:

  • client. client向状态机发送一个请求,要求状态机执行一条状态命令
  • 状态机.状态机负责执行状态命令,维护状态信息
  • output. output负责状态机处理结果的输出

状态机从宏观上就包含这三个组件,但是我们在提到状态机时,往往指的只是其中负责执行状态命令,维护状态信息的状态机.相当于一台计算机的操作系统.

状态机在执行client发送来的请求时,有这样的原则:

  • 同一个client发送来的请求,需要按序执行
  • 有因果关系的请求,需要按序执行

如果你读过我前一篇关于Lamport Clock的文章,你会发现,这不就是要求做到局部有序性嘛.跟Lamport Clock中的局部有序性的定义一样一样的.

如果状态机的初始状态相同,执行相同的状态命令序列,结束状态应该也相同.也就是说,状态机的输出,应该只跟执行的状态命令序列有关,跟操作系统,时间等没有关系.

下面是一个状态机的例子.client轮询传感器的值,发送给状态机,状态机进行处理,并发送给actuator:

monitor:
    process
        do true -> val := sensor;
            <pc.adjust, val>;
            delay D
        od
    end monitor
pc: state_machine
    var q:real;
    
    adjust:
        command(sensor_val:real)
        q := F(q, sensor_val);
        send q to actuator
        end adjust
    end pc

如果我们把读取传感器的值并发送给状态机的这个操作,放在状态机内部,也就是pc内部中,那么这就不是一个状态机了.因为这样就没有client了.

分布式系统中的两种错误

  • 拜占庭式错误.拜占庭式错误指的是,状态机可能发生任何错误,比如,客户端发送给状态机的请求由于网络延时而无序到达,又比如,客户端发送给状态机的请求被修改.本来是要修改状态机中变量a的值为1,结果被篡改为修改变量a的值为2.
  • Fail-stop Failures. 这种错误指的是,当发生了错误时,组件会处于失败状态,别的组件可以检测到其发生了错误.这种错误并不会有请求被篡改的这种问题.

我们后面的讨论也是建立在这两种错误的基础上的.

容错性状态机

如果我们要让状态机的可容错率为t,那么我们应该有多少个状态机呢?

先看最简单的情况,即我们假设只会发生Fail-stop Failures这个错误.那么很简单,我们需要有t+1个状态机.这样,即使t个状态机发生了错误,我们还是会通过剩下的那一个正确的状态机获取正确的结果.

再看另一种情况,就是我们假设会发生拜占庭式错误.我们在获取状态机的值的时候,是需要聚合全部状态机的对应的值的.比如说,要获取状态机中变量a的值,我们需要获取全部状态机中变量a的值,然后进行合并,假设有5台状态机,三台的值为1,两台的值为2,那么我们会认为1为正确的值.也就是说,我们总共需要2t+1台状态机.+1是因为我们认为占多数的值为正确的值.

要实现容错性状态机,我们需要保证以下条件:
Replica Coordination: 全部的状态机都收到并且处理相同的请求序列

我们可以进一步将其拆分成下面两条:

  • Agreement. 每一台正常运行的状态机,都会收到每一个请求,不会出现丢失请求的情况
  • Order. 每一台正常运行的状态机,都按相同的相对顺序来处理它收到的请求.

注意在Order这一条中,我们说的是按相同的相对顺序,我们在对状态机的介绍中,也提到了,状态机要求的是局部有序性.这就导致可能会从两个client, client1 和 client2中,收到两个并发的请求,有相同的时间戳,假设为5.Order要求所有的状态机,都按照相同的顺序来处理这两条并发的请求.可以都是先处理client1,然后再处理client2,也可以都是先处理client2,然后再处理client1,这是没有关系的,因为它们是并发的请求.只要保证按照相同的顺序来处理就好了.

在有些情况下,我们可以弱化这两个要求.

比如,如果我们假设只会发生Fail-Stop Failure,并且只会收到读请求,那么Agreement可以被弱化成只要一台正常运行的状态机收到这个读请求就好啦.很容易理解.

再比如,假设请求的顺序可以是互换的,那么Order就没有必要满足.那什么是可以互换的请求呢?如果状态机先执行请求1再执行请求2,和先执行请求2,再执行请求1,最后得到的状态都是一致的,那么我们就称这两个请求是可互换的

比如,我们处理一个投票请求.假设每个客户端最多可以投一次票,并且只有当一个候选者获得大多数选票时,才选择它.那么我们很容易就能知道请求的顺序是可以互换的.比如,假设总共有10个客户端进行投票,候选者A和候选者B此时分别得到了4票.由上面的假设,我们很容易地知道,只有其中一个候选者得到了6票时,我们才会选择它.现在还剩下两票,可能的情况为:都投A,都投B,投A一票投B一票.我们很容易地就能得知,此时跟选票的顺序并没有什么关系.此时Order不满足就没有关系.

但是,我们稍微改变一下假设的前提条件,那么结果就是天壤之别了.假设每个客户端还是最多可以投一次票,但是当一个候选者不必获得大多数选票时,我们就可以选他.一种情况就是只要一个候选者获取到一半选票时,我们就可以选它.那么在上面的那个例子中,我们很容易的就可以得知,结果是跟顺序有关的.也就是说,选票的顺序不是可互换的

我们再假设候选者还是必须获得大多数选票时,我们才可以选他.但是客户端可以提出不只一个选票.那么在上面的例子中,假设到最后的两个客户端,我们假设为客户端1和客户端2,客户端1提出两个选票,其均为投候选者A,客户端2也提出两个选票,其均为投B.很明显也是不符合可互换性的.

满足Agreement

我们可以通过引入一个新的组件,称为transmitter,它负责向其他的组件发送一个值,只要满足以下条件,那么就能满足Aggrement:

  • 全部的正常运行的processors同意同一个值
  • 如果transmitter正常运行,那么其他的正常运行的processors均使用它的值作为它们同意的那个值

这种协议已经引起了学术界的关注.目前也已经有相应的协议产生了.

我们可以将client作为transmitter,也可以单独设置这样一个组件.但是如果单独设置这样一个组件的话,我们需要确保请求在发送到trasmitter的过程中,丢失或者被篡改.我们可以通过让client也接收transmitter发送的请求,来避免这种情况.

满足Order和Stability

论文原文中,并没有给出Stability的定义,但是通过下文的一些信息,我认为Stability的定义为:如果一个请求是stable的,那么它就会执行,否则它不会被执行.

那么如何实现Order呢?论文中提出了三种方式,一种是Logical Clock,一种是Synchronized Real-Time Clocks,最后一种是Replica-Generated Identifiers.但是由于最后一种我读了好几遍也没有理解其思想,想不明白如何实现,所以这里我并不会介绍.感兴趣的读者请自行查看原论文.

另外,对于Logical ClockSynchronized Real-Time Clocks,它们的介绍,这里也不再介绍了.如果有不懂得朋友,请自行Google,或者查看我的关于Lamport Logical Clocks的文章,其中就包含了这两种方式.

Logical Clocks

Logical Clocks的实现方式,能够容错Fail-stop failure.它的实现方式为,每个客户端都隔一段时间就给状态机发送一个请求,可以发送空请求.那么这个请求有什么作用呢?状态机会取出这个请求的时间戳,然后跟本地等待队列中的请求的时间戳做比较,然后将那些有比全部客户端发送的请求的最小的时间戳都小的时间戳的请求,变为stable状态,即让它们可以被状态机读取执行了.

比如说,状态机A的本地等待队列中,有两个请求,一个时间戳是1,一个时间戳是2.有三个客户端给状态机A发送了三个请求,它们的时间戳分别是2,3,4.那么状态机A的本地等待队列中,时间戳为1的那个请求,会被转换为stable状态,而时间戳为2的那个请求,则不会被转换为stable状态.需要继续等待.

关于其为何能够容错Fail-stop failure的证明,请各位朋友自行读原论文了解.

Synchronized Real-Time Clocks

Synchronized Real-Time Clocks能够容错Byzantine Failures.它的实现方式为:

  • 在状态机中,只有一个请求的时间戳比状态机的时间戳-最大请求传输时间要小时,才会被转换为stable状态.
  • 如果在状态机中,它收到了一个请求A.并且它还从其他的全部client收到了请求.如果每一个client发送的请求中,都有一个时间戳比请求A的时间戳大的请求,那么请求A就会被转换为stable状态.

关于其证明,同样请各位朋友自行读原论文了解.

后记

这篇文章中,由于目前有些地方理解的不透彻,故省略了原论文中的一些内容,比如Replica-Generated Identifiers, Tolerating faulty output devices, Tolerating fault clients, configuration, repair errors等.所以,想深入了解其原理的朋友,务必读原论文.

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 214,922评论 6 497
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,591评论 3 389
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 160,546评论 0 350
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,467评论 1 288
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,553评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,580评论 1 293
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,588评论 3 414
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,334评论 0 270
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,780评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,092评论 2 330
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,270评论 1 344
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,925评论 5 338
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,573评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,194评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,437评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,154评论 2 366
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,127评论 2 352

推荐阅读更多精彩内容

  • Spring Cloud为开发人员提供了快速构建分布式系统中一些常见模式的工具(例如配置管理,服务发现,断路器,智...
    卡卡罗2017阅读 134,647评论 18 139
  • 可进入我的博客查看原文。 Raft 算法是可以用来替代 Paxos 算法的分布式一致性算法,而且 raft 算法比...
    Jeffbond阅读 13,323评论 4 91
  • 实时消息协议---流的分块 版权声明: 版权(c)2009 Adobe系统有限公司。全权所有。 摘要: 本备忘录描...
    一个人zy阅读 1,895评论 0 9
  • 开放源代码已经成为一些大型网站的基本原则。而在这些网站成长的过程中,一些优秀的实践经验和规则也出现在他们的结构中。...
    零一间阅读 1,013评论 0 4
  • 一不小心 我被命运之神 踢进了万丈深渊 我本能的挣扎着 痛苦的嚎叫着 并不是有意打扰您 您完全可以视而不见 充...
    呆萌的老张看世界687阅读 766评论 6 13