You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@druid.apache.org by "jasonk000 (via GitHub)" <gi...@apache.org> on 2023/01/25 23:47:03 UTC
[GitHub] [druid] jasonk000 opened a new pull request, #13710: Dimension dictionary perf
jasonk000 opened a new pull request, #13710:
URL: https://github.com/apache/druid/pull/13710
### Description
Following from https://github.com/apache/druid/pull/12105 with 1-20% CPU in `DimensionDictionary`, there are some improvements to be made to the `add()` path on the `StringDimensionIndexer`. The main concern is that the locking is more complicated than necessary.
There are three sub-changes:
- Introduce a benchmark
- Swap the existing lock implementation to use a `synchronized` block
- Reduce the number of times we have to cross the lock.
Estimate this code reduces CPU by ~5-7% on our indexing jobs overall, with ~30% improvements to the uncontended path.
### Alternative solutions / future work
It seems like this code is mostly used only one-at-a-time, so an alternative path that changes the DimensionDictionary would be to move responsibility for synchronization _outside_ of the dictionary and make the caller responsible for synchronization. This is likely to see a good boost to the later compareUnsorted stage but might constrain future work. Specifically it would prevent concurrent use of the dictionary from multiple threads during ingestion.
### Related
#12105, #12109,
##### Key changed/added classes in this PR
* Introduce benchmark `StringDimensionIndexerProcessBenchmark`
* `DimensionDictionary` locking changes
* `StringDimensionIndexer` simplification of call
<hr>
This PR has:
- [x] been self-reviewed.
- [x] using the [concurrency checklist](https://github.com/apache/druid/blob/master/dev/code-review/concurrency.md) (Remove this item if the PR doesn't have any relation to concurrency.)
- [x] been tested in a test Druid cluster. -- a solution more like 12105 on top of 0.20 is currently running in Production for many months.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] jasonk000 commented on pull request #13710: Dimension dictionary reduce locking
Posted by "jasonk000 (via GitHub)" <gi...@apache.org>.
jasonk000 commented on PR #13710:
URL: https://github.com/apache/druid/pull/13710#issuecomment-1407450510
@clintropolis , thx for comments. I think it's ready to take a look at.
I've included benchmark results [for each commit](https://github.com/apache/druid/pull/13710/commits), and shown the progress. Each commit is broken to a small change so if we would prefer distinct PRs we can do that too.
> it would probably be worth checking that query performance for realtime tasks is not negatively impacted too much by this change (especially from multiple concurrent threads). There is only one writer thread but potentially many reader threads, as new dimension selectors are created on top of this dictionary during realtime queries.
I've added test explicitly for the contended situation and brought in StampedLock which has much better performance with mixed read workloads.
It looks to me like most of the time it is one-thread-writing with possibly many readers, so I think this is a good blend. We could build a more advanced ArrayList structure that would be lockfree since this is append-only, but i'm not sure it's warranted. Let me know your thoughts.
> For batch ingestion tasks, it might be worth using a separate `DimensionDictionary` implementation that has no locks. I use a similar thing for the `NestedDataColumnIndexer`,
I included a benchmark for single-writer only and it shows up with similar performance to the contended writer situation.
Overall, for JDK11,
BEFORE
```
jdk11 -- Benchmark Mode Cnt Score Error Units
StringDimensionIndexerProcessBenchmark.parallelReadWrite avgt 10 18769.135 ± 705.057 us/op
StringDimensionIndexerProcessBenchmark.parallelReadWrite:parallelReader avgt 10 23772.439 ± 947.011 us/op
StringDimensionIndexerProcessBenchmark.parallelReadWrite:parallelWriter avgt 10 3759.221 ± 59.897 us/op
StringDimensionIndexerProcessBenchmark.soloReader avgt 10 666.688 ± 12.723 us/op
StringDimensionIndexerProcessBenchmark.soloWriter avgt 10 3013.473 ± 13.480 us/op
```
AFTER
```
jdk11 - Benchmark Mode Cnt Score Error Units
StringDimensionIndexerProcessBenchmark.parallelReadWrite avgt 10 873.654 ± 12.358 us/op
StringDimensionIndexerProcessBenchmark.parallelReadWrite:parallelReader avgt 10 283.315 ± 0.067 us/op
StringDimensionIndexerProcessBenchmark.parallelReadWrite:parallelWriter avgt 10 2644.672 ± 49.549 us/op
StringDimensionIndexerProcessBenchmark.soloReader avgt 10 284.451 ± 0.588 us/op
StringDimensionIndexerProcessBenchmark.soloWriter avgt 10 2284.851 ± 51.339 us/op
```
Overall, both the contended and solo read/write is all improved.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] github-code-scanning[bot] commented on a diff in pull request #13710: Dimension dictionary reduce locking
Posted by github-code-scanning.
github-code-scanning[bot] commented on code in PR #13710:
URL: https://github.com/apache/druid/pull/13710#discussion_r1089483988
##########
benchmarks/src/test/java/org/apache/druid/benchmark/indexing/StringDimensionIndexerProcessBenchmark.java:
##########
@@ -0,0 +1,169 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.benchmark.indexing;
+
+import org.apache.druid.common.config.NullHandling;
+import org.apache.druid.data.input.impl.DimensionSchema;
+import org.apache.druid.segment.StringDimensionIndexer;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Group;
+import org.openjdk.jmh.annotations.GroupThreads;
+import org.openjdk.jmh.annotations.Level;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.Warmup;
+import org.openjdk.jmh.infra.Blackhole;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.concurrent.ThreadLocalRandom;
+import java.util.concurrent.TimeUnit;
+
+@State(Scope.Benchmark)
+@Fork(value = 1)
+@Warmup(iterations = 10)
+@Measurement(iterations = 10)
+public class StringDimensionIndexerProcessBenchmark
+{
+ static {
+ NullHandling.initializeForTests();
+ }
+
+ String[] inputData;
+ StringDimensionIndexer emptyIndexer;
+ StringDimensionIndexer fullIndexer;
+ int[] readOrder;
+
+ @Setup(Level.Trial)
+ public void setup()
+ {
+ // maxNumbers : inputData ratio of 1000:50000 is 1:50, in other words we should expect each element to be 'added'
+ // 50x, the first time it is new, the next 49 times it is an existing entry; also 5% of values will be false
+
+ final int maxNumbers = 1000;
+ final int nullNumbers = 50; // 5%
+ final int validNumbers = (maxNumbers + 1) - nullNumbers;
+
+ // set up dummy input data, and load to indexer
+ inputData = new String[50000];
+ for (int i = 0; i < inputData.length; i++) {
+ int next = ThreadLocalRandom.current().nextInt(maxNumbers);
+ inputData[i] = (next < nullNumbers) ? null : ("abcd-" + next + "-efgh");
+ }
+
+ fullIndexer = new StringDimensionIndexer(DimensionSchema.MultiValueHandling.ofDefault(), true, false, false);
+ for (String data : inputData) {
+ fullIndexer.processRowValsToUnsortedEncodedKeyComponent(data, true);
+ }
+
+ // set up a random read order
+ readOrder = new int[inputData.length];
+ for (int i = 0; i < readOrder.length; i++) {
+ readOrder[i] = ThreadLocalRandom.current().nextInt(validNumbers);
+ }
+ }
+ @Setup(Level.Iteration)
+ public void setupEmptyIndexer()
+ {
+ emptyIndexer = new StringDimensionIndexer(DimensionSchema.MultiValueHandling.ofDefault(), true, false, false);
+ }
+
+ @Setup(Level.Iteration)
+ public void shuffleReadOrder()
+ {
+ ArrayList<Integer> asList = new ArrayList<>(readOrder.length);
+ for (int i : readOrder) {
+ asList.add(i);
+ }
+
+ Collections.shuffle(asList);
+
+ for (int i = 0; i < readOrder.length; i++) {
+ readOrder[i] = asList.get(i);
+ }
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.AverageTime)
+ @OutputTimeUnit(TimeUnit.MICROSECONDS)
+ public void soloWriter()
+ {
+ // load ALL input data to an empty index; duplicates will be present / should be ignored
+ for (String data : inputData) {
+ emptyIndexer.processRowValsToUnsortedEncodedKeyComponent(data, true);
+ }
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.AverageTime)
+ @OutputTimeUnit(TimeUnit.MICROSECONDS)
+ @Group("soloReader")
+ public void soloReader(Blackhole blackhole)
+ {
+ // read ALL elements from a fully loaded index
+ for (int i : readOrder) {
+ Object result = fullIndexer.convertUnsortedEncodedKeyComponentToActualList(new int[]{i});
+ blackhole.consume(result);
+ }
+ }
+
+ // parallel read/write test should simulate what happens when we are (1) ingesting data (aka writing to dictionary)
+ // and also (2) running query (aka reading from dictionary)
+ // the read side should continuously read
+ // the write side should continuously write; but we also need to throw in some random writes too
+ // since our dataset will fill the 'new write' path quickly, so 1-in-50 elements should be new
+
+ @Benchmark
+ @BenchmarkMode(Mode.AverageTime)
+ @OutputTimeUnit(TimeUnit.MICROSECONDS)
+ @Group("parallelReadWrite")
+ public void parallelWriter(Blackhole blackhole)
Review Comment:
## Useless parameter
The parameter 'blackhole' is never used.
[Show more details](https://github.com/apache/druid/security/code-scanning/4203)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] clintropolis merged pull request #13710: Dimension dictionary reduce locking
Posted by "clintropolis (via GitHub)" <gi...@apache.org>.
clintropolis merged PR #13710:
URL: https://github.com/apache/druid/pull/13710
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] github-code-scanning[bot] commented on a diff in pull request #13710: Dimension dictionary reduce locking
Posted by github-code-scanning.
github-code-scanning[bot] commented on code in PR #13710:
URL: https://github.com/apache/druid/pull/13710#discussion_r1087329725
##########
benchmarks/src/test/java/org/apache/druid/benchmark/indexing/StringDimensionIndexerProcessBenchmark.java:
##########
@@ -0,0 +1,76 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.benchmark.indexing;
+
+import org.apache.druid.common.config.NullHandling;
+import org.apache.druid.data.input.impl.DimensionSchema;
+import org.apache.druid.segment.StringDimensionIndexer;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.Threads;
+import org.openjdk.jmh.annotations.Warmup;
+import org.openjdk.jmh.infra.Blackhole;
+
+import java.util.concurrent.ThreadLocalRandom;
+import java.util.concurrent.TimeUnit;
+
+@State(Scope.Benchmark)
+@Fork(value = 1)
+@Warmup(iterations = 10)
+@Measurement(iterations = 10)
+public class StringDimensionIndexerProcessBenchmark
+{
+ static {
+ NullHandling.initializeForTests();
+ }
+
+ String[] inputData;
+ StringDimensionIndexer indexer;
+
+ @Setup()
+ public void setup()
+ {
+ inputData = new String[5000];
+ for (int i = 0; i < inputData.length; i++) {
+ int next = ThreadLocalRandom.current().nextInt(100);
+ inputData[i] = (next < 10) ? null : ("abcd-" + next);
+ }
+
+ indexer = new StringDimensionIndexer(DimensionSchema.MultiValueHandling.ofDefault(), true, false, false);
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.AverageTime)
+ @OutputTimeUnit(TimeUnit.MICROSECONDS)
+ @Threads(1)
+ public void singleThread(Blackhole blackhole)
Review Comment:
## Useless parameter
The parameter 'blackhole' is never used.
[Show more details](https://github.com/apache/druid/security/code-scanning/4200)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] clintropolis commented on pull request #13710: Dimension dictionary reduce locking
Posted by "clintropolis (via GitHub)" <gi...@apache.org>.
clintropolis commented on PR #13710:
URL: https://github.com/apache/druid/pull/13710#issuecomment-1404750983
it would probably be worth checking that query performance for realtime tasks is not negatively impacted too much by this change (especially from multiple concurrent threads). There is only one writer thread but potentially many reader threads, as new dimension selectors are created on top of this dictionary during realtime queries.
For batch ingestion tasks, it might be worth using a separate `DimensionDictionary` implementation that has no locks. I use a similar thing for the `NestedDataColumnIndexer`, `ComparatorDimensionDictionary`, which is basically a copy of `DimensionDictionary` except uses a `Comparator` instead of requiring a `Comparable`, and doesn't have any locks since the nested column indexer doesn't currently use the dictionary it is building for realtime queries.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] jasonk000 commented on pull request #13710: Dimension dictionary reduce locking
Posted by "jasonk000 (via GitHub)" <gi...@apache.org>.
jasonk000 commented on PR #13710:
URL: https://github.com/apache/druid/pull/13710#issuecomment-1404370793
@kfaraz I started a conversation on slack; I think this is in a similar area you've been working recently. CC @maytasm
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] jasonk000 commented on pull request #13710: Dimension dictionary reduce locking
Posted by "jasonk000 (via GitHub)" <gi...@apache.org>.
jasonk000 commented on PR #13710:
URL: https://github.com/apache/druid/pull/13710#issuecomment-1407511725
Made a typo in the old test cases, so I've rebased the lot and reprocessed the tests, which confirmed another opt I had in mind. Updated results:
```
BEFORE
jdk11 -- Benchmark Mode Cnt Score Error Units
StringDimensionIndexerProcessBenchmark.parallelReadWrite avgt 10 30471.552 ± 456.716 us/op
StringDimensionIndexerProcessBenchmark.parallelReadWrite:parallelReader avgt 10 18069.863 ± 327.923 us/op
StringDimensionIndexerProcessBenchmark.parallelReadWrite:parallelWriter avgt 10 67676.617 ± 2351.311 us/op
StringDimensionIndexerProcessBenchmark.soloReader avgt 10 1048.079 ± 1.120 us/op
StringDimensionIndexerProcessBenchmark.soloWriter avgt 10 4629.769 ± 29.353 us/op
AFTER
jdk11 - Benchmark Mode Cnt Score Error Units
StringDimensionIndexerProcessBenchmark.parallelReadWrite avgt 10 2914.859 ± 22.519 us/op
StringDimensionIndexerProcessBenchmark.parallelReadWrite:parallelReader avgt 10 508.010 ± 14.675 us/op
StringDimensionIndexerProcessBenchmark.parallelReadWrite:parallelWriter avgt 10 10135.408 ± 82.745 us/op
StringDimensionIndexerProcessBenchmark.soloReader avgt 10 205.415 ± 0.158 us/op
StringDimensionIndexerProcessBenchmark.soloWriter avgt 10 3098.743 ± 23.603 us/op
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] clintropolis commented on pull request #13710: Dimension dictionary reduce locking
Posted by "clintropolis (via GitHub)" <gi...@apache.org>.
clintropolis commented on PR #13710:
URL: https://github.com/apache/druid/pull/13710#issuecomment-1407491332
cool, thanks for checking. Btw, I actually had a bug in that lockless dictionary used by nested columns that resulted in it not fully merging dictionaries which is fixed in this PR https://github.com/apache/druid/pull/13714/files#diff-b00489e26a5bff0e308349f4bdf8dc21a55798f8d0f35c995c56599cb6485eb1R93 😅
anyway, I'll try to have a closer look at this PR sometime soon
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org