Perfloop Agent created CASSANDRA-21492:
------------------------------------------
Summary: 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
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.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
