ランポート・ベクトル時計を付けて失われた更新と再試行を数える

目標

4つのプロセスのイベント記録に、ランポート時計とベクトル時計を自分で付け、「番号が小さければ先に起きた」がどこで間違うかを、定義で確認します。続いて、壁時計がずれた3つのレプリカの同じキーへの書き込みから衝突を見つけ、壁時計のLWWで統合すると、どの更新が跡形もなく消えるかを数えます。最後に、層ごとにリトライを付けると、DB呼び出しが何倍になるかを計算し、総合レポートを書きます。

なぜ重要なのか

ランポート時計は、a → bなら番号が大きくなることだけを約束し、番号が小さいからといって先に起きたという意味ではありません。この逆を信じてログをソートしたり、衝突を判定したりすると、エラーなしで間違った答えが出ます。ベクトル時計は、並行なイベントを並行だと教えてくれるので、LWWが捨てた更新が何だったのかを数えられるようにしてくれます。リトライも同じ構造です。層ごとに別々に見ると合理的な数字が、掛け合わされて、もっとも弱い場所に集中します。そのため、このラボの採点ツールは、書いた数字だけを見るのではなく、あなたの関数を、用意された素材ではない記録で再実行して、基準の実装と突き合わせます。

用意するもの

/opt/fixtures/svccs/clocks/の下にあります。読み取り専用で使ってください。

events.csv    프로세스 P·Q·R·S 의 사건 기록. 끝내 도착하지 않은 메시지가 하나 있다
replicas.csv  복제본 A·B·C 의 쓰기와 동기화 메시지. 복제본마다 벽시계가 어긋나 있다
pairs.json    {"pairs": [["R3", "S11"], ...]} — 3단계에서 관계를 판정할 사건 쌍
retry.json    {"layers": [{"name", "retries"}, ...위→아래], "blip_fail_first": 정수}

このコードブロックの韓国語の説明は、順に、events.csvはプロセスP・Q・R・Sのイベント記録で、最後まで届かなかったメッセージが1つあること、replicas.csvはレプリカA・B・Cの書き込みと同期メッセージで、レプリカごとに壁時計がずれていること、pairs.jsonはステップ3で関係を判定するイベントのペアであること、retry.jsonは、上から下への層のリスト(nameとretries)と、blip_fail_firstの整数を持つこと、を述べています。

2つのCSVの列はproc,seq,kind,msg,key,value,wall_msです。ファイルはプロセスごと・番号順に書かれています。

proc     프로세스(복제본) 이름. 사건 id 는 proc + seq, 예) P3
seq      그 프로세스 안의 순번(1부터)
kind     local | send | recv | write        (write 는 로컬 사건의 한 종류)
msg      send/recv 의 메시지 id. 수신은 같은 id 의 송신이 보낸 것이다
key,value write 의 키와 값
wall_ms  그 프로세스의 벽시계 값(밀리초). 프로세스마다 어긋나 있다

このコードブロックの韓国語の説明は、順に、procはプロセス(レプリカ)の名前で、イベントidはprocとseqをつないだもの(例: P3)、seqはそのプロセスの中の番号(1から)、kindはlocal・send・recv・writeのいずれか(writeはローカルイベントの一種)、msgはsend/recvのメッセージidで、受信は同じidの送信が送ったものであること、keyとvalueはwriteのキーと値、wall_msはそのプロセスの壁時計の値(ミリ秒)で、プロセスごとにずれていること、を述べています。

ステップ

events.csvを数えて、/root/svccs/clocks/summary.jsonに、events(全イベント数)、by_process({プロセス: イベント数})、locals、sends、recvs(異なるメッセージの数)、in_flight(送信されたが受信されたことのないメッセージidのリスト、ソート済み)を書きます。
/root/svccs/clocks/clocks.pyに、load_events(path)(seqとwall_msは整数に)、lamport(events)を作成します。lamportは{イベントid: 値}を返します。ルール: イベントごとに+1、受信はmax(자기 앞 사건 값, 그 송신의 값) + 1(コード内の韓国語は、順に「自分の直前のイベントの値」「その送信の値」を意味する語です)、プロセスの最初のイベントの前は0。用意されたデータ全体の結果を、/root/svccs/clocks/lamport.jsonに{"clocks": {...}, "max": 가장 큰 값}の形式で書きます(韓国語で「最大の値」を意味する語です)。
同じファイルにhappened_before(events, a, b)を作成します(定義の3つの条件そのまま、a → bならTrue)。pairs.jsonのペアごとにrelationを"a->b"・"b->a"・"concurrent"として判定し、/root/svccs/clocks/hb.jsonに、{"pairs": [{"a", "b", "relation"}, ...], "lamport_misleading": 동시인데 램포트 값이 다른 쌍의 수}の形式で書きます(韓国語で「並行なのにランポートの値が異なるペアの数」を意味する語です)。
同じファイルにvector_clocks(events)({イベントid: [要素...]}、要素の順序はプロセス名の辞書順)とcompare(u, v)("before"・"after"・"equal"・"concurrent")を作成します。events.csvの異なるイベントのペアをすべて比較して、/root/svccs/clocks/vector.jsonに、processes、pairs_total、pairs_ordered、pairs_concurrent、lamport_misleading(並行なペアのうち、ランポートの値が異なるペアの数)、agrees_with_definition(すべてのペアで、ステップ3の定義と同じ答えならtrue)を書きます。
同じファイルにconflicts(events)を作成します。同じキーに対する2つの書き込みが、ベクトル時計で並行なら、衝突です。[[쓰기 id, 쓰기 id], ...]を返します(ペアの中の順序は自由です。韓国語で「書き込み」を意味する語です)。replicas.csvの結果を、/root/svccs/clocks/conflicts.jsonに、writes(書き込みの数)、conflict_pairs、keys(衝突があるキー、ソート済み)として書きます。
同じファイルにlww(events)を作成します。ルールは、下の「LWWのルール」のとおりです。replicas.csvの結果を、/root/svccs/clocks/lww.jsonに、final({キー: 残った値})、lost(リスト)、lost_updates(lostの個数)、causal_inversions(リスト)として書きます。
同じファイルにamplify(retries, fail_first=None)を作成します。ルールは、下の「リトライのルール」のとおりです。retry.jsonを使って、DBが失敗し続けるとき(fail_first=None)と、最初のblip_fail_first回だけ失敗するときを計算し、/root/svccs/clocks/retry.jsonに、layers(名前のリスト)、attempts、db_down・db_blip(それぞれinvocations・db_calls・success)を書きます。
/root/svccs/clocks/report.jsonに、lamport_max、pairs_concurrent、conflicts(衝突のペア数)、lost_updates、causal_inversions(個数)、db_calls_all_layers(DBが失敗し続けるときのDB呼び出し数)、retry_only_at(リトライを残す層の名前を1つ。あなたが選びます)、db_calls_retry_only_at(その層だけリトライし、残りは1回ずつしか試行しないとき、DBが失敗し続けると受ける呼び出し数)、order_with(並行を見分けるには、"lamport"・"vector"・"wall"のうち何で比較する必要があるか)を書きます。

LWWのルール

키마다 wall_ms 가 가장 큰 쓰기가 이긴다. wall_ms 가 같으면 proc 이름이 사전순으로 큰 쪽.
final     키 → 이긴 쓰기의 value            winner  키 → 이긴 쓰기의 id
lost      이긴 쓰기가 아니면서, 이긴 쓰기보다 앞서지(→) 않은 쓰기
          (이긴 쓰기가 이미 본 쓰기는 '덮어쓴' 것이지 잃은 것이 아니다)
inversions lost 가운데 이긴 쓰기보다 인과적으로 뒤인(winner → w) 쓰기
돌려줄 것: {"final", "winner", "lost", "inversions"} — 목록은 정렬

このコードブロックの韓国語の説明は、順に、キーごとにwall_msがもっとも大きい書き込みが勝ち、wall_msが同じならprocの名前が辞書順で大きいほうが勝つこと、finalはキーから勝った書き込みのvalueへの対応、winnerはキーから勝った書き込みのidへの対応、lostは勝った書き込みではなく、かつ勝った書き込みより前にない(→でない)書き込みで、勝った書き込みがすでに見た書き込みは「上書きされた」のであって失われたのではないこと、inversionsはlostのうち、勝った書き込みより因果的に後(winner → w)の書き込み、返す値はfinal・winner・lost・inversionsで、リストはソートすること、を述べています。

リトライのルール

retries 는 위 계층부터의 목록이다. 계층 i 는 불리면 아래를 최대 retries[i] + 1 번 부르고,
한 번이라도 성공하면 그만 부른다. 맨 아래 계층이 부르는 것이 DB 다.
DB 는 한 사용자 동작 동안 받은 호출 가운데 처음 fail_first 번은 실패, 그 뒤로는 성공한다
(fail_first 가 None 이면 계속 실패).
돌려줄 것: attempts(계층별 retries+1), invocations(계층별로 불린 횟수, 맨 위는 1),
          db_calls, success(맨 위 계층이 결국 성공했나)

このコードブロックの韓国語の説明は、順に、retriesは上の層からのリストで、層iは呼び出されると下を最大retries[i] + 1回呼び出し、1回でも成功すればそれ以上呼ばないこと、いちばん下の層が呼ぶのがDBであること、DBは1回のユーザー操作の間に受けた呼び出しのうち、最初のfail_first回は失敗し、その後は成功すること(fail_firstがNoneなら失敗し続ける)、返す値はattempts(層ごとのretries+1)・invocations(層ごとに呼び出された回数で、いちばん上は1)・db_calls・success(いちばん上の層が最終的に成功したか)であること、を述べています。

参考

採点ツールはclocks.pyを読み込みます。ファイルを読んで結果を作るコードは、if __name__ == "__main__":の下か、別のスクリプトに置いてください。関数は、引数として受け取ったイベントのリストだけを使う必要があります。採点ツールは、プロセスの名前や数が異なる記録も渡します。
ファイルがプロセスごとに書かれているので、上から1行ずつ計算すると、受信に出会ったときに送信の値がまだありません。先行するイベントがすべて計算されたイベントから処理してください。
よくある間違い: 受信でmaxなしに+1だけを行うランポート時計、「L(a) < L(b)ならa → b」として因果を判定すること、ベクトルを合計や1つの要素で比較して、並行なものを順序ありと見なすこと、層ごとの試行数を掛けずに足すこと。
出力物はセッションが終わると消えます。必要なら別に保管してください。

イベント記録を読む

events.csvを数えて、/root/svccs/clocks/summary.jsonにevents・by_process・locals・sends・recvs・in_flightを書いてください。

csv.DictReaderで読むと、1行が辞書になります。sendsとrecvsは、異なるmsgの数であり、in_flightは、送信のmsgの集合から受信のmsgの集合を引いたものです。受信されなかったメッセージは、その後のどのイベントの原因にもなれません。

ランポート時計を付ける

/root/svccs/clocks/clocks.pyにload_events・lamportを作成し、用意されたデータ全体の結果を、/root/svccs/clocks/lamport.jsonにclocks・maxとして書いてください。採点ツールは、プロセスの名前と数が異なる変形した記録3つでもlamportを呼び出します。

ローカルと送信は、直前のイベントの値 + 1、受信は、max(直前のイベントの値, 送信の値) + 1です。ファイルの順序どおりに1回走査すると、送信の値がまだない受信に出会います。先行するイベントがすべて計算されたイベントだけを処理し、残ったものは次の周回に回してください。

先に起きたことを定義で判定する

clocks.pyにhappened_before(events, a, b)を作成し、pairs.jsonのペアごとに関係を判定して、/root/svccs/clocks/hb.jsonにpairs・lamport_misleadingを書いてください。採点ツールは、変形した記録のランダムなペアでhappened_beforeを突き合わせます。

a → bは、bから「同じプロセスの直前のイベント」と「受信ならその送信」を逆にたどって、aに届くかどうかです。イベントごとに先行するイベントの集合を作っておくと簡単です。ランポートの値を比較して判定してはいけません。並行な2つのイベントも、値が異なります。

ベクトル時計で並行を見分ける

clocks.pyにvector_clocks・compareを作成し、events.csvのすべてのイベントのペアを比較して、/root/svccs/clocks/vector.jsonを書いてください。採点ツールは、変形した記録でvector_clocksを、手で作ったベクトルでcompareを突き合わせます。

自分の要素を1増やし、受信なら先に要素ごとにmaxで統合します。比較は要素ごとです。すべての要素が小さいか等しければbefore、すべての要素が大きいか等しければafter、どちらでもなければconcurrentです。要素の合計で比較すると、並行なペアにも順序が生じます。

同じキーへの並行する書き込みを見つける

clocks.pyにconflicts(events)を作成し、replicas.csvの結果を、/root/svccs/clocks/conflicts.jsonにwrites・conflict_pairs・keysとして書いてください。採点ツールは、レプリカの数とキーが異なる変形した記録でもconflictsを呼び出します。

衝突は、「キーが同じ」で「ベクトルで並行」な書き込みのペアです。どちらか一方でも欠けると、リストが変わります。壁時計で順序を決めると、並行する書き込みがすべて「前後のある書き込み」に見えます。

LWWが黙って捨てた更新を数える

clocks.pyに、LWWのルールどおりlww(events)を作成し、replicas.csvの結果を、/root/svccs/clocks/lww.jsonにfinal・lost・lost_updates・causal_inversionsとして書いてください。採点ツールは、壁時計のずれが異なる変形した記録でもlwwを呼び出します。

上書きされた書き込みがすべて失われたわけではありません。勝った書き込みがそれをすでに見て(→)書いたなら、意図された上書きです。失われたのは、勝った側が見たことのない書き込みであり、そのうち、勝った書き込みより因果的に後のものが因果の逆転です。

層ごとにリトライすると何倍になるか

clocks.pyに、リトライのルールどおりamplify(retries, fail_first=None)を作成し、retry.jsonを使って2つのシナリオを計算して、/root/svccs/clocks/retry.jsonに書いてください。採点ツールは、別の層の数・リトライ数・fail_firstでもamplifyを呼び出します。

retriesは「再試行する回数」なので、試行数はretries + 1です。層iが呼び出された回数は、上の層の試行数を掛けたものであり、DBが失敗し続けるなら、DB呼び出しは、すべての層の試行数の積です。DBが途中で復旧する場合は、再帰で実際に流してみるほうが安全です。

総合レポート

/root/svccs/clocks/report.jsonにlamport_max・pairs_concurrent・conflicts・lost_updates・causal_inversions・db_calls_all_layers・retry_only_at・db_calls_retry_only_at・order_withを書いてください。

前のステップの出力物から書き写せばよい値がほとんどです。retry_only_atは、あなたが選ぶ層の名前であり、その層だけがリトライするなら、DB呼び出しは、その層の試行数と等しくなります。order_withは、「並行」という答えを出せる方法でなければなりません。