This is an automated email from the ASF dual-hosted git repository.
maplefu pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/kvrocks-website.git
The following commit(s) were added to refs/heads/main by this push:
new a212185 Update data-structure-on-rocksdb.md for Hyperloglog (#207)
a212185 is described below
commit a21218559074dda9da3ebb9faa5b2d7d59a99ba6
Author: tutububug <[email protected]>
AuthorDate: Wed Jul 31 13:35:05 2024 +0800
Update data-structure-on-rocksdb.md for Hyperloglog (#207)
* Update data-structure-on-rocksdb.md for Hyperloglog
* Update data-structure-on-rocksdb.md for hyperloglog
* HLL: update storage format
* update protocol
---------
Co-authored-by: mwish <[email protected]>
---
community/data-structure-on-rocksdb.md | 40 ++++++++++++++++++++++++++++++++++
1 file changed, 40 insertions(+)
diff --git a/community/data-structure-on-rocksdb.md
b/community/data-structure-on-rocksdb.md
index 1cf54a4..ffb446a 100644
--- a/community/data-structure-on-rocksdb.md
+++ b/community/data-structure-on-rocksdb.md
@@ -46,6 +46,7 @@ The values encoded for other data types in flags can be found
in the table below
| Stream | 8 |
| BloomFilter| 9 |
| JSON | 10 |
+| Hyperloglog| 11 |
In the encoding version `0`, `expire` is stored in seconds and as a 4byte
field (32bit integer), `size` is stored as also a 4byte field (32bit integer);
while in the encoding version `1`, `expire` is stored in milliseconds and as a
8byte field (64bit integer), `size` is stored as also a 8byte field (64bit
integer).
@@ -316,3 +317,42 @@ where the `payload` is a string encoded in the
corresponding `format`:
| CBOR | 1 |
Also, if we decide to add a more IO-friendly format to avoid reading all
payload to the memory before searching an element via JSONPath or seperate a
relatively large JSON to multiple key-values, we can take advantage of the
`format` field.
+
+## HyperLogLog
+
+Redis HyperLogLog is a probabilistic data structure that estimates the
cardinality of a set. The idea comes from [original
paper](http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf) and [paper
from
Google](http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/40671.pdf).
It is particularly useful for applications that require the estimation of
unique elements in massive datasets, such as network traffic analysis, data
warehousing, and large-scale databases.
+
+The principle behind HyperLogLog is based on the idea that the number of
leading zeros in the binary representation of a hash value can be used to infer
the size of the set. It includes:
+1. Hashing: Each element in the dataset is passed through a hash function,
which produces a fixed-size binary string.
+2. Register Array: The algorithm maintains an array of registers, each
corresponding to a subset of the hash space. The size of the array is 2^p,
where p is a precision parameter that determines the trade-off between accuracy
and memory usage. The HyperLogLog algorithm uses a subset of the hash value to
determine the index in the register array. Specifically, it takes the first p
bits of the hash value.
+
+For the remaining bits of the hash value (after the first p bits), the
algorithm counts the number of leading zeros. Each entry in the array keeps
track of the maximum observed for all elements that hash to the same index. If
the newly encountered value is greater than the current value in the register,
it updates the register with this new value.
+
+Redis HyperLogLog can be thought of as a static array with a length of 16384.
The array elements are called registers, which are used to store the maximum
count of consecutive 0s. This register array is the input parameter for the
HyperLogLog algorithm. The Redis HyperLogLog implementation uses up to 12 KB
and provides a standard error of 0.81%.
+
+In Kvrocks, the hyperloglog data structure is stored in following two parts:
+
+#### HyperLogLog metadata
+
+```text
+ +----------+------------+-----------+--------------+
+key => | flags | expire | version | HLLType |
+ | (1byte) | (Ebyte) | (8byte) | (1byte) |
+ +----------+------------+-----------+--------------+
+```
+
+HLLType = 0 means a "dense" representation with Redis-like modified
MurmurHash2 and 16384 registers with 6bit LSB numbers,
+the values is stored like Bitmap but has smaller segment(768 bytes per
segment).
+
+#### hyperloglog sub keys-values
+
+```text
+ +---------------+
+key|version|index => | fragment |
+ +---------------+
+```
+
+The register index is calculated using the first 14 bits of the user element's
hash value (64 bits), which is why the register array length is 16384.
+The length of consecutive zeros is calculated using the last 50 digits of the
hash value of the user key.
+
+Inspired by the bitmap implementation, HyperLogLog divides the register array
into 16 segments, each with 1024 registers.
