分布式一致性
選主算法是保證在2n+1數(shù)量的集群中可以保證最多n個節(jié)點宕機時依然可以保證服務(wù)可用，并且在宕機的服務(wù)器啟動后可以加入集群繼續(xù)使用
第一個被共識的算法是Paxos算法，zookeeper就是使用這種算法。但是Paxos算法過于復雜，于是有了raft算法。
raft算法的實現(xiàn)
下面是節(jié)點狀態(tài)的切換圖。
任期Term
初始個節(jié)點任期都是一樣，并且選出learder后節(jié)點們都會統(tǒng)一他們的任期。每個節(jié)點也會存儲他們同步的日志index
選舉使用一個每個節(jié)點設(shè)置隨機的超時時間（Timeout）完成的。首先每個節(jié)點與leader進行心跳通信，并且每次通信后都會重置Timeout為值，重新倒計時。
如果Timeout倒計時到0時，則此節(jié)點認為leader已下線，開始選舉。會把自己的任期號加一 。隨機的Timeout應(yīng)設(shè)置為大于心跳間隔一個數(shù)量級，已防止因為網(wǎng)絡(luò)延遲遲到的心跳包讓節(jié)點認為leader已下線。
開始選舉，此節(jié)點會先投票給自己，然后給所有其他節(jié)點發(fā)送請求讓他們來選舉自己，會帶上自己的任期號和最后一條日志index。如果其他節(jié)點之前沒給任何人投票，并且任期號<=接收請求的任期號，并且日志index>=接到到index，那么他將獲得這一票。如果他獲得了半數(shù)以上的投票則他成為leader。如果沒有任何一個節(jié)點獲得半數(shù)投票則開啟下一任期選舉。
所以這個選舉的原理就是看那個節(jié)點先感知leader下線，搶在其他節(jié)點前發(fā)送投票請求取得半數(shù)投票。而誰先感知則由每個節(jié)點設(shè)置的隨機Timeout來決定。
因為是靠隨機來做的算法，所以在極端情況下會重新幾個節(jié)點同時發(fā)送投票請求，導致活鎖的情況，不過連續(xù)多次極端情況的幾率非常低
這個演示更加明了
http://thesecretlivesofdata.com/raft/
以上只是理論上的算法，實際還有一些特殊的點
下面看一個問題
在選舉時是通過任期號和索引index來判斷 誰的日志更新 ， 誰的任期號大誰的新，同樣任期號下誰的索引大誰新 這樣會出現(xiàn)一個問題
如表格 t代表時間 一共有a,b,c,d,e五個節(jié)點 ,(x,y)代表（任期，數(shù)據(jù)）
初始狀態(tài)t1 a為learder 用其他顏色表示，在t2時接受客戶端寫入了新的數(shù)據(jù)，并在同步過程中宕機 只同步了兩個節(jié)點
- t3 時e競選成了learder 因為大多數(shù)節(jié)點的任期和索引都和他一樣新 之后接受了消息但是在寫入自己后宕機
- t4 時a蘇醒成了learder 因為他的任期和索引都比大多數(shù)新 然后他繼續(xù)了之前數(shù)據(jù)的復制 并且復制到了大多數(shù)上 這個數(shù)據(jù)（1，7）應(yīng)該是有效的
- t5 e蘇醒并成為了learder 因為它最新一條數(shù)據(jù)的任期是2 然后它復制原來的消息（1，7）就丟失了 。
按理說這個a蘇醒后應(yīng)該是任期3 這樣e就不會成為learder 。
這里的根本原因是獲取任期要從日志里面最新的一條，因為a蘇醒時沒收到客戶端請求沒有新的日志所以其他節(jié)點存儲的最新任期還是1其實應(yīng)該是第3任期了。
比如節(jié)點d ，已經(jīng)換了好次的leader了 但是因為這些leader沒能寫入數(shù)據(jù) ，所以他記錄的任期卻還是1。
為了解決這個問題etcd有了一個限制：
每個節(jié)點競選成learder后，要先同步一條空日志，這樣一來大多數(shù)節(jié)點都能感知任期變動。
PreVote
這是為避免發(fā)生無意義選舉的一個機制，當learder沒掛掉時，因為發(fā)生網(wǎng)絡(luò)分區(qū)導致少數(shù)服務(wù)在一個分區(qū)內(nèi)，他們因為連不上learder會不斷的發(fā)起選舉，任期號不斷增加。導致網(wǎng)絡(luò)分區(qū)恢復時他的任期號大于learder，從而發(fā)送選舉，擾亂集群。
prevote 要求節(jié)點在開始選舉前，必須先和所有其他節(jié)點進行一次通訊，如果超過了半數(shù)以上響應(yīng)才能開始選舉。
節(jié)點會先進入PreCandidate狀態(tài)此時不會增加自己的任期號，當他可以和集群半數(shù)以上的節(jié)點通信時，才能進入Candidate狀態(tài)開始正式選舉
這樣網(wǎng)絡(luò)分區(qū)情況下，少數(shù)節(jié)點的分區(qū)不會不斷發(fā)起選舉也不會增加自己的任期號。
