[
https://issues.apache.org/jira/browse/CASSANDRA-21492?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Alex Petrov reassigned CASSANDRA-21492:
---------------------------------------
Assignee: Alex Petrov
> 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
> Assignee: Alex Petrov
> Priority: Normal
> Time Spent: 10m
> Remaining Estimate: 0h
>
> 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: [email protected]
For additional commands, e-mail: [email protected]
