論大型集群中的資料遺失

常用到的複製套路有三種：資料庫保證將每份資料拷貝到三個不同電腦上的三個獨立的磁碟上。這麼做的原因很簡單：磁碟只會在某個瞬間出現問題，如果一個磁碟掛掉了，你可以是有時間去把它替換掉，然後你仍然可以從你另外兩份拷貝中拿出一份來恢復資料並寫到新的磁碟上。在你恢復磁碟之前第二個磁碟也掛掉的機率太低了，你的磁碟在同一時刻都掛掉的可能性就如同小行星撞擊地球一樣微乎其微。

我們也特地進行了計算，一個磁碟壞掉的可能性差不多是0.1%（可能比較粗略），兩個磁碟掛掉的可能性差不多是10的-6次方，三個磁碟同時掛掉的可能性大概是10的-9次方，也就是十億分之一。這個計算顯示一個磁碟的出錯是獨立於其他磁碟的出錯的——這不是很準確，舉個例子，如果你的磁碟都是從一個生產線上生產出來的，那麼它們有可能都是壞的——但這對我們的想法來說已經是足夠好了的。

到目前為止，這看起來是合乎情理的，但是不幸的是這對許多資料儲存系統都不是正確的。在這篇部落格中我將向大家展示下這是為什麼。

遺失資料太容易了

如果你的資料庫叢集只包含三個機器，所有機器同時都掛掉的可能性實在太低了（排除相關的錯誤，例如一個資料中心被毀壞了）。然而一旦你使用了更大的集群，那麼問題也會相應地改變。你在叢集中使用了更多的節點和磁碟，你遺失資料的可能性就會變大。

這是根據計算得來的，你可能會想「真的嗎？我已經把資料複製到三個磁碟上了。失敗的可能性怎麼會根據叢集的增大而變高呢。管集群容量什麼事？

# 很明顯，這不是一個節點失敗的可能性——這是永久丟失所有三份拷貝資料的可能性，所以從備份中恢復資料只是保守的方法。你的集群越大，你遺失資料的可能性就越大。這可能是當你考慮為複製資料支付時你可能不會想到的。

圖的Y軸有點隨意，依賴了很多設想，但是線條的方向是難以置信的。基於先前的設想，在某個時刻一個節點失敗的可能性是0.1%，然而圖上顯示的是，在一個具有8000個節點的集群中，永遠失去一份數據的三個拷貝的機率大約是0.2 %。是的沒錯，遺失所有三個拷貝的風險是遺失一個節點的資料的風險的兩倍。那麼這些拷貝用來做什麼呢？

從這張圖直覺地判斷：在一個擁有8000個節點的集群中一些節點在某些時刻宕機的事件是時常發生的。這也許不是一個問題：一定機率的亂象和節點替換是可以推論的，還有一部分是例行的維護。然而，如果你很不幸，你複製的節點資料的目的節點都掛掉了，那麼你的資料就永遠找不回來了。數據的丟失緊緊是在集群的整體數據集中比較小的部分，但是當你丟失了三份複製，你可能認為“我確實不想丟失這些數據，”而不是“我沒想到偶然性地丟失了一些數據，儘管它們不是很大量的。

所有三份複製都是壞節點的可能性要依賴系統採用的複製演算法。上圖僅依賴資料被分成一定數量的分區（或稱為分片），這樣每個分區都儲存了三個隨機選擇的節點（或稱為偽隨機雜湊函數）。這是一致性哈希的特例，用在Cassandra和Riak（據我所知）。我不太確定其他系統是怎樣分配複製工作的，所以是從那些懂得多儲存系統的內部原理的人了解到。

計算遺失資料的可能性#

讓我使用一個複製資料庫的機率模型向你展示我是怎麼計算上圖的。

假設一個獨立節點遺失資料的機率是p=P（節點損失）。我打算忽略在這個模型中的時間，簡要地看下在某些時間段失敗的機率。舉個例子，我們可以假設p=0.001是某一天一個節點失敗的機率，花費一天時間去替換節點和將遺失資料轉儲到新的節點上也是合乎情理的。簡單來講，我並不想區分節點失敗和磁碟失敗，我只會把永久性失敗拿來說事。

設n為群集的節點數。 f為失敗的節點數（假設失敗是相對獨立的）是二項分佈的：

# 表達式是f個節點失敗的機率，表達式是保證n-f個節點不失敗的機率，是按照不同的方式從n中摘出f個節點的數量。讀作“n選擇f”，它被定義為：

。 。 。 。 。 。

具體的推導過程這裡也就不加詳細描述了。基於上面的公式，可以推導出在一個具有n個節點，複製因子是（複製的備份節點數量）的叢集會遺失一個或更多分區的機率。如果失敗的節點數f比複製因子少，我們可以確信沒有資料遺失。然而，我們需要增加所有的可能性，在f位於r和n之間的時候：

# 這稍微有些冗長，不過我認為它是精確的。如果你讓r=3，p=0.001，k=256n，n在3和10000之間，然後你就能得到上面那個圖。我寫了一些ruby程式去實現這個計算。

我們使用了聯合綁定的到一個更簡單的猜想結果：

# 儘管一個分割區的失敗不是完全獨立於其他分割區的，這個猜想仍然適用。它好像更接近實驗結果了：在途中，資料遺失機率更像是一條直線，和節點數量是成正比的。猜想顯示機率是和數量成正相關的，我們假設了每個節點有固定的256個分區。

在實踐中。 。 。

在實務上表現怎麼樣，我不太確定。但是我認為這是一個很有趣的計算敏感現象。我聽說過導致具有大型資料庫叢集的公司徽有真實資料遺失的情況。但是文章和報道中倒不是很常見。如果你現在正在研究這方面的課題，可以告訴我。

計算的結果顯示：如果你想減少資料遺失的可能性，你應該減少分區數量，並增加複製因子。使用更多的備份花費更多，所以在考慮大型叢集時這一點已經花費很大了。然而，分區數量顯示一個有意義的負載平衡處理。 Cassandra原來是一個節點一個分區，但後來變成了每個節點256個分區來應付更好的負載分佈和高效率的二次平衡。

你需要在這些起真正作用之前找到合理的大型集群，但是上千級別的集群是很多大型公司採用的。所以我很有興趣聽到在這個領域有實作經驗的人的敘述。如果10000個節點每天永久遺失資料的機率控制在0.25%以內，那就意味著一年有60%的資料都會遺失。

身為分散式資料系統的設計者看到了這篇文章之後有什麼想法？如果我講的是對的，設計複製方案時就應該加入更多的考慮。希望這片文章可以提升你對現實的重視。因為3個複製節點確實不是那麼的安全性。

以上是論大型集群中的資料遺失的詳細內容。更多資訊請關注PHP中文網其他相關文章！