You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by "Perfloop Agent (Jira)" <ji...@apache.org> on 2026/07/08 17:08:00 UTC
[jira] [Updated] (CASSANDRA-21492) Make RangeTombstoneList.copy() copy-on-write to avoid O(N²) array copying on range-tombstone memtable merges
[ https://issues.apache.org/jira/browse/CASSANDRA-21492?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Perfloop Agent updated CASSANDRA-21492:
---------------------------------------
Description:
h3. Problem
On every memtable write carrying a range tombstone, {{BTreePartitionUpdater.merge}} -> {{DeletionInfo.mutableCopy()}} -> {{RangeTombstoneList.copy()}} unconditionally {{Arrays.copyOf}}s all four parallel arrays ({{starts}}, {{ends}}, {{markedAts}}, {{delTimesUnsignedIntegers}}) regardless of insert position. N successive range-tombstone merges into one unflushed partition therefore pay 1+2+...+N = *O(N^2^)* array copying and discarded allocation on the mutation write path. This bites under range-DELETE-heavy or superseding-partition-delete traffic concentrated on a single partition between flushes.
h3. Fix
Make {{copy()}} copy-on-write: the copy shares the four backing arrays with the original and both are marked {{shared}}; every in-place mutation ({{add}}, {{addAll}}, {{updateAllTimestamp}}, {{updateAllTimestampAndLocalDeletionTime}}, {{insertFrom}}) calls {{isolate()}} to reallocate the arrays before its first write. Amortized *O(N^2^) -> O(N)*.
h3. Measured impact
JMH {{AverageTime}}, co-measured baseline vs patched on the same benchmarks:
||Benchmark||Baseline||Patched||Reduction||
|RangeTombstoneListBench.benchCopyOnly (size=1000)|~2935 ns/op|~7.8 ns/op|~99.7% (O(1) vs O(N))|
|RangeTombstoneListBench.benchCopyOnly (size=10)|~48 ns/op|~7.6 ns/op|~84%|
|RangeTombstoneListBench.benchCopyAndAdd (guardrails)| | |~33-38% faster|
|allocation, N=4096|421,953,645 B/op|2,475,362 B/op|-99.4%|
The growth curve confirms O(N^2^) -> O(N).
h3. Correctness
* Full {{RangeTombstoneListTest}} passes, including a new {{testCopyIndependence}} that asserts isolation across every mutating pathway (mutations to either the original or the copy never corrupt the other's shared arrays).
* A differential stress harness -- the candidate vs a true deep-copy reference run against identical randomized {{add}}/{{copy}}/{{addAll}}/{{updateAll}} op sequences over deeply-shared lists -- ran ~300k ops with zero divergence.
* Concurrency is unchanged: {{BTreePartitionUpdater.merge}} mutates a thread-local copy (isolate-on-write), while the live shared list is only read before a new holder is CAS-published.
h3. Code
Reference implementation + benchmarks on a {{trunk}} snapshot (public fork). The full patch is the *diff below* -- not any single commit (the branch tip is only a microbenchmark add):
* Full patch (baseline..patched, RangeTombstoneList.java + the copy-independence test + the JMH microbenchmarks): [compare 061749b0...20c86e5a|https://github.com/perfloop/cassandra/compare/061749b0ae48d5b3be1f78754f177bdd745c7a1e...20c86e5aa9990c43bce7f38fa889f1178b26f220]
A pull request against {{trunk}} -- the clean {{RangeTombstoneList.java}} + {{RangeTombstoneListTest}} change (minus the microbenchmark scaffolding), with a {{CHANGES.txt}} entry -- will follow.
was:
h3. Problem
On every memtable write carrying a range tombstone, {{BTreePartitionUpdater.merge}} -> {{DeletionInfo.mutableCopy()}} -> {{RangeTombstoneList.copy()}} unconditionally {{Arrays.copyOf}}s all four parallel arrays ({{starts}}, {{ends}}, {{markedAts}}, {{delTimesUnsignedIntegers}}) regardless of insert position. N successive range-tombstone merges into one unflushed partition therefore pay 1+2+...+N = *O(N^2^)* array copying and discarded allocation on the mutation write path. This bites under range-DELETE-heavy or superseding-partition-delete traffic concentrated on a single partition between flushes.
h3. Fix
Make {{copy()}} copy-on-write: the copy shares the four backing arrays with the original and both are marked {{shared}}; every in-place mutation ({{add}}, {{addAll}}, {{updateAllTimestamp}}, {{updateAllTimestampAndLocalDeletionTime}}, {{insertFrom}}) calls {{isolate()}} to reallocate the arrays before its first write. Amortized *O(N^2^) -> O(N)*.
h3. Measured impact
JMH {{AverageTime}}, co-measured baseline vs patched on the same benchmarks:
||Benchmark||Baseline||Patched||Reduction||
|RangeTombstoneListBench.benchCopyOnly (size=1000)|~2935 ns/op|~7.8 ns/op|~99.7% (O(1) vs O(N))|
|RangeTombstoneListBench.benchCopyOnly (size=10)|~48 ns/op|~7.6 ns/op|~84%|
|RangeTombstoneListBench.benchCopyAndAdd (guardrails)| | |~33-38% faster|
|allocation, N=4096|421,953,645 B/op|2,475,362 B/op|-99.4%|
The growth curve confirms O(N^2^) -> O(N).
h3. Correctness
* Full {{RangeTombstoneListTest}} passes, including a new {{testCopyIndependence}} that asserts isolation across every mutating pathway (mutations to either the original or the copy never corrupt the other's shared arrays).
* A differential stress harness -- the candidate vs a true deep-copy reference run against identical randomized {{add}}/{{copy}}/{{addAll}}/{{updateAll}} op sequences over deeply-shared lists -- ran ~300k ops with zero divergence.
* Concurrency is unchanged: {{BTreePartitionUpdater.merge}} mutates a thread-local copy (isolate-on-write), while the live shared list is only read before a new holder is CAS-published.
h3. Code
Reference implementation and benchmarks on a {{trunk}} snapshot (public fork):
* Diff (baseline -> patched): [compare 061749b0...20c86e5a|https://github.com/perfloop/cassandra/compare/061749b0ae48d5b3be1f78754f177bdd745c7a1e...20c86e5aa9990c43bce7f38fa889f1178b26f220]
* Candidate commit: [20c86e5a|https://github.com/perfloop/cassandra/commit/20c86e5aa9990c43bce7f38fa889f1178b26f220]
A pull request against {{trunk}} -- the clean {{RangeTombstoneList.java}} + {{RangeTombstoneListTest}} change (minus the microbenchmark scaffolding), with a {{CHANGES.txt}} entry -- will follow.
> Make RangeTombstoneList.copy() copy-on-write to avoid O(N²) array copying on range-tombstone memtable merges
> ------------------------------------------------------------------------------------------------------------
>
> Key: CASSANDRA-21492
> URL: https://issues.apache.org/jira/browse/CASSANDRA-21492
> Project: Apache Cassandra
> Issue Type: Improvement
> Reporter: Perfloop Agent
> Priority: Normal
>
> h3. Problem
> On every memtable write carrying a range tombstone, {{BTreePartitionUpdater.merge}} -> {{DeletionInfo.mutableCopy()}} -> {{RangeTombstoneList.copy()}} unconditionally {{Arrays.copyOf}}s all four parallel arrays ({{starts}}, {{ends}}, {{markedAts}}, {{delTimesUnsignedIntegers}}) regardless of insert position. N successive range-tombstone merges into one unflushed partition therefore pay 1+2+...+N = *O(N^2^)* array copying and discarded allocation on the mutation write path. This bites under range-DELETE-heavy or superseding-partition-delete traffic concentrated on a single partition between flushes.
> h3. Fix
> Make {{copy()}} copy-on-write: the copy shares the four backing arrays with the original and both are marked {{shared}}; every in-place mutation ({{add}}, {{addAll}}, {{updateAllTimestamp}}, {{updateAllTimestampAndLocalDeletionTime}}, {{insertFrom}}) calls {{isolate()}} to reallocate the arrays before its first write. Amortized *O(N^2^) -> O(N)*.
> h3. Measured impact
> JMH {{AverageTime}}, co-measured baseline vs patched on the same benchmarks:
> ||Benchmark||Baseline||Patched||Reduction||
> |RangeTombstoneListBench.benchCopyOnly (size=1000)|~2935 ns/op|~7.8 ns/op|~99.7% (O(1) vs O(N))|
> |RangeTombstoneListBench.benchCopyOnly (size=10)|~48 ns/op|~7.6 ns/op|~84%|
> |RangeTombstoneListBench.benchCopyAndAdd (guardrails)| | |~33-38% faster|
> |allocation, N=4096|421,953,645 B/op|2,475,362 B/op|-99.4%|
> The growth curve confirms O(N^2^) -> O(N).
> h3. Correctness
> * Full {{RangeTombstoneListTest}} passes, including a new {{testCopyIndependence}} that asserts isolation across every mutating pathway (mutations to either the original or the copy never corrupt the other's shared arrays).
> * A differential stress harness -- the candidate vs a true deep-copy reference run against identical randomized {{add}}/{{copy}}/{{addAll}}/{{updateAll}} op sequences over deeply-shared lists -- ran ~300k ops with zero divergence.
> * Concurrency is unchanged: {{BTreePartitionUpdater.merge}} mutates a thread-local copy (isolate-on-write), while the live shared list is only read before a new holder is CAS-published.
> h3. Code
> Reference implementation + benchmarks on a {{trunk}} snapshot (public fork). The full patch is the *diff below* -- not any single commit (the branch tip is only a microbenchmark add):
> * Full patch (baseline..patched, RangeTombstoneList.java + the copy-independence test + the JMH microbenchmarks): [compare 061749b0...20c86e5a|https://github.com/perfloop/cassandra/compare/061749b0ae48d5b3be1f78754f177bdd745c7a1e...20c86e5aa9990c43bce7f38fa889f1178b26f220]
> A pull request against {{trunk}} -- the clean {{RangeTombstoneList.java}} + {{RangeTombstoneListTest}} change (minus the microbenchmark scaffolding), with a {{CHANGES.txt}} entry -- will follow.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@cassandra.apache.org
For additional commands, e-mail: commits-help@cassandra.apache.org