Redis: HyperLogLog の実装について その1
だいぶ古い話だが、Redis 2.8.9 で新しいデータ構造 HyperLogLog が登場した。
その実装コードを読む。
（そして、モック作り に活かしたい）
2種類のデータ構造
Redis では、dense(密) と sparse(疎) の 2種類のデータ構造をシームレスに切り替えることで、最小限に近い空間計算量での高精度カーディナリティ推定を可能としている。
また、これらはいずれも STRING 型とよく似たデータ構造 (つまりバイト配列) をなしており、get コマンドを利用することでその実体を窺い知ることができる。
ヘッダの読み方
まずは実際に動かしてみる。
127.0.0.1:6379> get hll (nil) 127.0.0.1:6379> pfadd hll A B C (integer) 1 127.0.0.1:6379> pfcount hll (integer) 3 127.0.0.1:6379> strlen hll (integer) 27 127.0.0.1:6379> get hll "HYLL\x01\x00\x00\x00\x03\x00\x00\x00\x00\x00\x00\x00Q|\x88^\xc1\x80Bb\x88MZ"
get で表示されたデータの先頭 16 bytes がヘッダとして定義されているもの。
struct hllhdr {
char magic[4]; /* "HYLL" */
uint8_t encoding; /* HLL_DENSE or HLL_SPARSE. */
uint8_t notused[3]; /* Reserved for future use, must be zero. */
uint8_t card[8]; /* Cached cardinality, little endian. */
uint8_t registers[]; /* Data bytes. */
};- magic: 最初の4文字は、データが HyperLogLog であることを示す固定値「HYLL」が入る。
- encoding: 次の1バイトは、データ構造を示すフラグ。
上記のように「\x01」であれば sparse(疎)、「\0x00」なら dense(密) を表す。 - notused: 将来のために確保されている、未使用の領域が3バイトほど続く。
- card: カーディナリティの値が64bitぶん、リトルエンディアンで保存されている。
今回の場合は「0x03」「0x00」「0x00」「0x00」「0x00」「0x00」「0x00」「0x00」なので、
カーディナリティ 3 を表す。
そして、registers の部分が HyperLogLog のデータそのもの。
今回の例では、「Q|\x88^\xc1\x80Bb\x88MZ」の部分 (11 bytes) がそれに該当する。
16進数表記をすれば、順に
「51, 7c, 88, 5e, c1, 80, 42, 62, 88, 4d, 5a」
である。
0 件のコメント:
コメントを投稿