Skip to content

Commit 0896aff

Browse files
author
Eva
committed
spec: model no-op + fallible-snapshot fence; fold Quinn/Mari review
- TLA+: model changes/snapErr per push; MustPublish = changes \/ snapErr - new Inv_ChangedPublished catches the skip-on-error hole (mutation-verified) - Inv_NoLost scoped to installed pushes - Impl Correspondence: name the unique constructor seam as a code obligation, not a proven claim; conditional + fallible fence explicit - Conformance: required N-way CAS race, admission-gate wording, ETag-token consistency, explicit multipart/delete non-goals
1 parent fbd07db commit 0896aff

2 files changed

Lines changed: 167 additions & 61 deletions

File tree

‎docs/git-on-object-storage.md‎

Lines changed: 100 additions & 33 deletions
Original file line numberDiff line numberDiff line change
@@ -222,17 +222,46 @@ may do wasted indexing before its 412), not correctness. ∎
222222
A3 is the only axiom not guaranteed by the protocol itself; for AWS S3 it is
223223
documented, for any other backend (MinIO, Ceph RGW, ...) it is an empirical
224224
claim. It is discharged by a **conformance probe** run at startup against the
225-
target backend:
226-
227-
> Spawn N concurrent `PUT M_R If-Match: e` (and `If-None-Match: *`) predicated on
228-
> the same ETag, with distinct payloads. **Pass** iff exactly one PUT returns
229-
> success and the remaining N−1 return precondition-failed, and a subsequent read
230-
> observes the single winner's value. Repeat under sustained contention.
231-
232-
If the probe passes, A3 holds for that backend and Theorems 1–3 transfer
233-
unchanged. If it fails, the design is invalid against that backend — exactly as
234-
non-atomic `rename()` would invalidate reftable. The probe is therefore a
235-
**gate**, not a benchmark, and must pass before the backend is trusted.
225+
target backend. The probe is a **deployment admission gate**: a backend is
226+
trusted only if it passes. Passing does *not* prove the universal axiom — a
227+
finite probe yields operational confidence for *this backend, build, and
228+
config*; failure invalidates the design against that backend, exactly as
229+
non-atomic `rename()` would invalidate reftable.
230+
231+
The probe has both a sequential half (semantic correctness) and a concurrent
232+
half (linearizability under contention). The concurrent half is the load-bearing
233+
part — A3 is a claim about *races*, so a probe that only checks sequential
234+
conditional writes does not discharge it.
235+
236+
1. **Sequential semantics.** create-if-absent succeeds; duplicate
237+
`If-None-Match: *` fails; `If-Match: E` with current ETag succeeds; stale
238+
`If-Match` fails; `If-Match` on a missing key does not create; read-after-write
239+
returns the written value.
240+
2. **N-way `If-Match` race (required).** Write key with body `base`; read its
241+
ETag `E` via the *same code path production uses for the pointer*. Spawn N
242+
(e.g. 32–64) concurrent `PUT key If-Match: E` with unique bodies. **Pass** iff
243+
exactly one succeeds, the other N−1 classify as precondition-failed, a
244+
subsequent read returns the winner's body and a new ETag, and the final body is
245+
never one of the *failed* payloads. Repeat for R rounds (configurable; default
246+
trades boot time against confidence).
247+
3. **N-way `If-None-Match: *` race (required).** Same shape on a missing key:
248+
exactly one create wins, N−1 precondition failures, final body is the winner.
249+
4. **ETag-token consistency.** Verify HEAD-path and GET-path ETag extraction
250+
agree byte-for-byte (quoting included). `If-Match` compares tokens literally;
251+
a quote mismatch between the read path and the write path silently tests the
252+
wrong thing. The probe must use the exact token format the pointer write uses.
253+
254+
**Proof surface (explicit non-goals of the probe and the design).** The protocol
255+
depends only on conditional writes of *small single objects* (the manifest
256+
pointer). It does **not** depend on, and the probe does **not** test:
257+
conditional *multipart* uploads (packs are content-addressed plain PUTs, staged
258+
without conditionals) or conditional *delete* (GC uses retention/sweep over a
259+
republished manifest, not `If-Match` delete). Keeping the proof surface to
260+
single-object conditional PUT is what makes A3 both sufficient and cheaply
261+
checkable.
262+
263+
If the probe passes, A3 is admitted for that backend and Theorems 1–3 transfer
264+
unchanged.
236265

237266
## Prior Art
238267

@@ -264,37 +293,75 @@ knowledge, new.
264293

265294
## Implementation Correspondence
266295

267-
The fence (Theorem 1) is enforced by the type system, not convention: the only
268-
function that constructs a success `Response` from a push consumes a value that
269-
exists only after the CAS succeeds. Snapshot reads of ref state are *fallible*;
270-
a failure to read either the before- or after-state is treated as "assume
271-
changed" so the CAS path runs rather than silently skipping publish — closing
272-
the double-failure hole where two failed ref scans compare equal and bypass the
273-
fence. Two ordering tests pin the behavior: a ref-changing push waits for CAS; a
274-
no-op push does not.
296+
The fence (Theorem 1) maps to a single structural obligation on the
297+
implementation, stated here as a requirement the code must meet for the proof to
298+
transfer:
299+
300+
- **Unique constructor seam.** There must be exactly one path that builds a
301+
success `Response` from push output (the `PackOutput → Response` conversion),
302+
and it must live inside `finalize_push` after the CAS returns success. If any
303+
other path can construct that `Response`, the fence is convention, not
304+
structure, and Theorem 1 does not hold for the implementation. This is a
305+
checkable property of the code (one conversion site), not a claim provable
306+
here; it is the spec↔code obligation, verified by reviewers against the actual
307+
`finalize_push`.
308+
- **Fallible snapshot.** Ref-state snapshots are `Result`, and the skip predicate
309+
is `Ok(after) == Ok(before)`, never `after == before` over values that default
310+
to equal on error. Any `Err` on either snapshot falls through to publish
311+
("assume changed"). This closes the double-failure hole — two failed scans
312+
comparing equal and bypassing the fence — and is exactly the `MustPublish ==
313+
changes \/ snapErr` rule the model checks.
314+
- **Conditional fence.** The fence engages only when refs changed; a no-op push
315+
returns success without awaiting publish (the `SkipPublish` path). The
316+
obligation is "publish-before-success *for ref-changing pushes*," not
317+
unconditional publish.
318+
319+
Two ordering tests pin the behavior: a ref-changing push waits for CAS; a no-op
320+
push does not (and a both-snapshots-fail push waits, per the fallible rule).
275321

276322
## Mechanized Verification
277323

278-
The three safety theorems are model-checked, not only argued in prose. The
279-
companion TLA+ module `docs/spec/GitOnObjectStore.tla` models concurrent pushers
280-
racing to advance the manifest pointer, with the CAS action (`If-Match`) as the
281-
sole pointer writer — directly encoding axiom A3. TLC checks four invariants
282-
corresponding to T1–T3 plus pointer well-formedness.
324+
The safety theorems are model-checked, not only argued in prose. The companion
325+
TLA+ module `docs/spec/GitOnObjectStore.tla` models concurrent pushers racing to
326+
advance the manifest pointer, with the CAS action (`If-Match`) as the sole
327+
pointer writer — directly encoding axiom A3. Each push independently models
328+
**(a)** whether it actually changes refs (`changes`) and **(b)** whether its ref
329+
snapshot reads succeed (`snapErr`), so the publish-or-skip fence is exercised on
330+
all four combinations, including the both-snapshots-fail case. The skip predicate
331+
is `MustPublish(p) == changes[p] \/ snapErr[p]` — "publish unless we *observed*
332+
no change," never "publish unless `b == a`" with failed reads compared equal.
333+
334+
TLC checks five invariants: durability-ordering for obligated pushes (T1), a
335+
ref-changing push is always published (the fallible-snapshot bite),
336+
no-lost-update among installed pushes (T3), pack-set coverage (T2), and pointer
337+
well-formedness.
283338

284339
```
285340
$ tlc GitOnObjectStore.tla -config GitOnObjectStore.cfg
286341
Model checking completed. No error has been found.
287-
1747 states generated, 398 distinct states found, 0 states left on queue.
342+
107128 states generated, 14833 distinct states found, 0 states left on queue.
288343
```
289344

290-
The check is **non-vacuous**: removing the `If-Match` guard from the CAS action
291-
(a deliberate mutation that violates A3) makes TLC report
292-
`Invariant Safety is violated` within a few hundred states — confirming the
293-
invariants actually couple ref-safety to the CAS axiom rather than holding
294-
trivially. The model is parametric in the number of pushers and bounded manifest
295-
count (`Pushers = {p1,p2,p3}`, `MaxManifests = 5` in the supplied config); larger
296-
bounds check identically and are limited only by state-space, as expected for a
297-
property whose proof is bounded-independent (Theorems 1–3).
345+
The check is **non-vacuous**, confirmed by two deliberate mutations:
346+
347+
- Removing the `If-Match` guard from CAS (violating A3) → `Invariant Safety is
348+
violated` (no-lost-update breaks): the invariants bind ref-safety to the CAS
349+
axiom.
350+
- Changing the skip predicate to `changes[p] /\ ~snapErr[p]` — i.e. a real ref
351+
change whose snapshots *both failed* compares "equal" and is silently skipped,
352+
exactly the double-failure hole — → `Invariant Safety is violated` in 181
353+
states (`Inv_ChangedPublished` breaks). The model catches the silent-corruption
354+
bug that motivated the fallible-snapshot fix.
355+
356+
(A weaker mutation, `MustPublish == changes[p]` alone, does *not* break safety —
357+
it over-publishes, which is safe-but-wasteful, not unsafe. Noting this so the
358+
mutation set is honest: only the skip-on-error mutation is a true safety
359+
regression, and the model distinguishes the two.)
360+
361+
The model is parametric in pusher count and bounded manifest count
362+
(`Pushers = {p1,p2,p3}`, `MaxManifests = 5`); larger bounds check identically,
363+
limited only by state space, as expected for a bounded-independent safety
364+
property.
298365

299366
## Summary
300367

‎docs/spec/GitOnObjectStore.tla‎

Lines changed: 67 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -23,96 +23,134 @@ VARIABLES
2323
pc, \* pusher id -> control state
2424
readEtag, \* pusher id -> pointer value it last read (its CAS precondition)
2525
staged, \* pusher id -> manifest id it intends to install
26+
changes, \* pusher id -> does this push actually change refs? (BOOLEAN)
27+
snapErr, \* pusher id -> did either ref-snapshot read fail? (BOOLEAN)
2628
observed \* set of pusher ids that have observed success (fence passed)
2729

28-
vars == <<pointer, published, packs, pc, readEtag, staged, observed>>
30+
vars == <<pointer, published, packs, pc, readEtag, staged, changes, snapErr, observed>>
2931

3032
ManifestIds == 0..MaxManifests
3133

3234
TypeOK ==
3335
/\ pointer \in ManifestIds
3436
/\ published \subseteq ManifestIds
3537
/\ packs \in [ManifestIds -> SUBSET ManifestIds]
36-
/\ pc \in [Pushers -> {"idle","read","staged","done","lost"}]
38+
/\ pc \in [Pushers -> {"idle","staged","done","lost"}]
3739
/\ readEtag \in [Pushers -> ManifestIds]
3840
/\ staged \in [Pushers -> ManifestIds]
41+
/\ changes \in [Pushers -> BOOLEAN]
42+
/\ snapErr \in [Pushers -> BOOLEAN]
3943
/\ observed \subseteq Pushers
4044

4145
Init ==
4246
/\ pointer = 0
4347
/\ published = {0}
44-
/\ packs = [m \in ManifestIds |-> IF m = 0 THEN {} ELSE {}]
48+
/\ packs = [m \in ManifestIds |-> {}]
4549
/\ pc = [p \in Pushers |-> "idle"]
4650
/\ readEtag = [p \in Pushers |-> 0]
4751
/\ staged = [p \in Pushers |-> 0]
52+
/\ changes = [p \in Pushers |-> FALSE]
53+
/\ snapErr = [p \in Pushers |-> FALSE]
4854
/\ observed = {}
4955

5056
\* A fresh manifest id not yet used as a pointer value, to model content-addressed
5157
\* distinctness of each push's new manifest.
52-
FreshId(p) == CHOOSE m \in ManifestIds : m \notin published /\ m # 0
58+
FreshId == CHOOSE m \in ManifestIds : m \notin published /\ m # 0
5359

54-
CanStage(p) == \E m \in ManifestIds : m \notin published /\ m # 0
60+
CanStage == \E m \in ManifestIds : m \notin published /\ m # 0
5561

56-
\* Step 3-4: read pointer, validate, stage a new manifest extending the read state.
57-
Read(p) ==
62+
\* The publish-skip decision (the fallible-snapshot fence, Quinn #2 / Dawn's case).
63+
\* A push skips publish ONLY if its snapshots succeeded AND showed no ref change.
64+
\* If either snapshot errored (snapErr), it must NOT skip -- it falls through to CAS.
65+
\* This is "Ok(b) = Ok(a)", never "b = a" with errors silently equal.
66+
MustPublish(p) == changes[p] \/ snapErr[p]
67+
68+
\* Steps 3-6: read pointer; nondeterministically this push either changes refs or
69+
\* is a no-op, and its ref-snapshot reads either succeed or fail. Stage a manifest.
70+
Begin(p) ==
5871
/\ pc[p] = "idle"
59-
/\ CanStage(p)
72+
/\ CanStage
73+
/\ \E c \in BOOLEAN, e \in BOOLEAN :
74+
/\ changes' = [changes EXCEPT ![p] = c]
75+
/\ snapErr' = [snapErr EXCEPT ![p] = e]
6076
/\ readEtag' = [readEtag EXCEPT ![p] = pointer]
61-
/\ LET m == FreshId(p) IN
62-
/\ staged' = [staged EXCEPT ![p] = m]
63-
\* new manifest names the read state's packs plus this push's new pack (m itself as a token)
64-
/\ packs' = [packs EXCEPT ![m] = packs[pointer] \union {m}]
77+
/\ staged' = [staged EXCEPT ![p] = FreshId]
78+
/\ packs' = [packs EXCEPT ![FreshId] = packs[pointer] \union {FreshId}]
6579
/\ pc' = [pc EXCEPT ![p] = "staged"]
6680
/\ UNCHANGED <<pointer, published, observed>>
6781

82+
\* No-op fast path: a push that must NOT publish (no change, snapshots ok) goes
83+
\* straight to done WITHOUT touching the pointer -- zero CAS/publish latency.
84+
SkipPublish(p) ==
85+
/\ pc[p] = "staged"
86+
/\ ~MustPublish(p)
87+
/\ pc' = [pc EXCEPT ![p] = "done"]
88+
/\ UNCHANGED <<pointer, published, packs, readEtag, staged, changes, snapErr, observed>>
89+
6890
\* Step 7: CAS. Succeeds iff pointer still equals the etag this pusher read (A3).
6991
CasSucceed(p) ==
7092
/\ pc[p] = "staged"
93+
/\ MustPublish(p)
7194
/\ pointer = readEtag[p]
7295
/\ pointer' = staged[p]
7396
/\ published' = published \union {staged[p]}
7497
/\ pc' = [pc EXCEPT ![p] = "done"]
75-
/\ UNCHANGED <<packs, readEtag, staged, observed>>
98+
/\ UNCHANGED <<packs, readEtag, staged, changes, snapErr, observed>>
7699

77100
CasFail(p) ==
78101
/\ pc[p] = "staged"
102+
/\ MustPublish(p)
79103
/\ pointer # readEtag[p]
80104
/\ pc' = [pc EXCEPT ![p] = "lost"] \* will retry from idle
81-
/\ UNCHANGED <<pointer, published, packs, readEtag, staged, observed>>
105+
/\ UNCHANGED <<pointer, published, packs, readEtag, staged, changes, snapErr, observed>>
82106

83-
\* Step 8: the fence. Observe success ONLY after CAS succeeded (pc = done).
107+
\* Step 8: the fence. Observe success ONLY after the push reached "done"
108+
\* (either via successful CAS or a legitimate skip).
84109
Observe(p) ==
85110
/\ pc[p] = "done"
86111
/\ observed' = observed \union {p}
87-
/\ UNCHANGED <<pointer, published, packs, pc, readEtag, staged>>
112+
/\ UNCHANGED <<pointer, published, packs, pc, readEtag, staged, changes, snapErr>>
88113

89114
\* A loser retries: back to idle, ready to re-read the advanced pointer.
90115
Retry(p) ==
91116
/\ pc[p] = "lost"
92117
/\ pc' = [pc EXCEPT ![p] = "idle"]
93-
/\ UNCHANGED <<pointer, published, packs, readEtag, staged, observed>>
118+
/\ UNCHANGED <<pointer, published, packs, readEtag, staged, changes, snapErr, observed>>
94119

95120
Next ==
96121
\E p \in Pushers :
97-
Read(p) \/ CasSucceed(p) \/ CasFail(p) \/ Observe(p) \/ Retry(p)
122+
Begin(p) \/ SkipPublish(p) \/ CasSucceed(p) \/ CasFail(p)
123+
\/ Observe(p) \/ Retry(p)
98124

99125
Spec == Init /\ [][Next]_vars /\ WF_vars(Next)
100126

101127
------------------------------------------------------------------------------
102128
\* SAFETY PROPERTIES
103129

104-
\* T1 (Durability-Ordering): any pusher that observed success has its staged
105-
\* manifest in the durable published history.
130+
\* T1 (Durability-Ordering): any observed push that was obligated to publish
131+
\* (it changed refs, or its snapshot reads errored) has its staged manifest in
132+
\* the durable published history before the client observes success. A
133+
\* legitimately-skipped no-op push (no change, snapshots ok) is exempt -- it
134+
\* publishes nothing and is correct to do so.
106135
Inv_Fence ==
107-
\A p \in observed : staged[p] \in published
108-
109-
\* T3 (No Lost Update): the pointer only ever advances to a manifest that
110-
\* extended the pointer value at the time of the winning CAS; i.e. every
111-
\* published non-root manifest's pack set strictly contains its predecessor's.
112-
\* Operationally: no two distinct observed pushers share the same staged id
113-
\* (each success is a distinct, ordered install — no silent overwrite).
136+
\A p \in observed : MustPublish(p) => staged[p] \in published
137+
138+
\* The bite for the fallible-snapshot case (Quinn #2 / Dawn): if a push actually
139+
\* changed refs and was observed, its change is durably published -- regardless of
140+
\* snapshot outcome. This is what breaks if SkipPublish ignores snapErr (i.e. if
141+
\* the skip predicate were "b = a" instead of "Ok(b) = Ok(a) /\ no change").
142+
Inv_ChangedPublished ==
143+
\A p \in observed : changes[p] => staged[p] \in published
144+
145+
\* T3 (No Lost Update): no two distinct pushers that BOTH published (reached
146+
\* "done" via CasSucceed, hence staged in published) share the same installed
147+
\* manifest. Each successful CAS is a distinct, ordered install -- no silent
148+
\* overwrite. No-op skips are excluded: they install nothing, so their staged id
149+
\* is irrelevant (and may legitimately collide -- a skip is not an install).
150+
Installed(p) == (p \in observed) /\ MustPublish(p) /\ (staged[p] \in published)
114151
Inv_NoLost ==
115-
\A p1, p2 \in observed : (p1 # p2) => (staged[p1] # staged[p2])
152+
\A p1, p2 \in Pushers :
153+
(p1 # p2 /\ Installed(p1) /\ Installed(p2)) => (staged[p1] # staged[p2])
116154

117155
\* T2 (Snapshot closure): every published manifest names a pack set that
118156
\* includes everything its predecessor named (closed under the push chain).
@@ -127,6 +165,7 @@ Inv_PointerPublished ==
127165
Safety ==
128166
/\ TypeOK
129167
/\ Inv_Fence
168+
/\ Inv_ChangedPublished
130169
/\ Inv_NoLost
131170
/\ Inv_SnapshotClosed
132171
/\ Inv_PointerPublished

0 commit comments

Comments
 (0)