{"id":"c0be09f0-a458-47a0-904e-1ca48db0ed1b","arxiv_id":"2507.00839","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"RapidStore reports up to 3.46x faster graph analytics and 56.34% memory savings versus existing dynamic graph systems by using subgraph-level versioning and a compressed radix tree.","lead":"RapidStore is a new in-memory database layout for graphs that are read often and updated occasionally. It separates read queries from write queries and stores version history at the level of groups of vertices, which lets readers work without locks.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"GC can reclaim the snapshot a reader needs before the reader publishes its start time, breaking snapshot isolation.","rationale":"The reader's weakest_assumption concerns atomic visibility across the multiple subgraphs updated by one commit. That specific concern is, on close reading, already addressed by the protocol: a reader's start time is a single atomic read of tr; all versions created by a commit share the same timestamp t; and tr is advanced only after every affected subgraph version is linked. A reader that reads tr before the advance sees no version with timestamp t, and a reader that reads tr after the advance sees all of them. Partial visibility of a single commit does not arise from the described memory operations. However, the same area of the design has a more serious flaw: the interaction between reader registration and garbage collection. A reader that reads tr but has not yet published its start time is invisible to GC, so a writer committing in that window can reclaim the very snapshot the reader will need. This is a concrete violation of the snapshot-isolation guarantee stated in Proposition 5.1, and the proof in Appendix A.1 does not cover it. The central claim of the paper—correct concurrent reads with high performance—depends on this guarantee, so the concern is load-bearing. The paper otherwise presents a coherent design, a reasonable ablation, and substantial experimental comparisons, so a conditional acceptance with a mandated fix and a revised correctness argument is appropriate. The reader's other conditions (error bars, artifact availability) remain valid, and the GC race is an additional mandatory revision.","tokens_in":25648,"tokens_out":17911,"duration_ms":217244,"concrete_test":"Instrument the implementation to pause a reader thread after it reads tr but before it performs the CAS in §5.2.2. Have a writer thread commit a transaction touching a subgraph and run the §5.3 GC in that pause. Resume the reader and check whether its snapshot construction dereferences a reclaimed version or fails to find a version with timestamp ≤ its start time. Repeat this with a barrier to force the interleaving deterministically; if no failure appears because the implementation happens to use refcounting or a grace period, inspect whether the paper's described GC rule actually prevents reclaiming versions needed by unregistered readers.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The serializability guarantee depends on readers being protected by the garbage collector from the moment they choose a start time. In §5.2.2, a reader reads the global read timestamp tr and then uses CAS to publish its start time in the reader tracer. Between these two steps, a writer can complete a commit: §5.2.1 advances tr and then §5.3 immediately runs GC on the modified subgraphs. If that GC scans the tracer before the reader's CAS, the reader is not marked active, so the writer reclaims every non-latest subgraph version. The reader's start time is the stale tr value (e.g., t−1), and the version it needs for each modified subgraph is exactly the one the writer just reclaimed (e.g., timestamp t−1, now superseded by t). The reader subsequently constructs its snapshot from a version chain whose required version has been freed, producing a use-after-free or a missing-version error. The proof in Appendix A.1 asserts that GC preserves versions needed by active readers, but the reader is not active during the window; the proof does not rule out this interleaving. This is a genuine correctness hole in the concurrency control mechanism, not merely a missing error bar: it can break snapshot isolation for a real, if narrow, scheduling window.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"RapidStore proposes an in-memory dynamic graph storage system targeting read-intensive concurrent workloads. The graph is partitioned into subgraphs, and each subgraph maintains a version chain, replacing per-edge versioning; write transactions use MV2PL with a global write timestamp, while readers register in a reader tracer and access immutable copy-on-write snapshots selected by a global read timestamp. The storage layer introduces C-ART, a leaf-compressed adaptive radix tree for high-degree neighbor sets, and a clustered index for low-degree vertices. The evaluation compares RapidStore with Sortledton, Teseo, Aspen, and LiveGraph on six datasets and five GAP workloads, reporting faster analytics, competitive insertion throughput, lower memory consumption, and better read-write concurrency than the baselines.","tokens_in":25804,"tokens_out":11581,"duration_ms":140675,"significance":"If the correctness issues are resolved, the paper makes a useful contribution: subgraph-level versioning is a clean way to eliminate per-edge version checks, C-ART's horizontal leaf compression and the clustered index are concrete and implementable ideas, and the evaluation is more thorough than the average systems paper (six datasets, five workloads, medians over five runs, four baselines, an ablation study, and a partition-size sensitivity analysis). The performance claims are falsifiable and mostly consistent with the reported experiments. However, the serializability guarantee currently rests on an informal proof, and the garbage-collection race described below means the central correctness claim is not yet established.","major_comments":[{"comment":"The garbage-collection protocol has a snapshot-isolation race. A reader R samples the global read timestamp tr and then publishes its start time in the reader tracer via CAS. Between these two steps, a writer W can commit a new version at timestamp t, advance tr to t, and run GC on the modified subgraphs. Because R has not yet set its status bit, W's scan of the reader tracer does not see R, so W reclaims every non-latest version, including the version with timestamp tr that R is about to request. R then publishes tr and traverses the version chain, finding that the required snapshot has been freed, which can cause a use-after-free or a missing-version error. Appendix A.1 only argues that GC preserves versions of active readers; it does not cover a reader in the window between sampling tr and publishing its start time. The protocol needs a mechanism such as registering the slot before sampling tr, treating slots in the process of registration as active, or delaying GC until no reader can hold the pre-advance value of tr.","section":"§5.2.2, §5.3, Appendix A.1"},{"comment":"The read-timestamp advancement rule is underspecified. The paper states that after assigning commit timestamp t, the writer polls tr and 'if tr = t-1, atomically increments tr by 1,' but it does not say what happens when the condition is false. Consider writers W1 and W2 receiving commit timestamps 1 and 2; if W2 finishes first, it observes tr=0 and, under a literal reading, proceeds without advancing tr. W1 later advances tr from 0 to 1, and no writer is left to advance it to 2, so readers permanently see a stale snapshot. The protocol must specify that a writer waits or retries until tr = t-1, or otherwise enforces ordered tr advancement, before completing its commit or performing GC; Proposition 5.1 depends on this.","section":"§5.2.1"},{"comment":"The reader snapshot construction is described as iterating over the version chains of all p subgraphs and copying p snapshot pointers into the reader workspace. For Friendster (|V|≈65M, |P|=64), p≈1M, so every read query pays O(p·k) ≈ 32M version-chain operations before performing any graph operation. This is inconsistent with the high search throughput reported in Appendix B.1 and with the claim that C-ART provides effectively constant-time search; the snapshot-construction cost alone would dominate short queries. Please clarify whether snapshot construction is eager, and if so report this cost in the experiments, or whether it is lazy/on-demand per accessed subgraph, and adjust the complexity analysis in §5.4 accordingly.","section":"§5.2.2 and §5.4"}],"minor_comments":[{"comment":"The partitioning rule is stated as contiguous blocks of |P| vertices in §5.1 and as 'randomly dividing the graph into equal-sized partitions' in §5.4; please reconcile these descriptions, since the definition of subgraphs and the vertex-index lookup depend on it.","section":"§5.1 vs §5.4"},{"comment":"The leaf segment size B is given as 256 in §6.2 and as 512 in §6.5 and the hyperparameters paragraph; please standardize the value and the notation.","section":"§6.2 vs §6.5 and hyperparameters paragraph"},{"comment":"The sentence 'showing negligible performance drop even with 31 or 28 writers' appears to refer to the number of readers (31 or 28) given the fixed total of 32 threads; as written, 31 writers leaves only 1 reader, which conflicts with the subsequent memory-bandwidth saturation discussion.","section":"§7.3"},{"comment":"Aspen is described as designed for single-writer execution but is benchmarked with 32 writer threads; if this is intended as a stress test, please state so explicitly, otherwise use its supported configuration for the insertion comparison.","section":"§7.2"}],"recommendation":"major_revision","confidential_remarks":"The technical report link in reference [2] is an anonymous Google Drive link; for a journal submission, please replace it with a stable archival reference and include the full correctness proof in the paper. The contribution is within scope for a database systems venue and is incremental but acceptable if the concurrency-control gaps are fixed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should read this one for the C-ART and subgraph-versioning ideas, but don't cite the concurrency control until the registration/GC race is fixed.\n\nThe core design is genuinely new. Subgraph-level versioning with copy-on-write is a sensible alternative to per-edge MVCC for read-heavy workloads, and the C-ART filling ratio jump from single digits to ~65% is a concrete, credible improvement. The evaluation is also above the bar: six datasets, five analytics workloads, four baselines, ablation, and a partition-size sensitivity. The 1.5–2.1x slowdown versus CSR, with much smaller penalties than Sortledton or LiveGraph, is plausible given the mechanisms.\n\nNow the soft part, and it is load-bearing. The stress-test note is correct. A reader reads tr, then CAS-publishes its start time in the tracer. Between those two steps, a writer can commit, advance tr, and run GC. If GC scans the tracer before the reader registers, the reader's needed version (the one for its stale tr) is reclaimed. The reader then builds a snapshot from a chain that no longer contains its version. The proof in A.1 asserts that readers see consistent snapshots and that GC protects active readers, but the reader is not yet active during that window. This is a textbook race, not a missing error bar. The conditional increment on tr does not help, because the reader's start time was sampled before the increment.\n\nThe reader's report flags atomic visibility across subgraphs as the main worry. I think the GC race is actually the sharper problem. The multi-subgraph commit visibility issue is at least plausible to resolve by having readers always take the new tr after all version links are updated; the GC race is a real hole unless registration and timestamp sampling are made atomic or GC uses a grace period.\n\nOther weaknesses are minor by comparison: no error bars, no artifact, and the serializability proof is a sketch. Those would be fixable in a revision.\n\nThis paper deserves a serious referee. The design is worth exploring, and the bug is clearly identifiable and likely fixable. But as submitted, the concurrency guarantee does not hold. I'd send it to review with a strong request for the authors to address the registration/GC interleaving and provide a rigorous proof.\n\nFor a reading group, this would be a good case study in how easy it is to race a reader's timestamp against GC.","headline":"Polished systems paper with an uneven concurrency protocol: the GC race against reader registration is a real correctness bug that breaks snapshot isolation.","tokens_in":26450,"tokens_out":3003,"would_cite":false,"duration_ms":38723,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Graph storage cuts concurrent query latency up to 71 percent by versioning whole subgraphs instead of edges.","keywords":["dynamic graph storage","concurrent queries","subgraph-centric concurrency control","copy-on-write","compressed adaptive radix tree","multi-version concurrency control","graph analytics","read-intensive workloads"],"falsifier":"Run a stress test in which one writer transaction inserts edges spanning two subgraphs while a reader repeatedly checks a cross-subgraph invariant, such as a global edge counter or the presence of a two-edge path stored across the partition boundary. If the reader ever observes one updated subgraph together with an unupdated partner from the same commit, the atomic snapshot guarantee is broken; the protocol's correctness depends on the read timestamp making the whole multi-subgraph commit visible at once.","tokens_in":25373,"feed_emoji":"⚡","tokens_out":5686,"duration_ms":62272,"temperature":0.7,"pith_summary":"RapidStore is an in-memory storage system for graphs that change over time, aimed at workloads where reads vastly outnumber writes. The paper argues that the usual per-edge versioning and vertex locking used for concurrency make reads slow: every edge access carries a version check, every vertex visit can contend with a writer's lock, and memory fills with version chains. Its answer is to version whole subgraphs instead of edges, so readers can build a consistent snapshot by picking one immutable version per subgraph and then traverse lock-free. The authors report that this approach brings analytic workloads to within 0.92x to 2.11x of a static CSR baseline, cuts query latency by 31.86 percent to 71.08 percent against the best alternative system, and saves up to 56.34 percent of memory, while keeping writes within a modest factor of the fastest competitor.","feed_headline":"Graph store cuts concurrent query latency up to 71 percent","feed_subtitle":"Versioning whole subgraphs instead of single edges lets readers skip locks and run analytics near static-CSR speed.","key_machinery":"The load-bearing piece is subgraph-centric multi-version concurrency control with copy-on-write: the graph is partitioned into subgraphs of 64 vertices; each update creates a new immutable snapshot of only the affected subgraph and links it into that subgraph's version chain; readers take the current read timestamp and assemble a snapshot by selecting, for each subgraph, the latest version with timestamp no greater than that start time. Because new versions are made by copying a root-to-leaf path in C-ART, a compressed adaptive radix tree whose leaves hold up to 256 consecutive vertex IDs, version creation is cheap and existing snapshots are never modified, so readers need no locks and never do version checks during scans or searches.","core_discovery":"On its own terms, the paper's central discovery is that the granularity of versioning, not the graph data structure alone, determines whether concurrent reads can be fast. By maintaining versions at the subgraph level, with each version an immutable copy-on-write snapshot stored separately from the data, RapidStore eliminates the per-edge version checks that dominate scan-heavy analytics, and by giving readers a start timestamp with lock-free snapshot construction it removes read-write lock contention. The C-ART structure then supplies constant-depth search, linear scans, and cheap path copying so that snapshot creation does not tax writes. The measured consequences are that PageRank, BFS, SSSP, WCC, and triangle counting all run close to static CSR speed while concurrent writers continue to make progress with little reader slowdown.","pith_inferences":["The decoupling suggests that read latency under mixed workloads will be limited by memory bandwidth rather than by contention; the paper's bandwidth measurements point to a ceiling that faster memory or higher-radix tree nodes could raise.","An adaptive partition-size strategy, hinted at in the paper but not implemented, could reduce write conflicts on skewed graphs by shrinking partitions around hot vertices while keeping large partitions for low-degree regions; this is a testable extension not claimed by the authors.","Because C-ART compresses leaves by longest common prefix, the design should carry over naturally to graphs with 64-bit vertex IDs and to workloads that mix point lookups with range scans; this implication goes beyond the reported 32-bit experiments."],"forward_implications":["Read queries should stay fast even with many concurrent writers, because they never touch locks; the measured read completion time grows at most 13.36 percent with 4 writers and 28 readers, versus up to 41.04 percent for baseline systems.","Scan-heavy analytics and search-heavy work both benefit, with latency reduced by 31.86 percent to 71.08 percent over the best baseline across five standard graph algorithms and six datasets.","Memory footprint drops by up to 56.34 percent, because per-edge version chains are replaced by one copy-on-write path per subgraph version and vertex IDs are compressed inside C-ART leaves.","Write throughput remains within a 1.9x to 2.2x factor of the fastest insert-only baseline, and the system handles batch updates well because a large update amortizes the cost of copying shared paths."],"supporting_citations":[{"why":"Serves as the per-edge MVCC and vertex-locking baseline whose measured slowdowns motivate coarse-grained subgraph versioning.","marker":"[15]"},{"why":"A comparison system using packed memory arrays and ART whose read and write numbers anchor the concurrency evaluation.","marker":"[8]"},{"why":"A copy-on-write, snapshot-oriented graph system used as a baseline and as the source of the PAM-tree comparison.","marker":"[10]"},{"why":"A timestamp-log graph system used as a baseline whose search and scan results highlight the cost of unsorted neighbor sets.","marker":"[49]"},{"why":"The adaptive radix tree that C-ART extends with horizontal leaf compression.","marker":"[22]"},{"why":"Supplies the five graph algorithms and standard parameters used in the read-performance experiments.","marker":"[3]"},{"why":"The technical report containing the full correctness proof of the subgraph-centric concurrency control protocol.","marker":"[2]"}],"fun_headline_variants":["Subgraph versioning makes dynamic graph reads lock-free","RapidStore: near-static speed for concurrent graph scans","Decoupled version data speeds concurrent graph queries","Graph storage that decouples reads from writes","Subgraph snapshots cut lock contention in graph stores"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole design rests on the assumption that a reader's start timestamp always defines a consistent graph state, even when one writer has updated several subgraphs at once; if a reader could see some of those updated subgraphs but not others, the snapshot guarantee would break.","fun_headline_variants_meta":{"raw":{"variants":["Subgraph versioning makes dynamic graph reads lock-free","RapidStore: near-static speed for concurrent graph scans","Decoupled version data speeds concurrent graph queries","Graph storage that decouples reads from writes","Subgraph snapshots cut lock contention in graph stores"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000194,"raw_usage":{"total_tokens":1316,"prompt_tokens":867,"completion_tokens":449,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":483,"completion_tokens_details":{"reasoning_tokens":375}},"tokens_in":483,"tokens_out":449,"duration_ms":5004,"temperature":1.0,"reasoning_tokens":375,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:04:07.082543+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a stress test in which one writer transaction inserts edges spanning two subgraphs while a reader repeatedly checks a cross-subgraph invariant, such as a global edge counter or the presence of a two-edge path stored across the partition boundary. If the reader ever observes one updated subgraph together with an unupdated partner from the same commit, the atomic snapshot guarantee is broken; the protocol's correctness depends on the read timestamp making the whole multi-subgraph commit visible at once.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Serves as the per-edge MVCC and vertex-locking baseline whose measured slowdowns motivate coarse-grained subgraph versioning."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"A comparison system using packed memory arrays and ART whose read and write numbers anchor the concurrency evaluation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"A copy-on-write, snapshot-oriented graph system used as a baseline and as the source of the PAM-tree comparison."},{"cited_title":"LiveGraph: A Transactional Graph Storage System with Purely Sequential Adjacency List Scans","cited_arxiv_id":"1910.05773","evidence_quote":"A timestamp-log graph system used as a baseline whose search and scan results highlight the cost of unsorted neighbor sets."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The adaptive radix tree that C-ART extends with horizontal leaf compression."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The technical report containing the full correctness proof of the subgraph-centric concurrency control protocol."}],"review_version":1}