在研究Raft算法的時候般婆，看到其是使用狀態(tài)機實現(xiàn)的到腥，于是找了一篇論文，了解了一下狀態(tài)機．

論文原文為Implementing Fault-Tolerant Services Using the State Machine Approach:A Tutorial．這篇文章是作者在讀了論文之后的一些心得蔚袍，一些體會．所以不會跟論文中那樣詳細(xì)乡范，來證明一些公式．當(dāng)然配名，作者的水平有限，理解的跟作者的意思還是有一些差距的晋辆，所以渠脉，希望讀者還是要讀原文，防止作者誤人子弟．

狀態(tài)機

顧名思義瓶佳，狀態(tài)機就是關(guān)于狀態(tài)的一種機器芋膘，其由狀態(tài)變量以及狀態(tài)命令組成，狀態(tài)命令用于改變狀態(tài)機的狀態(tài)．狀態(tài)機的三個組件為:

• client. client向狀態(tài)機發(fā)送一個請求霸饲，要求狀態(tài)機執(zhí)行一條狀態(tài)命令
• 狀態(tài)機．狀態(tài)機負(fù)責(zé)執(zhí)行狀態(tài)命令为朋，維護(hù)狀態(tài)信息
• output. output負(fù)責(zé)狀態(tài)機處理結(jié)果的輸出

狀態(tài)機從宏觀上就包含這三個組件，但是我們在提到狀態(tài)機時贴彼，往往指的只是其中負(fù)責(zé)執(zhí)行狀態(tài)命令潜腻，維護(hù)狀態(tài)信息的狀態(tài)機．相當(dāng)于一臺計算機的操作系統(tǒng)．

狀態(tài)機在執(zhí)行client發(fā)送來的請求時埃儿，有這樣的原則:

• 同一個client發(fā)送來的請求器仗，需要按序執(zhí)行
• 有因果關(guān)系的請求，需要按序執(zhí)行

如果你讀過我前一篇關(guān)于Lamport Clock的文章童番，你會發(fā)現(xiàn)精钮，這不就是要求做到局部有序性嘛．跟Lamport Clock中的局部有序性的定義一樣一樣的．

如果狀態(tài)機的初始狀態(tài)相同，執(zhí)行相同的狀態(tài)命令序列剃斧，結(jié)束狀態(tài)應(yīng)該也相同．也就是說轨香，狀態(tài)機的輸出，應(yīng)該只跟執(zhí)行的狀態(tài)命令序列有關(guān)幼东，跟操作系統(tǒng)臂容，時間等沒有關(guān)系．

下面是一個狀態(tài)機的例子.client輪詢傳感器的值，發(fā)送給狀態(tài)機根蟹，狀態(tài)機進(jìn)行處理脓杉，并發(fā)送給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

如果我們把讀取傳感器的值并發(fā)送給狀態(tài)機的這個操作，放在狀態(tài)機內(nèi)部简逮，也就是pc內(nèi)部中球散，那么這就不是一個狀態(tài)機了．因為這樣就沒有client了．

分布式系統(tǒng)中的兩種錯誤

• 拜占庭式錯誤．拜占庭式錯誤指的是，狀態(tài)機可能發(fā)生任何錯誤散庶，比如蕉堰，客戶端發(fā)送給狀態(tài)機的請求由于網(wǎng)絡(luò)延時而無序到達(dá)，又比如悲龟，客戶端發(fā)送給狀態(tài)機的請求被修改．本來是要修改狀態(tài)機中變量a的值為1屋讶，結(jié)果被篡改為修改變量a的值為2.
• Fail-stop Failures.　這種錯誤指的是，當(dāng)發(fā)生了錯誤時须教，組件會處于失敗狀態(tài)皿渗，別的組件可以檢測到其發(fā)生了錯誤．這種錯誤并不會有請求被篡改的這種問題．

我們后面的討論也是建立在這兩種錯誤的基礎(chǔ)上的．

容錯性狀態(tài)機

如果我們要讓狀態(tài)機的可容錯率為t，那么我們應(yīng)該有多少個狀態(tài)機呢?

先看最簡單的情況，即我們假設(shè)只會發(fā)生Fail-stop Failures這個錯誤．那么很簡單羹奉，我們需要有t+1個狀態(tài)機．這樣秒旋，即使t個狀態(tài)機發(fā)生了錯誤，我們還是會通過剩下的那一個正確的狀態(tài)機獲取正確的結(jié)果．

再看另一種情況诀拭，就是我們假設(shè)會發(fā)生拜占庭式錯誤．我們在獲取狀態(tài)機的值的時候迁筛，是需要聚合全部狀態(tài)機的對應(yīng)的值的．比如說，要獲取狀態(tài)機中變量ａ的值耕挨，我們需要獲取全部狀態(tài)機中變量ａ的值细卧，然后進(jìn)行合并，假設(shè)有5臺狀態(tài)機筒占，三臺的值為1,兩臺的值為2,那么我們會認(rèn)為1為正確的值．也就是說贪庙，我們總共需要2t+1臺狀態(tài)機．+1是因為我們認(rèn)為占多數(shù)的值為正確的值．

要實現(xiàn)容錯性狀態(tài)機，我們需要保證以下條件:
Replica Coordination: 全部的狀態(tài)機都收到并且處理相同的請求序列

我們可以進(jìn)一步將其拆分成下面兩條:

• Agreement. 每一臺正常運行的狀態(tài)機翰苫，都會收到每一個請求止邮，不會出現(xiàn)丟失請求的情況
• Order. 每一臺正常運行的狀態(tài)機，都按相同的相對順序來處理它收到的請求．

注意在Order這一條中奏窑，我們說的是按相同的相對順序导披，我們在對狀態(tài)機的介紹中，也提到了埃唯，狀態(tài)機要求的是局部有序性．這就導(dǎo)致可能會從兩個client撩匕， client1 和　client2中，收到兩個并發(fā)的請求墨叛，有相同的時間戳止毕，假設(shè)為5．Order要求所有的狀態(tài)機，都按照相同的順序來處理這兩條并發(fā)的請求．可以都是先處理client1,然后再處理client2漠趁，也可以都是先處理client2扁凛，然后再處理client1,這是沒有關(guān)系的，因為它們是并發(fā)的請求．只要保證按照相同的順序來處理就好了．

在有些情況下棚潦，我們可以弱化這兩個要求．

比如令漂，如果我們假設(shè)只會發(fā)生Fail-Stop Failure,并且只會收到讀請求，那么Agreement可以被弱化成只要一臺正常運行的狀態(tài)機收到這個讀請求就好啦．很容易理解．

再比如丸边，假設(shè)請求的順序可以是互換的叠必，那么Order就沒有必要滿足．那什么是可以互換的請求呢?如果狀態(tài)機先執(zhí)行請求1再執(zhí)行請求2，和先執(zhí)行請求2,再執(zhí)行請求1,最后得到的狀態(tài)都是一致的妹窖，那么我們就稱這兩個請求是可互換的．

比如纬朝，我們處理一個投票請求．假設(shè)每個客戶端最多可以投一次票，并且只有當(dāng)一個候選者獲得大多數(shù)選票時骄呼，才選擇它．那么我們很容易就能知道請求的順序是可以互換的．比如共苛，假設(shè)總共有10個客戶端進(jìn)行投票判没，候選者A和候選者B此時分別得到了4票．由上面的假設(shè)，我們很容易地知道隅茎，只有其中一個候選者得到了6票時澄峰，我們才會選擇它．現(xiàn)在還剩下兩票，可能的情況為:都投A,都投B,投A一票投B一票．我們很容易地就能得知辟犀，此時跟選票的順序并沒有什么關(guān)系．此時Order不滿足就沒有關(guān)系．

但是俏竞，我們稍微改變一下假設(shè)的前提條件，那么結(jié)果就是天壤之別了．假設(shè)每個客戶端還是最多可以投一次票堂竟，但是當(dāng)一個候選者不必獲得大多數(shù)選票時魂毁，我們就可以選他．一種情況就是只要一個候選者獲取到一半選票時，我們就可以選它．那么在上面的那個例子中出嘹，我們很容易的就可以得知席楚，結(jié)果是跟順序有關(guān)的．也就是說，選票的順序不是可互換的．

我們再假設(shè)候選者還是必須獲得大多數(shù)選票時税稼，我們才可以選他．但是客戶端可以提出不只一個選票．那么在上面的例子中烦秩，假設(shè)到最后的兩個客戶端，我們假設(shè)為客戶端１和客戶端２娶聘，客戶端１提出兩個選票闻镶，其均為投候選者A甚脉，客戶端2也提出兩個選票丸升，其均為投B.很明顯也是不符合可互換性的．

滿足Agreement

我們可以通過引入一個新的組件，稱為transmitter牺氨，它負(fù)責(zé)向其他的組件發(fā)送一個值狡耻，只要滿足以下條件，那么就能滿足Aggrement:

• 全部的正常運行的processors同意同一個值
• 如果transmitter正常運行猴凹，那么其他的正常運行的processors均使用它的值作為它們同意的那個值

這種協(xié)議已經(jīng)引起了學(xué)術(shù)界的關(guān)注．目前也已經(jīng)有相應(yīng)的協(xié)議產(chǎn)生了．

我們可以將client作為transmitter,也可以單獨設(shè)置這樣一個組件．但是如果單獨設(shè)置這樣一個組件的話夷狰，我們需要確保請求在發(fā)送到trasmitter的過程中，丟失或者被篡改．我們可以通過讓client也接收transmitter發(fā)送的請求郊霎，來避免這種情況．

滿足Order和Stability

論文原文中沼头，并沒有給出Stability的定義，但是通過下文的一些信息书劝，我認(rèn)為Stability的定義為:如果一個請求是stable的进倍，那么它就會執(zhí)行，否則它不會被執(zhí)行．

那么如何實現(xiàn)Order呢购对？論文中提出了三種方式猾昆，一種是Logical Clock,一種是Synchronized Real-Time Clocks，最后一種是Replica-Generated Identifiers．但是由于最后一種我讀了好幾遍也沒有理解其思想骡苞，想不明白如何實現(xiàn)垂蜗，所以這里我并不會介紹．感興趣的讀者請自行查看原論文．

另外楷扬，對于Logical Clock和Synchronized Real-Time Clocks，它們的介紹贴见，這里也不再介紹了．如果有不懂得朋友烘苹，請自行Google，或者查看我的關(guān)于Lamport Logical Clocks的文章片部，其中就包含了這兩種方式．

Logical Clocks

Logical Clocks的實現(xiàn)方式螟加，能夠容錯Fail-stop failure.它的實現(xiàn)方式為，每個客戶端都隔一段時間就給狀態(tài)機發(fā)送一個請求吞琐，可以發(fā)送空請求．那么這個請求有什么作用呢捆探？狀態(tài)機會取出這個請求的時間戳，然后跟本地等待隊列中的請求的時間戳做比較站粟，然后將那些有比全部客戶端發(fā)送的請求的最小的時間戳都小的時間戳的請求黍图，變?yōu)?strong>stable狀態(tài)，即讓它們可以被狀態(tài)機讀取執(zhí)行了．

比如說奴烙，狀態(tài)機A的本地等待隊列中助被，有兩個請求，一個時間戳是1,一個時間戳是2．有三個客戶端給狀態(tài)機A發(fā)送了三個請求切诀，它們的時間戳分別是2,3,4．那么狀態(tài)機A的本地等待隊列中揩环，時間戳為1的那個請求，會被轉(zhuǎn)換為stable狀態(tài)幅虑，而時間戳為2的那個請求丰滑，則不會被轉(zhuǎn)換為stable狀態(tài)．需要繼續(xù)等待．

關(guān)于其為何能夠容錯Fail-stop failure的證明，請各位朋友自行讀原論文了解．

Synchronized Real-Time Clocks

Synchronized Real-Time Clocks能夠容錯Byzantine Failures.它的實現(xiàn)方式為:

• 在狀態(tài)機中倒庵，只有一個請求的時間戳比狀態(tài)機的時間戳-最大請求傳輸時間要小時褒墨，才會被轉(zhuǎn)換為stable狀態(tài)．
• 如果在狀態(tài)機中，它收到了一個請求A．并且它還從其他的全部client收到了請求．如果每一個client發(fā)送的請求中擎宝，都有一個時間戳比請求A的時間戳大的請求郁妈，那么請求A就會被轉(zhuǎn)換為stable狀態(tài)．

關(guān)于其證明，同樣請各位朋友自行讀原論文了解．

后記

這篇文章中绍申，由于目前有些地方理解的不透徹噩咪，故省略了原論文中的一些內(nèi)容，比如Replica-Generated Identifiers, Tolerating faulty output devices, Tolerating fault clients, configuration, repair errors等．所以极阅，想深入了解其原理的朋友胃碾，務(wù)必讀原論文．