Alan Wang created CASSANDRA-21841:
-------------------------------------
Summary: 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
Reporter: Alan Wang
Assignee: Alan Wang
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]
