常規(guī)情況下，我們一般使用多副本技術(shù)來提高存儲(chǔ)系統(tǒng)的可靠性，無論是結(jié)構(gòu)化數(shù)據(jù)庫(kù)存儲(chǔ) (如典型的 mysql)、文檔型 Nosql 數(shù)據(jù)庫(kù)存儲(chǔ) (mongodb ) 或者是常規(guī)的 blob 存儲(chǔ)系統(tǒng) (GFS、Hadoop) 等，無不如此。

因?yàn)閿?shù)據(jù)幾乎可以稱得上是企業(yè)生命力的核心，保障數(shù)據(jù)存儲(chǔ)系統(tǒng)的可靠性對(duì)于任何企業(yè)來說都不是一件小事。

那么，如何較為準(zhǔn)確地去衡量集群數(shù)據(jù)的可靠性？如何進(jìn)行系統(tǒng)設(shè)計(jì)使得集群數(shù)據(jù)達(dá)到更高的可靠性？本文將試著去解答這些問題。

[[214781]]

數(shù)據(jù)丟失與 copyset（復(fù)制組）

“在由 999 塊磁盤組成的 3 副本存儲(chǔ)系統(tǒng)中，同時(shí)壞三塊盤的情況下數(shù)據(jù)丟失的概率是多大？ ”，這個(gè)跟存儲(chǔ)系統(tǒng)的設(shè)計(jì)息息相關(guān)，我們先考慮兩個(gè)極端設(shè)計(jì)下的情況。

設(shè)計(jì)一：把 999 塊磁盤組成 333 塊磁盤對(duì)。

在這種設(shè)計(jì)下，只有選中其中一個(gè)磁盤對(duì)才會(huì)發(fā)生數(shù)據(jù)丟失。這種設(shè)計(jì)中，丟失數(shù)據(jù)的概率為 333/C(999,3) = 5.025095326058336*e-07。

設(shè)計(jì)二：數(shù)據(jù)隨機(jī)打散到 999 塊盤中。

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

通過這兩種極端的例子我們可以看到，數(shù)據(jù)的丟失概率跟數(shù)據(jù)的打散程度息息相關(guān)。為了方便后續(xù)閱讀，這里我們引入一個(gè)新的概念 copyset (復(fù)制組)。

CopySet：包含一個(gè)數(shù)據(jù)的所有副本數(shù)據(jù)的設(shè)備組合，比如一份數(shù)據(jù)寫入 1，2，3 三塊盤，那么 {1,2,3} 就是一個(gè)復(fù)制組。

9 個(gè)磁盤的集群中，最小情況下的 copyset 的組合數(shù)為 3，copysets = {1,2,3}、{4,5,6}、{7,8,9}，即一份數(shù)據(jù)的寫入只能選擇其中一個(gè)復(fù)制組，那么只有 {1,2,3}、{4,5,6} 或者 {7,8,9} 同時(shí)壞的情況下才會(huì)出現(xiàn)數(shù)據(jù)丟失。即最小 copyset 數(shù)量為 N/R。

系統(tǒng)中***的 copyset 的數(shù)目為 C(N,R) ，其中 R 為副本數(shù)，N 為磁盤的數(shù)量。在完全隨機(jī)選擇節(jié)點(diǎn)寫入副本數(shù)據(jù)的情況下，系統(tǒng)中的 copyset 數(shù)目會(huì)達(dá)到***值 C(N,R)。即任意選擇 R 個(gè)磁盤都會(huì)發(fā)生一部分?jǐn)?shù)據(jù)的三個(gè)副本都在這 R 個(gè)盤上的情況。

磁盤數(shù)量 N，副本為 R 的存儲(chǔ)系統(tǒng)中，copyset 數(shù)量 S, N/R < S < C(N, R)

磁盤故障與存儲(chǔ)系統(tǒng)可靠性估算

1. 磁盤故障與柏松分布

在正式估算相關(guān)概率之前還需要科普一個(gè)基礎(chǔ)的概率學(xué)分布：柏松分布。柏松分布主要描述在一個(gè)系統(tǒng)中隨機(jī)事件發(fā)生的概率，譬如描述汽車站臺(tái)候客人數(shù)為某個(gè)值的概率，某個(gè)醫(yī)院 1 小時(shí)內(nèi)出生 N 個(gè)新生兒的概率等等。

如上為泊松分布的公式。其中，P 表示概率，N 表示某種函數(shù)關(guān)系，t 表示時(shí)間，n 表示數(shù)量，λ 表示事件的頻率。

舉個(gè)例子：1000 塊磁盤在 1 年內(nèi)出現(xiàn) 10 塊故障的概率為 P (N(365) = 10) [注：t 的平均單位為天]。λ 為 1000 塊磁盤 1 天內(nèi)發(fā)生故障磁盤的數(shù)量，按照 google 的統(tǒng)計(jì)，年故障率在 8%，那么 λ = 1000*8%/365 。

如上只是損壞 N 塊磁盤概率的統(tǒng)計(jì)，那么怎么利用這個(gè)公式計(jì)算分布式系統(tǒng)中數(shù)據(jù)可靠性 (即數(shù)據(jù)丟失概率) 的近似值呢？

2. 分布式存儲(chǔ)系統(tǒng)中丟失率的估算

2.1 T 時(shí)間內(nèi)的故障率

對(duì)于分布式存儲(chǔ)系統(tǒng)中如何進(jìn)行年故障率的估算，我們先假定一種情況：T 為 1 年的情況下，系統(tǒng)存滿數(shù)據(jù)，壞盤不處理，這種情況下統(tǒng)計(jì)一下數(shù)據(jù)的年故障率。

這里我們先定義一些值

N： 磁盤數(shù)量

T：統(tǒng)計(jì)時(shí)間

K：壞盤數(shù)量

S：系統(tǒng)中 copyset 數(shù)量 (復(fù)制組的個(gè)數(shù))

R：備份數(shù)量

如何計(jì)算 T（1年）時(shí)間內(nèi)數(shù)據(jù)丟失的概率，從概率統(tǒng)計(jì)角度來說就是把 T (1 年) 時(shí)間內(nèi)所有可能出現(xiàn)數(shù)據(jù)丟失的事件全部考慮進(jìn)去。包含 N 個(gè)磁盤 R 副本冗余的系統(tǒng)中，在 T 時(shí)間內(nèi)可能出現(xiàn)數(shù)據(jù)丟失的事件，即壞盤大于等于 R 的事件，即 R，R+1，R+2，… N ( 即為 K∈[R,N] 區(qū)間所有的事件 )。這些隨機(jī)事件發(fā)生時(shí)，什么情況下會(huì)造成數(shù)據(jù)丟失？沒錯(cuò)，就是***復(fù)制組的情況下。

K 個(gè)損壞情況下 (隨機(jī)選擇 K 個(gè)盤情況下) ***復(fù)制組的概率為：

p = X/C(N,K) 其中 X 為隨機(jī)選擇 K 個(gè)磁盤過程中***復(fù)制組的組合數(shù)

那么系統(tǒng)出現(xiàn) K 個(gè)磁盤損壞造成數(shù)據(jù)丟失的概率為：

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

***系統(tǒng)中 T 時(shí)間內(nèi)出現(xiàn)數(shù)據(jù)丟失的概率為所有可能出現(xiàn)數(shù)據(jù)丟失的事件的概率總和。

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

2.2 分布式系統(tǒng)衡量年故障率

以上我們假設(shè)在一年中，不對(duì)任何硬件故障做恢復(fù)措施，那么 t 用一年代入即可算出此種系統(tǒng)狀態(tài)下的年故障率。但是在大規(guī)模存儲(chǔ)系統(tǒng)中，數(shù)據(jù)丟失情況下往往會(huì)啟動(dòng)恢復(fù)程序，恢復(fù)完了之后理論上又算是從初始狀態(tài)的隨機(jī)事件，加入這個(gè)因素之后計(jì)算可靠性會(huì)變得比較復(fù)雜。

理論上大規(guī)模存儲(chǔ)系統(tǒng)中壞盤、恢復(fù)是極其復(fù)雜的連續(xù)事件，這里我們把這個(gè)概率模型簡(jiǎn)化為不同個(gè)單位時(shí)間 T 內(nèi)的離散事件來進(jìn)行統(tǒng)計(jì)計(jì)算。只要兩個(gè) T 之間連續(xù)事件發(fā)生的概率極小，并且 T 時(shí)間內(nèi)絕大部份壞盤情況能夠恢復(fù)，那么下個(gè)時(shí)間 T 就是重新從新的狀態(tài)開始，則這種估算能夠保證近似正確性。T 的單位定義為小時(shí)，那么 1 年可以劃分為 365*24/T 個(gè)時(shí)間段，那么系統(tǒng)的年故障率可以理解為 100% 減去所有單位 T 時(shí)間內(nèi)都不發(fā)生故障的概率。

即系統(tǒng)整體丟失數(shù)據(jù)的概率為:Pc = 1 - (1-Pb(T))*(36524/T)