Multithreading via sharded reactors (path B)

Status: design draft — no code lands without explicit approval per item.

Goal

Take the RESP2 server multi-core without breaking alcove's invariants:

Refcounted exp_t* graph, mutated in place.
Tree-walker / VM evaluator that recurses on the C stack.
Single global dict_t for the keyspace.
Lisp callbacks via (redis-defcmd "NAME" fn) that reach back into the evaluator and may call any builtin, including (redis-get k).
NO CLOSURES invariant for the env arena.

Concurrency we want: N CPU cores serving M independent client connections with throughput that scales sublinearly but materially with N (target: 3–4× on 4 cores for non-conflicting key access).

Why not the simpler paths

Path A — multi-process shared-nothing (SO_REUSEPORT). Trivial to implement (fork N workers, accept on the same port). Zero atomics. But no shared keyspace: SET foo 1 on worker 0 isn't visible to worker 1 without an external store. The whole point of an embedded RESP server is shared in-process state. Rejected. (Note: Path B does still use SO_REUSEPORT — but for thread-level accept fan-out across N reactors inside one process, not for fork-based shared-nothing workers.)

Path C — full lock-free dict (Cliff Click NBHT, hazard pointers). Highest payoff on contended single keys. But our values are refcounted mutable exp_t* — every GET k would need hazard-pointer protection on the value pointer to safely read it before another thread mutates, and every SET k v would need to coordinate the unref of the old value with concurrent readers. RCU/epoch reclamation works but at this scale it's a 6-month project and the steady state is "alcove is fast enough already." Deferred indefinitely.

Path B in one paragraph

Hash each connection's RESP key to one of N shards. Each shard owns its own keyspace dict, its own select() reactor, its own evaluator state. A connection is pinned to a shard for the lifetime of the command (not the connection — see "Cross-shard ops" below). Single writer per shard means no atomics on dict mutations and no atomics on refcounts within a shard. Cross-shard ops use a serialized fallback.

Architecture

Updated 2026-04-30: dedicated acceptor pthread removed. Each reactor calls bind() directly with SO_REUSEPORT; the kernel hands each incoming connection to exactly one reactor (Linux: flow-hashed; macOS: weaker fairness). No user-space dispatcher, no inbox-handoff per connection.

                    127.0.0.1:6379  (SO_REUSEPORT)
                    │       │            │
        ┌───────────┴┬──────┴──────┬─────┴───────────┐
        │  shard 0   │  shard 1    │  shard N-1      │
        │  ┌──────────┐  ┌──────────┐  ┌──────────┐  │
        │  │ reactor  │  │ reactor  │  │ reactor  │  │
        │  │  loop    │  │  loop    │  │  loop    │  │
        │  │ + accept │  │ + accept │  │ + accept │  │
        │  ├──────────┤  ├──────────┤  ├──────────┤  │
        │  │ dict_t * │  │ dict_t * │  │ dict_t * │  │
        │  │ exp_t*…  │  │ exp_t*…  │  │ exp_t*…  │  │
        │  │ env_t  * │  │ env_t  * │  │ env_t  * │  │
        │  └──────────┘  └──────────┘  └──────────┘  │
        │  pthread_t     pthread_t     pthread_t     │
        │  + mpsc inbox + wake fd (cross-shard ops)  │
        └────────────────────────────────────────────┘

Each shard is a separate pthread running a copy of resp_serve's inner loop. Shards do not share resp_clients, g_global_env, or any exp_t* (with one exception, see "Lisp globals").

Sharding key

Decision: hash on the RESP key (first arg of most commands), not on fd.

Rationale: hashing on fd is dead simple but defeats the point — two connections both pounding key:hot will land on different shards if fds happen to differ, so the shared dict illusion has to span shards again. Hashing on the key keeps each key's home shard stable, which makes intra-shard ops fully lock-free.

Implementation: in the parsed-RESP-command stage, before dispatch, read argv[1] (the key for SET/GET/INCR/LPUSH/HSET/...) and route:

shard_id = bernstein_hash(argv[1], argl[1]) & (N - 1);

Commands without a key (PING, COMMAND, FLUSHDB, KEYS *, DBSIZE) are broadcast or aggregated — see below.

Per-shard data

typedef struct shard {
  int id;
  pthread_t tid;

  /* reactor state — private */
  resp_client_t *clients;     /* clients currently steered to this shard */
  fd_set rfds, wfds;

  /* keyspace — single-writer (this thread), readers within thread */
  dict_t *db;

  /* evaluator state — separate per-shard env/arena */
  env_t *global;
  exp_arena_t *exp_arena;     /* exp_t freelist, bump alloc */
  env_arena_t *env_arena;

  /* cross-shard inbox: lock-free MPSC queue of work to execute on
     this shard's thread. Producers are other shards; consumer is this
     shard's reactor. */
  mpsc_queue_t inbox;
  int inbox_eventfd;          /* select()-able wake-up */
} shard_t;

static shard_t shards[N_SHARDS];

Refcount macros revert to plain ++/-- within a shard (ALCOVE_SINGLE_THREADED=1 semantics) because no two threads ever touch the same exp_t* simultaneously (modulo the cross-shard exception, see below).

Connection lifecycle

Each reactor binds the listen socket with SO_REUSEPORT and accepts directly inside its select() loop. The kernel routes each new connection to exactly one reactor.
The accepting reactor is the connection's home reactor: it owns the read buffer, the write buffer, and the socket lifecycle.
Subsequent commands from that fd are read by the home reactor — but a command with a different key may need to hop shards (see "Per-command vs per-connection pinning").

Per-command vs per-connection pinning

Per-connection pinning (cheap, broken): once a connection lands on shard 0, all its commands stay on shard 0 even when they target keys owned by shard 1. shard 0 then needs to either lock shard 1's dict or synchronously RPC into shard 1. Both defeat the locality model.

Per-command pinning (correct, more plumbing): each parsed command ships to the shard owning its key. The current connection's reactor goes back to reading; the response from the target shard is enqueued back via a per-connection response queue, and the home reactor flushes it. This requires:

An MPSC inbox per shard for inbound commands.
An MPSC outbox per connection for ordered responses (RESP is pipeline-ordered; out-of-order replies break clients).
A "home reactor" per connection that owns the wbuf and the socket write. Other shards never touch the wbuf.

Decision: per-command pinning, with the connection's home reactor chosen at accept time (e.g. round-robin) and stable for the connection lifetime. Home reactor handles read, parses, dispatches to owner shard, drains responses from outbox, writes.

Pipeline ordering invariant: each command parsed on the home reactor is tagged with a monotonic seq number. The home reactor's outbox is a priority queue keyed by seq; it only writes responses in seq order, so slow shards block the wbuf flush behind them. Backpressure naturally propagates.

Cross-shard operations

Command	Strategy
`SET k v`, `GET k`, `INCR k`, single-key ops	route to `shard_of(k)`. Default path.
`MGET k1 k2 ...`	split by shard, scatter, gather, reorder by request index.
`MSET k1 v1 k2 v2 ...`	split by shard, scatter, no atomicity guarantee (already true in alcove single-threaded since we don't have transactions).
`KEYS *`, `DBSIZE`, `SCAN`	broadcast: enqueue on every shard inbox, gather.
`FLUSHDB`, `FLUSHALL`	broadcast. Each shard flushes its own dict.
`DEL k1 k2 ...`	split by shard.
`EXPIRE k`, `PEXPIRE k`, `TTL k`, `PERSIST k`	route to `shard_of(k)`.
`LPUSH q v`, `LRANGE q ...`, all list ops	route to `shard_of(q)`. The list value lives entirely on one shard.
`HSET h f v`, all hash ops	route to `shard_of(h)`.
`(redis-defcmd ...)` user commands	see below.

Lisp globals — the only shared state

reserved_symbol, the builtin function table, and (redis-defcmd)- registered user commands need to be visible to every shard, but they are read-mostly.

Strategy: initialize the global symbol dict and lispProcList before any shard thread starts. After that, treat them as immutable from shard threads. (redis-defcmd) and (def) from a connection- issued REPL form mutate them — that path is rare and can take a coarse pthread_rwlock_t write lock; reads are wait-free under pthread_rwlock_rdlock (or, on platforms with seqlock support, a seqlock for true wait-free reads).

g_global_env: one shared global env, but writes to it (def, defmacro, updatebang on a global key) take the same rwlock. Reads are protected by holding the read lock for the duration of the lookup chain — this is correct because a writer can't free env entries that a reader is walking.

(redis-defcmd "FOO" fn) evaluation:

Lookup of FOO in the user-cmd table: rwlock read.
Evaluation of fn: runs on the shard that owns the requested key, using that shard's env arena. The closure body and its constants are shared via the global env, but every per-call env_t allocation comes from the shard-local arena. Refcount writes on the closure's param/let slots stay shard-local because the env is shard-local.
Shared exp_t* (the closure body itself, its symbol/literal nodes) must use atomic refcount. Compromise: any exp_t* reachable from g_global_env flips to atomic refcounting; per-shard intermediate values stay non-atomic. Distinguishing them at runtime needs either a per-exp_t flag bit or two separate allocators (see "Refcount duality").

Refcount duality

The hardest part. Today every exp_t* uses the same REFCOUNT_INC/DEC macros. Path B needs:

Shard-local exp_t* (the vast majority — closure bodies parsed per call, intermediate values during eval): plain ++/--.
Shared exp_t* (anything reachable from the global env or the user-cmd table): atomic.

Option 1 — flag bit. Add EXP_FLAG_SHARED to e->flags. The refcount macros become:

#define REFCOUNT_INC(e) ((e)->flags & EXP_FLAG_SHARED \
    ? __sync_add_and_fetch(&(e)->nref, 1) : ++(e)->nref)

Cost: a load+test+branch on every refcount op. Branch is well-predicted (99% shard-local in steady state) but still 1-2 cycles in the hot path.

Option 2 — two arenas. Shard-local and shared arenas have different addresses; we can derive is_shared(e) from e's page or from a bit of the address (e.g. high bit of arena base). Cleaner runtime check but requires an arena-design pass.

Option 3 — write barrier on assignment to global env. When set_get_keyval_dict(g_global_env, ...) is called, walk the value's exp_t graph and flip every node to shared/atomic refcounting. Keeps the hot path branch-free. Cost: graph walk on every global mutation (rare). Implementation: a "promote to shared" function that recursively flips the flag and re-counts via atomics from then on.

Decision: Option 3 with the flag bit (Option 1) as the runtime check. Promotion is rare. Steady-state hot path: one branch, well- predicted. This gets the benefit without the arena rewrite.

The MPSC inbox/outbox

Multiple producer single consumer queue, lock-free. The standard implementation: a singly-linked list with atomic head pointer for producers, a separate stack-of-popped-items for the consumer to drain in batches.

typedef struct mpsc_node {
  struct mpsc_node *next;
  void *payload;
} mpsc_node_t;

typedef struct {
  _Atomic(mpsc_node_t *) head;   /* producers CAS here */
  mpsc_node_t *consumer_local;   /* drained by consumer, no atomics */
  int eventfd;                   /* writes wake up the consumer */
} mpsc_queue_t;

void mpsc_push(mpsc_queue_t *q, void *p) {
  mpsc_node_t *n = malloc(sizeof *n);
  n->payload = p;
  mpsc_node_t *old;
  do { old = atomic_load(&q->head); n->next = old; }
  while (!atomic_compare_exchange_weak(&q->head, &old, n));
  uint64_t one = 1; write(q->eventfd, &one, 8);  /* wake reactor */
}

Consumer (the shard's reactor) calls mpsc_drain after select() wakes on eventfd, which atomically swaps the head with NULL and walks the list in producer-LIFO order. We reverse it to get FIFO.

eventfd is Linux-only. macOS path: pipe() with the read end in the reactor's rfds. Same shape.

Layer-2 keyspace watches

The RESP keyspace has a layer-2 watch mechanism: an opt-in event stream for every lfkv mutation (SET / DEL / CAS / NX / XX / replace / expire-retire). Multi-threaded producers feed a strictly single-threaded consumer through a lock-free Vyukov MPSC queue.

Producers: when enabled via (redis-watch! t), mutators emit events from any reactor thread. Values are cloned at emit time into their stored blob form (matching redis-get). DEL events omit the :new field. No key-pattern filtering and no :old values, by design.
Bounded queue: capped at 65536 events. Emits beyond the bound — or that hit allocation failure — drop the event and count it; the overflow counter is read and reset via (redis-watch-dropped). The queue-size accounting is per-node and saturating (never blanket-reset), so a producer racing a disable-drain can't wedge the counter.
Main-thread consumers, enforced: the MPSC queue allows one consumer. All three consumer builtins — (redis-watch! flag) (its toggle paths drain), (redis-next-event!), (redis-drain-events!) — refuse from a RESP callback (which runs on a reactor thread) with the callback read-only error. Legitimate consumers: the -r REPL main thread while serving, or script code after respN_serve returns.
Blocking wait: (redis-wait-event! ms) blocks until an event arrives — ms > 0 waits up to that many milliseconds, 0/nil waits forever, negative never blocks; returns the event plist or nil on timeout/Ctrl-C/watch-disabled. Producers signal an eventfd only while a waiter is armed (one relaxed load on the mutator path otherwise); seq_cst fences on both sides close the Dekker lost-wakeup window. Topology note: under -R (combined REPL+RESP, single reactor) a blocked wait also blocks serving, so a network client can't wake it — the cross-thread wake exists for embedders whose host threads mutate the keyspace while the Lisp main thread waits (the signal→poll cycle is unit-tested in mpsc_test.c, TSan-gated).
Lifecycle & teardown: (redis-watch! flag) returns the previous state. Disabling frees all queued events; enabling first drains stale stragglers emitted by racing producers. Server teardown (resp_kv_clear) emits one DEL per surviving key, so a post-serve drain observes keyspace-wide deletions.

Gate: tools/test_resp_watch.sh (also make resp-watch-test) exercises the layer against a live --threads 4 server.

Shard count

Default N = ceil(num_cores * 0.75), min 1, max 16. Configurable via -r-shards N flag.

Single-shard mode (N=1) is identical to today's behavior. Useful for debugging and as the migration's first step (the shared infra works with N=1, just doesn't help).

Rollout plan

Step 0 — refcount audit. Today's __sync_* macros are still live in the multi-thread build. Verify every e->nref access goes through them; verify the freelist (exp_freelist) is per-shard, not global. (It's currently global. Easy fix: TLS variable.)
Step 1 — single-shard scaffold. Land shard_t, mpsc_queue_t, per-shard freelist, accept-and-route. N=1 shard. Must match today's perf within ±5%.
Step 2 — promote-to-shared write barrier on global-env writes. Ship Option 1+3 from "Refcount duality." Validate via a 2-shard test that mutating an exp_t reachable from the global env from one shard while another reads it doesn't crash.
Step 3 — N-shard with key-based routing. Cross-shard MGET/DEL, broadcast for KEYS/FLUSHDB/DBSIZE.
Step 4 — Lisp callback path. (redis-defcmd) runs on owning shard, with reads of the global env protected by the rwlock.
Step 5 — connection-home reactor + per-connection ordered outbox. Pipeline ordering correctness.
Step 6 — benchmark. Target: 4-shard ≥ 3× single-shard on a key-distributed workload (redis-benchmark -t SET,GET -r 100000).

Each step is its own commit and its own benchmark gate. If step 6 doesn't show the win, we revisit before merging.

Risks

Promote-to-shared races. A symbol cached via e->meta may be promoted on one shard while another shard is mid-read. Need a rcu-style one-time fence after promotion before the new shared pointer becomes visible. Or: do the promotion eagerly at startup (parse all initial Lisp before any shard starts) and forbid runtime promotion (no (def) from running connections).
GC pauses. No GC today (refcount only) so this is a non-issue — but if cycle collection ever lands, it has to be per-shard or stop- the-world.
(redis-defcmd) callback that reads OTHER keys. A user command pinned to shard A that calls (redis-get "key-on-shard-B") from its body. Today this is one C call. Under path B it becomes a cross- shard RPC with a blocking wait — easy to implement (sync on a per-call eventfd), but the latency floor jumps from ns to µs. May motivate a "small" cache of shared read-mostly keys.
TTL sweep. Currently a single 1s tick that walks the global dict. Under path B each shard sweeps its own dict, so the sweep scales linearly with N — strict win.

What we are NOT doing

Lock-free dict (path C). Per-shard dict is single-writer, no atomics needed.
Async/await reactor rewrite. Reactors stay select()-based; only the inbox/outbox channels are concurrency primitives.
Distributed clustering. This is in-process N-thread parallelism, not Redis Cluster.

Open questions

What's the right default for N when this is embedded in a Lisp process that's also doing arbitrary user computation? 1 might be the safer default and N opt-in.
Should (redis-defcmd) callbacks be allowed to mutate the global env? If yes, every callback hits the rwlock write path — slow. If no, that's a runtime restriction we need to document and enforce.
EXPIRE precision under N-shard: each shard's sweep is independent, so a key may live 2 ticks longer than expected on some shards. The 1s sweep already has 1s slop, so this is fine — call it out in docs.

Step 0 — audit results (2026-04-29)

Inventory of refcount accesses and global state that has to move before multi-shard scaffolding can land. Findings split into "safe as-is", "needs fix", and "needs sharding."

Refcount: direct `nref` writes (bypass `REFCOUNT_INC/DEC`)

Site	Kind	Verdict
`alcove.c:519` `newenv->nref = 1` in `make_env`	initial store, fresh env	Safe — env is not visible to any other thread until `ref_env`/install.
`alcove.c:843` `nil_exp->nref = 1` in `make_nil`	initial store, fresh exp	Safe — same reasoning.
`alcove.c:4894` `v->nref` printf in `inspect_value`	diagnostic read	Tolerable — torn read at worst, debug-only.

These three are publication writes and stay non-atomic.

Refcount: JIT-emitted load/inc/store (NON-ATOMIC)

The JIT inlines refexp and unrefexp as plain word-size load/add/store. This is incorrect under multi-thread for any exp_t that has been promoted-to-shared (Option 3 from "Refcount duality"). Sites:

Backend	Function (file)
arm64	`try_jit_is_prime_given` (`jit_arm64.h`)
arm64	`try_jit_safe_p` (`jit_arm64.h`)
x86_64	`try_jit_safe_p` (`jit_amd64.h`)
x86_64	`try_jit_is_prime_given` (`jit_amd64.h`)

(The list/tree-walking shapes that inline refexp/unrefexp as raw load/add/store. The newer JIT shapes — float_acc_loop, wide_counter_loop, predicate_cons_loop — are NOT additional sites: they call the real refexp/make_floatf/make_node (via callout or a C kernel), which already route through the __sync_* refcount macros. Functions referenced by name, not line, since the JIT now lives in jit_arm64.h / jit_amd64.h / jit_common.h.)

Resolution under path B: each JIT'd lambda runs on its lambda-home shard, so its environment slots and locals are single-threaded — non-atomic ops stay correct. The unsafe case is when a JIT'd function dereferences an exp reachable through the global env (a shared exp). The promote-to-shared write barrier marks shared exps with a flag bit (EXP_FLAG_SHARED). The JIT must:

Before each refexp/unrefexp inline, test the flag bit on the target.
If unset → keep the fast non-atomic path.
If set → branch to a deopt stub (fall back to bytecode, which uses the __sync_* macros).

Cost: one TBZ + one branch per inline refop. Same shape as the existing is_ptr / nil / true tag-check skips, so it folds into the predictor the same way. try_jit_for_loop_inc and the others that don't touch nref are unaffected.

Globals to convert to per-shard / TLS

Global	Line	Purpose	Plan
`exp_freelist`	383	exp_t recycling free-list	`__thread` (TLS, one per shard worker).
`exp_bump_next`, `exp_bump_left`	391, 392	exp_t bump-alloc fallback	`__thread` together with freelist.
`env_arena[]`, `env_arena_sp`	485, 486	env_t LIFO arena	per-shard (move into `shard_t`; `make_env` takes shard ptr).
`in_tail_position`	55	TCO marker for `evaluate`	`__thread` — per evaluator stack.
`alcove_load_depth`	1182	recursive `load` guard	`__thread` — depth is caller-local.

Note on env_arena: TLS is fine for the freelist (a 16-byte pointer pair), but the arena is 8192 × sizeof(env_t) ≈ 1 MB per shard. Putting it in TLS bloats the executable's TLS section. Better: store it in shard_t and thread the shard pointer through make_env/destroy_env.

Globals that stay global

Global	Line	Why it's safe
`nil_singleton`, `true_singleton`	45, 46	Allocated once in `main`; refexp/unrefexp short-circuit so nref is never touched.
`reserved_symbol`	41	Init-once read-only dict.
`exp_tfuncList`	42	Init-once dispatch table.
`lispProcList`	158	const initializer.
`bernstein_seed`	606	const after init.
`g_global_env`	50	Read-mostly; protected by rwlock per design above.

Globals needing atomicization (not sharding)

Global	Line	Why	Fix
`alcove_global_gen`	494	Bumped from 6 sites on global mutation; read by every gcache check. Currently `uint64_t++` — torn under SMP.	`__sync_add_and_fetch(&alcove_global_gen, 1)` on every bump; reads stay plain (a stale read just forces a re-resolve, which is correct).
`g_ffi_libs`	3276	Linked-list mutated on `(ffi-fn)` calls.	Mutex (rare path; FFI calls are not hot). Or per-shard cache (libs are idempotent; double-load is fine).

Items already correct

__sync_add_and_fetch / __sync_sub_and_fetch are the right primitives; they imply full barriers on both arm64 and x86_64. No need to switch to C11 atomic_* for the macros.
jit_alloc() mmap is per-bytecode and read-only after jit_write_end. No global JIT cache to protect.
The ENV_INLINE_SLOTS hot path (make_env → inline_vals[i]) is single- writer per env, and an env is single-shard, so inline-slot stores stay plain.
bytecode_t.gcache[].gen is per-bytecode and only written by the owning shard's evaluator, so the gcache check gcache[i].gen == alcove_global_gen works as long as the read of alcove_global_gen is monotonic — __sync_add_and_fetch guarantees that.

Punch list for Step 1

In commit-sized chunks, ordered for bisectability:

Convert exp_freelist, exp_bump_next, exp_bump_left to __thread. Run benchmarks — must match within ±1%. (Single-thread today, so TLS adds an addressing mode but no contention.)
Convert in_tail_position and alcove_load_depth to __thread. Trivial.
Wrap every alcove_global_gen++ in __sync_add_and_fetch. 6 sites.
Introduce shard_t with env_arena[ENV_ARENA_SLOTS] and env_arena_sp as members. Thread shard_t *self through make_env/destroy_env. (Or use TLS-pointer-to-shard if signature churn is too painful. Decide before this step.)
g_ffi_libs: add a mutex around the linked-list mutation. Minimal footprint.

After (1–5), the codebase compiles to a binary that's still single-shard but has zero non-shard global mutable state outside the g_global_env rwlock + alcove_global_gen atomic. That's the precondition for Step 1's shard scaffold.

Step 1 status (2026-04-29)

Punch list above is complete:

#	What	Commit
1	`exp_freelist` + `exp_bump_*` → `__thread`	`e44fc5e`
2	`in_tail_position` + `alcove_load_depth` → TLS	`31e924c`
3	`GEN_BUMP()` macro + atomicize 6 sites	`4cafcfb`
4	`shard_t { arena, arena_sp, arena_end }`	`eee0f51`
5	`g_ffi_libs_mtx` mutex around list mutation	`8d4a76f`
	JIT flag-gated deopt for `FLAG_SHARED` exps	`68fe268`

Single-shard binary; mono build is byte-equivalent to pre-Step-1 fast paths (TLS storage class collapses to one backing slot; macros expand to plain ++/--). Multi-thread build adds one TLS-base load on env ops (cached at function entry), six full-barrier increments on global-binding mutations, and one mutex around FFI dlopen — all contention-free at N=1.

Step 2 — sharded reactor scaffold

Goal: introduce N worker pthreads, each running its own RESP reactor on its own shard. N=1 first (main thread becomes shard 0; behavior identical to today). Then accept-and-route. Then N>1.

Snapshot strategy: fork-and-write (BGSAVE-style)

savedb today is synchronous: it walks the global dict and writes db.dump, blocking the only thread. Under the sharded reactor this breaks two ways: (a) the writer would have to gather across shards; (b) blocking the worker stalls every connection homed on that shard.

Decision: adopt Redis's BGSAVE pattern. The coordinator fork()s, the child gets a COW snapshot of every shard's dict, and the child iterates + writes the dump while the parents keeps serving. The parent's pre-existing synchronous (savedb) becomes the fallback for small dumps and tests; the new (bgsave) becomes the default for production and any --db auto-save.

Why this works for our design:

Per-shard dicts have no mutex (single-writer invariant) — a COW snapshot is consistent without coordination.
The only mutex in the system is g_ffi_libs_mtx. The child never calls FFI; even if a worker held that mutex at fork time, the child is unaffected.
Refcounts: the child sees post-fork copies; it unrefexps nothing, it only reads. No double-free risk.
TLS state: the child inherits only the calling thread, with that thread's freelist + arena. Child doesn't allocate exps either.

Constraints the child must obey:

No Lisp eval, no FFI, no allocator-heavy work. Only read exp_t/dict_t graphs and write to a file. This is by-construction for the dump format; we just need to keep it that way.
Exit via _exit(2), not exit(3). Skips atexit hooks and fclose on shared FDs the parent still owns.
Write to a tempfile + rename(2) so a partial write never replaces a good dump.

Coordinator side:

Parent issues (bgsave) → fork. On error, parent reports.
Child writes db.dump.tmp.<pid> then rename and _exit(0).
Parent waitpid(WNOHANG) in the reactor loop; on success, log; on non-zero exit, log + keep old dump.
Concurrent (bgsave) calls: parent rejects if child already running. Single in-flight snapshot.

Risks accepted: the brief fork latency proportional to RSS (Linux ~1ms per GB; macOS slower under recent kernels). At alcove's typical sizes (<100MB) the fork itself is sub-millisecond.

Step 2 punch list

In commit-sized chunks. Each step is bisectable + benchmarkable on its own.

2.1 — MPSC queue primitive. Header-only, lock-free single- consumer/multi-producer queue (Vyukov's intrusive design). Eventfd on Linux, pipe-pair on macOS, for select()-able wake-up. Stand-alone unit test before any wiring.
2.2 — shard_main skeleton. A pthread entrypoint that: binds current_shard to its argument; runs the existing resp_serve inner loop; pumps its inbox between iterations. N=1: main thread wraps shard_main(&main_shard) directly — no new thread spawned yet. Behavior identical.
2.3 — Acceptor split (superseded — see 2.4-pre). Originally planned as a dedicated pthread blocking on accept() and routing new fds to shard 0's inbox via a SHARD_MSG_NEW_CLIENT envelope. Landed and worked, but the user-space dispatcher turned out redundant given the kernel's SO_REUSEPORT flow-hashing. Replaced in 2.4-pre.
2.4-pre — SO_REUSEPORT pivot. Drop the acceptor pthread and the typed envelope. Each reactor calls bind() with SO_REUSEPORT and accepts directly inside its select() loop. At N=1 equivalent to a plain bind; at N>1 the foundation for 2.4. Smoke test in benchmark/test-reuseport.sh.
2.4 — N reactors. Spawn one shard pthread per CPU thread (default min(num_cores, 16), override via -r-shards). On Linux pin each with pthread_setaffinity_np; on macOS the affinity is a hint at best. Route at command-dispatch time by bernstein_hash(argv[1]) & (N-1) to the owner shard. The home reactor still owns the socket; cross-shard work goes through the per-shard inbox.
2.5 — Cross-shard ops. Broadcast/aggregate for KEYS, FLUSHDB, DBSIZE. MGET fan-out, gather-respond. First real producer for the inbox dispatcher.
2.6 — (bgsave). Fork-and-write child; parent waitpid loop. Fall back to synchronous (savedb) semantics for compat.
2.7 — Benchmark gate. N=4 must be ≥ 3× N=1 on redis-benchmark -t SET,GET -r 100000 -P 64. If not, revisit.

Step 2 status (2026-04-30)

#	What	Commit
2.1	MPSC primitive + cross-thread wake shim	`b75b7cf`
2.2	`shard_main` skeleton + per-shard inbox/wake	`1d961ed`
2.3	Acceptor pthread + inbox-driven new-client handoff	`e10b688`
2.4-pre	`SO_REUSEPORT` pivot — acceptor pthread removed	uncommitted

After 2.4-pre, single-binary behavior at N=1 is unchanged (the kernel routes the only listener it has). The per-shard inbox + wake fd stay wired but currently have no producer; they're the substrate Step 2.6 (cross-shard ops) will plug into. The SHARD_MSG_NEW_CLIENT envelope that 2.3 introduced was deleted — the Step 2.4-N path no longer needs a typed handoff for new connections.

Microbenchmark, single shard, MacBook Pro M-series, loopback, P=16:

c=50 ........ ~1.45M SET/sec, ~1.6M GET/sec
c=200 ....... ~1.5M SET/sec, ~1.5M GET/sec

These are unchanged from the pre-acceptor baseline, confirming the SO_REUSEPORT pivot is performance-neutral at N=1. The Step 2.5 benchmark gate will measure N>1.

Concurrency contract for `--threads N` (user-facing, EXPERIMENTAL)

alcove -r --threads N (N>1) runs N reactor pthreads. This mode is EXPERIMENTAL. What is and isn't safe, and why it's safe without per-request locking:

Safe and fully parallel

The keyspace (redis-get/redis-set/… and the RESP data commands) is a lock-free sharded structure (lfkv.c) designed for concurrent access. This is where your throughput comes from.

The shared RESP command table is immutable-after-spawn

(redis-defcmd "NAME" fn) / (redis-undefcmd …) mutate process-global state (resp_user_commands, resp_user_env). They are intended to run once at setup, before the server starts — respN_serve spawns the reactor pool after setup, so pthread_create publishes the table to every worker with a happens-before edge. Dispatch then only reads the table, lock-free, with no concurrent writer — so there is no data race and no per-request lock cost.
To keep that invariant unbreakable, redis-defcmd/redis-undefcmd refuse (raise an error) once multi-reactor serving is live — both from inside a RESP callback and from any other context. Register all commands before serving.

RESP callbacks must be read-only w.r.t. Lisp state

A (redis-defcmd …) callback runs concurrently on whatever reactor received the request. Mutating Lisp globals from a callback (def, = on a global, persist/forget/unpersist) is refused under --threads N>1 (it would race on the shared global env). Operate on the keyspace instead.
Not yet enforced (your responsibility): in-place mutation of a shared object the callback reaches (e.g. vec-set! on a captured vector), or reassigning a captured closure variable. Treat callbacks as pure functions of their args + the keyspace.

Single-reactor (N=1) is unrestricted — callbacks may mutate globals freely; none of the above guards apply.

CI runs the MPSC queue primitive under ThreadSanitizer (mpsc-test-tsan); a full multi-reactor TSan harness is future work.

-R reactor pool: thread-safety contract

alcove -R --threads N runs an interactive REPL on the main thread concurrently with N RESP reactor threads. The REPL may evaluate forms that mutate Lisp globals (def, defclass, require), while reactor callbacks read those globals lock-free.

Options: Global Env & REPL Mutation

Option 1: Global RWLock

Design: pthread_rwlock_t taken for write by the REPL on global mutations, and for read by reactor callbacks on every global lookup.
Cost: High. rdlock bounces a cache line on the reader atomic count, destroying multicore scaling for the 99% pure-read callback workload.
Migration: Easy, but permanently impairs throughput.

Option 2: Keep Current Contract (Strict Read-Only)

Design: Refuse all mutating forms (def, require, =/setq) from the REPL while the -R pool is running.
Cost: Zero runtime overhead.
Migration: Trivial (re-use g_resp_cb_guard on the main thread), but defeats the UX goal of a live-coding -R environment.

Option 3: Stop-the-world (Freeze Reactors)

Design: REPL mutates globals lock-free. When a mutating form is evaluated, the main thread signals all reactors (via their MPSC inbox or a global epoch flag) to park. Once all reactors ack, the REPL mutates, increments alcove_global_gen, and unparks them.
Cost: Zero steady-state overhead for callbacks. High latency for REPL mutations (human-speed).
Migration: Requires a park/unpark handshake mechanism wired into the reactor select() loop.

Decision: Option 3 (Stop-the-world). Optimizing for steady-state reactor throughput is strictly better than an RWLock. REPL mutations are human-driven and rare; paying a handshake latency penalty is acceptable to preserve wait-free reactor reads.

Enforcement Mechanism

REPL Mutations: The stop-the-world handshake is triggered automatically by def/require eval on the main thread.
Mono builds: Refuse -R --threads N>1 entirely at startup with a fatal error if compiled without atomics.
Callback Restrictions: Reactor callbacks are strictly read-only. g_resp_cb_guard continues to enforce this by trapping def/require attempts from reactor threads with a read-only error.

Forbidden (Even in Recommended Design)

Reactor-driven global mutation: Callbacks cannot mutate globals. Period.
In-place mutation of shared objects: vec-set! or assoc! on structures reachable from the global env from within a callback remains UB (unenforced, user responsibility).

Migration Path from Today

Restrict mono builds from launching -R --threads N>1.
Implement the reactor park/unpark handshake (e.g., SHARD_MSG_PARK).
Wrap main-thread global mutations (set_get_keyval_dict on g_global_env) with the park/unpark barrier.
Apply the FLAG_SHARED write barrier (from "Refcount duality") during the parked window so REPL-allocated exp_ts are atomic before reactors see them.

TLS allocator & epoch reclamation

Cross-thread unref: exp_freelist is per-thread (__thread). A REPL-allocated exp_t dropped to 0 by a reactor is pushed to the reactor's TLS freelist. This is memory safe because chunks are process-lived and never freed. The push is single-threaded (no tearing), and concurrent access before the drop is protected by atomic refcounting. However, cycle-collection (gc-cycles) walks exp_chunk_bases which is also TLS. The consequence: the main thread's collector cannot see reactor chunks. Any garbage cycle spanning the REPL and a reactor will leak.
Epoch reclamation: The -R REPL main thread blocks in readline(). If registered as an epoch participant (epoch_register), its blocked state will stall epoch_min_quiescent, preventing memory reclamation across all reactors. Rule: the main thread must remain unregistered (and thus never touch lfkv entries outside a stop-the-world window) or explicitly park its epoch state (e.g., quiescent = 0) before blocking.

FilesExpand file tree

multithreading.md

Latest commit

History