[
https://issues.apache.org/jira/browse/CASSANDRA-20333?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=18116779#comment-18116779
]
Dmitry Konstantinov commented on CASSANDRA-20333:
-------------------------------------------------
Hi, I have prepared a patch with a performance improvement for
DecayingEstimatedHistogramReservoir:
https://github.com/apache/cassandra/pull/5185
It is based on [~benedict]'s idea + include a set of other optimizations.
The main idea: we accumulate reservoir updates in a thread-local buffer (using
CassandraThread). The updates can be encoded into int values (reservoir id,
bucket id, temestamp delta). So, we have have just an int[] buffer. The buffer
is common for all reservoirs. It has a single writer and multiple readers.
During a flush of this buffer we count identical values using a simple
open-addressing hashtable, it allows to reduce number of atomic updates per
bucket. Taking in account that in reality we have a lot of mostly constant
value histograms (like written rows count) and durations usually have
multi-modal distribution then saving from such aggregation can be huge.
Also we want to group buckets for the same reservoir together, to re-use
calculated exponential decay factors + for better memory locality.
The original way to do it was sorting but I found it not fast enough, so I
introduced a logic to do it using another open-addressing hashtable for
reservoir id, so we can count how many entries per reservoir we have, identify
require ranges per reservoir and do a compaction which puts all of entries
together using few additional data structures. All flushing data structures are
re-used, so there is no allocation there.
For metric read operations a time limiter is added for buffer flushing, to
reduce threads iteration overhead here.
Additionally:
- findIndex logic is optimized a bit by avoiding float computation for log2
calculation using short[] lookup table.
- AtomicLongArray offset is added for 1st value to avoid false sharing with
array object header for length read
- clock.nowInSec is introduced for approximated clocks to avoid a frequent unit
conversion (division)
In total such change give the following performance results:
1) microbenhmark, DecayingEstimatedHistogramBench.update — Mode.Throughput,
ops/ms, 12 threads, 16-cores server: Intel Xeon 6975P-C (Granite Rapids)
{code:java}
┌────────────┬──────────┬──────────┬───────────┬──────────┐
│ histograms │ maxValue │ before │ after │ speed-up │
├────────────┼──────────┼──────────┼───────────┼──────────┤
│ (count) │ (value) │ (ops/ms) │ (ops/ms) │ (×) │
├────────────┼──────────┼──────────┼───────────┼──────────┤
│ 1 │ 10 │ 47,151 │ 1,136,306 │ 24.10× │
├────────────┼──────────┼──────────┼───────────┼──────────┤
│ 1 │ 500 │ 75,396 │ 995,328 │ 13.20× │
├────────────┼──────────┼──────────┼───────────┼──────────┤
│ 1 │ 100,000 │ 81,608 │ 1,084,287 │ 13.29× │
├────────────┼──────────┼──────────┼───────────┼──────────┤
│ 16 │ 10 │ 124,317 │ 641,430 │ 5.16× │
├────────────┼──────────┼──────────┼───────────┼──────────┤
│ 16 │ 500 │ 124,746 │ 507,754 │ 4.07× │
├────────────┼──────────┼──────────┼───────────┼──────────┤
│ 16 │ 100,000 │ 134,469 │ 484,406 │ 3.60× │
└────────────┴──────────┴──────────┴───────────┴──────────┘{code}
2) e2e test, write single row (easy-stress keyvalue write-only workload)
CPU is spent in Reservoir logic according to async-profiler cpu flamegraph:
before : 8.05% [^histogram_buffer_final_before_cpu.html]
after : 1.85% [^histogram_buffer_final_after_cpu.html]
> Reduce DecayingEstimatedHistogramReservoir update cost
> ------------------------------------------------------
>
> Key: CASSANDRA-20333
> URL: https://issues.apache.org/jira/browse/CASSANDRA-20333
> Project: Apache Cassandra
> Issue Type: Improvement
> Components: Observability/Metrics
> Reporter: Dmitry Konstantinov
> Assignee: Maxim Muzafarov
> Priority: High
> Fix For: 7.x
>
> Attachments: Cumulative Occurrences - MutationStage.png, Cumulative
> Occurrences - ReadStage.png, Cumulative occurrences -
> Native-Transport-Requests.png,
> Flamegraph-getBucketsThreadLocal-Contirbution.png,
> Perf-Conribution-Histogram-Update.png,
> flame-jmh-20333-optlock-210425-nowl-1-volatile.html,
> flamegraph-20333-optlock-210425-warmed-nowl-1-volatile.html,
> flamegraph-trunk-final-warmed.html, histogram_buffer_final_after_cpu.html,
> histogram_buffer_final_before_cpu.html
>
> Time Spent: 1h 10m
> Remaining Estimate: 0h
>
> Based on the discussions in CASSANDRA-20250
> [~benedict]:
> {quote}We can probably improve our reservoir performance if we want to,
> perhaps in a follow-up patch? For instance, we could have a small
> thread-local buffer of (time, latency) pairs that we periodically flush
> together, so that we amortise the memory latency costs. Or we could explore
> maintaining a per-thread HdrHistogram, that we periodically flush. This would
> be a good time to explore fully migrating to HdrHistogram, as it has built-in
> merge semantics iirc. I am not sure what the decayed version would look like
> there, but I am certain we could maintain a separate decayed HdrHistogram.
> Having a thread-local buffer of updates we intend to flush to the histograms
> would amortise the latency penalties without fundamentally redesigning
> anything (as well as reducing contention).
> Other possibilities might include e.g. changing the bucket distribution so we
> don't need a LUT for computing lg2, although the above would gracefully
> handle any contribution this has as well.
> {quote}
>
> Other ideas about squeezing extra bits from the current design:
> * bucket id can be calculated once (currently we do it 2 times for decaying
> and current buckets), like:
> {code:java}
> int stripe = (int) (Thread.currentThread().getId() & (nStripes - 1));
> int bucket = stripedIndex(index, stripe);
> rescaledDecayingBuckets.update(bucket, now);
> updateBucket(buckets, bucket, 1); {code}
> * for histograms on highly loaded paths we can use another number of stripes
> (by default it is 2, we can set for example 4 for them)
> * I noticed some variation in performance for a micro-benchmark (existing
> one: DecayingEstimatedHistogramBench) depending on what exact value for
> distributionPrime is used (but I need to double check it)
> * forwardDecayWeight function depends on SampledClock value, so we can try
> to recalculate the weight only when time is changed
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
