スキーナのアルゴリズム設計マニュアル（第2版）の質問2-44の正しい答えは何でしょうか。
質問は次のとおりです。
1,000ノードに保存する1,000個のデータアイテムがあります。各ノードは、正確に3つの異なるアイテムのコピーを格納できます。ノードに障害が発生したときのデータ損失を最小限に抑えるためのレプリケーションスキームを提案します。3つのランダムノードに障害が発生したときに失われるデータエントリの予想数はいくつですか？
n、n + 1、n+2のデータ項目を持つノードnについて考えていました。
したがって、3つの連続するノードが失われると、1つのアイテムが失われます。
より良い解決策はありますか？
あなたが提案するアプローチは悪くはありませんが、ここも見てください。RAIDで使用されるアイデアは、いくつかのアイデアを与える可能性があります。たとえば、2つのデータ項目がある場合、3つの項目のストレージがあるよりも、他の項目が失敗した場合にそれらのいずれかを回復できます。考え方は非常に単純です。アイテムを2つのノードに格納し、それらのビットのxorを3番目のアイテムに格納します。このアイデアを利用すると、1つのデータ項目のバックアップを3つ以上持つことができると思います（つまり、情報を失うには3つ以上のノードで障害が発生する必要があります）。
RAIDレベルのような方法を考えましたが、Skienaは「各ノードは正確に3つの異なるアイテムのコピーを保存できる」と言っています。2つの別々のデータのXOR'redビットパターンを同じ量のスペースに格納できますが、それが問題であるとは思いませんでした。
そこで、私はOPの考えから始めました。各データの3つのコピーを、次の2つの隣接データにストライプ状に保存します。たとえば、以下はN == 6の場合で、データは0から5までの整数です（4と5はラップアラウンドし、ノード0と1を使用します）。
nodes: 0 1 2 3 4 5
===========
copy 0 -> 0 1 2 3 4 5
copy 1 -> 5 0 1 2 3 4
copy 2 -> 4 5 0 1 2 3
3ノード障害の20の組み合わせすべてのうち、正確に1つのデータを失うのは6つです。例えば; ノード1、2、および3に障害が発生すると、データ1は失われます。
===========
0 X X X 4 5
5 X X X 3 4
4 X X X 2 3
互いにデータが類似しているため、20の組み合わせのうち6つを作成するとデータが失われます。Skienaは、アプリケーションにとっての「データ損失」の意味を説明していないため、単一のデータポイントの損失は、コレクション全体が無駄になることを意味しますか、それとも1つのデータポイントを失うことは許容でき、2つを失うよりも優れていますか？
データポイントが1つでも失われるということは、コレクション全体が無駄になることを意味する場合は、より良い結果が得られます。3倍良い！:)
データのコピーをストライプ形式で右側のノードに配布する代わりに、データを共有する3つのノードのグループを定義します。たとえば、0、1、および2がデータを共有し、3、4、および5がデータを共有するとします。
nodes: 0 1 2 3 4 5
===========
copy 0 -> 0 1 2 3 4 5
copy 1 -> 2 0 1 5 3 4
copy 2 -> 1 2 0 4 5 3
今回は、20の組み合わせのうち2つだけがデータ損失を引き起こします。ノード0、1、および2に障害が発生すると、データ0、1、および2が一緒に失われます。
===========
x x x 3 4 5
x x x 5 3 4
x x x 4 5 3
また、ノード3、4、および5に障害が発生すると、データ3、4、および5は一緒に失われます。
===========
0 1 2 x x x
2 0 1 x x x
1 2 0 x x x
これは、3ノード障害の20の組み合わせのうちの2つに相当します。同じノードが同じデータを共有する場合、データ損失をより少ない数の組み合わせに効果的にマージします。
アリ
させて、
D = {1,...,d_i,...,d} denote the data items and d_i a given data element
N = {1,...,n_k,...,n} denote the storage cluster and n_k a given storage node.
We say d_i is stored by n_k, loosely denoted by d_i \in n_k.
私のレプリケーションモデルには、次の前提があります。
1-すべてのデータ項目は、初期化中に少なくとも1つの特定のノードに格納する必要があります。すなわち：
Exist at least one 1 <= k <=n s.t. P(d_i \in n_k) = 1.
2-（1）から、初期化時に、d_iが特定のノードに存在する確率は少なくとも1/nです。すなわち：
For any data item 1 <= i <= d and a random node n, P(d_i \in n) >= 1/n.
問題の記述を考えると、設計上、この分布をデータセット全体で均一にする必要があります。
3-最後に、設計上、データ項目d_iが特定のノードnに存在する確率は、データ項目間で独立している必要があります。すなわち：
P(d_i \in n | d_j \in n) = P(d_i \in n)
これは、ノード障害の確率が隣接ノード間で独立しているとは想定していないためです（たとえば、データセンターでは、隣接ノードが同じネットワークスイッチを共有しているなど）。
これらの仮定から、次のレプリケーションモデルを提案しました（d = nであり、各ノードが正確に3つの異なるデータ項目を格納する問題インスタンスの場合）。
（1）データセットのランダム置換を実行します。（2）長さ3およびストライド1のスライディングウィンドウを使用して、シャッフルされたデータセット上で回転し、データ項目を各ノードにマップします。
E.g.:
D = {A,B,C,D}
N = {1,2,3,4}
(1) {C, B, A, D}
(2) 1 -> {C, B, A}, 2 -> {B, A, D}, 3-> {A, D, C}, 4-> {D, C, B}
ランダムシャッフルにより、独立（3）および均一な分布（2）が保証されます。ストライド1のスライディングウィンドウは（1）を保証します。
与えられたノードn_kのスライディングウィンドウを順序集合w_k={w_k1、w_k2、w_k3}として示しましょう。n_kは、w_k1（w_kの最初の要素）のマスターノードであると言われます。w_k1を含む他のノードn_jは、レプリカノードです。注意：提案されたレプリケーションモデルは、任意のd_iに対して1つのマスターノードのみを保証しますが、レプリカノードの数はウィンドウの長さに依存します。
上記の例では、n_1はCのマスターノードであり、n_3とn_4のレプリカノードです。
元の問題に戻ると、このスキーマが与えられると、データが失われる可能性は、特定のデータ項目のマスターノードとすべてのレプリカが失われることであると言えます。
P（d_iが失われました）= P（d_iのマスターノードが失敗し、レプリカ1が失敗し、レプリカ2が失敗します）。
正式な証明がない場合、上記のステップ（1）の偏りのないランダム順列は次のようになります。
P（d_iが失われる）= P（d_iのマスターノードが失敗する）* P（レプリカ1が失敗する）* P（レプリカ2が失敗する）。
繰り返しますが、ランダム順列は、ノード障害の同時分布を抽象化するためのヒューリスティックです。
仮定（2）および（3）から、初期化時に、任意のd_iに対してP（d_iが失われます）=cになります。
つまり、d = n = 1000で、レプリケーション係数が3（つまり、ウィンドウの長さが3に等しい）の場合です。
P（d_iが失われる）= 1/1000 * 1/999 * 1 / 998〜10 ^ -9
あなたのアプローチは本質的に正しいように見えますが、フェイルオーバー戦略の恩恵を受けることができます。スキーナ教授が「ノードに障害が発生した場合のデータ損失を最小限に抑える」ように求めていることに注意してください。これは、ノードの障害が一般的に発生することを示唆しています。
コンシステントハッシュ法を確認することをお勧めします。
また、（固定MODハッシュを使用する代わりに）コンシステントハッシュを使用しないことの危険性について、redditエンジニアによるすばらしい投稿があります。