CONCURRENCY.md

Concurrency model

This document defines how the WAL coordinates producers, readers, maintenance, payload objects, and consumers. It is normative for lock ordering, admission boundaries, and library-owned goroutine lifetimes. Storage and durability semantics remain normative in DESIGN.md.

Core rules

• File has one physical WAL writer. Concurrent producers are admitted in FIFO order and may form bounded commit groups, but their bytes never interleave.
• Caller-controlled readers, callbacks, and large payload writes do not run under the append queue lock or the main WAL state lock.
• A lock protects in-memory ownership. An admission gate limits work. A durability barrier establishes a storage claim. These are distinct concepts.
• Cancellation can reject work only before its documented admission boundary. After admission, the operation returns the definite storage outcome.
• ErrBackpressure means an operation was not admitted and the instance may be retried. ErrClosed is returned only after terminal close admission has been published.
• No lock order may be inferred from goroutine start order or callback order. Only the graph below is valid.

File concurrency units

Unit	Purpose	Contention behavior
flushMutex	Orders concurrent Synced flush barriers.	FIFO and context-cancellable before acquisition.
maintenanceMutex	Excludes conflicting flush, truncate, compaction, and first-close work.	Non-blocking conflicts return ErrBackpressure.
stagingMutex	Protects reader-preparation admission and reservation counters.	Critical sections contain no caller reads or filesystem I/O.
stagingTokens	Bounds active caller-reader workers across all streaming requests.	At most MaxStagingRequests readers are active; a value of one makes batch staging serial.
scanMutex	Protects scan admission and the active scan/reader lease count.	Critical sections contain no payload I/O or callbacks.
scanTokens	Bounds simultaneous scans and exact readers.	Saturation returns ErrBackpressure; callers do not wait while holding application resources.
queueMutex and queueCondition	Own append admission order, pending charges, commit leadership, completion, and flush-barrier coordination.	Waiters sleep on the condition; no payload I/O or user callback runs while it is held.
main contextMutex	Protects logical WAL state, indexes, active-segment state, and publication.	Contended ownership is handed off in FIFO registration order; canceled tickets are removed safely.
atomic capacity counters	Expose segment, object, staging-reservation, and compaction-reservation bytes to pre-admission checks.	Capacity admission does not acquire the main WAL or object-state locks.

The append queue and the main state mutex deliberately have different jobs. Queue admission establishes producer order. State publication establishes the visible WAL prefix. Large physical payload writes may release the state mutex after framing and capacity decisions are fixed; commit leadership still prevents a second physical writer, while state and retained reads remain responsive.

Streaming preparation

AppendFrom and AppendBatchFrom reserve one bounded preparation request before consuming a reader. A batch creates at most min(record count, MaxStagingRequests) short-lived workers. All requests share the same stagingTokens semaphore, so the number of active Read calls remains globally bounded.

Workers write only to their own input-indexed slots. Commit planning later walks those slots in input order; positions, receipts, checksums, and atomic batch visibility therefore do not depend on staging completion order. After a reader failure no new index starts, already-active readers finish, and the lowest failing input index is reported. Aggregate byte overflow is batch-scoped and has no record index.

A generic io.Reader cannot be interrupted while blocked inside Read. Cancellation is checked between reads and bounded filesystem operations. Close does not wait for such a reader: it returns ErrBackpressure without starting terminal close. Recovery removes abandoned staging residue after a process crash.

Append and flush

The first admitted producer becomes commit leader and selects a bounded FIFO prefix. Followers wait for their own published results. One request may span multiple physical groups or segments without losing atomic visibility.

Flush(ctx, Written) waits for its admitted append prefix and performs no storage sync. Flush(ctx, Synced) additionally takes flushMutex, the maintenance gate, and a queue barrier. New append requests may remain bounded and charged behind that barrier, but cannot become physical writer until it is released. Slow file barriers release the main state mutex while commit and maintenance ownership keep the segment set stable.

Close

First close uses the maintenance gate. It provisionally blocks staging and scan admission, then verifies that no preparation, scan lease, or commit leader is active. If it finds one, it restores the gates and returns ErrBackpressure. Operations that encounter these provisional gates also receive ErrBackpressure, never a false terminal ErrClosed.

After terminal admissionClosed publication, queued callers are woken with ErrClosed, descriptors are closed, and repeated Close calls return the stored result. Close has no implicit Synced barrier.

Lock order

The normative graph below is rendered from internal/lockrank, which is also used by the lockrank test build. Unless marked direct-only, edges are transitive: a code path may enter at any node and may skip intermediate nodes, but it may acquire only a reachable descendant. Peer nodes have no edge and therefore cannot nest. Ordered families additionally require increasing instance order. Run make lock-doc after changing the machine-readable graph; ordinary tests fail if this block is stale.

Domain	Rank	ID	Lock unit	Directly permits
File WAL	F0	file.flush	flushMutex	F1 maintenanceMutex
File WAL	F1	file.maintenance	maintenanceMutex	F2 stagingMutex F2 scanMutex X0 filesystem lifecycle mutex (direct only)
File WAL	F2	file.staging	stagingMutex	F3 queueMutex
File WAL	F2	file.scan	scanMutex	F3 queueMutex
File WAL	F3	file.queue	queueMutex	F4 main contextMutex
File WAL	F4	file.state	main contextMutex	O1 object key stripe
File WAL	O1	file.object-key	object key stripe	higher O1 instance O2 object directoryMutex
File WAL	O2	file.object-directory	object directoryMutex	O3 object state mutex
File WAL	O3	file.object-state	object state mutex	none
File lifecycle	X0	file.filesystem	filesystem lifecycle mutex	isolated from File WAL
Memory	M0	memory.state	Memory contextMutex	M1 Memory stagingMutex
Memory	M1	memory.staging	Memory stagingMutex	none
FIFO consumer	C0	fifo.operation	Consumer operation mutex	C1 Consumer statsMutex
FIFO consumer	C1	fifo.stats	Consumer statsMutex	none
Out-of-order consumer	R0	receiver.delivery	Delivery settlement mutex	R1 Delivery reader mutex R1 Receiver checkpointMutex R1 Receiver cleanupMutex R2 Receiver state mutex
Out-of-order consumer	R1	receiver.reader	Delivery reader mutex	none
Out-of-order consumer	R1	receiver.checkpoint	Receiver checkpointMutex	R2 Receiver state mutex
Out-of-order consumer	R1	receiver.cleanup	Receiver cleanupMutex	R2 Receiver state mutex
Out-of-order consumer	R2	receiver.state	Receiver state mutex	none

Additional rules:

• stagingMutex and scanMutex are peer gates and are not nested.
• Stats uses stagingMutex → queueMutex → main mutex → object state to produce a cross-component snapshot.
• Streaming capacity admission reads an atomic object-byte total; it does not add a stagingMutex → object state edge.
• Main WAL state may enter object key/state locks while publishing reference ownership. Object code never calls back into a fileLog lock.
• Object key stripes are deduplicated and acquired in ascending numeric order.
• The filesystem mutex is outside the normal graph. Terminal close may retain only maintenanceMutex while releasing descriptors and the ownership lock; queue, state, scan, staging, and object locks have already been released. This direct-only exception is not inherited by flushMutex.
• Do not invoke caller code while holding queue, state, scan, staging, object, or filesystem locks. Operation gates may remain held so callback reentry gets deterministic ErrBackpressure instead of deadlocking.

Enforcement

The graph has three independent executable controls:

• TestLockGraphDocumentationIsCurrent regenerates the marked table in memory and fails when this document differs from the machine-readable graph.
• TestProductionMutexesUseLockGraph rejects a new raw sync.Mutex in root or consumer production code. The internal state mutex used to implement contextMutex is the only exception.
• make test-lockrank compiles the repository with the lockrank build tag. Every ranked acquisition then checks the current goroutine's held-lock stack before it can block; release must be last-acquired-first-released.

The production build embeds the standard-library mutex directly and has the same mutex size. It performs no goroutine lookup or graph traversal. The debug build derives a goroutine identifier from runtime.Stack; this unsupported runtime detail is intentionally confined to tests and must not be enabled in a production binary or benchmark.

Dynamic checking proves only schedules that execute. It complements the race detector and deterministic blocked-operation tests; it is not a static proof that every possible control-flow path is deadlock-free.

Payload object serialization

Same-key publication, deduplication, and removal use one of 64 key stripes. Different keys can validate and compare concurrently. Namespace mutation uses one directoryMutex; it remains held through the matching directory barrier. This prevents a later rename from claiming durability from the wrong barrier.

The directory barrier is therefore an intentional global serialization point. On a filesystem with expensive directory sync, it imposes a measurable throughput ceiling even though hashing and exact comparison are concurrent. Moving the barrier outside the gate would weaken publication durability. A planned shared segmented extent store will amortize barriers by reusing the WAL's extracted physical segment layer for both WAL frames and payload objects. The target payload layout abandons cross-record deduplication. Its detailed concurrency and lifecycle design remains a separate follow-up.

The short object state mutex protects reference/preparation maps and detailed inventory counters. It contains no payload I/O. A separate atomic managed-byte projection serves capacity admission without weakening the lock-consistent FileStats snapshot.

Memory

Memory has a FIFO state contextMutex and a preparation accounting mutex. Stats and Close use state → preparation. Reader preparation otherwise holds only the preparation mutex, consumes payloads outside both locks, then acquires state for one atomic batch publication.

Memory shares the same bounded staging worker helper as File. It has no filesystem or object locks and supports only Volatile durability.

FIFO consumer

The root Consumer has an operation mutex and a stats mutex.

• Run, Drain, and Next are mutually exclusive for the complete delivery attempt.
• Sender, RejectionHandler, and Acknowledger execute synchronously in the caller's goroutine while operation ownership prevents another FIFO attempt.
• The stats mutex is nested only for short snapshot/counter updates.
• The package does not create a background delivery goroutine. Applications own the goroutine that calls Run or repeatedly calls Next.

This serialization is the FIFO contract, not an implementation limitation. Use the consumer subpackage when downstream work must finish out of order.

Out-of-order consumer

The consumer.Receiver uses independent state, checkpoint, and cleanup units:

Unit	Purpose
Receiver state mutex	Short reservation, cursor, window, sparse-ACK, prefetch, and failure-state updates.
checkpointMutex	One monotonic contiguous source checkpoint, including Acknowledger I/O.
cleanupMutex	One acknowledgment-journal truncation.
buffered notify channel	Coalesced wakeup for window, retry, checkpoint, and new-source progress; it carries no state.
per-Delivery mutex	One idempotent settlement choice: Ack or Retry.
per-delivery reader mutex	One caller-driven payload cursor and completion state.

The allowed nesting is:

Delivery settlement → delivery reader
Delivery settlement → Receiver state
checkpointMutex     → Receiver state
cleanupMutex        → Receiver state

Receiver state never acquires the checkpoint or cleanup gates. checkpointMutex and cleanupMutex are never nested.

checkpointMutex intentionally spans the source Acknowledger call so two contiguous checkpoints cannot overtake each other. The Receiver state mutex is released during that I/O. The selected checkpoint target is published as a virtual prefix first, allowing an independent sparse ACK beyond a gap to complete without waiting for the callback. An Acknowledger must not synchronously settle another delivery on the same Receiver: a checkpoint that depends on itself cannot make progress.

Runtime journal cleanup is opportunistic: if cleanupMutex.TryLock fails, the ACK returns and an existing or later settlement performs cleanup. Startup recovery uses blocking Lock because Open must establish one reconciled starting state before returning the Receiver.

Receive reserves a position under the state mutex, then validates and opens its payload outside it. Different positions can therefore open concurrently. Prefetch publication rechecks reservations and never overwrites a position claimed by another receiver. Each exact-reader delivery retains one source scan lease until its payload is exhausted or the delivery is settled, so source MaxConcurrentScans remains an independent concurrency bound.

Goroutine lifecycle

The library has no persistent background goroutine.

Source	Start	End and ownership
Batch reader workers	AppendBatchFrom with more than one record	The method waits for every started worker before returning. Each worker releases its global staging token. A blocked caller reader can extend the method but cannot outlive it invisibly.
Context wake callback	A cancellable append-prefix or flush-barrier wait	context.AfterFunc only locks the queue, broadcasts, and exits. The waiter calls its stop function before returning when cancellation did not fire.
Runtime timer	FIFO consumer retry/idle wait or Receiver idle wait	The timer is stopped on every non-timer return path; no package goroutine is retained.

Scans, exact readers, deliveries, progress observers, senders, acknowledgers, and rejection handlers are synchronous. They may hold resource leases, but they do not own hidden goroutines. The caller must eventually return from a scan callback, close or exhaust an exact reader, and settle or retry a delivery. Progress and internal-error callbacks may be invoked concurrently by different caller-owned operations; applications that write to a shared sink must serialize that sink themselves.

Applications may add their own producer, consumer, or maintenance goroutines. Those goroutines must respect public admission and shutdown contracts:

1. stop new application work;
2. let admitted calls return;
3. perform any required Flush(ctx, Synced);
4. stop scans and consumers; and
5. retry Close after ErrBackpressure.

Do not wrap an admitted append in an abandoned goroutine to emulate cancellation. The WAL still borrows its input and must return a definite outcome.

Verification policy

Concurrency changes require:

• a written update to this lock graph when a new nested edge is introduced;
• a deterministic test that holds or blocks the earlier unit and proves the required independent operation still progresses;
• cancellation and rollback tests for every provisional admission gate;
• -race runs for the affected package and adversarial schedule; and
• leak/resource assertions for worker, descriptor, staging, and reservation lifecycles.

The project does not use a goroutine-local lock-rank checker. Go exposes no stable goroutine identity or supported goroutine-local storage; deriving one from stack text is fragile, allocates in the paths being tested, and changes scheduling. A partial wrapper would also create false confidence because standard mutexes, channels, and condition variables participate in the same graph. The explicit graph, field-level rank comments, small critical sections, and deterministic blocked-operation tests are the enforced policy. Reconsider instrumentation only if it can cover every synchronization primitive without depending on unsupported runtime details.