Attach Lamport and Vector Clocks and Count Lost Updates and Retries

목표

프로세스 넷의 사건 기록에 램포트 시계와 벡터 시계를 직접 달고, "번호가 작으면 먼저 일어났다" 가 어디서 틀리는지 정의로 확인합니다. 이어서 벽시계가 어긋난 복제본 셋의 같은 키 쓰기에서 충돌을 찾고, 벽시계 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": 정수}

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

단계

1. events.csv 를 세어 /root/svccs/clocks/summary.json 에 events(전체 사건 수), by_process({프로세스: 사건 수}), locals, sends, recvs(서로 다른 메시지 수), in_flight(보냈지만 받힌 적 없는 메시지 id 목록, 정렬)를 적습니다.
2. /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": 가장 큰 값} 으로 적습니다.
3. 같은 파일에 happened_before(events, a, b) 를 만듭니다(정의의 세 조건 그대로, a → b 이면 True). pairs.json 의 쌍마다 relation 을 "a->b"·"b->a"·"concurrent" 로 판정해 /root/svccs/clocks/hb.json 에 {"pairs": [{"a", "b", "relation"}, ...], "lamport_misleading": 동시인데 램포트 값이 다른 쌍의 수} 로 적습니다.
4. 같은 파일에 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)을 적습니다.
5. 같은 파일에 conflicts(events) 를 만듭니다. 같은 키에 대한 쓰기 두 개가 벡터 시계로 동시이면 충돌입니다. [[쓰기 id, 쓰기 id], ...] 를 돌려줍니다(쌍 안의 순서는 자유). replicas.csv 의 결과를 /root/svccs/clocks/conflicts.json 에 writes(쓰기 수), conflict_pairs, keys(충돌이 있는 키, 정렬)로 적습니다.
6. 같은 파일에 lww(events) 를 만듭니다. 규칙은 아래 'LWW 규칙' 그대로입니다. replicas.csv 의 결과를 /root/svccs/clocks/lww.json 에 final({키: 남은 값}), lost(목록), lost_updates(lost 의 개수), causal_inversions(목록)로 적습니다.
7. 같은 파일에 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)을 적습니다.
8. /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 만 하는 램포트 시계, "L(a) < L(b) 이면 a → b" 로 인과를 판정하는 것, 벡터를 합(sum)이나 한 칸으로 비교해 동시를 순서 있음으로 보는 것, 계층별 시도 수를 곱하지 않고 더하는 것.
• 산출물은 세션이 끝나면 사라집니다. 필요하면 따로 보관하세요.

사건 기록을 읽는다

events.csv 를 세어 /root/svccs/clocks/summary.json 에 events·by_process·locals·sends·recvs·in_flight 를 적는다.

csv.DictReader 로 읽으면 한 줄이 딕셔너리입니다. sends 와 recvs 는 서로 다른 msg 의 수이고, in_flight 는 송신 msg 집합에서 수신 msg 집합을 뺀 것입니다. 받히지 않은 메시지는 이후 어떤 사건의 원인도 되지 못합니다.

램포트 시계를 단다

/root/svccs/clocks/clocks.py 에 load_events·lamport 를 만들고, 재료 전체의 결과를 /root/svccs/clocks/lamport.json 에 clocks·max 로 적는다. 채점기는 프로세스 이름과 개수가 다른 변형 기록 셋으로도 lamport 를 부른다.

로컬·송신은 앞 사건 값 + 1, 수신은 max(앞 사건 값, 송신 값) + 1 입니다. 파일 순서대로 한 번 훑으면 송신 값이 아직 없는 수신이 나옵니다 — 선행 사건이 모두 계산된 사건만 처리하고, 남은 것은 다음 바퀴로 넘기세요.

먼저 일어남을 정의로 판정한다

clocks.py 에 happened_before(events, a, b) 를 만들고, pairs.json 의 쌍마다 관계를 판정해 /root/svccs/clocks/hb.json 에 pairs·lamport_misleading 을 적는다. 채점기는 변형 기록의 무작위 쌍으로 happened_before 를 대조한다.

a → b 는 b 에서 '같은 프로세스의 앞 사건' 과 '수신이면 그 송신' 을 거꾸로 따라가 a 에 닿는가입니다. 사건마다 앞선 사건 집합을 만들어 두면 쉽습니다. 램포트 값을 비교해 판정하면 안 됩니다 — 동시인 두 사건도 값이 다릅니다.

벡터 시계로 동시를 가려낸다

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 으로 두 시나리오를 계산해 /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 는 '동시' 라는 답을 낼 수 있는 방법이어야 합니다.