我想知道Skiena算法设计手册（第 2 版）中问题 2-44的正确答案是什么
问题如下：
我们有 1,000 个数据项要存储在 1,000 个节点上。每个节点可以存储恰好三个不同项目的副本。提出一种复制方案，以最大程度地减少节点故障时的数据丢失。当三个随机节点发生故障时，预计丢失的数据条目数是多少？
我在考虑节点 n 具有来自 n、n+1 和 n+2 的数据项。
因此，如果丢失 3 个连续节点，那么我们会丢失 1 个项目。
有更好的解决方案吗？
问问题
2731 次
4 回答
6
您提出的方法还不错，但也可以在这里看看。RAID中使用的想法可能会给您一些想法。例如，如果您有 2 个数据项，而不是存储 3 个数据项，如果另一个失败，您可以恢复其中任何一个。这个想法很简单 - 您将项目存储在 2 个节点中，并将它们的位异或存储在第三个项目中。我相信如果您利用这个想法，您将能够对单个数据项进行 3 个以上的备份（即，必须有 3 个以上的节点发生故障才能丢失信息）。
于 2012-04-24T07:00:05.573 回答
3
我想到了像 RAID 级别这样的方法，但 Skiena 说“每个节点可以存储恰好三个不同项目的副本”。尽管两个独立数据的 XOR'red 位模式可以存储在相同数量的空间中，但我不认为这是问题所在。
所以，我从 OP 的想法开始：将每个数据的三个副本以条带方式存储到其下两个邻居。例如，以下是当 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
在所有 20 种三节点故障组合中，有 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 没有描述“数据丢失”对应用程序意味着什么：单个数据点的丢失是否意味着整个集合都被浪费了，或者丢失单个数据点是可以接受的并且比丢失两个更好？
如果即使是单个数据点的丢失就意味着整个集合都被浪费了，那么我们可以做得更好。好三倍！:)
不是以条带方式将数据副本分发到右侧节点，而是定义共享数据的三个节点组。例如，让 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
这仅是 20 种三节点故障组合中的 2 种。当相同的节点共享相同的数据时，它有效地将数据丢失合并到更少的组合中。
阿里
于 2013-12-29T04:45:01.677 回答
1
让，
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- 在初始化期间，每个数据项必须至少存储在一个给定节点中。IE：
Exist at least one 1 <= k <=n s.t. P(d_i \in n_k) = 1.
2- 从 (1) 开始，在初始化时，d_i 在给定节点中的概率至少为 1/n。IE：
For any data item 1 <= i <= d and a random node n, P(d_i \in n) >= 1/n.
给定问题陈述，通过设计，我们希望这种分布在整个数据集中均匀分布。
3- 最后，根据设计，数据项 d_i 在给定节点 n 中的概率应该在数据项之间是独立的。IE：
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）。而 stride 1 的滑动窗口保证 (1)。
让我们将给定节点 n_k 的滑动窗口表示为有序集 w_k = {w_k1, w_k2, w_k3}。n_k 被称为 w_k1（w_k 的第一个元素）的主节点。包含 w_k1 的任何其他节点 n_j 都是副本节点。注意：所提出的复制模型保证任何 d_i 都只有一个主节点，而复制节点的数量取决于窗口长度。
在上面的示例中：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)，P(d_i is lost) = c，对于任何 d_i，在初始化时。
这就是说 d = n = 1000 和复制因子 3（即：窗口长度等于 3）。
P(d_i 丢失) = 1/1000 * 1/999 * 1/998 ~ 10^-9
于 2014-11-07T05:37:05.533 回答