需要比 MMDS 更好的解释 MapReduce 的通信成本模型

Question

我正在阅读 MMDS 书籍，该书有一个同名的在线 MOOC。我无法理解主题 2.5 中提到的通信成本模型和连接操作计算，并且对这本书的组织如此糟糕感到惊讶，因为 MOOC 在“MapReduce 的高级主题/计算复杂性”中涵盖了相同的主题。课程。

有一个练习题（示例根本没有帮助），如下所示：

我们希望采用连接 R(A,B) |><| S(B,C) |><| T(A,C) as a single MapReduce process, in a way that minimizes the communication cost. We shall use 512 Reduce tasks, and the sizes of relations R, S, and T are 220 = 1,048,576, 217 = 131,072, and 214 = 16,384, respectively. Compute the number of buckets into which each of the attributes A, B, and C are to be hashed. Then, determine the number of times each tuple of R, S, and T is replicated by the Map function.

你能引导我完成它吗？我不知道他是如何从简单的 R+S+T 跳到拉格朗日恒等式而不考虑中间步骤的。

Answer 1

假设我们应该将三个属性 A、B、C 分别哈希到 a、b、c 桶中，使得 abc = k，其中 k 是减速器的数量（512）。 根据2.5节中提到的通信成本模型，我们可以将拉格朗日方程扩展如下：

as+cr+bc-lambda*(abc - k)

如果对上式求导。我们有：

s -lambda*bc=0      r -lambda*ab=0    t -lambda*ac=0

(1) s =lambda*bc
(2) r =lambda*ab
(3) t =lambda*ac

如果我们乘以 1,2,3 我们有 rst=(lamba^3)a^2b^2*c^2

lamba=(srt/k^2)^(1/3)

通过替换这些值，我们得到 lambda=2048 并可以计算 a,b,c