Суть Читай код обновления часов и трассы событий — инкремент Lamport, merge vector clock, сравнение happens-before и детекцию конкурентности — и предсказывай результат.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на senior-высоте — в орбите
◷ 14 min
Логические часы — это крошечные куски кода с тонкими правилами корректности. Прочитай каждую процедуру обновления и трассу событий, затем выбери ответ, который senior-инженер защитит на ревью — где на самом деле живёт баг, порядок или вердикт о конкурентности.
Цель
Отработай базовые операции логических часов в коде: инкремент Lamport на отправку и приём, merge vector clock, сравнение happens-before и детекцию того, что два события конкурентны, а не упорядочены.
Обработчик приёма игнорирует msg_t. Какой инвариант это ломает и каков фикс?
Heads-up Простой инкремент игнорирует прогресс отправителя. Если часы отправителя были далеко впереди, событие receive может получить МЕНЬШИЙ timestamp, чем send, нарушая то, что send happens-before receive.
Heads-up Сброс в msg_t может сдвинуть часы назад и теряет собственный локальный прогресс. Правило — max из двух плюс единица, никогда не просто принять входящее значение.
Heads-up Приём — ЭТО событие и обязан продвинуть часы. Дефект в отбрасывании msg_t, а не в инкременте; фикс сначала берёт max, затем инкрементит.
Сниппет 2 — merge vector clock
def merge_receive(local, msg_vec, my_id): # local and msg_vec are dicts: node_id -> counter merged = {} for node in set(local) | set(msg_vec): merged[node] = max(local.get(node, 0), msg_vec.get(node, 0)) merged[my_id] += 1 return merged
Викторина
Completed
Этот merge при приёме корректен. Какое утверждение объясняет, почему поэлементный max плюс один self-инкремент — ровно то, что нужно?
Heads-up Инкремент каждой компоненты ложно заявил бы, что этот узел наблюдал новые события на каждом другом узле. На локальном/приёмном событии продвигается только собственный счётчик; остальные мержатся через max.
Heads-up Сложение дважды считает события, которые обе стороны уже разделяют, и ломает семантику сравнения. Max держит каждую компоненту на последнем счёте, который каждая сторона реально видела.
Heads-up Получатель никогда не должен продвигать счётчик отправителя — им владеет только отправитель. Получатель бампит свою компоненту и максит остальные.
Сниппет 3 — сравнение двух vector clock
def compare(a, b): # returns 'before', 'after', or 'concurrent' le = all(a.get(k, 0) <= b.get(k, 0) for k in set(a) | set(b)) ge = all(a.get(k, 0) >= b.get(k, 0) for k in set(a) | set(b)) if le and not ge: return 'before' # a happens-before b if ge and not le: return 'after' if le and ge: return 'equal' return 'concurrent'
Что вернёт compare(A, B) для этих двух векторов и что это значит для разрешения конфликтов?
Heads-up Vector clock сравнивают покомпонентно, никогда суммированием. A впереди по n1, B впереди по n3, поэтому ни один не меньше-или-равен повсюду — это и есть определение concurrent.
Heads-up Одна большая компонента не делает A 'after'; нужно, чтобы КАЖДАЯ компонента A была больше-или-равна. Здесь B обходит A по n3, так что они concurrent, а не упорядочены.
Heads-up Equal требует одинаковых счётов на каждом узле. Эти различаются по n1 и n3 в противоположных направлениях — ровно тот concurrent-случай, который merge обязан вынести наружу.
Используя happens-before по этой трассе, каково отношение между e на P1 и d на P3?
Heads-up Lamport timestamp дают тотальный порядок, но меньшее-или-большее значение Lamport НЕ влечёт причинности. Нет пути сообщений от e к d, поэтому они concurrent независимо от чисел.
Heads-up P3 принимает m2; он не начинает цепочку (её начинает a на P1), и ни одно сообщение не течёт от d обратно к e на P1. Без связующего пути сообщений события concurrent.
Heads-up e и d — разные события на разных процессах. Happens-before спрашивает, связывает ли их путь сообщений; здесь его нет, значит они concurrent.
Итог
Операции с часами малы, но беспощадны: приём Lamport обязан брать max(local, msg) + 1, иначе может проштамповать receive раньше его send; приём vector clock берёт поэлементный max и бампит только свою компоненту; сравнение векторов покомпонентно, и когда каждая сторона впереди по какому-то узлу — события concurrent и должны держаться как siblings. И никакое числовое упорядочивание Lamport не влечёт причинности без связующего пути сообщений. Читай код и трассу, затем решай порядок vs конкурентность по причинной структуре, а не по сырым целым числам.