分布式设计与开发
http://blog.csdn.net/cutesource/article/details/5811914
在IDF05（Intel Developer Forum 2005）上，Intel首席執行官Craig Barrett就取消4GHz芯片計劃一事，半開玩笑當眾單膝下跪致歉，給廣大軟件開發者一個明顯的信號，單純依靠垂直提升硬件性能來提高系統性能的時代已結束，分布式開發的時代實際上早已悄悄地成為了時代的主流，吵得很熱的云計算實際上只是包裝在分布式之外的商業概念，很多開發者（包括我）都想加入研究云計算這個潮流，在google上通過“云計算”這個關鍵詞來查詢資料，查到的都是些概念性或商業性的宣傳資料，其實真正需要深入的還是那個早以被人熟知的概念------分布式。
分布式可繁也可以簡，最簡單的分布式就是大家最常用的，在負載均衡服務器后加一堆web服務器，然后在上面搞一個緩存服務器來保存臨時狀態，后面共享一個數據庫，其實很多號稱分布式專家的人也就停留于此，大致結構如下圖所示：
這種環境下真正進行分布式的只是web server而已，并且web server之間沒有任何聯系，所以結構和實現都非常簡單。
有些情況下，對分布式的需求就沒這么簡單，在每個環節上都有分布式的需求，比如Load Balance、DB、Cache和文件等等，并且當分布式節點之間有關聯時，還得考慮之間的通訊，另外，節點非常多的時候，得有監控和管理來支撐。這樣看起來，分布式是一個非常龐大的體系，只不過你可以根據具體需求進行適當地裁剪。按照最完備的分布式體系來看，可以由以下模塊組成：
分布式任務處理服務：負責具體的業務邏輯處理
分布式節點注冊和查詢：負責管理所有分布式節點的命名和物理信息的注冊與查詢，是節點之間聯系的橋梁
分布式DB：分布式結構化數據存取
分布式Cache：分布式緩存數據（非持久化）存取
分布式文件：分布式文件存取
網絡通信：節點之間的網絡數據通信
監控管理：搜集、監控和診斷所有節點運行狀態
分布式編程語言：用于分布式環境下的專有編程語言，比如Elang、Scala
分布式算法：為解決分布式環境下一些特有問題的算法，比如解決一致性問題的Paxos算法
因此，若要深入研究云計算和分布式，就得深入研究以上領域，而這些領域每一塊的水都很深，都需要很底層的知識和技術來支撐，所以說，對于想提升技術的開發者來說，以分布式來作為切入點是非常好的，可以以此為線索，探索計算機世界的各個角落。
分布式設計與開發中有些疑難問題必須借助一些算法才能解決，比如分布式環境一致性問題，感覺以下分布式算法是必須了解的（隨著學習深入有待添加）：
- Paxos算法
- 一致性Hash算法
Paxos算法
1）問題描述
分布式中有這么一個疑難問題，客戶端向一個分布式集群的服務端發出一系列更新數據的消息，由于分布式集群中的各個服務端節點是互為同步數據的，所以運行完客戶端這系列消息指令后各服務端節點的數據應該是一致的，但由于網絡或其他原因，各個服務端節點接收到消息的序列可能不一致，最后導致各節點的數據不一致。舉一個實例來說明這個問題，下面是客戶端與服務端的結構圖：
當client1、client2、client3分別發出消息指令A、B、C時，Server1~4由于網絡問題，接收到的消息序列就可能各不相同，這樣就可能由于消息序列的不同導致Server1~4上的數據不一致。對于這么一個問題，在分布式環境中很難通過像單機里處理同步問題那么簡單，而Paxos算法就是一種處理類似于以上數據不一致問題的方案。
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的。
4）適用場景
弄清楚paxos的來龍去脈后，會發現它的適用場景非常多，Tim有篇blog《Paxos在大型系統中常見的應用場景》?專門談這個問題。我所見到的項目里，naming service是運用Paxos最廣的領域，具體應用可參考ZooKeeper
一致性Hash算法
1）問題描述
分布式常常用Hash算法來分布數據，當數據節點不變化時是非常好的，但當數據節點有增加或減少時，由于需要調整Hash算法里的模，導致所有數據得重新按照新的模分布到各個節點中去。如果數據量龐大，這樣的工作常常是很難完成的。一致性Hash算法是基于Hash算法的優化，通過一些映射規則解決以上問題
2）算法本身
對于一致性Hash算法本身我也不做完整的闡述，有篇blog《一致性hash算法 - consistent hashing》?描述這個算法非常到位，我就不重復造輪子了。
實際上，在其他設計和開發領域我們也可以借鑒一致性Hash的思路，當一個映射或規則導致有難以維護的問題時，可以考慮更一步抽象這些映射或規則，通過規則的變化使得最終數據的不變。一致性hash實際就是把以前點映射改為區段映射，使得數據節點變更后其他數據節點變動盡可能小。這個思路在操作系統對于存儲問題上體現很多，比如操作系統為了更優化地利用存儲空間，區分了段、頁等不同緯度，加了很多映射規則，目的就是要通過靈活的規則避免物理變動的代價
3）算法實現
一致性Hash算法本身比較簡單，不過可以根據實際情況有很多改進的版本，其目的無非是兩點：
- 節點變動后其他節點受影響盡可能小
- 節點變動后數據重新分配盡可能均衡
實現這個算法就技術本身來說沒多少難度和工作量，需要做的是建立起你所設計的映射關系，無需借助什么框架或工具，sourceforge上倒是有個項目libconhash?，可以參考一下
以上兩個算法在我看來就算從不涉及算法的開發人員也需要了解的，算法其實就是一個策略，而在分布式環境常常需要我們設計一個策略來解決很多無法通過單純的技術搞定的難題，學習這些算法可以提供我們一些思路。
分布式設計與開發中有些疑難問題必須借助一些算法才能解決，比如分布式環境一致性問題，感覺以下分布式算法是必須了解的（隨著學習深入有待添加）：
- Paxos算法
- 一致性Hash算法
Paxos算法
1）問題描述
分布式中有這么一個疑難問題，客戶端向一個分布式集群的服務端發出一系列更新數據的消息，由于分布式集群中的各個服務端節點是互為同步數據的，所以運行完客戶端這系列消息指令后各服務端節點的數據應該是一致的，但由于網絡或其他原因，各個服務端節點接收到消息的序列可能不一致，最后導致各節點的數據不一致。舉一個實例來說明這個問題，下面是客戶端與服務端的結構圖：
當client1、client2、client3分別發出消息指令A、B、C時，Server1~4由于網絡問題，接收到的消息序列就可能各不相同，這樣就可能由于消息序列的不同導致Server1~4上的數據不一致。對于這么一個問題，在分布式環境中很難通過像單機里處理同步問題那么簡單，而Paxos算法就是一種處理類似于以上數據不一致問題的方案。
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的。
4）適用場景
弄清楚paxos的來龍去脈后，會發現它的適用場景非常多，Tim有篇blog《Paxos在大型系統中常見的應用場景》?專門談這個問題。我所見到的項目里，naming service是運用Paxos最廣的領域，具體應用可參考ZooKeeper
一致性Hash算法
1）問題描述
分布式常常用Hash算法來分布數據，當數據節點不變化時是非常好的，但當數據節點有增加或減少時，由于需要調整Hash算法里的模，導致所有數據得重新按照新的模分布到各個節點中去。如果數據量龐大，這樣的工作常常是很難完成的。一致性Hash算法是基于Hash算法的優化，通過一些映射規則解決以上問題
2）算法本身
對于一致性Hash算法本身我也不做完整的闡述，有篇blog《一致性hash算法 - consistent hashing》?描述這個算法非常到位，我就不重復造輪子了。
實際上，在其他設計和開發領域我們也可以借鑒一致性Hash的思路，當一個映射或規則導致有難以維護的問題時，可以考慮更一步抽象這些映射或規則，通過規則的變化使得最終數據的不變。一致性hash實際就是把以前點映射改為區段映射，使得數據節點變更后其他數據節點變動盡可能小。這個思路在操作系統對于存儲問題上體現很多，比如操作系統為了更優化地利用存儲空間，區分了段、頁等不同緯度，加了很多映射規則，目的就是要通過靈活的規則避免物理變動的代價
3）算法實現
一致性Hash算法本身比較簡單，不過可以根據實際情況有很多改進的版本，其目的無非是兩點：
- 節點變動后其他節點受影響盡可能小
- 節點變動后數據重新分配盡可能均衡
實現這個算法就技術本身來說沒多少難度和工作量，需要做的是建立起你所設計的映射關系，無需借助什么框架或工具，sourceforge上倒是有個項目libconhash?，可以參考一下
以上兩個算法在我看來就算從不涉及算法的開發人員也需要了解的，算法其實就是一個策略，而在分布式環境常常需要我們設計一個策略來解決很多無法通過單純的技術搞定的難題，學習這些算法可以提供我們一些思路。
ZooKeeper是Hadoop的正式子項目，它是一個針對大型分布式系統的可靠協調系統，提供的功能包括：配置維護、名字服務、分布式同步、組服務等。ZooKeeper的目標就是封裝好復雜易出錯的關鍵服務，將簡單易用的接口和性能高效、功能穩定的系統提供給用戶。
Zookeeper是Google的Chubby一個開源的實現.是高有效和可靠的協同工作系統.Zookeeper能夠用來leader選舉,配置信息維護等.在一個分布式的環境中,我們需要一個Master實例或存儲一些配置信息,確保文件寫入的一致性等.Zookeeper能夠保證如下3點:
- Watches are ordered with respect to other events, other watches, and
asynchronous replies. The ZooKeeper client libraries ensures that
everything is dispatched in order. - A client will see a watch event for a znode it is watching before seeing the new data that corresponds to that znode.
- The order of watch events from ZooKeeper corresponds to the order of the updates as seen by the ZooKeeper service.
?
在Zookeeper中,znode是一個跟Unix文件系統路徑相似的節點,可以往這個節點存儲或獲取數據.如果在創建znode時Flag設置 為EPHEMERAL,那么當這個創建這個znode的節點和Zookeeper失去連接后,這個znode將不再存在在Zookeeper 里.Zookeeper使用Watcher察覺事件信息,當客戶端接收到事件信息,比如連接超時,節點數據改變,子節點改變,可以調用相應的行為來處理數 據.Zookeeper的Wiki頁面展示了如何使用Zookeeper來處理事件通知,隊列,優先隊列,鎖,共享鎖,可撤銷的共享鎖,兩階段提交.
那么Zookeeper能幫我們作什么事情呢?簡單的例子:假設我們我們有個20個搜索引擎的服務器(每個負責總索引中的一部分的搜索任務)和一個 總服務器(負責向這20個搜索引擎的服務器發出搜索請求并合并結果集),一個備用的總服務器(負責當總服務器宕機時替換總服務器),一個web的 cgi(向總服務器發出搜索請求).搜索引擎的服務器中的15個服務器現在提供搜索服務,5個服務器正在生成索引.這20個搜索引擎的服務器經常要讓正在 提供搜索服務的服務器停止提供服務開始生成索引,或生成索引的服務器已經把索引生成完成可以搜索提供服務了.使用Zookeeper可以保證總服務器自動 感知有多少提供搜索引擎的服務器并向這些服務器發出搜索請求,備用的總服務器宕機時自動啟用備用的總服務器,web的cgi能夠自動地獲知總服務器的網絡 地址變化.這些又如何做到呢?
"hostname".getBytes(), Ids.OPEN_ACL_UNSAFE, CreateFlags.EPHEMERAL);
總結
- 上一篇： zoj1081判断点是否在多边形内
- 下一篇： 开源日志系统