You are viewing a plain text version of this content. The canonical link for it is here.
Posted to pr@cassandra.apache.org by "cheeeee (via GitHub)" <gi...@apache.org> on 2026/09/09 02:57:15 UTC

[PR] CASSANDRA-21492: Make RangeTombstoneList.copy() copy-on-write to avoid O(N^2) array copying [cassandra]

cheeeee opened a new pull request, #5132:
URL: https://github.com/apache/cassandra/pull/5132

   ### Jira Issue
   * [CASSANDRA-21492](https://issues.apache.org/jira/browse/CASSANDRA-21492)
   
   ### Motivation
   On every memtable write carrying a range tombstone, `BTreePartitionUpdater.merge()` invokes `DeletionInfo.mutableCopy()` which called `RangeTombstoneList.copy()`. Previously, this unconditionally copied all four parallel arrays (`starts`, `ends`, `markedAts`, `delTimesUnsignedIntegers`). Successive merges of $N$ range tombstones into an unflushed partition resulted in $O(N^2)$ array allocations and severe young-gen garbage collector churn.
   
   ### Changes
   1. **Copy-on-Write:** Added internal `volatile boolean isShared` flag to `RangeTombstoneList`. `copy()` shares existing arrays and marks both source and copy as shared without array copying.
   2. **Lazy Detach (`ensureWritable`):** Arrays are detached only when a mutating operation occurs.
   3. **Exception Safety / OOM Safety:** Allocations occur into local references before atomic field reassignment, preventing corrupted split-brain state upon out-of-memory.
   4. **Capacity Bloat Protection:** When detaching from an excessively bloated capacity (> 2x actual size), compacts to `size + growthBuffer` to avoid holding dead array capacity.
   5. **Thread Safety & Mutability:** Completely transparent to existing callers; retains 100% thread safety and mutability semantics.
   
   ### Testing
   * `RangeTombstoneListTest`: all 28 tests pass cleanly.
   * Added `copyOnWriteTest` verifying independence upon subsequent mutation.
   * Added `copyOnWriteMergePerformanceTest` verifying $O(1)$ allocation on successive copy operations ($400\times$ allocation reduction).
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: pr-unsubscribe@cassandra.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@cassandra.apache.org
For additional commands, e-mail: pr-help@cassandra.apache.org