1

问题
假设我有一个可以与父节点通信但不能相互通信的节点系统。假设然后父节点上的文件被分成块并在子节点之间划分。然后从父节点中删除该文件。

如果父级随后向子级请求块，如何在不保留父级上所有文件的列表的情况下重建原始顺序。此外，为了防止其中一个节点恶意修改区块，父节点还必须验证返回的区块。

最佳解决方案
命名文件块的系统，其中文件列表可以在给定种子的任何节点上生成。给定列表，父母应该能够以某种方式使用该列表来验证从孩子返回的块。

尝试#1
所以到目前为止我所拥有的是能够最小化存储块列表的能力。我通过这样命名块来做到这一点：

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

这可以通过仅保留种子（block_0 的名称）和块数（例如 5d41402abc4b2a76b9719d911017c592,5 --> seed,files）来保留文件的顺序。但是，这将不允许独立验证文件。

尝试 #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存储分区的编号 - 以供以后重建。

编辑：

我可能没有注意到你指出的这个额外的存储空间，但这是我试图提出的。考虑具有初始数据的四台机器、A、和：BCP

                             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 分片data[i]和接收到的 keyhash(key, data[i])上，因为您必须假设key它是全局有效的。这里的要点是hash(key, data[i])值列表也分布在机器之间，而不仅仅是数据分区本身，也就是说，您不需要将所有文件单独存储在任何机器中的列表。

考虑到您可以负担得起key在每个节点中进行维护，或者至少发送key到尝试重建原始数据的一个节点，这里有一个减少步骤的示例，例如 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 回答