You are viewing a plain text version of this content. The canonical link for it is here.

Posted to commits@druid.apache.org by GitBox <gi...@apache.org> on 2021/11/10 22:37:02 UTC

[GitHub] [druid] wjhypo opened a new pull request #11307: [WIP] Add an option to enable bitmap in IncrementalIndex during real time ingestion

wjhypo opened a new pull request #11307:
URL: https://github.com/apache/druid/pull/11307

Fixes #11301

### Description

- Choice of algorithms

If `enableInMemoryBitmap` is set to true in `tuningConfig` in the supervisor spec, a bitmap is maintained during the data is in incremental index for each dimension that uses bitmap in the schema, i.e., for a dimension, only if bitmap is to be created when creating the immutable segment during handoff, will a corresponding temporary in memory bitmap be created.

This in-memory bitmap is not serialized or reused during persistence to completely separate from the other bitmap created in the immutable segment for clean logic separation.

In terms of the implementation of this in-memory bitmap, currently user can't specify it anywhere and only Roaring bitmap is used as the default implementation. The PR doesn't add choices to pick other compressed bitmaps like Concise Bitmap because we don't see clear performance benefits to add other implementations at the moment.

In terms of the implementation of Roaring bitmap, there are 3 implementations available in the Roaring bitmap library: `MutableRoaringBitmap`, `ImmutableRoaringBitmap` and `RoaringBitmap`. `RoaringBitmap` is supposed to be more performant than the other two in this case because it doesn't need to maintain a byte buffer backend and byte buffer backend is only convenient if we need to do Mmap or if there's serde involved, which is the case for batch ingested immutable segments querying. However, the implementation in the PR tries reusing the logic in the current Java classes built for the batch ingested immutable segments, so the byte buffer backed implementation `MutableRoaringBitmap` is used to store row indexes for each new rows. During query time, a snapshot of the bitmap is needed so `MutableRoaringBitmap` is cast to `ImmutableRoaringBitmap`, which involves copying at one of the stages of the conversion. During the copy, for high cardinality dimensions, the number of row indexe
s for a given row value should be small so the copying overhead should be minimal; for low cardinality dimensions, supposedly there are more data to copy than the previous case, though we don't see obvious issue during testing and we can add metrics on the copying time and as long as the benefit outweigh the no bitmap full scan case, it should still be worthwhile.

- Behavioral aspects. What configuration values are acceptable? How are corner cases and error conditions handled, such as when there are insufficient resources?

Enable in memory bitmap construction in supervisor spec
```
{
"type": "kafka",
"tuningConfig": {
...
"enableInMemoryBitmap": true
...
}
}
```

- Class organization and design (how the logic is split between classes, inheritance, composition, design patterns)

The implementation tries piggybacking on the bitmap query related classes of batch generated immutable segment index (QueryableIndex and its support classes) as much as possible to reduce duplicate work.

### Benchmark

#### Production Cluster Benchmark

<img width="631" alt="Screen Shot 2021-08-24 at 5 10 07 PM" src="https://user-images.githubusercontent.com/8614743/130705911-fb6d749b-07f2-400b-ac5d-419209f164c4.png">
Figure 1: Production cluster use case 1 P99 latency reduction on Middle Managers. The diagram shows Middle Manager P99 latency reduction (more than 30x) with the same middle manager capacity before and after enabling in memory bitmap for use case 1.

<img width="446" alt="Screen Shot 2021-08-24 at 5 17 41 PM" src="https://user-images.githubusercontent.com/8614743/130706345-faaf17d6-4fa8-42c9-8941-40f05e96ef5a.png">
Figure 2: Production cluster use case 1 QPS on Middle Managers. The diagram shows the corresponding increase of QPS throughput before and after enabling in-memory bitmap for use case 1 in Figure 1.

<img width="642" alt="Screen Shot 2021-08-24 at 5 12 10 PM" src="https://user-images.githubusercontent.com/8614743/130705930-6a133036-ccc6-45fa-8d4b-db2d9e06846f.png">
Figure 3: Production cluster use case 2 P90 latency (ms) and infrastructure cost reduction on Middle Managers. The diagram shows a 10x reduction in Middle Manager P90 latency before and after enabling in-memory bitmap for use case 2. The diagram also shows a follow-up 68.89% host capacity reduction without impacting latency (the green to red line switch).

#### Unit Test Benchmark

Additional unit test benchmark result is also included in the comments of this PR: https://github.com/apache/druid/pull/11307#issuecomment-859209115

### Correctness Validation
We added a query context flag that controls the broker to only return results from middle manager hosts (not included in the PR). We added a temporary query time flag `useInMemoryBitmapInQuery` that can control whether to use the in-memory bitmap index during query time even though the in-memory bitmap index is already created during ingestion (this flag is removed in the PR created because it doesn't serve any purpose other than validation during development). We stopped the Kafka producer temporarily and left some records in memory in the incremental index (~852,000 records, when reaching 1M, persistence will trigger) before persistence triggered to verify that the results are the same when `useInMemoryBitmapInQuery` is set to true or false.

<img width="371" alt="Screen Shot 2021-08-24 at 5 29 39 PM" src="https://user-images.githubusercontent.com/8614743/130707097-084c4dbf-775c-490f-9e3e-a8bb7b91424a.png">
Figure 4: Number of events ingested on Middle Managers for verification data source. The diagram shows the number of events ingested dropped to 0 and remained 0 as we stopped the Kafka producer.

<img width="356" alt="Screen Shot 2021-08-24 at 5 29 28 PM" src="https://user-images.githubusercontent.com/8614743/130707099-77a83632-568e-48aa-b1f2-c3e296f23ae3.png">
Figure 5: Number of events in incremental index on Middle Managers for verification data source. The diagram shows the number of events in incremental index remained a little over 800k and temporarily not qualified for persistence threshold as we stopped the Kafka producer.

We ran the follow queries (some sensitive business related column name and filter value in the queries before are replaced with dummy value but they were issued with real value during the verification).

```
Query 1: aggregate sanity check. This query doesn't use in-memory bitmap in reality because no filter is there.
SELECT __time, SUM(spend)/1000000.00 as spend,
sum(paid_events) as paid_events,
sum(cnt) as cnt,
sum(cnt_gross) as cnt_gross
FROM verification_data_source
WHERE __time >= timestamp'2021-07-20 20:00:00'
GROUP BY __time
ORDER BY __time

Query 2: filter with random value. Column `advertiserid` has in-memory bitmap index created.
SELECT __time, SUM(spend)/1000000.00 as spend, sum(paid_events) as paid_events, sum(cnt) as cnt, sum(cnt_gross) as cnt_gross FROM verification_data_source WHERE advertiserid = '123' and __time >= timestamp'2021-07-20 20:00:00' group by __time

Query 3: filter on one of top 10 large advertisers. Column `advertiserid` and column `apptype` have in-memory bitmap index created.
SELECT __time, SUM(spend)/1000000.00 as spend, sum(paid_events) as paid_events, sum(cnt) as cnt, sum(cnt_gross) as cnt_gross FROM verification_data_source WHERE advertiserid = '123' and apptype = 3 and __time >= timestamp'2021-07-20 20:00:00' GROUP BY __time ORDER BY __time

Query 4: filter on one of top 10 small advertiser. Column `advertiserid` and column `apptype` have in-memory bitmap index created.
SELECT __time, SUM(spend)/1000000.00 as spend, sum(paid_events) as paid_events, sum(cnt) as cnt, sum(cnt_gross) as cnt_gross FROM verification_data_source WHERE advertiserid = '123' and __time >= timestamp'2021-07-20 20:00:00' GROUP BY __time ORDER BY __time
```
We verified that non empty results are return and they are the same whether `useInMemoryBitmapInQuery` is set to true or false for all the above queries.

<!-- Some of the aspects mentioned above may be omitted for simple and small changes.

<hr>

##### Key changed/added classes in this PR
* `MyFoo`
* `OurBar`
* `TheirBaz`

<hr>

-->

This PR has:
- [x] been self-reviewed.
- [ ] 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.)
- [ ] added documentation for new or modified features or behaviors.
- [ ] added Javadocs for most classes and all non-trivial methods. Linked related entities via Javadoc links.
- [ ] added comments explaining the "why" and the intent of the code wherever would not be obvious for an unfamiliar reader.
- [x] added unit tests or modified existing tests to cover new code paths, ensuring the threshold for [code coverage](https://github.com/apache/druid/blob/master/dev/code-review/code-coverage.md) is met.
- [ ] added integration tests.
- [x] been tested in a test Druid cluster.

--
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