分布式檔案系統的副本分布政策

      分布式存儲系統中，檔案/對象，多采用副本的方式，提高資料的可靠性以及讀資料的io throughput。系統中副本在節點間的分布政策，對于快速定位資料的位置，以及整個系統的網絡流量、節點間io負載均衡，非常重要。副本分布政策，大緻分為三種：

    1.基于統計和監控的副本分布政策；

    2.基于一緻性hash的副本分布政策；

    3.基于僞随機算法的副本分布政策；

     基于統計和監控的政策：

        這種政策在傳統的，有中心（MDS metadata server）的架構中比較常見。全局統一的中繼資料伺服器中，記錄了目前系統中每個資料節點的存儲空間使用率，可以監控到每個節點目前網絡、blockio的負載。metadata sever相當于一個全能節點，時刻洞察到系統中變化。中繼資料伺服器基于這些統計、監控資訊，綜合多種的負載均衡政策（例如空間使用率最低，機架位置選擇，網絡raid10、節點狀态等）來為新增的blcok選取資料節點的位置。采用這種政策的分布式存儲系統有Googlefs，HDFS，Moosefs。

這種政策的缺點是，當中繼資料伺服器存在多個時，統計和監控的壓力增加，多個中心節點的決策很難協調。例如新上線一個節點，根據空間使用率原則，這個節點需要優先配置設定，但是同時，也不能所有的新資料都向這個節點上寫；如果隻有一個中繼資料伺服器，比較簡單，可以設法規避新資料熱點。如果多個中繼資料伺服器，就很難協調。

      基于一緻性hash的副本政策：

        這種政策是去中心架構的核心技術。有了一緻性hash的副本選擇政策，任何一個client，都可以根據少量的中繼資料映射關系（virtual nnode到physical node），計算出每個objectID/fileID對應的實體位置。詳細算法不在詳細贅述，有興趣的同學可以研究下aws Dynamo和openstack swift的副本分布政策。

這種政策的明顯的優勢是可以去掉中繼資料伺服器，這個很容易成為瓶頸的系統組成部分（hot sopt）。資料定位的速度更快了，是算出來的，而不是去一個伺服器查詢出來的。不足之處是：1.擴容的時候很難完全自動化，目前swift擴容時還是需要人工參與。2.需要提前規劃好virtual node的資料量。

     基于僞随機算法的副本分布政策：

      采用這種政策的分布式系統比較少。簡單的随機配置設定算法，可以解決給分布配置設定節點時的多個中繼資料伺服器沖突的問題。例如一個metadata server叢集中，任意一個MDS都可以從叢集中随機選擇一個節點為副本所在位置。簡單的随機選擇算法有兩個問題：

     一、因為是完全随機選擇，client不能簡單的根據ID計算得出位置，還是需要中繼資料伺服器 記錄下來位置資訊供後續查詢；

     二、擴容之後，資料如何rebalance，比較困難。

     目前比較熱門的分布式存儲系統ceph，采用了一個名為crush的 算法，很好的 解決了以上兩個問題。cursh算法其實也是先要計算objectID取hash值，hash值再乘以節點的權重，然後所有節點中這個乘積的最大節點，為選擇節點。objectID是确定的，如果每個節點權重也确定，那麼hash值不變，位置也是固定的。當節點發生變化後，變動比較小的情況下，發生位置變化的objec的數量也是比較小的。具體的資料對比和分析，可以考慮sage weil的crush論文http://ceph.com/papers/weil-crush-sc06.pdf

     這種算法也有一個局限性，就是随機算法隻有在資料量比較大的情況下，才能達到較好的随機性和均勻性。ceph的設計思想，決定了它天生是web-scale的分布式存儲系統，适合大叢集，規模越大越好。但是對于一個可以預見性的小規模叢集來說，随機算法效果不見得好，一緻性hash是一個更好的選擇。

     apache ignite采用的Rendezvous hash本質上也是一種僞随機算法，跟ceph的crush有相通之處。

後記：

     昨天被人問到了一緻性hash選擇副本和随機選擇 的差別 ，竟然一時沒有回答出來，事後仔細思考了下，謹以此文，供諸位參考。