基本介紹
- 中文名：分散式算法
- 外文名：Distributed Algorithm
- 同類：Centralized Algorithm
- 解釋：相加，從而完成整個乘加運算
概述,經典算法,Paxos算法,一致性Hash算法,
概述
分散式計算簡單來說，是把一個大計算任務拆分成多個小計算任務分布到若干台機器上去計算，然後再進行結果匯總。 目的在於分析計算海量的數據，從雷達監測的海量歷史信號中分析異常信號(外星文明)，淘寶雙十一實時計算各地區的消費習慣等。
海量計算最開始的方案是提高單機計算性能，如大型機，後來由於數據的爆發式增長、單機性能卻跟不上，才有分散式計算這種妥協方案。 因為計算一旦拆分，問題會變得非常複雜，像一致性、數據完整、通信、容災、任務調度等問題也都來了。
舉個例子，產品要求從資料庫中100G的用戶購買數據，分析出各地域的消費習慣金額等。 如果沒什麼時間要求，程式設計師小明就寫個對應的業務處理服務程式，部署到伺服器上，讓它慢慢跑就是了，小明預計10個小時能處理完。 後面產品嫌太慢，讓小明想辦法加快到3個小時。
平常開發中類似的需求也很多，總結出來就是，數據量大、單機計算慢。 如果上Hadoop、storm之類成本較高、而且有點大才小用。 當然讓老闆買更好的伺服器配置也是一種辦法。
平常開發中類似的需求也很多，總結出來就是，數據量大、單機計算慢。 如果上Hadoop、storm之類成本較高、而且有點大才小用。 當然讓老闆買更好的伺服器配置也是一種辦法。
分布性和並發性是分散式算法的兩個最基本的特徵。分散式系統的執行存在著許多非穩定性的因素。由於這些多方面的差異，導致分散式算法的設計和分析，較之集中式算法來講，要複雜得多，也困難得多。
所謂分散式算法，就是指在完成乘加功能時通過將各輸入數據每一對應位產生的運算結果預先進行相加形成相應的部分積，然後再對各部分進行累加形成最終結果。
而傳統算法則是等到所有乘積結果之後再進行相加，從而完成整個乘加運算。
經典算法
Paxos算法
1）問題描述
分散式中有這么一個疑難問題，客戶端向一個分散式集群的服務端發出一系列更新數據的訊息，由於分散式集群中的各個服務端節點是互為同步數據的，所以運行完客戶端這系列訊息指令後各服務端節點的數據應該是一致的，但由於網路或其他原因，各個服務端節點接收到訊息的序列可能不一致，最後導致各節點的數據不一致。
2）算法本身
算法本身我就不進行完整的描述和推導，網上有大量的資料做了這個事情，但我學習以後感覺萊斯利·蘭伯特（Leslie Lamport，paxos算法的奠基人，此人現在在微軟研究院）的Paxos Made Simple是學習paxos最好的文檔，它並沒有像大多數算法文檔那樣搞一堆公式和數學符號在那裡嚇唬人，而是用人類語言讓你搞清楚Paxos要解決什麼問題，是如何解決的。這裡也藉機抨擊一下那些學院派的研究者，要想讓別人認可你的成果，首先要學會怎樣讓大多數人樂於閱讀你的成果，而這個描述Paxos算法的文檔就是我們學習的榜樣。
言歸正傳，透過Paxos算法的各個步驟和約束，其實它就是一個分散式的選舉算法，其目的就是要在一堆訊息中通過選舉，使得訊息的接收者或者執行者能達成一致，按照一致的訊息順序來執行。其實，以最簡單的想法來看，為了達到大夥執行相同序列的指令，完全可以通過串列來做，比如在分散式環境前加上一個FIFO佇列來接收所有指令，然後所有服務節點按照佇列里的順序來執行。這個方法當然可以解決一致性問題，但它不符合分散式特性，如果這個佇列down掉或是不堪重負這么辦？而Paxos的高明之處就在於允許各個client互不影響地向服務端發指令，大夥按照選舉的方式達成一致，這種方式具有分散式特性，容錯性更好。
說到這個選舉算法本身，可以聯想一下現實社會中的選舉，一般說來都是得票者最多者獲勝，而Paxos算法是序列號更高者獲勝，並且當嘗試提交指令者被拒絕時（說明它的指令所占有的序列號不是最高），它會重新以一個更好的序列參與再次選舉，通過各個提交者不斷參與選舉的方式，達到選出大夥公認的一個序列的目的。也正是因為有這個不斷參與選舉的過程，所以Paxos規定了三種角色（proposer，acceptor，和 learner）和兩個階段（accept和learn），三種角色的具體職責和兩個階段的具體過程就見Paxos Made Simple，另外一個國內的哥們寫了個不錯的PPT，還通過動畫描述了paxos運行的過程。不過還是那句話不要一開始就陷入算法的細節中，一定要多想想設計這些遊戲規則的初衷是什麼。
Paxos算法的最大優點在於它的限制比較少，它允許各個角色在各個階段的失敗和重複執行，這也是分散式環境下常有的事情，只要大夥按照規矩辦事即可，算法的本身保障了在錯誤發生時仍然得到一致的結果。
3）算法的實現
Paxos的實現有很多版本，最有名的就是google chubby，不過看不了源碼。開源的實現可見libpaxos。另外，ZooKeeper也基於paxos解決數據一致性問題，也可以看看它是如果實現paxos的。
一致性Hash算法
1）問題描述
分散式常常用Hash算法來分布數據，當數據節點不變化時是非常好的，但當數據節點有增加或減少時，由於需要調整Hash算法里的模，導致所有數據得重新按照新的模分布到各個節點中去。如果數據量龐大，這樣的工作常常是很難完成的。一致性Hash算法是基於Hash算法的最佳化，通過一些映射規則解決以上問題
2）算法本身
實際上，在其他設計和開發領域我們也可以借鑑一致性Hash的思路，當一個映射或規則導致有難以維護的問題時，可以考慮更一步抽象這些映射或規則，通過規則的變化使得最終數據的不變。一致性hash實際就是把以前點映射改為區段映射，使得數據節點變更後其他數據節點變動儘可能小。這個思路在作業系統對於存儲問題上體現很多，比如作業系統為了更最佳化地利用存儲空間，區分了段、頁等不同緯度，加了很多映射規則，目的就是要通過靈活的規則避免物理變動的代價
3）算法實現
一致性Hash算法本身比較簡單，不過可以根據實際情況有很多改進的版本，其目的無非是兩點：
- 節點變動後其他節點受影響儘可能小
- 節點變動後數據重新分配儘可能均衡
