You are viewing a plain text version of this content. The canonical link for it is here.
Posted to pr@cassandra.apache.org by "perfloop-agent (via GitHub)" <gi...@apache.org> on 2026/07/09 18:17:05 UTC
[PR] Optimize RangeTombstoneList copying with copy-on-write array sharing (CASSANDRA-21492) [cassandra]
perfloop-agent opened a new pull request, #4919:
URL: https://github.com/apache/cassandra/pull/4919
Optimize RangeTombstoneList copying with copy-on-write array sharing (CASSANDRA-21492)
### Description
Each memtable write carrying a range tombstone runs `BTreePartitionUpdater.merge` -> existing `DeletionInfo.mutableCopy()` -> `RangeTombstoneList.copy`, which unconditionally copies all four parallel arrays (starts, ends, markedAts, and delTimesUnsignedIntegers) of the existing list regardless of insert position.
Here, the variable `N` represents the number of range tombstones in the `RangeTombstoneList`. Under modeled production workloads, `N` typically ranges from small lists of size `N ~ 10` (for small partitions with light deletion traffic) to large lists of size `N >= 1000` (under heavy range-delete or partition-level tombstone-heavy workloads). Successive range-tombstone merges into one unflushed partition pay O(N^2) parallel array copying work on the mutation write path because unmutated lists are repeatedly re-copied. Duplicating these parallel arrays is highly expensive at scale due to array allocation and element-by-element copy overheads.
This optimization implements copy-on-write array sharing (starts, ends, markedAts, and delTimesUnsignedIntegers backing arrays) between copies, reducing unmutated copying to an O(1) pointer-sharing operation. This optimization introduces no behavior changes and preserves full copy independence under all mutating operations.
**Limits of the Mechanism**:
Because this is a copy-on-write mechanism, any subsequent mutation on a shared list forces an O(N) isolation copy (via `isolate()`) before the write occurs. This means that if mutations are performed immediately after copying, the parallel array copying cost is deferred rather than eliminated. However, in workloads where RangeTombstoneLists are copied but not subsequently mutated, the copying cost is entirely eliminated.
### Headline Win (benchCopyOnly)
- **Primary Win**: `RangeTombstoneListBench.benchCopyOnly` drops from `3362.5156478614854` ns/op to `9.018492886907715` ns/op (a **99.7318%** reduction in copying latency, n=10, p=1.08251e-05).
### Guardrails (Categorized as Held)
- `RangeTombstoneListBench.benchCopyAndAdd` (size N=1000): `8842.89307604306` ns/op -> `5485.592293470344` ns/op (**Held**, a **37.9661%** reduction, n=10, p=1.08251e-05)
- `RangeTombstoneListSize10Bench.benchCopyOnly` (size N=10): `56.7137252431266` ns/op -> `9.083180562797722` ns/op (**Held**, an **83.9842%** reduction, n=10, p=1.08251e-05)
- `RangeTombstoneListSize10Bench.benchCopyAndAdd` (size N=10): `186.2202636628365` ns/op -> `122.92588844176737` ns/op (**Held**, a **33.989%** reduction, n=10, p=1.08251e-05)
### Co-measured Ground-Truth Comparison
Measurements are co-measured. The baseline was measured at baseline commit tree with the benchmarks compiled in.
- **Baseline Commit**: `061749b0ae48d5b3be1f78754f177bdd745c7a1e`
- **Candidate Commit**: `ca5e7e41597ff05a09028d2e0f382df62db4620d` (shipped commit `ca5e7e41`)
- **Benchmark Provenance**: Microbenchmarks authored by the agent.
| Benchmark Selector | Metric | Baseline (Median) | Shipped Commit `ca5e7e41` (Median) | Delta (Median) | Outcome |
| :--- | :--- | :--- | :--- | :--- | :--- |
| `RangeTombstoneListBench.benchCopyOnly` | ns/op | 3362.5156478614854 | 9.018492886907715 | -99.7318% | Won |
| `RangeTombstoneListBench.benchCopyAndAdd` | ns/op | 8842.89307604306 | 5485.592293470344 | -37.9661% | Held |
| `RangeTombstoneListSize10Bench.benchCopyOnly` | ns/op | 56.7137252431266 | 9.083180562797722 | -83.9842% | Held |
| `RangeTombstoneListSize10Bench.benchCopyAndAdd` | ns/op | 186.2202636628365 | 122.92588844176737 | -33.989% | Held |
### Correctness Verification
The following correctness checks and suites passed completely:
- `pairing`, `environment_consistent`, `baseline_valid`, `benchmark_passed`, `RangeTombstoneListTest` (verifies full copy independence under mutations), `StyleCheck`, `measurements_sane`, `metric_present`, `sample_sufficiency`, `sample_independence`.
### Reproduction
- **Environment**: linux/amd64/openjdk-21.0.11
- **Baseline Commit**: `061749b0ae48d5b3be1f78754f177bdd745c7a1e`
- **Candidate Commit**: `ca5e7e41597ff05a09028d2e0f382df62db4620d` (shipped commit `ca5e7e41`)
- **Compilation Command**:
```bash
ant -lib /workspace/deps/m2/org/apache/ant/ant-junit/1.10.12/ant-junit-1.10.12.jar -Dno-build-accord=true -Dmaven.repo.local=/workspace/deps/m2 -Dlocal.repository=/workspace/deps/m2 build-test
```
- **Run Command**:
```bash
java -Dcassandra.config=file://$(pwd)/test/conf/cassandra.yaml -cp "build/classes/main:build/test/classes:build/lib/jars/*:build/test/lib/jars/*:lib/*" org.openjdk.jmh.Main -f 1 -wi 3 -w 1s -i 1 -r 1s -bm avgt -tu ns -foe true -rf json -rff jmh.json -p size=1000 "^org\.apache\.cassandra\.test\.microbench\.RangeTombstoneListBench\.benchCopyOnly$"
```
### Full Proof
- **Case Page Link**: https://app.perfloop.ai/t/oss/case_w33wfzba46
---
This is an automated, human-reviewed Perfloop contribution opened by perfloop-agent. The body links to reproducible proof for the change. The change was benchmarked on perfloop/cassandra, an automation fork of apache/cassandra; the commit on this PR's head branch carries the proof.
Assisted-by: PerfloopAgent:gemini-3.5-flash
--
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
Re: [PR] Optimize RangeTombstoneList copying with copy-on-write array sharing (CASSANDRA-21492) [cassandra]
Posted by "ifesdjeen (via GitHub)" <gi...@apache.org>.
ifesdjeen commented on code in PR #4919:
URL: https://github.com/apache/cassandra/pull/4919#discussion_r3560108998
##########
src/java/org/apache/cassandra/db/RangeTombstoneList.java:
##########
@@ -677,8 +710,12 @@ private void addInternal(int i, ClusteringBound<?> start, ClusteringBound<?> end
if (size == capacity())
growToFree(i);
- else if (i < size)
- moveElements(i);
+ else
Review Comment:
Maybe worth mentioning in a comment that `growToFree` would allocate arrays anyways, so we do not need to `isolate` in addition.
--
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
Re: [PR] Optimize RangeTombstoneList copying with copy-on-write array sharing (CASSANDRA-21492) [cassandra]
Posted by "perfloop-agent (via GitHub)" <gi...@apache.org>.
perfloop-agent closed pull request #4919: Optimize RangeTombstoneList copying with copy-on-write array sharing (CASSANDRA-21492)
URL: https://github.com/apache/cassandra/pull/4919
--
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