[
https://issues.apache.org/jira/browse/CASSANDRA-21841?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Alan Wang updated CASSANDRA-21841:
----------------------------------
Test and Documentation Plan: tests
Status: Patch Available (was: Open)
> HyperLogLog library can over estimate the number of keys
> ---------------------------------------------------------
>
> Key: CASSANDRA-21841
> URL: https://issues.apache.org/jira/browse/CASSANDRA-21841
> Project: Apache Cassandra
> Issue Type: Bug
> Components: Local/SSTable
> Reporter: Alan Wang
> Assignee: Alan Wang
> Priority: Normal
> Time Spent: 10m
> Remaining Estimate: 0h
>
> The version that we are using for com.clearspring.analytics.stream is 2.5.2.
> The library has two formats for HyperLogLog a sparse format, used for cases
> when the number of partitions is below a certain partition count, and a
> normal format for when there are more partitions. For the version that we are
> using, there is a bug that can cause over estimation of the number of unique
> elements when merging the sparse format. A contrived worst case test shows a
> 42x over estimation of the number of partition keys. The effects of this
> today are EstimatedPartitionCount for metrics can be inaccurate and the HLL
> is also used to determine bloom filter sizing which means bloom filters can
> over allocate the amount of bits by a small amount.
> The issue has been fixed in version 2.6.0 which includes the commits below.
> However, some of the HLL's that we have serialized to disk are out of order.
> This means that bumping the library version still won't produce the correct
> results. The proposed fix is to perform the merge by converting the sparse
> format into the normal format and performing the merge by going through the
> normal format's merge code which does this correctly.
> [https://github.com/addthis/stream-lib/pull/54]
> [https://github.com/addthis/stream-lib/commit/207acdc204f6206af744eec9f284798693e53e4c]
> [https://github.com/addthis/stream-lib/commit/65237f8b619e4051a6384dda1357d8466fa0c890]
>
--
This message was sent by Atlassian Jira
(v10.3.26#10030026)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
