論文メモ Availability in Globally Distributed Storage Systems

December 12, 2020

Googleの分散ストレージで生じた障害の統計をとり、ストレージの可用性の予測モデルを提唱した。 ディスク、ノード、ラックなどハードウェアの粒度を変えて、粒度ごとの平均故障間隔を計測し、故障原因を分類した。 2分のウィンドウで生じた障害をグループにまとめると、ほとんどの障害が同時多発的な障害の一部であった。 20以上のノードを巻き込む大きな障害では、別々のラックにあるノードに障害が起きるよりも、特定のラックのノードに障害が起きることが多かった。

誤り訂正機能をもつストレージの可用性をマルコフモデルで予測する。 このストレージをストライプと呼び、チャンクというコードブロックを冗長にもつことで、誤りを訂正すると仮定する。 ストライプに\(s\)個のチャンクがあり、ストライプの復元に必要な正常なチャンクの数が\(r\)のとき、\(s,s-1, \dots , r, r-1\)のように、復元可能なときのチャンク数と復元不能を示す記号で状態を作る。 以下の図は、\(s=2, r=2\)のモデルを表す。

markov

チャンクが一度に一つしか壊れないとして、故障する確率を\(\lambda\)、復元する確率を\(\rho\)おくと、Gambler’s Ruinより、\(s\)から\(s-r\)に遷移するまでの遷移回数は次の式になる。

$$ \frac{1}{\lambda}\left(\sum^{s-r}_{k=0}\sum^k_{i=0}\frac{\rho^i}{\lambda^i}\frac{1}{(s-k+i)_{(i+1)}}\right) $$

ただし、\((a)_{(b)}\)は\((a)(a-1)(a-2)\dots (a-b+1)\)をしめす。 このとき、さらに、\(\rho » \lambda\)とすると、ストライプの平均故障間隔(MTTF)は

$$ \frac{\rho^{s-r}}{\lambda^{s-r+1}}\frac{1}{(s)_{(s-r+1)}}+\mathcal{O}\left(\frac{\rho^{s-r-1}}{\lambda^{s-r}}\right) $$

になる。


論文をこちらからダウンロードできます。