加上 Lamport 与向量时钟，统计丢失的更新与重试

目标

亲手给四个进程的事件记录加上 Lamport 时钟和向量时钟，按定义确认“编号小就先发生”错在哪里。接着在墙钟有偏差的三个副本对同一个键的写入中找出冲突，并统计如果用墙钟 LWW 合并，哪些更新会毫无痕迹地消失。最后计算如果每一层都加上重试，DB 调用会变成几倍，并写出综合报告。

为什么重要

Lamport 时钟只承诺如果 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": 정수}

两个 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  그 프로세스의 벽시계 값(밀리초). 프로세스마다 어긋나 있다

步骤

把 events.csv 数一遍，把 events（全部事件数）、by_process（{进程: 事件数}）、locals、sends、recvs（互不相同的消息数）、in_flight（已发送但从未被接收的消息 id 列表，已排序）写入 /root/svccs/clocks/summary.json。
在 /root/svccs/clocks/clocks.py 中编写 load_events(path)（seq、wall_ms 为整数）和 lamport(events)。lamport 返回 {事件 id: 值}。规则：每个事件 +1，接收是 max(자기 앞 사건 값, 그 송신의 값) + 1（占位符依次为自己前一个事件的值、对应发送的值），进程的第一个事件之前为 0。把对全部材料的结果，以 {"clocks": {...}, "max": 가장 큰 값}（占位符为最大值）写入 /root/svccs/clocks/lamport.json。
在同一个文件里编写 happened_before(events, a, b)（完全按定义的三个条件，如果 a → b 则为 True）。对 pairs.json 中的每一对，把 relation 判定为 "a->b"、"b->a"、"concurrent"，并以 {"pairs": [{"a", "b", "relation"}, ...], "lamport_misleading": 동시인데 램포트 값이 다른 쌍의 수}（占位符为并发但 Lamport 值不同的事件对数）写入 /root/svccs/clocks/hb.json。
在同一个文件里编写 vector_clocks(events)（{事件 id: [格...]}，格的顺序为进程名称的字典序）和 compare(u, v)（"before"、"after"、"equal"、"concurrent"）。把 events.csv 中互不相同的全部事件对都比较一遍，把 processes、pairs_total、pairs_ordered、pairs_concurrent、lamport_misleading（并发的事件对中 Lamport 值不同的对数）、agrees_with_definition（所有事件对的答案都与第 3 步的定义相同则为 true）写入 /root/svccs/clocks/vector.json。
在同一个文件里编写 conflicts(events)。同一个键的两个写入如果按向量时钟是并发的，就是冲突。返回 [[쓰기 id, 쓰기 id], ...]（占位符均为写入 id；每对内部的顺序任意）。把对 replicas.csv 的结果，以 writes（写入数）、conflict_pairs、keys（有冲突的键，已排序）写入 /root/svccs/clocks/conflicts.json。
在同一个文件里编写 lww(events)。规则完全按下面的“LWW 规则”。把对 replicas.csv 的结果，以 final（{键: 留下的值}）、lost（列表）、lost_updates（lost 的个数）、causal_inversions（列表）写入 /root/svccs/clocks/lww.json。
在同一个文件里编写 amplify(retries, fail_first=None)。规则完全按下面的“重试规则”。用 retry.json 计算 DB 持续失败时（fail_first=None）和只在最初 blip_fail_first 次失败时两种情形，把 layers（名称列表）、attempts、db_down、db_blip（各自带有 invocations、db_calls、success）写入 /root/svccs/clocks/retry.json。
在 /root/svccs/clocks/report.json 中写入 lamport_max、pairs_concurrent、conflicts（冲突对数）、lost_updates、causal_inversions（个数）、db_calls_all_layers（DB 持续失败时的 DB 调用数）、retry_only_at（保留重试的那一层的名称——由你来选）、db_calls_retry_only_at（只在该层重试、其余各层只尝试一次，而 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"} — 목록은 정렬

重试规则

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

参考

评分器会导入 clocks.py。读取文件并生成结果的代码，请放在 if __name__ == "__main__": 之下或单独的脚本里。函数只能使用作为参数收到的事件列表——评分器也会传入进程名称和数量都不同的记录。
文件是按进程记录的，所以如果从上往下逐行计算，遇到接收时，发送的值还没有。请从先行事件都已计算完毕的事件开始处理。
常见错误：在接收时不取 max 只做 +1 的 Lamport 时钟；用“如果 L(a) < L(b) 则 a → b”来判定因果；把向量按和（sum）或只看一格来比较，把并发看成有顺序；对各层的尝试次数不做乘法而是做加法。
产出会在会话结束后消失。需要的话请另行保存。

读取事件记录

把 events.csv 数一遍，把 events、by_process、locals、sends、recvs、in_flight 写入 /root/svccs/clocks/summary.json。

用 csv.DictReader 读取，每一行是一个字典。sends 和 recvs 是互不相同的 msg 的数量，in_flight 是发送的 msg 集合减去接收的 msg 集合。没有被接收的消息，不会成为之后任何事件的原因。

加上 Lamport 时钟

在 /root/svccs/clocks/clocks.py 中编写 load_events、lamport，并把对全部材料的结果，以 clocks、max 写入 /root/svccs/clocks/lamport.json。评分器也会用进程名称和数量各不相同的三份变形记录调用 lamport。

本地事件和发送是前一个事件的值 + 1，接收是 max(前一个事件的值, 发送的值) + 1。如果按文件顺序扫一遍，就会遇到发送的值还没有的接收——只处理先行事件都已计算完毕的事件，把剩下的留到下一轮。

按定义判定先发生

在 clocks.py 中编写 happened_before(events, a, b)，对 pairs.json 的每一对判定关系，把 pairs、lamport_misleading 写入 /root/svccs/clocks/hb.json。评分器会用变形记录的随机事件对来对照 happened_before。

a → b 就是：从 b 出发，沿着“同一进程的前一个事件”和“如果是接收则对应的发送”反向追溯，能否到达 a。为每个事件事先做好先行事件集合就很容易。不能比较 Lamport 值来判定——并发的两个事件，值也不同。

用向量时钟分辨并发

在 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 的结果，以 writes、conflict_pairs、keys 写入 /root/svccs/clocks/conflicts.json。评分器也会用副本数和键各不相同的变形记录调用 conflicts。

冲突就是“键相同”且“按向量时钟并发”的写入对。缺了其中任何一个，列表都会不同。如果用墙钟来定顺序，所有并发写入看上去都成了“有先后的写入”。

数出 LWW 悄悄丢弃的更新

在 clocks.py 中按 LWW 规则编写 lww(events)，把对 replicas.csv 的结果，以 final、lost、lost_updates、causal_inversions 写入 /root/svccs/clocks/lww.json。评分器也会用墙钟偏差不同的变形记录调用 lww。

被覆盖的写入并不都是丢失。如果获胜的写入已经看过（→）它再写的，那就是有意的覆盖。丢失的是获胜一方没有见过的写入，其中在因果上晚于获胜写入的，就是因果倒置。

每层都重试会变成几倍

在 clocks.py 中按重试规则编写 amplify(retries, fail_first=None)，用 retry.json 计算两种情形，写入 /root/svccs/clocks/retry.json。评分器也会用别的层数、重试次数、fail_first 调用 amplify。

retries 是“再次尝试的次数”，所以尝试次数是 retries + 1。第 i 层被调用的次数，是上面各层尝试次数之积，而如果 DB 持续失败，DB 调用数就是所有层尝试次数之积。DB 中途恢复的情形，用递归真正流转一遍更稳妥。

综合报告

把 lamport_max、pairs_concurrent、conflicts、lost_updates、causal_inversions、db_calls_all_layers、retry_only_at、db_calls_retry_only_at、order_with 写入 /root/svccs/clocks/report.json。

大多数值只要从前面步骤的产出中抄过来就行。retry_only_at 是由你选的层的名称，只在该层重试时，DB 调用数就等于该层的尝试次数。order_with 必须是能给出“并发”这个答案的方法。