1

問題
親ノードとは通信できるが、相互には通信できないノードのシステムがあるとします。次に、親ノード上のファイルがブロックに分割され、子の間で分割されたとします。その後、ファイルは親ノードから削除されます。

親が子からブロックを要求した場合、親のすべてのファイルのリストを保持せずに元の順序を再構築するにはどうすればよいでしょうか。さらに、ノードの 1 つが悪意を持ってブロックを変更するのを防ぐために、親は戻ってくるブロックを検証する必要もあります。

最適解
ファイルのブロックに名前を付けるシステムで、シードが与えられた任意のノードでファイルのリストを生成できます。リストが与えられた場合、親はリストを使用して、子から返されるブロックを検証できるはずです。

試行 #1
これまでのところ、ブロックのリストを最小限に格納する機能が得られました。ブロックに次のように名前を付けることでそうします。

block_0 = hash(file_contents)
block_n = hash(block_n-1) [hashing the name of the previous file]

これにより、シード (block_0 の名前) とブロック数 (例: 5d41402abc4b2a76b9719d911017c592,5 --> シード、ファイル) を保持するだけで、ファイルの順序を保持できます。ただし、これではファイルを個別に検証することはできません。

試行 #2
各ブロックのハッシュを取得し、それをリストに格納するだけです。ただし、これは効率的ではなく、多数のブロックを追跡する必要がある場合、このタスクだけに大量のメモリが割り当てられることになります。これはしません。

4

1 に答える 1

0

問題があるかどうかはわかりませんが、これが可能な解決策だと思います：

       | Distribution:
parent | buffer = [hash(key, id)), data[id]]; send(buffer);
nodes  | recv(buffer); h_id, data = buffer;

親ノードはローカルを使用して、送信するデータの一部にkeyハッシュ値 ( h_id) を生成し、ローカル ノードは結果とデータ自体の両方を受け取ります。idh_id

       | Reduction:
nodes  | buffer = [h_id, data]; send(buffer);
parent | recv(buffer); h_id, data_id = buffer;

カウンター フローでは、ノードは元h_idのデータと以前に受信したデータの両方を送信する必要があります。そうしないと、次の検証が失敗します。

hash(key, data) == h_id

は親ノードでしか認識されていないためkey、ローカル ノードを変更することは難しく、親ノードで が引き続き有効になるdata よう h_idに変更することは困難です。hash(key, data_id)

data順序付けに関しては、後で再構築するために、 の最初の 4 バイトにパーティションの番号が格納されていると単純に想定できます。

編集：

あなたが指摘したこの余分なストレージに気付いていないかもしれませんが、ここに私が提案しようとしたものがあります. 初期データを持つ4 台のマシン 、 A、B、Cおよびを考えます。P

                             P{key, data[3]}
                                ____|____
                               /    |    \
                             A{}   B{}   C{}

次に、Pマシン間でデータを分散し、データ シャード自体と生成されたハッシュの両方を送信します。

                             P{key, data[3]}
                                ____|____
                               /    |    \
                              A     |     C
     {data[0], hash(key, data[0])}  |  {data[2], hash(key, data[2])}
                                    B
                     {data[1], hash(key, data[1])}

ストア内の最初のバイトがグローバル インデックスであると仮定すると、最初のベースを元の順序でdata[i]再構築できます。data[3]また、各マシンが を保存/受信keyできるようにすると、後ですべてのローカル ノードでハッシュを解除data[i]して再構築することができます。data[3]

エラーの追加は、グローバルに有効であると想定する必要があるため、データのシャードとdata[i]受信したキーに対してのみ発生する可能性があることに注意してください。ここでの要点は、データ パーティション自体だけでなく、値のリストもマシン間で分散されるということです。つまり、任意のマシンだけに保存​​されるすべてのファイルのリストは必要ありません。hash(key, data[i])keyhash(key, data[i])

すべてのノードで維持する余裕があることkey、または少なくともkey元のデータを再構築しようとしている 1 つのノードに送信する余裕があることを考慮して、たとえば node の削減ステップの例を次に示しますB。AそしてCローカル{data[i], hash(key, data[i])}をノードBにP送信keyしB、に送信するため、このノードは受信したデータのハッシュを解除できます。

                             P{key, data[3]}
                                    |
                              A     |     C
     {data[0], hash(key, data[0])}  |  {data[0], hash(key, data[0])}
                                  \ | /
                                    B
                     {data[1], hash(key, data[1])}

次に、次をB計算します。

            / {data[1], hash(key, data[1])} \      {data[1]}
     unhash(  {data[0], hash(key, data[0])}  ) =>  {data[0]}  => {data[3]}
            \ {data[2], hash(key, data[2])} /      {data[2]}

元のデータを正しい順序で復元します。

于 2013-05-30T20:23:05.693 に答える