Documentation
¶
Overview ¶
Package rangeconflict is RFC-199 Tier 2's range-conflict interleaving driver.
The interleave driver (pkg/simfdb/hunt/interleave) only makes POINT-width conflict ranges — every read and write is a single key, so its conflict range is [k, keyAfter(k)). That leaves SimFDB's resolver arithmetic over genuine SPANS untested: rangesOverlap on wide ranges, the GetRange read-conflict extent, ClearRange write-conflict ranges, the keyAfter boundary between adjacent keys. This driver fills that gap. It interleaves point AND range operations — GetRange (a read conflict over a span), ClearRange (a write conflict over a span), point Get/Set/Clear — across several open transactions through one deterministic goroutine, and commits through the serialized SSI resolver.
The oracle stays airtight because, for keys laid out at ascending tuple-encoded indices, byte- range overlap maps EXACTLY onto integer half-open-interval overlap over DOUBLED indices: key i sits at position 2i and keyAfter(k_i) at 2i+1, so a key is [2i, 2i+1) and the gap after it is [2i+1, 2i+2). Two byte ranges overlap iff their position intervals do. So the model resolves conflicts over plain integer intervals — a far simpler representation than the resolver's byte ranges, and that gap is its teeth. (The doubling is not decoration: read conflicts are filtered through the RYW write map, which cuts a range at keyAfter(k) for every key the transaction wrote, and that cut lands inside a gap. See step.span.)
Two intrinsic oracles, no external reference:
- VERDICT — independently recompute each commit's SSI verdict from the transaction's read INTERVALS versus the write INTERVALS of transactions that committed after its read version. Catches a missed conflict (a span the resolver failed to detect overlapping) and a spurious abort — specifically over ranges, where keyAfter / rangesOverlap / the GetRange conflict extent could be off by a boundary.
- STATE — writes are BLIND (a Set stores a value fixed by (txn, step); a Clear removes a key or span; no read-modify-write), so after retry-draining every abort to a single commit, the final keyspace is the deterministic replay of every committed transaction's writes IN COMMIT ORDER. Catches a lost/late write, a ClearRange that clears too much or too little, a leaked rolled-back write, or a wrong last-writer-in-commit-order result.
Unlimited GetRange reads (no row limit) keep the read-conflict extent the full requested span (SimFDB narrows it only for a limit-truncated read), so the interval model matches the resolver exactly — after the write-map filter is applied to it, which the model does by subtracting each transaction's own prior writes from its later reads. Fault-free by design — the resolver is what's under test.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type Result ¶
type Result struct {
Report *hunt.Report
Conflicts int // phase-1 transactions aborted 1020 (real range-conflict resolution)
Predicted int // phase-1 transactions the verdict oracle predicted would abort
RangeOps int // range (GetRange/ClearRange) operations issued — the span coverage metric
// contains filtered or unexported fields
}
Result is the driver's rich outcome: the hunt.Report plus resolver-exercise metrics.
type Workload ¶
type Workload struct {
Keys int // key domain [0,Keys); small = more overlap = more conflicts (default 8)
Txns int // transactions held open and interleaved per run (default 4)
OpsPerTxn int // steps per transaction program (default 4)
MaxSpan int // largest range width a range op may cover (default 4; clamped to Keys)
}
Workload is the range-conflict interleaving driver, a hunt.Workload. Self-parameterized; runs fault-free (the resolver is under test).
Source Files