分散ネットワークでのシステム障害の確率を計算する

https://stackoverflow.com/questions/3092694

29-09-2019
|

質問

分散ファイルシステム内のファイルの可用性の数学的モデルを構築しようとしています。この質問をMathoverFlowに投稿しましたが、これはCS-Questionとして分類される可能性があるため、ここでもショットを撮ります。

システムは次のように機能します。Aノードは、r*bリモートノードにファイル（消去コードを使用してエンコード）を保存します。ここで、Rは複製ファクターで、Bは整数定数です。消去コードされたファイルには、少なくともリモートノードのBが利用可能であり、ファイルの一部を返す場合、ファイルを復元できるというプロパティがあります。

これに対する最も簡単なアプローチは、すべてのリモートノードが互いに独立しており、同じ可用性pを持っていると仮定することです。これらの仮定により、ファイルの可用性は二項分布に従います。二項分布http://bit.ly/dyjwwe

残念ながら、これらの2つの仮定は、この論文に示すように、非対応エラーを導入できます。 http://deim.urv.cat/~lluis.pamies/uploads/main/icpp09-paper.pdf.

すべてのノードが同じ可用性を持っているという仮定を克服する1つの方法は、利用可能/利用可能なノードの各組み合わせの可能な組み合わせの確率を計算し、これらすべての結果の合計を取ることです（これは、上記の論文で示唆するもののようなものです。私が今説明したものよりも正式に）。このアプローチは、深さr*bを持つバイナリツリーとして見ることができ、各休暇は利用可能な/利用可能なノードの1つの組み合わせです。ファイルの可用性は、> = b利用可能なノードで休暇に到達する確率と同じです。このアプローチはより正確ですが、の計算コストがあります Ordo http://bit.ly/cezcap. 。また、ノードの独立性の仮定には対処しません。

君たちは、二項分布の広がりよりも少ないエラーを導入するが、計算コストが向上している良い近似のアイデアを持っていますか？ http://bit.ly/d52mm9 http://bit.ly/cezcap?

各ノードの可用性データは、からなるタプルのセットであると仮定できます。 (measurement-date, node measuring, node being measured, succes/failure-bit). 。このデータを使用すると、たとえば、ノードと可用性の差異の間の可用性の相関関係を計算できます。

解決

大きなために r と b Monte-Carlo統合と呼ばれる方法を使用できます。ウィキペディアのモンテカルロ統合（および/またはSICPの第3.1.2章）合計を計算します。小さい場合 r と b そして、大幅に異なるノードフェイル確率 p[i] 正確な方法は優れています。の正確な定義 小さな と 大きい いくつかの要因に依存し、実験的に試してみるのが最適です。

特定のサンプルコード: ：これは、そのような手順がどのように機能するかを示すための非常に基本的なサンプルコード（Python）です。

def montecarlo(p, rb, N):
    """Corresponds to the binomial coefficient formula."""
    import random
    succ = 0

    # Run N samples
    for i in xrange(N):
        # Generate a single test case
        alivenum = 0
        for j in xrange(rb):
            if random.random()<p: alivenum += 1
        # If the test case succeeds, increase succ
        if alivenum >= b: succ += 1
    # The final result is the number of successful cases/number of total cases
    # (I.e., a probability between 0 and 1)
    return float(succ)/N

関数は二項テストケースに対応し、実行されます N テスト、チェックの場合 b からのノード r*b ノードは、故障の可能性で生きています p. 。いくつかの実験は、あなたがの値が必要であることをあなたに納得させるでしょう N 合理的な結果を得る前に数千のサンプルの範囲では、原則として複雑さは O(N*r*b). 。結果の精度はasとして sqrt(N), 、つまり、精度を2倍にするには、増加する必要があります N 4倍。十分に大きい場合 r*b この方法は明らかに優れています。

近似の拡張: ：システムのすべてのプロパティを尊重するように、テストケースを設計する必要があります。いくつかの拡張機能を提案しましたが、その一部は簡単に実装できますが、他の拡張機能は簡単に実装できます。いくつかの提案をさせてください：

1）明確だが無相関の場合 p[i], 、上記のコードの変更は最小限です。関数ヘッドでは、単一のフロートの代わりに配列を渡す p そして、あなたは線を交換します if random.random()<p: alivenum += 1 に

if random.random()<p[j]: alivenum += 1

2）相関の場合 p[i] システムに関する追加情報が必要です。私がコメントで言及していた状況は、次のようなネットワークである可能性があります。

A--B--C
   |  |
   D  E
   |
   F--G--H
      |
      J

この場合 A 「ルートノード」とノードの障害である可能性があります D ノードの100％確率で自動障害を意味する可能性があります F, G, H と J;ノードの障害中 F 自動的にダウンします G, H と J 少なくともこれは私が私のコメントで言及していた場合でした（これは、元の質問の確率の木の構造について話しているので、もっともらしい解釈です）。このような状況では、コードを変更する必要があります p 木の構造を指します for j in ... ツリーを横断し、テストが失敗するとすぐに、現在のノードから下部ブランチをスキップします。結果のテストはまだかどうかです alivenum >= b もちろん、前と同じです。

3）ネットワークがツリー構造で表すことができない周期的なグラフである場合、このアプローチは失敗します。そのような場合、最初に死んだか生き生きとしているグラフノードを作成し、次にグラフでルーティングアルゴリズムを実行して、一意の到達可能なノードの数をカウントする必要があります。これにより、アルゴリズムの時間的酸素性は増加しませんが、明らかにコードの複雑さは増加しません。

4）時間の依存は非自明ですが、MTBF/R（平均的なものの間の対戦/修理）を知っている場合は、可能な変更です。 p ツリー構造または無相関線形のいずれかのいずれか p[i] 指数の合計によって。その後、対応する結果を使用して、さまざまな時間にMCプロセッドを実行する必要があります p.

5）（最後の段落で示唆されているように）ログファイルを持っているだけの場合、このボードでできる以上のアプローチを大幅に変更する必要があります。ログファイルは、ネットワークグラフのモデルを再構築するために十分に徹底的である必要があります（したがって、のグラフは p）のすべてのノードの個々の値と同様に p. 。それ以外の場合、精度は信頼できません。また、これらのログファイルは、障害と修理のタイムスケールよりもかなり長くする必要があります。これは、実際のネットワークでは現実的ではないかもしれない仮定です。

他のヒント

各ノードに一定の既知の独立した可用性率があると仮定すると、格差と征服のアプローチが思い浮かびます。

あなたが持っていると言ってください N ノード。

それらを2つのセットに分割します N/2 ノード。
それぞれの側について、任意の数のノード（[0,N/2]）ダウンしています。
必要に応じてこれらを乗算して合計して、任意の数字（[0,N]）フルセットがダウンしています。

ステップ2は再帰的に行うことができ、最上位レベルでは、いくつかの数が減少している頻度を見つける必要があるため、合計することができます。

私はこれの複雑さを知りませんが、私が推測する必要があるなら、私は下または下に言うと言います O(n^2 log n)

これの仕組みは、端末ケースに示すことができます。アップタイムの5つのノードがあるとします $p_1...p_5$ . 。これをセグメントに分割できます A と $p_1...p_2$ と B と $p_2...p_6$ . 。次に、これらを処理して、各セグメントの「nノードアップ」時間を見つけることができます。

のために：

$a_2=p_1p_2$

$a_1=p_1(1-p_2)+(1-p_1)p_2$

$a_0=(1-p_1)(1-p_2)$

Bの場合：

$b_2=p_3p_4p_5$

$b_2..b_0$

この段階の最終結果は、それぞれを掛けることで見つけることができます aそれぞれと b適切に合計しています。

v[0] = a[0]*b[0]
v[1] = a[1]*b[0] + a[0]*b[1]
v[2] = a[2]*b[0] + a[1]*b[1] + a[0]*b[2]
v[3] =             a[2]*b[1] + a[1]*b[2] + a[0]*b[3]
v[4] =                         a[2]*b[2] + a[1]*b[3]
v[5] =                                     a[2]*b[3]

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow