電話之于短信、微信的一個很大的不同點在于，前者更加及時，有更快速直接的回報；而後面兩個雖然稱之為instant message，但經常時發出去了就得等對方回複，等多久是不确定的。打電話能明确知道對方在不在，我所表達的資訊是否已經傳達；而短信或者微信，隻知道消息發出去了，但對方是否收到，或者是否檢視就不清楚了。
在通過網絡通信的環境下，也是很難知道一個消息對方是否已經處理，因為要知道對方是否處理，依賴于對方的回複（ack），但即使對方沒有回複，也不能說明對方就沒有處理，也許僅僅是對方回複的那條消息丢失了
很多時候，一個程序需要判斷另外一個程序是否還在工作，如何判斷呢？判斷是否準确呢，能否保證一緻性呢？本文嘗試回答這些問題。
本文中，節點通常就是指一個程序，一個提供服務的程序。後文中，隻要不加以強調，程序和節點是同一個意思。
本文位址：http://www.cnblogs.com/xybaby/p/8710421.html
一個程序是否crash（在本文中，隻要程序是非預期的終止，就成為crash），在單機環境下是很好判斷的，隻要檢視還有沒有這個程序就行了。這裡有兩個問題：
第一：分布式環境下能否準确判斷程序crash？
第二：是否需要明确一個程序是否crash？
對于第一個問題，答案是幾乎不能的，後面詳細分析。
而第二個問題，有的時候是無需明确一個程序是否已經crash，而需要明确的是該程序是否持續對外提供服務，即使沒有crash，如果不按程式的預期工作了（比如程序死循環、死鎖、斷網），那麼也可以說這個服務挂了，“有的人活着，他已經死了”。分布式環境中，我們關心的是，節點（程序）是否對外提供服務，真死（crash）假死（活着但不工作）都是死（從系統的角度看）。
我們稱一個對外提供服務的程序處于active狀态，否則處于none-active狀态。
如何判斷一個程序是否處于active狀态，最簡單明了的方式就是：每隔一段時間就和這個程序通通信，如果目标程序在一定的時間門檻值内回複，那麼我們就說這個程序是active的，否則就是none－active的。這種定時通信的政策我們統稱為心跳。
心跳有兩種方式：第一種是單向的heartbeat；第二種是ping pong（ping ack）
在後文中，被檢測的程序稱之為target，而負責檢測的程序稱之為detector
第一種方式，target程序需要告知detector程序自己的存活性，隻需要定時給detector發消息就行了，“hi， duddy， I am Ok！”。detector無需給target回複任何消息，detector的任務是，每隔一定時間去檢查一下target是否有來彙報，沒有的話，detector就認為target處于none-active狀态了
而第二種方式，ping pong或者ping ack，更為常見：
detector給target發消息：hi，man，are you ok? target回複detector：Yes， I am ok！ 然後detector、target定時重複上面兩步
detector負責發起檢測：如果target連續N次不回複消息，那麼detector就可以認為target處于none-active狀态了。
這兩種方式，差別在于誰來主動發消息，而相同點在于：誰關心active狀态，誰來檢測。就是說，不管是簡單的heartbeat，還是ping ack，都是detector來檢測target的狀态。在實際中，ping ack的方式會應用得多一些，因為在ack消息中也可以攜帶一些資訊，比如後文會提到的lease。
gunicorn是一個遵循python wsgi的http server，使用了prefork master-worker模型（在gunicorn中，master被稱為Arbiter），能夠與各種wsgi web架構協作。在本文，關注的是Arbiter程序對Worker程序狀态的檢測。
既然Worker程序是Arbiter fork出來的，即Arbiter是Worker程序的父程序，那麼當Worker程序退出的時候，Master是可以通過監聽signal.SIGCHLD信号來知道子程序的結束。但這還不夠，gunicorn還有另外一招，我在《gunicorn syncworker 源碼解析》中也有所提及：
（1）gunicorn為每一個Worker程序建立一個臨時檔案
（2）worker程序在每次輪訓的時候修改該臨時檔案的屬性
（3）Arbiter程序檢查臨時檔案最新一次修改時間是否超過門檻值，如果超過，那麼就給Worker發信号，kill掉該Worker
不難看出，這是上面提到的第一種檢測方式（單向的heartbeat），worker程序（target）通過修改檔案屬性的方式表明自己處于active狀态，Arbiter（detector）程序檢測檔案屬性來判斷worker程序最近是否是active狀态。
這個檢測的目的就是防止worker程序處于假死狀态，沒有crash，但是不工作。
在計算機網絡中，心跳也使用非常廣泛。比如為了檢測目标IP是否可達的ping指令、TCP的keepalive。
A keepalive (KA) is a message sent by one device to another to check that the link between the two is operating, or to prevent the link from being broken.
在TCP協定中，是自帶keepalive來保活的，有三個很重要的選項（option）
tcp_keepidle ：對一個連接配接進行有效性探測之前運作的最大非活躍時間間隔 tcp_keepintvl ：兩個探測的時間間隔 tcp_keepcnt ：關閉一個非活躍連接配接之前進行探測的最大次數
三個選項是這麼配合的：如果一條連接配接上tcp_keepidle 這麼長時間沒有發消息之後，則開始心跳檢測，心跳檢測的時間間隔是tcp_keepintvl ，如果連續探測tcp_keepcnt 這麼多次，還沒有收到對應的回應，那麼主動關閉連接配接。
這三個參數的預設值都比較大，就是說需要較長時間才能檢測網絡不可達，是以一般情況下，程式會将三個參數調小。
可以看到，這是典型的ping ack探測方式。
如果我們使用TCP最為傳輸層協定，那麼是否就可以依賴TCP的keepalive來檢查連接配接的狀态，或者說對端程序的active狀态呢？
答案是不能的，因為，TCP隻能保證說連結是通的，但并不能表明對端是可用的，比如說對端程序處于死鎖狀态，但連結仍然是通的，tcp keepalive會持續收到回應，是以傳輸層的心跳無法發現程序的不可用狀态。是以我們需要應用層的心跳，如果收到應用層的心跳回複，那麼對端肯定不會是none-active的。
前面提到，通過心跳，是無法準确判斷target是否是crash，但有的情況下我們又需要明确知道對方是crash了？還是說隻是網絡不通？畢竟這是兩個不同的狀态。
而且target的crash還分為crash-stop，crash-recovery兩種情況。crash-stop是說一個程序如果crash了，那麼不會重新啟動，也就不會接受任何後續請求；而crash-recovery是說，程序crash之後會重新開機（是否在同一個實體機上重新開機沒有任何關系）。
如果目标是檢測出target的crash狀态，那麼檢測算法有兩個重要的衡量标準：
Completeness: every process failure is eventually detected (no misses) Accuracy: every detected failure corresponds to a crashed process (no mistakes)
前者（completeness）是說，如果一個程序挂掉，那麼一定能被檢測到；後者（accuracy）是說，如果detector認為target程序挂掉了，那麼就一定挂掉了，不會出現誤判。
對于crash-stop模型，隻能保證completenss，不能保證accurary。completeness不難了解，而accuracy不能保證是因為網絡通信中， 由于延時、丢包、網絡分割的存在，導緻心跳消息（無論是單向的heartbeat還是ping ack）無法到達，也就沒法判斷target是否已經crash，也許還活得好好的，隻是與detector之間的網絡出了問題。
那如果是crash-recovery模型呢，通過簡單的心跳，不僅不能保證accuracy，甚至不能保證completeness，因為target程序可能快速重新開機，當然增加一些程序相關的資訊還是能判斷crash-recovery的情況，比如target程序維護一個版本号，心跳需要對比版本号。
總之，網絡環境下，很難保證故障檢測的準确性（accuracy）。
接下來，考慮一個很常見的場景，在系統中有兩類程序：一個master和多個slave，master給slave配置設定任務，master需要通過心跳知道每個slave的狀态，如果某個slave處于none-active狀态，那麼需要将該slave負責的任務轉移到其他處于active狀态的slave上。master也充當了detector的角色，每個slave都是被檢測的target。
在這個場景中，有兩點需要注意，第一，使用了心跳作為探測方式，而心跳探測隻能保證completeness（完整性），而不能保證accuracy（準确性）。第二，slave負責的任務是否是可重複的？即同一份任務是否可以同時在多個slave上進行。failure detection的不準确性對slave任務的重新配置設定有至關重要的影響。
如果任務是可重複的，比如幂等的運算，那麼當master通過心跳判斷slave處于none-active狀态的時候，隻需要将任務重新配置設定給其他slave就行，不用管該slave是否還存活着。MapReduce就是這樣的例子，master在worker（MapReduce中的slave程序）程序失活（甚至隻是運算進度太慢）的時候，将該worker負責的任務（task）排程到其他worker上。是以可能出現多個worker負責同一份任務的情況，但這并不會産生什麼錯誤，因為任務的計算結果需要回報給master，master保證對于一份任務隻會采納一份計算結果，而且同一份任務，不管是哪個worker執行，結果都是一緻的。
但如果任務隻能由一個節點來執行呢，由于心跳檢測的不準确性，那麼将任務從本來還在工作的節點重新排程到其他節點時，就會出現嚴重的問題。比如在primary-secondary副本控制協定中，primary的角色隻能由一個節點來扮演，如果同時有兩個primary，那麼就出現了腦裂（brain-split），從這名字就能聽出來問題的嚴重性。是以，即使在心跳檢測出現誤判的情況下，也要保證任務的唯一性，或者說，需要detector與target之間達成共識：target不要對外提供服務了。這個時候Lease機制就是很不錯的選擇，因為Lease機制具有很好的容錯性，不會受到網絡故障、延遲的影響。
關于lease機制，我在《帶着問題學習分布式系統之資料分片》中有簡單介紹，這裡再簡單提一下Lease在GFS中的使用。
GFS采用了primary－seconday副本控制協定，primary決定了資料修改的順序。而primary的選舉、維護是由master節點負責的，master與primary的心跳中，會攜帶lease資訊。這個lease資訊是master對primary的承諾：在lease_term這個時間範圍内，我不會選舉出新的primary。那麼對于primary，在這個時間内，執行primary的職責，一旦過了這個時間，就自動失去了primary的權利。如果primary節點本身是ok的，并且與master之間網絡正常，那麼在每次心跳的時候，會延長這個lease_term，primary節點持續對外服務。一旦超過lease_term約定的時間，master就會選出新的primary節點，而舊的primary節點如果沒有crash，在恢複與master的心跳之後，會意識到已經有了新的primary，然後将自己降級為secondary。
從上面GFS的例子，可以看到master是一個單點，也就是說由一個節點來負責是以其它節點的failure detection，這就是集中式的故障檢測。如下圖所示：
由于detector是單點，是以壓力會比較大。更為嚴重的問題，在使用了lease機制的系統中，一旦detector故障，是以節點都無法擷取lease，也就無法提供服務，整個系統完全不可用。
是以，detector的高性能、高可用非常重要，以一個叢集的形式提供failure detection功能。
buffalo cse486 failure_detectors.pdf
gunicorn.org
Failure_detector
Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency
本文版權歸作者xybaby（博文位址：http://www.cnblogs.com/xybaby/）所有，歡迎轉載和商用，請在文章頁面明顯位置給出原文連結并保留此段聲明，否則保留追究法律責任的權利，其他事項，可留言咨詢。