linkrs_storage/edge/mutable_csr.rs
1//! Mutable CSR Implementation
2//!
3//! Two-level CSR with fixed-size overflow chunks for stable append cost.
4//! Primary blocks are stored contiguously in `hot_list`/`cold_list`
5//! (flat CSR layout with split topology and timestamp halves).
6//! Each overflow allocation adds one chunk and never copies an existing chunk. This keeps
7//! high-degree vertex growth linear and avoids the repeated doubling/copying behavior that
8//! previously produced unreachable blocks in the primary neighbor array.
9//!
10//! # Zero-Degree Rows
11//!
12//! Primary blocks are allocated lazily on the first edge of a vertex. A vertex without
13//! edges holds no slots in the primary halves, and overflow chunks plus live-key
14//! sets are addressed by segmented sparse row index (only touched segments
15//! allocate). This keeps the per-row fixed cost to 12 bytes
16//! (offset + degree + capacity) with no per-row hashing.
17//!
18//! Layout by responsibility (`mutable_csr/` subdirectory):
19//! - `core` holds lifecycle and capacity management.
20//! - `live_set` maintains the live endpoint index.
21//! - `row` handles density tiering, gaps and rebalance.
22//! - `write` implements the mutation path.
23//! - `read` implements timestamped and physical reads.
24//! - `iter` holds iterators and their constructors.
25//! - `persistence` handles dump, load and encoding reports.
26//! - `compaction` reclaims eligible tombstones.
27//! - `stats` reports memory and fragmentation.
28//! - `trait_impl` adapts the type to CSR traits.
29//! - `overflow` and `serialization` stay as storage primitives.
30//!
31//! # Concurrency contract (canonical)
32//!
33//! This section is the single authority for CSR write discipline; the
34//! sharded container (`node_group`) and the table (`edge_table::core`) only
35//! reference it and add no second set of rules.
36//!
37//! - Single writer: `MutableCsr` carries no internal locks. Every mutation
38//! takes `&mut self`, so aliased writes are rejected by the borrow checker
39//! at compile time, never detected at runtime.
40//! - Concurrent readers are safe while no mutation is in flight. The type is
41//! `Send + Sync`, so shared references may cross threads; obtaining a
42//! `&mut` while readers exist is again a compile-time error.
43//! - Caller serialization: the table or transaction layer serializes writers.
44//! Vertex-level locking is a caller decision, not a property of this struct.
45//! - The only runtime-shared mutable state below this level is the sharded
46//! route cache, built from atomics: a stale entry costs a re-lookup, never
47//! a wrong answer. Debug builds cross-check cached routes against the group
48//! map so cache-coherence violations fail fast instead of hiding.
49//! - No new lock module exists. If write concurrency is ever needed, per-row
50//! locking must be evaluated against a contention benchmark first; a global
51//! lock is not an acceptable default.
52
53use std::fmt;
54
55use super::csr_shared::VertexBookkeeping;
56use super::{ColdStamps, HotNbr, Nbr, Timestamp};
57
58use live_set::LiveSetStorage;
59
60pub(crate) mod compaction;
61pub(crate) mod core;
62pub mod iter;
63pub(crate) mod live_set;
64pub mod overflow;
65pub(crate) mod persistence;
66pub(crate) mod read;
67pub(crate) mod row;
68pub mod serialization;
69pub(crate) mod stats;
70pub(crate) mod trait_impl;
71pub(crate) mod write;
72
73pub use iter::{MutableCsrIterator, VertexEdgesIter};
74pub use overflow::{OverflowChunk, OverflowStorage};
75pub use write::EdgePosition;
76
77pub(crate) use row::PACKED_CSR_DENSITY;
78
79/// Mutable multi-edge CSR with lazy primary blocks and overflow chains.
80///
81/// Single-writer discipline: this type carries no internal locks. Concurrent
82/// readers are safe while no mutation is in flight; concurrent writers must
83/// be serialized by the caller (table or transaction layer). Vertex-level
84/// locking is a caller decision, not a property of this struct. Multi-core
85/// work is carried by shard-level parallelism over `NodeGroup` shards
86/// (freeze, reclaim, read-only scans); point-write parallelism is an import
87/// pressure decision above this layer, and no row lock is added here before
88/// that measurement.
89pub struct MutableCsr {
90 hot_list: Vec<HotNbr>,
91 cold_list: Vec<ColdStamps>,
92 rows: VertexBookkeeping,
93
94 overflow_chunks: OverflowStorage,
95 overflow_chunk_edges: usize,
96 /// Single live-endpoint set per wide vertex covering primary and overflow:
97 /// (endpoint, rank) of edges whose `delete_ts == MAX`. One set replaces
98 /// the former primary/overflow pair, so duplicate checks never consult
99 /// two heaps and never fall back to linear scans on indexed rows.
100 /// Only rows wider than the live-set bound carry a set; narrow rows
101 /// answer through direct row scans with no per-vertex memory. Rows are
102 /// addressed by dense subscript; empty and narrow rows hold no set.
103 live_sets: LiveSetStorage,
104 /// Watermark-derived cutoff for hot-path tombstone reuse, refreshed by
105 /// the table maintenance pass. The sentinel disables reuse. Memory-only:
106 /// never persisted, rebuilt to the default on construction.
107 tombstone_reuse_cutoff: Timestamp,
108 /// First known reclaimable primary slot per vertex, or unknown sentinel.
109 /// Set on primary deletes, consumed on reuse, invalidated by any row move.
110 /// Memory-only hint: a stale value only costs one failed probe before the
111 /// bounded scan fallback.
112 reuse_hint: Vec<u32>,
113
114 /// Incremental live entry count per vertex (narrow rows only).
115 /// Indexed rows track membership via the live set instead.
116 live_counts: Vec<u32>,
117 /// Incremental tombstone count per vertex (narrow rows only).
118 tombstone_counts: Vec<u32>,
119 /// Cached primary-block key order per vertex: true when the primary
120 /// window arrives in `(endpoint, rank, edge_id)` order.
121 ///
122 /// Threshold scans consult this instead of probing the whole row on
123 /// every query. New and empty rows start ordered; any primary write of
124 /// a new key clears the row, cold-only deletes and order-preserving
125 /// moves keep it, and the maintenance sort establishes it. Memory-only:
126 /// never persisted, rebuilt to unordered on load.
127 primary_sorted: Vec<bool>,
128
129 edge_count: u64,
130 total_edge_capacity: usize,
131
132 // -- baseline instrumentation probes (memory-only, not persisted) --
133 overflow_chunk_allocs: u64,
134 primary_block_allocs: u64,
135 repack_count: u64,
136 tombstone_reuse_count: u64,
137 live_set_rebuild_count: u64,
138 tombstone_reuse_hint_hits: u64,
139 tombstone_reuse_hint_misses: u64,
140}
141
142impl MutableCsr {
143 /// Assembled slot copy at a primary-list index.
144 ///
145 /// Hot and cold halves grow in lockstep, so one index addresses both.
146 /// Callers that only need one half must read it directly instead of
147 /// paying for the assembly here.
148 #[inline]
149 pub(crate) fn slot_at(&self, idx: usize) -> Option<Nbr> {
150 Some(Nbr::from_parts(
151 *self.hot_list.get(idx)?,
152 *self.cold_list.get(idx)?,
153 ))
154 }
155
156 /// Write an assembled record into a primary-list index.
157 ///
158 /// Sole paired writer for the primary halves: hot and cold stay in
159 /// lockstep by construction instead of by caller discipline.
160 #[inline]
161 pub(crate) fn set_slot(&mut self, idx: usize, nbr: Nbr) {
162 self.hot_list[idx] = nbr.hot();
163 self.cold_list[idx] = nbr.cold();
164 debug_assert_eq!(self.hot_list.len(), self.cold_list.len());
165 }
166
167 /// Cold half at a primary-list index without touching topology lines.
168 #[inline]
169 pub(crate) fn cold_at(&self, idx: usize) -> Option<ColdStamps> {
170 self.cold_list.get(idx).copied()
171 }
172}
173
174impl Clone for MutableCsr {
175 fn clone(&self) -> Self {
176 Self {
177 hot_list: self.hot_list.clone(),
178 cold_list: self.cold_list.clone(),
179 rows: self.rows.clone(),
180 overflow_chunks: self.overflow_chunks.clone(),
181 overflow_chunk_edges: self.overflow_chunk_edges,
182 live_sets: self.live_sets.clone(),
183 tombstone_reuse_cutoff: self.tombstone_reuse_cutoff,
184 reuse_hint: self.reuse_hint.clone(),
185 live_counts: self.live_counts.clone(),
186 tombstone_counts: self.tombstone_counts.clone(),
187 primary_sorted: self.primary_sorted.clone(),
188 edge_count: self.edge_count,
189 total_edge_capacity: self.total_edge_capacity,
190 overflow_chunk_allocs: self.overflow_chunk_allocs,
191 primary_block_allocs: self.primary_block_allocs,
192 repack_count: self.repack_count,
193 tombstone_reuse_count: self.tombstone_reuse_count,
194 live_set_rebuild_count: self.live_set_rebuild_count,
195 tombstone_reuse_hint_hits: self.tombstone_reuse_hint_hits,
196 tombstone_reuse_hint_misses: self.tombstone_reuse_hint_misses,
197 }
198 }
199}
200
201impl fmt::Debug for MutableCsr {
202 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
203 f.debug_struct("MutableCsr")
204 .field("vertex_capacity", &self.vertex_capacity())
205 .field("total_edge_capacity", &self.total_edge_capacity)
206 .field("edge_count", &self.edge_count)
207 .finish_non_exhaustive()
208 }
209}
210
211#[cfg(test)]
212mod tests;