[
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: [email protected]
For additional commands, e-mail: [email protected]
