Lec1: Introduction

[kmansei]

paper: https://pdos.csail.mit.edu/6.824/papers/mapreduce.pdf

[kmansei]

MapReduceはGoogle File Systemの機能の一つ。 GFSはHadoopやApatchの前身となる分散システム

[kmansei]

It is easy to make the master write periodic checkpoints of the master data structures described above. If the master task dies, a new copy can be started from the last checkpointed state. However, given that there is only a single master, its failure is unlikely:

なぜsingle masterの故障がunlikelyなのか

[kmansei]

Semantics in the Presence of Failures ユーザーがmap/reduceに与えた関数が決定的 $\forall xy. x = y \to f(x) = f(y)$ ならば、 map/reduceによる分散処理で得られる出力は、non-faultingな逐次的実行で得られる出力と等しい。

weaker semantics

When the map and/or reduce operators are nondeterministic, we provide weaker but still reasonable semantics. In the　presence of non-deterministic operators, the output of a particular reduce task R1 is equivalent to the output for R1 produced by a sequential execution of the non-deterministic program. However, the output for a different reduce task R2 may correspond to the output for R2 produced by a different sequential execution of the non-deterministic program.

説明が良くわからない。 与えられたmap/reduceが非決定的なら分散による出力と逐次的な実行で得られる値が変わってしまうということなら納得する。 例えば、inputファイルを2分して、それぞれにmapをかけたとき、mapは決定的ではないため、元のinput全体をmapしたものと等しい保証はない。 $f(s1+s2) \neq f(s1) + f(s2)$

[kmansei]

network bandwidth 通信に使われる波の周波数の範囲。 通信速度の速さに直結

[kmansei]

Combiner map -> reduceの間に行われるsemi-reducerみたいなもの

[kmansei]

idempotent 冪等性 $f(x) = f(f(x))$

[kmansei]

sanity check プログラムやシステムが正常に動作しているかのテスト

[kmansei]

Strong Consistency

データxに対する任意の読み込み操作は、xへの（実時間において）最も新しい書き込み結果に対応した値を返す」 分散システムには一般に実装不可能。メッセージ伝送遅延が存在するため

Weak Consistency

一つのプロセスの一連のread/write操作の結果が直ちに他のプロセスに反映されなくてもよい 一連の操作の最終結果のみが他のプロセスの処理に反映されればよい synchronize操作を実行後は、必ず最終結果の値をreadできることを保証

http://www-higashi.ist.osaka-u.ac.jp/~nakata/mobile-cp/chap-06j-1.pdf