硬碟任性丟數據，但分散式存儲一定可靠嗎？

05-03

原標題：分散式存儲系統可靠性-如何估算

作者：孫建良，網易雲對象存儲負責人

1. 存儲系統的可靠性

常規情況下，我們一般使用多副本技術來提高存儲系統的可靠性，不論是結構化資料庫存儲（典型的如MySQL）、文檔型NoSQL資料庫存儲（MongoDB）或者是常規的Blob存儲系統(GFS、Hadoop)等。

數據幾乎是企業的生命所在，如何較為正確地衡量集群數據的可靠性，如何進行系統設計使得集群數據達到更高的可靠性，這是本文要解答的疑問。

2. 數據丟失與copyset（複製組）

「在999塊磁碟3備份系統中，同時壞三塊盤情況下的數據丟失概率?」，這個跟存儲系統的設計息息相關。我們先考慮兩個極端設計下的情況

設計一：把999塊磁碟組層333塊磁碟對。

在這種設計情況下，只有選中其中一個磁碟對才會發生數據丟失。這種設計中，丟失數據的概率為 333/C(999,3) = 5.025095326058336*e-07。

設計二：數據隨機打散到999盤中，極端情況下，隨機一塊盤上的邏輯數據的副本數據打散在在所有集群中的998塊盤中。這種設計中，丟失數據的概率為 C(999,3)/C(999,3)=1，也就是必然存在。

通過這兩種極端的栗子，我們可以看到數據的丟失概率跟數據的打散程度息息相關，為了方便後續閱讀，這裡我們引入一個新的概念copyset（複製組）。

CopySet：包含一個數據的所有副本數據的設備組合，比如一份數據寫入1，2，3三塊盤，那麼{1,2,3}就是一個複製組。

9個磁碟的集群中，最小情況下的copyset的組合數為3，copysets = {1,2,3}、{4,5,6}、{7,8,9}，即一份數據的寫入只能選擇其中一個複製組，那麼只有 {1,2,3}、{4,5,6}或者{7,8,9} 同時壞的情況下才會出現數據丟失。即最小copyset數量為N/R。

系統中最大的copyset的數目為 C(N,R) ，其中R為副本數，N為磁碟的數量。在完全隨機選擇節點寫入副本數據的情況下，系統中的copyset數目會達到最大值C(N,R)。即任意選擇R個磁碟都會發生一部分數據的三個副本都在這R個盤上。

磁碟數量N，副本為R的存儲系統中，copyset數量S, N/R < S < C(N, R)

3. 磁碟故障與存儲系統可靠性估算

3.1 磁碟故障與泊松分布

在正式估算概率之前還需要科普下一個基礎的概率學分布：泊松分布。泊松分布主要描述在一個系統中隨機事件發生的概率，譬如汽車站台的候客人數的概率，某個醫院1個小時內出生N個新生兒的概率等等，更形象的可參見阮一峰的《泊松分布和指數分布：10分鐘教程》)。

如上為泊松分布的公式。等號的左邊，P 表示概率，N表示某種函數關係，t 表示時間，n 表示數量，λ 表示事件的頻率。

舉個栗子：1000塊磁碟在1年內出現10塊概率為P(N(365) = 10)[註：t的平均單位為天]。λ 為1000塊磁碟1天內發生故障磁碟的數量，按照Google的統計，年故障率在8%，那麼 λ = 1000*8%/365 。

如上只是損壞N塊磁碟的概率統計，那麼怎麼利用這個信息計算分散式系統中數據的可靠性(即數據丟失概率)的近似估算。

3.2 分散式存儲系統中的丟失率估算

3.2.1 T時間內故障率

分散式存儲存儲系統中如何進行年故障率估算，我們先假定一種情況，T(1年時間內)，系統存滿數據的情況下，壞盤不處理。這種情況下統計下數據的年故障率。

這裡我們先定義一些數據 N:磁碟數量T：統計時間K：壞盤數量S: 系統中copyset數量(複製組的個數)R：備份數量

如何計算T（1年）時間內數據丟失的概率，從概率統計角度來說就是把T(1年)時間內所有可能出現數據丟失的事件全部考慮進去。包含N個磁碟R副本冗餘的系統中，在T時間內可能出現數據丟失數據的事件為壞盤大於等於R的事件，即R，R+1，R+2，… N (即為 K∈[R,N] 區間所有的時間)，這些隨機事件發生時，什麼情況下會造成數據丟失？沒錯就是命中複製組的情況。

K個損壞情況下(隨機選擇K個盤情況下)命中複製組的概率為

p = X/C(N,K) 其中X為隨機選擇K個磁碟過程中命中複製組的組合數。

那麼系統出現K個磁碟損壞造成數據丟失的概率為

Pa(T,K) = p * P(N(T)=K)

最後系統中T時間內出現數據丟失的概率為所有可能出現數據丟失的事件的概率加起來。

Pb(T) = Σ Pa(T,K) ; K∈[R,N]

3.2.2 分散式系統衡量年故障率

以上我們假設在一年中，不對任何硬體故障做恢復措施，那麼t用一年代入即可算出此種系統狀態下的年故障率。但是在大規模存儲系統中，數據丟失情況下往往會啟動恢復程序，恢復完了之後理論上又是從初始狀態的隨機事件，加入這個因素之後計算可靠性會變得比較複雜。

理論上大規模存儲系統中壞盤、恢復是極其複雜的連續事件，這裡我們把這個概率模型簡化為不同個單位時間T內的離散事件進行統計計算。只要兩個T之間連續事件的發生概率極小，並且T時間內絕大部份壞盤情況能夠恢復在T時間內恢復，那麼下個時間T能就是重新從新的狀態開始，則這種估算能夠保證近似正確性。T的單位定義為小時（即），那麼1年可以劃分為365/24/T個時間段，那麼系統的年故障率可以理解為100%減去所有單位T時間內都不發生故障的概率。

即系統整體丟失數據的概率為:

Pc = 1 - (1-Pb(T))**(365*24/T)

4 參考文獻：

Google』s Disk Failure Experience
柏松分布
泊松分布和指數分布：10分鐘教程
概率論，二項分布和Poisson分布
磁碟故障與存儲系統的年失效率估算