[科普中國(guó)]-分布式算法

概述

分布式計(jì)算簡(jiǎn)單來(lái)說(shuō)，是把一個(gè)大計(jì)算任務(wù)拆分成多個(gè)小計(jì)算任務(wù)分布到若干臺(tái)機(jī)器上去計(jì)算，然后再進(jìn)行結(jié)果匯總。 目的在于分析計(jì)算海量的數(shù)據(jù)，從雷達(dá)監(jiān)測(cè)的海量歷史信號(hào)中分析異常信號(hào)(外星文明)，淘寶雙十一實(shí)時(shí)計(jì)算各地區(qū)的消費(fèi)習(xí)慣等。

海量計(jì)算最開(kāi)始的方案是提高單機(jī)計(jì)算性能，如大型機(jī)，后來(lái)由于數(shù)據(jù)的爆發(fā)式增長(zhǎng)、單機(jī)性能卻跟不上，才有分布式計(jì)算這種妥協(xié)方案。 因?yàn)橛?jì)算一旦拆分，問(wèn)題會(huì)變得非常復(fù)雜，像一致性、數(shù)據(jù)完整、通信、容災(zāi)、任務(wù)調(diào)度等問(wèn)題也都來(lái)了。

舉個(gè)例子，產(chǎn)品要求從數(shù)據(jù)庫(kù)中100G的用戶購(gòu)買(mǎi)數(shù)據(jù)，分析出各地域的消費(fèi)習(xí)慣金額等。 如果沒(méi)什么時(shí)間要求，程序員小明就寫(xiě)個(gè)對(duì)應(yīng)的業(yè)務(wù)處理服務(wù)程序，部署到服務(wù)器上，讓它慢慢跑就是了，小明預(yù)計(jì)10個(gè)小時(shí)能處理完。 后面產(chǎn)品嫌太慢，讓小明想辦法加快到3個(gè)小時(shí)。
平常開(kāi)發(fā)中類似的需求也很多，總結(jié)出來(lái)就是，數(shù)據(jù)量大、單機(jī)計(jì)算慢。 如果上Hadoop、storm之類成本較高、而且有點(diǎn)大才小用。 當(dāng)然讓老板買(mǎi)更好的服務(wù)器配置也是一種辦法。

分布性和并發(fā)性是分布式算法的兩個(gè)最基本的特征。分布式系統(tǒng)的執(zhí)行存在著許多非穩(wěn)定性的因素。由于這些多方面的差異，導(dǎo)致分布式算法的設(shè)計(jì)和分析，較之集中式算法來(lái)講，要復(fù)雜得多，也困難得多。

所謂分布式算法，就是指在完成乘加功能時(shí)通過(guò)將各輸入數(shù)據(jù)每一對(duì)應(yīng)位產(chǎn)生的運(yùn)算結(jié)果預(yù)先進(jìn)行相加形成相應(yīng)的部分積，然后再對(duì)各部分進(jìn)行累加形成最終結(jié)果。

而傳統(tǒng)算法則是等到所有乘積結(jié)果之后再進(jìn)行相加，從而完成整個(gè)乘加運(yùn)算。

經(jīng)典算法Paxos算法1）問(wèn)題描述

分布式中有這么一個(gè)疑難問(wèn)題，客戶端向一個(gè)分布式集群的服務(wù)端發(fā)出一系列更新數(shù)據(jù)的消息，由于分布式集群中的各個(gè)服務(wù)端節(jié)點(diǎn)是互為同步數(shù)據(jù)的，所以運(yùn)行完客戶端這系列消息指令后各服務(wù)端節(jié)點(diǎn)的數(shù)據(jù)應(yīng)該是一致的，但由于網(wǎng)絡(luò)或其他原因，各個(gè)服務(wù)端節(jié)點(diǎn)接收到消息的序列可能不一致，最后導(dǎo)致各節(jié)點(diǎn)的數(shù)據(jù)不一致。

2）算法本身

算法本身我就不進(jìn)行完整的描述和推導(dǎo)，網(wǎng)上有大量的資料做了這個(gè)事情，但我學(xué)習(xí)以后感覺(jué)萊斯利·蘭伯特（Leslie Lamport，paxos算法的奠基人，此人現(xiàn)在在微軟研究院）的Paxos Made Simple是學(xué)習(xí)paxos最好的文檔，它并沒(méi)有像大多數(shù)算法文檔那樣搞一堆公式和數(shù)學(xué)符號(hào)在那里嚇唬人，而是用人類語(yǔ)言讓你搞清楚Paxos要解決什么問(wèn)題，是如何解決的。這里也借機(jī)抨擊一下那些學(xué)院派的研究者，要想讓別人認(rèn)可你的成果，首先要學(xué)會(huì)怎樣讓大多數(shù)人樂(lè)于閱讀你的成果，而這個(gè)描述Paxos算法的文檔就是我們學(xué)習(xí)的榜樣。

言歸正傳，透過(guò)Paxos算法的各個(gè)步驟和約束，其實(shí)它就是一個(gè)分布式的選舉算法，其目的就是要在一堆消息中通過(guò)選舉，使得消息的接收者或者執(zhí)行者能達(dá)成一致，按照一致的消息順序來(lái)執(zhí)行。其實(shí)，以最簡(jiǎn)單的想法來(lái)看，為了達(dá)到大伙執(zhí)行相同序列的指令，完全可以通過(guò)串行來(lái)做，比如在分布式環(huán)境前加上一個(gè)FIFO隊(duì)列來(lái)接收所有指令，然后所有服務(wù)節(jié)點(diǎn)按照隊(duì)列里的順序來(lái)執(zhí)行。這個(gè)方法當(dāng)然可以解決一致性問(wèn)題，但它不符合分布式特性，如果這個(gè)隊(duì)列down掉或是不堪重負(fù)這么辦？而Paxos的高明之處就在于允許各個(gè)client互不影響地向服務(wù)端發(fā)指令，大伙按照選舉的方式達(dá)成一致，這種方式具有分布式特性，容錯(cuò)性更好。

說(shuō)到這個(gè)選舉算法本身，可以聯(lián)想一下現(xiàn)實(shí)社會(huì)中的選舉，一般說(shuō)來(lái)都是得票者最多者獲勝，而Paxos算法是序列號(hào)更高者獲勝，并且當(dāng)嘗試提交指令者被拒絕時(shí)（說(shuō)明它的指令所占有的序列號(hào)不是最高），它會(huì)重新以一個(gè)更好的序列參與再次選舉，通過(guò)各個(gè)提交者不斷參與選舉的方式，達(dá)到選出大伙公認(rèn)的一個(gè)序列的目的。也正是因?yàn)橛羞@個(gè)不斷參與選舉的過(guò)程，所以Paxos規(guī)定了三種角色（proposer，acceptor，和 learner）和兩個(gè)階段（accept和learn），三種角色的具體職責(zé)和兩個(gè)階段的具體過(guò)程就見(jiàn)Paxos Made Simple，另外一個(gè)國(guó)內(nèi)的哥們寫(xiě)了個(gè)不錯(cuò)的PPT，還通過(guò)動(dòng)畫(huà)描述了paxos運(yùn)行的過(guò)程。不過(guò)還是那句話不要一開(kāi)始就陷入算法的細(xì)節(jié)中，一定要多想想設(shè)計(jì)這些游戲規(guī)則的初衷是什么。

Paxos算法的最大優(yōu)點(diǎn)在于它的限制比較少，它允許各個(gè)角色在各個(gè)階段的失敗和重復(fù)執(zhí)行，這也是分布式環(huán)境下常有的事情，只要大伙按照規(guī)矩辦事即可，算法的本身保障了在錯(cuò)誤發(fā)生時(shí)仍然得到一致的結(jié)果。

3）算法的實(shí)現(xiàn)

Paxos的實(shí)現(xiàn)有很多版本，最有名的就是google chubby，不過(guò)看不了源碼。開(kāi)源的實(shí)現(xiàn)可見(jiàn)libpaxos。另外，ZooKeeper也基于paxos解決數(shù)據(jù)一致性問(wèn)題，也可以看看它是如果實(shí)現(xiàn)paxos的1。

一致性Hash算法1）問(wèn)題描述

分布式常常用Hash算法來(lái)分布數(shù)據(jù)，當(dāng)數(shù)據(jù)節(jié)點(diǎn)不變化時(shí)是非常好的，但當(dāng)數(shù)據(jù)節(jié)點(diǎn)有增加或減少時(shí)，由于需要調(diào)整Hash算法里的模，導(dǎo)致所有數(shù)據(jù)得重新按照新的模分布到各個(gè)節(jié)點(diǎn)中去。如果數(shù)據(jù)量龐大，這樣的工作常常是很難完成的。一致性Hash算法是基于Hash算法的優(yōu)化，通過(guò)一些映射規(guī)則解決以上問(wèn)題

2）算法本身

實(shí)際上，在其他設(shè)計(jì)和開(kāi)發(fā)領(lǐng)域我們也可以借鑒一致性Hash的思路，當(dāng)一個(gè)映射或規(guī)則導(dǎo)致有難以維護(hù)的問(wèn)題時(shí)，可以考慮更一步抽象這些映射或規(guī)則，通過(guò)規(guī)則的變化使得最終數(shù)據(jù)的不變。一致性hash實(shí)際就是把以前點(diǎn)映射改為區(qū)段映射，使得數(shù)據(jù)節(jié)點(diǎn)變更后其他數(shù)據(jù)節(jié)點(diǎn)變動(dòng)盡可能小。這個(gè)思路在操作系統(tǒng)對(duì)于存儲(chǔ)問(wèn)題上體現(xiàn)很多，比如操作系統(tǒng)為了更優(yōu)化地利用存儲(chǔ)空間，區(qū)分了段、頁(yè)等不同緯度，加了很多映射規(guī)則，目的就是要通過(guò)靈活的規(guī)則避免物理變動(dòng)的代價(jià)

3）算法實(shí)現(xiàn)

一致性Hash算法本身比較簡(jiǎn)單，不過(guò)可以根據(jù)實(shí)際情況有很多改進(jìn)的版本，其目的無(wú)非是兩點(diǎn)：

節(jié)點(diǎn)變動(dòng)后其他節(jié)點(diǎn)受影響盡可能小

節(jié)點(diǎn)變動(dòng)后數(shù)據(jù)重新分配盡可能均衡2