1/* hyperloglog.c - Redis HyperLogLog probabilistic cardinality approximation.
2 * This file implements the algorithm and the exported Redis commands.
3 *
4 * Copyright (c) 2014, Salvatore Sanfilippo <antirez at gmail dot com>
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are met:
9 *
10 * * Redistributions of source code must retain the above copyright notice,
11 * this list of conditions and the following disclaimer.
12 * * Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * * Neither the name of Redis nor the names of its contributors may be used
16 * to endorse or promote products derived from this software without
17 * specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
23 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 */
31
32#include "server.h"
33
34#include <stdint.h>
35#include <math.h>
36
37/* The Redis HyperLogLog implementation is based on the following ideas:
38 *
39 * * The use of a 64 bit hash function as proposed in [1], in order to estimate
40 * cardinalities larger than 10^9, at the cost of just 1 additional bit per
41 * register.
42 * * The use of 16384 6-bit registers for a great level of accuracy, using
43 * a total of 12k per key.
44 * * The use of the Redis string data type. No new type is introduced.
45 * * No attempt is made to compress the data structure as in [1]. Also the
46 * algorithm used is the original HyperLogLog Algorithm as in [2], with
47 * the only difference that a 64 bit hash function is used, so no correction
48 * is performed for values near 2^32 as in [1].
49 *
50 * [1] Heule, Nunkesser, Hall: HyperLogLog in Practice: Algorithmic
51 * Engineering of a State of The Art Cardinality Estimation Algorithm.
52 *
53 * [2] P. Flajolet, Éric Fusy, O. Gandouet, and F. Meunier. Hyperloglog: The
54 * analysis of a near-optimal cardinality estimation algorithm.
55 *
56 * Redis uses two representations:
57 *
58 * 1) A "dense" representation where every entry is represented by
59 * a 6-bit integer.
60 * 2) A "sparse" representation using run length compression suitable
61 * for representing HyperLogLogs with many registers set to 0 in
62 * a memory efficient way.
63 *
64 *
65 * HLL header
66 * ===
67 *
68 * Both the dense and sparse representation have a 16 byte header as follows:
69 *
70 * +------+---+-----+----------+
71 * | HYLL | E | N/U | Cardin. |
72 * +------+---+-----+----------+
73 *
74 * The first 4 bytes are a magic string set to the bytes "HYLL".
75 * "E" is one byte encoding, currently set to HLL_DENSE or
76 * HLL_SPARSE. N/U are three not used bytes.
77 *
78 * The "Cardin." field is a 64 bit integer stored in little endian format
79 * with the latest cardinality computed that can be reused if the data
80 * structure was not modified since the last computation (this is useful
81 * because there are high probabilities that HLLADD operations don't
82 * modify the actual data structure and hence the approximated cardinality).
83 *
84 * When the most significant bit in the most significant byte of the cached
85 * cardinality is set, it means that the data structure was modified and
86 * we can't reuse the cached value that must be recomputed.
87 *
88 * Dense representation
89 * ===
90 *
91 * The dense representation used by Redis is the following:
92 *
93 * +--------+--------+--------+------// //--+
94 * |11000000|22221111|33333322|55444444 .... |
95 * +--------+--------+--------+------// //--+
96 *
97 * The 6 bits counters are encoded one after the other starting from the
98 * LSB to the MSB, and using the next bytes as needed.
99 *
100 * Sparse representation
101 * ===
102 *
103 * The sparse representation encodes registers using a run length
104 * encoding composed of three opcodes, two using one byte, and one using
105 * of two bytes. The opcodes are called ZERO, XZERO and VAL.
106 *
107 * ZERO opcode is represented as 00xxxxxx. The 6-bit integer represented
108 * by the six bits 'xxxxxx', plus 1, means that there are N registers set
109 * to 0. This opcode can represent from 1 to 64 contiguous registers set
110 * to the value of 0.
111 *
112 * XZERO opcode is represented by two bytes 01xxxxxx yyyyyyyy. The 14-bit
113 * integer represented by the bits 'xxxxxx' as most significant bits and
114 * 'yyyyyyyy' as least significant bits, plus 1, means that there are N
115 * registers set to 0. This opcode can represent from 0 to 16384 contiguous
116 * registers set to the value of 0.
117 *
118 * VAL opcode is represented as 1vvvvvxx. It contains a 5-bit integer
119 * representing the value of a register, and a 2-bit integer representing
120 * the number of contiguous registers set to that value 'vvvvv'.
121 * To obtain the value and run length, the integers vvvvv and xx must be
122 * incremented by one. This opcode can represent values from 1 to 32,
123 * repeated from 1 to 4 times.
124 *
125 * The sparse representation can't represent registers with a value greater
126 * than 32, however it is very unlikely that we find such a register in an
127 * HLL with a cardinality where the sparse representation is still more
128 * memory efficient than the dense representation. When this happens the
129 * HLL is converted to the dense representation.
130 *
131 * The sparse representation is purely positional. For example a sparse
132 * representation of an empty HLL is just: XZERO:16384.
133 *
134 * An HLL having only 3 non-zero registers at position 1000, 1020, 1021
135 * respectively set to 2, 3, 3, is represented by the following three
136 * opcodes:
137 *
138 * XZERO:1000 (Registers 0-999 are set to 0)
139 * VAL:2,1 (1 register set to value 2, that is register 1000)
140 * ZERO:19 (Registers 1001-1019 set to 0)
141 * VAL:3,2 (2 registers set to value 3, that is registers 1020,1021)
142 * XZERO:15362 (Registers 1022-16383 set to 0)
143 *
144 * In the example the sparse representation used just 7 bytes instead
145 * of 12k in order to represent the HLL registers. In general for low
146 * cardinality there is a big win in terms of space efficiency, traded
147 * with CPU time since the sparse representation is slower to access:
148 *
149 * The following table shows average cardinality vs bytes used, 100
150 * samples per cardinality (when the set was not representable because
151 * of registers with too big value, the dense representation size was used
152 * as a sample).
153 *
154 * 100 267
155 * 200 485
156 * 300 678
157 * 400 859
158 * 500 1033
159 * 600 1205
160 * 700 1375
161 * 800 1544
162 * 900 1713
163 * 1000 1882
164 * 2000 3480
165 * 3000 4879
166 * 4000 6089
167 * 5000 7138
168 * 6000 8042
169 * 7000 8823
170 * 8000 9500
171 * 9000 10088
172 * 10000 10591
173 *
174 * The dense representation uses 12288 bytes, so there is a big win up to
175 * a cardinality of ~2000-3000. For bigger cardinalities the constant times
176 * involved in updating the sparse representation is not justified by the
177 * memory savings. The exact maximum length of the sparse representation
178 * when this implementation switches to the dense representation is
179 * configured via the define server.hll_sparse_max_bytes.
180 */
181
182struct hllhdr {
183 char magic[4]; /* "HYLL" */
184 uint8_t encoding; /* HLL_DENSE or HLL_SPARSE. */
185 uint8_t notused[3]; /* Reserved for future use, must be zero. */
186 uint8_t card[8]; /* Cached cardinality, little endian. */
187 uint8_t registers[]; /* Data bytes. */
188};
189
190/* The cached cardinality MSB is used to signal validity of the cached value. */
191#define HLL_INVALIDATE_CACHE(hdr) (hdr)->card[7] |= (1<<7)
192#define HLL_VALID_CACHE(hdr) (((hdr)->card[7] & (1<<7)) == 0)
193
194#define HLL_P 14 /* The greater is P, the smaller the error. */
195#define HLL_Q (64-HLL_P) /* The number of bits of the hash value used for
196 determining the number of leading zeros. */
197#define HLL_REGISTERS (1<<HLL_P) /* With P=14, 16384 registers. */
198#define HLL_P_MASK (HLL_REGISTERS-1) /* Mask to index register. */
199#define HLL_BITS 6 /* Enough to count up to 63 leading zeroes. */
200#define HLL_REGISTER_MAX ((1<<HLL_BITS)-1)
201#define HLL_HDR_SIZE sizeof(struct hllhdr)
202#define HLL_DENSE_SIZE (HLL_HDR_SIZE+((HLL_REGISTERS*HLL_BITS+7)/8))
203#define HLL_DENSE 0 /* Dense encoding. */
204#define HLL_SPARSE 1 /* Sparse encoding. */
205#define HLL_RAW 255 /* Only used internally, never exposed. */
206#define HLL_MAX_ENCODING 1
207
208static char *invalid_hll_err = "-INVALIDOBJ Corrupted HLL object detected";
209
210/* =========================== Low level bit macros ========================= */
211
212/* Macros to access the dense representation.
213 *
214 * We need to get and set 6 bit counters in an array of 8 bit bytes.
215 * We use macros to make sure the code is inlined since speed is critical
216 * especially in order to compute the approximated cardinality in
217 * HLLCOUNT where we need to access all the registers at once.
218 * For the same reason we also want to avoid conditionals in this code path.
219 *
220 * +--------+--------+--------+------//
221 * |11000000|22221111|33333322|55444444
222 * +--------+--------+--------+------//
223 *
224 * Note: in the above representation the most significant bit (MSB)
225 * of every byte is on the left. We start using bits from the LSB to MSB,
226 * and so forth passing to the next byte.
227 *
228 * Example, we want to access to counter at pos = 1 ("111111" in the
229 * illustration above).
230 *
231 * The index of the first byte b0 containing our data is:
232 *
233 * b0 = 6 * pos / 8 = 0
234 *
235 * +--------+
236 * |11000000| <- Our byte at b0
237 * +--------+
238 *
239 * The position of the first bit (counting from the LSB = 0) in the byte
240 * is given by:
241 *
242 * fb = 6 * pos % 8 -> 6
243 *
244 * Right shift b0 of 'fb' bits.
245 *
246 * +--------+
247 * |11000000| <- Initial value of b0
248 * |00000011| <- After right shift of 6 pos.
249 * +--------+
250 *
251 * Left shift b1 of bits 8-fb bits (2 bits)
252 *
253 * +--------+
254 * |22221111| <- Initial value of b1
255 * |22111100| <- After left shift of 2 bits.
256 * +--------+
257 *
258 * OR the two bits, and finally AND with 111111 (63 in decimal) to
259 * clean the higher order bits we are not interested in:
260 *
261 * +--------+
262 * |00000011| <- b0 right shifted
263 * |22111100| <- b1 left shifted
264 * |22111111| <- b0 OR b1
265 * | 111111| <- (b0 OR b1) AND 63, our value.
266 * +--------+
267 *
268 * We can try with a different example, like pos = 0. In this case
269 * the 6-bit counter is actually contained in a single byte.
270 *
271 * b0 = 6 * pos / 8 = 0
272 *
273 * +--------+
274 * |11000000| <- Our byte at b0
275 * +--------+
276 *
277 * fb = 6 * pos % 8 = 0
278 *
279 * So we right shift of 0 bits (no shift in practice) and
280 * left shift the next byte of 8 bits, even if we don't use it,
281 * but this has the effect of clearing the bits so the result
282 * will not be affected after the OR.
283 *
284 * -------------------------------------------------------------------------
285 *
286 * Setting the register is a bit more complex, let's assume that 'val'
287 * is the value we want to set, already in the right range.
288 *
289 * We need two steps, in one we need to clear the bits, and in the other
290 * we need to bitwise-OR the new bits.
291 *
292 * Let's try with 'pos' = 1, so our first byte at 'b' is 0,
293 *
294 * "fb" is 6 in this case.
295 *
296 * +--------+
297 * |11000000| <- Our byte at b0
298 * +--------+
299 *
300 * To create an AND-mask to clear the bits about this position, we just
301 * initialize the mask with the value 63, left shift it of "fs" bits,
302 * and finally invert the result.
303 *
304 * +--------+
305 * |00111111| <- "mask" starts at 63
306 * |11000000| <- "mask" after left shift of "ls" bits.
307 * |00111111| <- "mask" after invert.
308 * +--------+
309 *
310 * Now we can bitwise-AND the byte at "b" with the mask, and bitwise-OR
311 * it with "val" left-shifted of "ls" bits to set the new bits.
312 *
313 * Now let's focus on the next byte b1:
314 *
315 * +--------+
316 * |22221111| <- Initial value of b1
317 * +--------+
318 *
319 * To build the AND mask we start again with the 63 value, right shift
320 * it by 8-fb bits, and invert it.
321 *
322 * +--------+
323 * |00111111| <- "mask" set at 2&6-1
324 * |00001111| <- "mask" after the right shift by 8-fb = 2 bits
325 * |11110000| <- "mask" after bitwise not.
326 * +--------+
327 *
328 * Now we can mask it with b+1 to clear the old bits, and bitwise-OR
329 * with "val" left-shifted by "rs" bits to set the new value.
330 */
331
332/* Note: if we access the last counter, we will also access the b+1 byte
333 * that is out of the array, but sds strings always have an implicit null
334 * term, so the byte exists, and we can skip the conditional (or the need
335 * to allocate 1 byte more explicitly). */
336
337/* Store the value of the register at position 'regnum' into variable 'target'.
338 * 'p' is an array of unsigned bytes. */
339#define HLL_DENSE_GET_REGISTER(target,p,regnum) do { \
340 uint8_t *_p = (uint8_t*) p; \
341 unsigned long _byte = regnum*HLL_BITS/8; \
342 unsigned long _fb = regnum*HLL_BITS&7; \
343 unsigned long _fb8 = 8 - _fb; \
344 unsigned long b0 = _p[_byte]; \
345 unsigned long b1 = _p[_byte+1]; \
346 target = ((b0 >> _fb) | (b1 << _fb8)) & HLL_REGISTER_MAX; \
347} while(0)
348
349/* Set the value of the register at position 'regnum' to 'val'.
350 * 'p' is an array of unsigned bytes. */
351#define HLL_DENSE_SET_REGISTER(p,regnum,val) do { \
352 uint8_t *_p = (uint8_t*) p; \
353 unsigned long _byte = regnum*HLL_BITS/8; \
354 unsigned long _fb = regnum*HLL_BITS&7; \
355 unsigned long _fb8 = 8 - _fb; \
356 unsigned long _v = val; \
357 _p[_byte] &= ~(HLL_REGISTER_MAX << _fb); \
358 _p[_byte] |= _v << _fb; \
359 _p[_byte+1] &= ~(HLL_REGISTER_MAX >> _fb8); \
360 _p[_byte+1] |= _v >> _fb8; \
361} while(0)
362
363/* Macros to access the sparse representation.
364 * The macros parameter is expected to be an uint8_t pointer. */
365#define HLL_SPARSE_XZERO_BIT 0x40 /* 01xxxxxx */
366#define HLL_SPARSE_VAL_BIT 0x80 /* 1vvvvvxx */
367#define HLL_SPARSE_IS_ZERO(p) (((*(p)) & 0xc0) == 0) /* 00xxxxxx */
368#define HLL_SPARSE_IS_XZERO(p) (((*(p)) & 0xc0) == HLL_SPARSE_XZERO_BIT)
369#define HLL_SPARSE_IS_VAL(p) ((*(p)) & HLL_SPARSE_VAL_BIT)
370#define HLL_SPARSE_ZERO_LEN(p) (((*(p)) & 0x3f)+1)
371#define HLL_SPARSE_XZERO_LEN(p) (((((*(p)) & 0x3f) << 8) | (*((p)+1)))+1)
372#define HLL_SPARSE_VAL_VALUE(p) ((((*(p)) >> 2) & 0x1f)+1)
373#define HLL_SPARSE_VAL_LEN(p) (((*(p)) & 0x3)+1)
374#define HLL_SPARSE_VAL_MAX_VALUE 32
375#define HLL_SPARSE_VAL_MAX_LEN 4
376#define HLL_SPARSE_ZERO_MAX_LEN 64
377#define HLL_SPARSE_XZERO_MAX_LEN 16384
378#define HLL_SPARSE_VAL_SET(p,val,len) do { \
379 *(p) = (((val)-1)<<2|((len)-1))|HLL_SPARSE_VAL_BIT; \
380} while(0)
381#define HLL_SPARSE_ZERO_SET(p,len) do { \
382 *(p) = (len)-1; \
383} while(0)
384#define HLL_SPARSE_XZERO_SET(p,len) do { \
385 int _l = (len)-1; \
386 *(p) = (_l>>8) | HLL_SPARSE_XZERO_BIT; \
387 *((p)+1) = (_l&0xff); \
388} while(0)
389#define HLL_ALPHA_INF 0.721347520444481703680 /* constant for 0.5/ln(2) */
390
391/* ========================= HyperLogLog algorithm ========================= */
392
393/* Our hash function is MurmurHash2, 64 bit version.
394 * It was modified for Redis in order to provide the same result in
395 * big and little endian archs (endian neutral). */
396REDIS_NO_SANITIZE("alignment")
397uint64_t MurmurHash64A (const void * key, int len, unsigned int seed) {
398 const uint64_t m = 0xc6a4a7935bd1e995;
399 const int r = 47;
400 uint64_t h = seed ^ (len * m);
401 const uint8_t *data = (const uint8_t *)key;
402 const uint8_t *end = data + (len-(len&7));
403
404 while(data != end) {
405 uint64_t k;
406
407#if (BYTE_ORDER == LITTLE_ENDIAN)
408 #ifdef USE_ALIGNED_ACCESS
409 memcpy(&k,data,sizeof(uint64_t));
410 #else
411 k = *((uint64_t*)data);
412 #endif
413#else
414 k = (uint64_t) data[0];
415 k |= (uint64_t) data[1] << 8;
416 k |= (uint64_t) data[2] << 16;
417 k |= (uint64_t) data[3] << 24;
418 k |= (uint64_t) data[4] << 32;
419 k |= (uint64_t) data[5] << 40;
420 k |= (uint64_t) data[6] << 48;
421 k |= (uint64_t) data[7] << 56;
422#endif
423
424 k *= m;
425 k ^= k >> r;
426 k *= m;
427 h ^= k;
428 h *= m;
429 data += 8;
430 }
431
432 switch(len & 7) {
433 case 7: h ^= (uint64_t)data[6] << 48; /* fall-thru */
434 case 6: h ^= (uint64_t)data[5] << 40; /* fall-thru */
435 case 5: h ^= (uint64_t)data[4] << 32; /* fall-thru */
436 case 4: h ^= (uint64_t)data[3] << 24; /* fall-thru */
437 case 3: h ^= (uint64_t)data[2] << 16; /* fall-thru */
438 case 2: h ^= (uint64_t)data[1] << 8; /* fall-thru */
439 case 1: h ^= (uint64_t)data[0];
440 h *= m; /* fall-thru */
441 };
442
443 h ^= h >> r;
444 h *= m;
445 h ^= h >> r;
446 return h;
447}
448
449/* Given a string element to add to the HyperLogLog, returns the length
450 * of the pattern 000..1 of the element hash. As a side effect 'regp' is
451 * set to the register index this element hashes to. */
452int hllPatLen(unsigned char *ele, size_t elesize, long *regp) {
453 uint64_t hash, bit, index;
454 int count;
455
456 /* Count the number of zeroes starting from bit HLL_REGISTERS
457 * (that is a power of two corresponding to the first bit we don't use
458 * as index). The max run can be 64-P+1 = Q+1 bits.
459 *
460 * Note that the final "1" ending the sequence of zeroes must be
461 * included in the count, so if we find "001" the count is 3, and
462 * the smallest count possible is no zeroes at all, just a 1 bit
463 * at the first position, that is a count of 1.
464 *
465 * This may sound like inefficient, but actually in the average case
466 * there are high probabilities to find a 1 after a few iterations. */
467 hash = MurmurHash64A(ele,elesize,0xadc83b19ULL);
468 index = hash & HLL_P_MASK; /* Register index. */
469 hash >>= HLL_P; /* Remove bits used to address the register. */
470 hash |= ((uint64_t)1<<HLL_Q); /* Make sure the loop terminates
471 and count will be <= Q+1. */
472 bit = 1;
473 count = 1; /* Initialized to 1 since we count the "00000...1" pattern. */
474 while((hash & bit) == 0) {
475 count++;
476 bit <<= 1;
477 }
478 *regp = (int) index;
479 return count;
480}
481
482/* ================== Dense representation implementation ================== */
483
484/* Low level function to set the dense HLL register at 'index' to the
485 * specified value if the current value is smaller than 'count'.
486 *
487 * 'registers' is expected to have room for HLL_REGISTERS plus an
488 * additional byte on the right. This requirement is met by sds strings
489 * automatically since they are implicitly null terminated.
490 *
491 * The function always succeed, however if as a result of the operation
492 * the approximated cardinality changed, 1 is returned. Otherwise 0
493 * is returned. */
494int hllDenseSet(uint8_t *registers, long index, uint8_t count) {
495 uint8_t oldcount;
496
497 HLL_DENSE_GET_REGISTER(oldcount,registers,index);
498 if (count > oldcount) {
499 HLL_DENSE_SET_REGISTER(registers,index,count);
500 return 1;
501 } else {
502 return 0;
503 }
504}
505
506/* "Add" the element in the dense hyperloglog data structure.
507 * Actually nothing is added, but the max 0 pattern counter of the subset
508 * the element belongs to is incremented if needed.
509 *
510 * This is just a wrapper to hllDenseSet(), performing the hashing of the
511 * element in order to retrieve the index and zero-run count. */
512int hllDenseAdd(uint8_t *registers, unsigned char *ele, size_t elesize) {
513 long index;
514 uint8_t count = hllPatLen(ele,elesize,&index);
515 /* Update the register if this element produced a longer run of zeroes. */
516 return hllDenseSet(registers,index,count);
517}
518
519/* Compute the register histogram in the dense representation. */
520void hllDenseRegHisto(uint8_t *registers, int* reghisto) {
521 int j;
522
523 /* Redis default is to use 16384 registers 6 bits each. The code works
524 * with other values by modifying the defines, but for our target value
525 * we take a faster path with unrolled loops. */
526 if (HLL_REGISTERS == 16384 && HLL_BITS == 6) {
527 uint8_t *r = registers;
528 unsigned long r0, r1, r2, r3, r4, r5, r6, r7, r8, r9,
529 r10, r11, r12, r13, r14, r15;
530 for (j = 0; j < 1024; j++) {
531 /* Handle 16 registers per iteration. */
532 r0 = r[0] & 63;
533 r1 = (r[0] >> 6 | r[1] << 2) & 63;
534 r2 = (r[1] >> 4 | r[2] << 4) & 63;
535 r3 = (r[2] >> 2) & 63;
536 r4 = r[3] & 63;
537 r5 = (r[3] >> 6 | r[4] << 2) & 63;
538 r6 = (r[4] >> 4 | r[5] << 4) & 63;
539 r7 = (r[5] >> 2) & 63;
540 r8 = r[6] & 63;
541 r9 = (r[6] >> 6 | r[7] << 2) & 63;
542 r10 = (r[7] >> 4 | r[8] << 4) & 63;
543 r11 = (r[8] >> 2) & 63;
544 r12 = r[9] & 63;
545 r13 = (r[9] >> 6 | r[10] << 2) & 63;
546 r14 = (r[10] >> 4 | r[11] << 4) & 63;
547 r15 = (r[11] >> 2) & 63;
548
549 reghisto[r0]++;
550 reghisto[r1]++;
551 reghisto[r2]++;
552 reghisto[r3]++;
553 reghisto[r4]++;
554 reghisto[r5]++;
555 reghisto[r6]++;
556 reghisto[r7]++;
557 reghisto[r8]++;
558 reghisto[r9]++;
559 reghisto[r10]++;
560 reghisto[r11]++;
561 reghisto[r12]++;
562 reghisto[r13]++;
563 reghisto[r14]++;
564 reghisto[r15]++;
565
566 r += 12;
567 }
568 } else {
569 for(j = 0; j < HLL_REGISTERS; j++) {
570 unsigned long reg;
571 HLL_DENSE_GET_REGISTER(reg,registers,j);
572 reghisto[reg]++;
573 }
574 }
575}
576
577/* ================== Sparse representation implementation ================= */
578
579/* Convert the HLL with sparse representation given as input in its dense
580 * representation. Both representations are represented by SDS strings, and
581 * the input representation is freed as a side effect.
582 *
583 * The function returns C_OK if the sparse representation was valid,
584 * otherwise C_ERR is returned if the representation was corrupted. */
585int hllSparseToDense(robj *o) {
586 sds sparse = o->ptr, dense;
587 struct hllhdr *hdr, *oldhdr = (struct hllhdr*)sparse;
588 int idx = 0, runlen, regval;
589 uint8_t *p = (uint8_t*)sparse, *end = p+sdslen(sparse);
590
591 /* If the representation is already the right one return ASAP. */
592 hdr = (struct hllhdr*) sparse;
593 if (hdr->encoding == HLL_DENSE) return C_OK;
594
595 /* Create a string of the right size filled with zero bytes.
596 * Note that the cached cardinality is set to 0 as a side effect
597 * that is exactly the cardinality of an empty HLL. */
598 dense = sdsnewlen(NULL,HLL_DENSE_SIZE);
599 hdr = (struct hllhdr*) dense;
600 *hdr = *oldhdr; /* This will copy the magic and cached cardinality. */
601 hdr->encoding = HLL_DENSE;
602
603 /* Now read the sparse representation and set non-zero registers
604 * accordingly. */
605 p += HLL_HDR_SIZE;
606 while(p < end) {
607 if (HLL_SPARSE_IS_ZERO(p)) {
608 runlen = HLL_SPARSE_ZERO_LEN(p);
609 idx += runlen;
610 p++;
611 } else if (HLL_SPARSE_IS_XZERO(p)) {
612 runlen = HLL_SPARSE_XZERO_LEN(p);
613 idx += runlen;
614 p += 2;
615 } else {
616 runlen = HLL_SPARSE_VAL_LEN(p);
617 regval = HLL_SPARSE_VAL_VALUE(p);
618 if ((runlen + idx) > HLL_REGISTERS) break; /* Overflow. */
619 while(runlen--) {
620 HLL_DENSE_SET_REGISTER(hdr->registers,idx,regval);
621 idx++;
622 }
623 p++;
624 }
625 }
626
627 /* If the sparse representation was valid, we expect to find idx
628 * set to HLL_REGISTERS. */
629 if (idx != HLL_REGISTERS) {
630 sdsfree(dense);
631 return C_ERR;
632 }
633
634 /* Free the old representation and set the new one. */
635 sdsfree(o->ptr);
636 o->ptr = dense;
637 return C_OK;
638}
639
640/* Low level function to set the sparse HLL register at 'index' to the
641 * specified value if the current value is smaller than 'count'.
642 *
643 * The object 'o' is the String object holding the HLL. The function requires
644 * a reference to the object in order to be able to enlarge the string if
645 * needed.
646 *
647 * On success, the function returns 1 if the cardinality changed, or 0
648 * if the register for this element was not updated.
649 * On error (if the representation is invalid) -1 is returned.
650 *
651 * As a side effect the function may promote the HLL representation from
652 * sparse to dense: this happens when a register requires to be set to a value
653 * not representable with the sparse representation, or when the resulting
654 * size would be greater than server.hll_sparse_max_bytes. */
655int hllSparseSet(robj *o, long index, uint8_t count) {
656 struct hllhdr *hdr;
657 uint8_t oldcount, *sparse, *end, *p, *prev, *next;
658 long first, span;
659 long is_zero = 0, is_xzero = 0, is_val = 0, runlen = 0;
660
661 /* If the count is too big to be representable by the sparse representation
662 * switch to dense representation. */
663 if (count > HLL_SPARSE_VAL_MAX_VALUE) goto promote;
664
665 /* When updating a sparse representation, sometimes we may need to
666 * enlarge the buffer for up to 3 bytes in the worst case (XZERO split
667 * into XZERO-VAL-XZERO). Make sure there is enough space right now
668 * so that the pointers we take during the execution of the function
669 * will be valid all the time. */
670 o->ptr = sdsMakeRoomFor(o->ptr,3);
671
672 /* Step 1: we need to locate the opcode we need to modify to check
673 * if a value update is actually needed. */
674 sparse = p = ((uint8_t*)o->ptr) + HLL_HDR_SIZE;
675 end = p + sdslen(o->ptr) - HLL_HDR_SIZE;
676
677 first = 0;
678 prev = NULL; /* Points to previous opcode at the end of the loop. */
679 next = NULL; /* Points to the next opcode at the end of the loop. */
680 span = 0;
681 while(p < end) {
682 long oplen;
683
684 /* Set span to the number of registers covered by this opcode.
685 *
686 * This is the most performance critical loop of the sparse
687 * representation. Sorting the conditionals from the most to the
688 * least frequent opcode in many-bytes sparse HLLs is faster. */
689 oplen = 1;
690 if (HLL_SPARSE_IS_ZERO(p)) {
691 span = HLL_SPARSE_ZERO_LEN(p);
692 } else if (HLL_SPARSE_IS_VAL(p)) {
693 span = HLL_SPARSE_VAL_LEN(p);
694 } else { /* XZERO. */
695 span = HLL_SPARSE_XZERO_LEN(p);
696 oplen = 2;
697 }
698 /* Break if this opcode covers the register as 'index'. */
699 if (index <= first+span-1) break;
700 prev = p;
701 p += oplen;
702 first += span;
703 }
704 if (span == 0 || p >= end) return -1; /* Invalid format. */
705
706 next = HLL_SPARSE_IS_XZERO(p) ? p+2 : p+1;
707 if (next >= end) next = NULL;
708
709 /* Cache current opcode type to avoid using the macro again and
710 * again for something that will not change.
711 * Also cache the run-length of the opcode. */
712 if (HLL_SPARSE_IS_ZERO(p)) {
713 is_zero = 1;
714 runlen = HLL_SPARSE_ZERO_LEN(p);
715 } else if (HLL_SPARSE_IS_XZERO(p)) {
716 is_xzero = 1;
717 runlen = HLL_SPARSE_XZERO_LEN(p);
718 } else {
719 is_val = 1;
720 runlen = HLL_SPARSE_VAL_LEN(p);
721 }
722
723 /* Step 2: After the loop:
724 *
725 * 'first' stores to the index of the first register covered
726 * by the current opcode, which is pointed by 'p'.
727 *
728 * 'next' ad 'prev' store respectively the next and previous opcode,
729 * or NULL if the opcode at 'p' is respectively the last or first.
730 *
731 * 'span' is set to the number of registers covered by the current
732 * opcode.
733 *
734 * There are different cases in order to update the data structure
735 * in place without generating it from scratch:
736 *
737 * A) If it is a VAL opcode already set to a value >= our 'count'
738 * no update is needed, regardless of the VAL run-length field.
739 * In this case PFADD returns 0 since no changes are performed.
740 *
741 * B) If it is a VAL opcode with len = 1 (representing only our
742 * register) and the value is less than 'count', we just update it
743 * since this is a trivial case. */
744 if (is_val) {
745 oldcount = HLL_SPARSE_VAL_VALUE(p);
746 /* Case A. */
747 if (oldcount >= count) return 0;
748
749 /* Case B. */
750 if (runlen == 1) {
751 HLL_SPARSE_VAL_SET(p,count,1);
752 goto updated;
753 }
754 }
755
756 /* C) Another trivial to handle case is a ZERO opcode with a len of 1.
757 * We can just replace it with a VAL opcode with our value and len of 1. */
758 if (is_zero && runlen == 1) {
759 HLL_SPARSE_VAL_SET(p,count,1);
760 goto updated;
761 }
762
763 /* D) General case.
764 *
765 * The other cases are more complex: our register requires to be updated
766 * and is either currently represented by a VAL opcode with len > 1,
767 * by a ZERO opcode with len > 1, or by an XZERO opcode.
768 *
769 * In those cases the original opcode must be split into multiple
770 * opcodes. The worst case is an XZERO split in the middle resulting into
771 * XZERO - VAL - XZERO, so the resulting sequence max length is
772 * 5 bytes.
773 *
774 * We perform the split writing the new sequence into the 'new' buffer
775 * with 'newlen' as length. Later the new sequence is inserted in place
776 * of the old one, possibly moving what is on the right a few bytes
777 * if the new sequence is longer than the older one. */
778 uint8_t seq[5], *n = seq;
779 int last = first+span-1; /* Last register covered by the sequence. */
780 int len;
781
782 if (is_zero || is_xzero) {
783 /* Handle splitting of ZERO / XZERO. */
784 if (index != first) {
785 len = index-first;
786 if (len > HLL_SPARSE_ZERO_MAX_LEN) {
787 HLL_SPARSE_XZERO_SET(n,len);
788 n += 2;
789 } else {
790 HLL_SPARSE_ZERO_SET(n,len);
791 n++;
792 }
793 }
794 HLL_SPARSE_VAL_SET(n,count,1);
795 n++;
796 if (index != last) {
797 len = last-index;
798 if (len > HLL_SPARSE_ZERO_MAX_LEN) {
799 HLL_SPARSE_XZERO_SET(n,len);
800 n += 2;
801 } else {
802 HLL_SPARSE_ZERO_SET(n,len);
803 n++;
804 }
805 }
806 } else {
807 /* Handle splitting of VAL. */
808 int curval = HLL_SPARSE_VAL_VALUE(p);
809
810 if (index != first) {
811 len = index-first;
812 HLL_SPARSE_VAL_SET(n,curval,len);
813 n++;
814 }
815 HLL_SPARSE_VAL_SET(n,count,1);
816 n++;
817 if (index != last) {
818 len = last-index;
819 HLL_SPARSE_VAL_SET(n,curval,len);
820 n++;
821 }
822 }
823
824 /* Step 3: substitute the new sequence with the old one.
825 *
826 * Note that we already allocated space on the sds string
827 * calling sdsMakeRoomFor(). */
828 int seqlen = n-seq;
829 int oldlen = is_xzero ? 2 : 1;
830 int deltalen = seqlen-oldlen;
831
832 if (deltalen > 0 &&
833 sdslen(o->ptr)+deltalen > server.hll_sparse_max_bytes) goto promote;
834 if (deltalen && next) memmove(next+deltalen,next,end-next);
835 sdsIncrLen(o->ptr,deltalen);
836 memcpy(p,seq,seqlen);
837 end += deltalen;
838
839updated:
840 /* Step 4: Merge adjacent values if possible.
841 *
842 * The representation was updated, however the resulting representation
843 * may not be optimal: adjacent VAL opcodes can sometimes be merged into
844 * a single one. */
845 p = prev ? prev : sparse;
846 int scanlen = 5; /* Scan up to 5 upcodes starting from prev. */
847 while (p < end && scanlen--) {
848 if (HLL_SPARSE_IS_XZERO(p)) {
849 p += 2;
850 continue;
851 } else if (HLL_SPARSE_IS_ZERO(p)) {
852 p++;
853 continue;
854 }
855 /* We need two adjacent VAL opcodes to try a merge, having
856 * the same value, and a len that fits the VAL opcode max len. */
857 if (p+1 < end && HLL_SPARSE_IS_VAL(p+1)) {
858 int v1 = HLL_SPARSE_VAL_VALUE(p);
859 int v2 = HLL_SPARSE_VAL_VALUE(p+1);
860 if (v1 == v2) {
861 int len = HLL_SPARSE_VAL_LEN(p)+HLL_SPARSE_VAL_LEN(p+1);
862 if (len <= HLL_SPARSE_VAL_MAX_LEN) {
863 HLL_SPARSE_VAL_SET(p+1,v1,len);
864 memmove(p,p+1,end-p);
865 sdsIncrLen(o->ptr,-1);
866 end--;
867 /* After a merge we reiterate without incrementing 'p'
868 * in order to try to merge the just merged value with
869 * a value on its right. */
870 continue;
871 }
872 }
873 }
874 p++;
875 }
876
877 /* Invalidate the cached cardinality. */
878 hdr = o->ptr;
879 HLL_INVALIDATE_CACHE(hdr);
880 return 1;
881
882promote: /* Promote to dense representation. */
883 if (hllSparseToDense(o) == C_ERR) return -1; /* Corrupted HLL. */
884 hdr = o->ptr;
885
886 /* We need to call hllDenseAdd() to perform the operation after the
887 * conversion. However the result must be 1, since if we need to
888 * convert from sparse to dense a register requires to be updated.
889 *
890 * Note that this in turn means that PFADD will make sure the command
891 * is propagated to slaves / AOF, so if there is a sparse -> dense
892 * conversion, it will be performed in all the slaves as well. */
893 int dense_retval = hllDenseSet(hdr->registers,index,count);
894 serverAssert(dense_retval == 1);
895 return dense_retval;
896}
897
898/* "Add" the element in the sparse hyperloglog data structure.
899 * Actually nothing is added, but the max 0 pattern counter of the subset
900 * the element belongs to is incremented if needed.
901 *
902 * This function is actually a wrapper for hllSparseSet(), it only performs
903 * the hashing of the element to obtain the index and zeros run length. */
904int hllSparseAdd(robj *o, unsigned char *ele, size_t elesize) {
905 long index;
906 uint8_t count = hllPatLen(ele,elesize,&index);
907 /* Update the register if this element produced a longer run of zeroes. */
908 return hllSparseSet(o,index,count);
909}
910
911/* Compute the register histogram in the sparse representation. */
912void hllSparseRegHisto(uint8_t *sparse, int sparselen, int *invalid, int* reghisto) {
913 int idx = 0, runlen, regval;
914 uint8_t *end = sparse+sparselen, *p = sparse;
915
916 while(p < end) {
917 if (HLL_SPARSE_IS_ZERO(p)) {
918 runlen = HLL_SPARSE_ZERO_LEN(p);
919 idx += runlen;
920 reghisto[0] += runlen;
921 p++;
922 } else if (HLL_SPARSE_IS_XZERO(p)) {
923 runlen = HLL_SPARSE_XZERO_LEN(p);
924 idx += runlen;
925 reghisto[0] += runlen;
926 p += 2;
927 } else {
928 runlen = HLL_SPARSE_VAL_LEN(p);
929 regval = HLL_SPARSE_VAL_VALUE(p);
930 idx += runlen;
931 reghisto[regval] += runlen;
932 p++;
933 }
934 }
935 if (idx != HLL_REGISTERS && invalid) *invalid = 1;
936}
937
938/* ========================= HyperLogLog Count ==============================
939 * This is the core of the algorithm where the approximated count is computed.
940 * The function uses the lower level hllDenseRegHisto() and hllSparseRegHisto()
941 * functions as helpers to compute histogram of register values part of the
942 * computation, which is representation-specific, while all the rest is common. */
943
944/* Implements the register histogram calculation for uint8_t data type
945 * which is only used internally as speedup for PFCOUNT with multiple keys. */
946void hllRawRegHisto(uint8_t *registers, int* reghisto) {
947 uint64_t *word = (uint64_t*) registers;
948 uint8_t *bytes;
949 int j;
950
951 for (j = 0; j < HLL_REGISTERS/8; j++) {
952 if (*word == 0) {
953 reghisto[0] += 8;
954 } else {
955 bytes = (uint8_t*) word;
956 reghisto[bytes[0]]++;
957 reghisto[bytes[1]]++;
958 reghisto[bytes[2]]++;
959 reghisto[bytes[3]]++;
960 reghisto[bytes[4]]++;
961 reghisto[bytes[5]]++;
962 reghisto[bytes[6]]++;
963 reghisto[bytes[7]]++;
964 }
965 word++;
966 }
967}
968
969/* Helper function sigma as defined in
970 * "New cardinality estimation algorithms for HyperLogLog sketches"
971 * Otmar Ertl, arXiv:1702.01284 */
972double hllSigma(double x) {
973 if (x == 1.) return INFINITY;
974 double zPrime;
975 double y = 1;
976 double z = x;
977 do {
978 x *= x;
979 zPrime = z;
980 z += x * y;
981 y += y;
982 } while(zPrime != z);
983 return z;
984}
985
986/* Helper function tau as defined in
987 * "New cardinality estimation algorithms for HyperLogLog sketches"
988 * Otmar Ertl, arXiv:1702.01284 */
989double hllTau(double x) {
990 if (x == 0. || x == 1.) return 0.;
991 double zPrime;
992 double y = 1.0;
993 double z = 1 - x;
994 do {
995 x = sqrt(x);
996 zPrime = z;
997 y *= 0.5;
998 z -= pow(1 - x, 2)*y;
999 } while(zPrime != z);
1000 return z / 3;
1001}
1002
1003/* Return the approximated cardinality of the set based on the harmonic
1004 * mean of the registers values. 'hdr' points to the start of the SDS
1005 * representing the String object holding the HLL representation.
1006 *
1007 * If the sparse representation of the HLL object is not valid, the integer
1008 * pointed by 'invalid' is set to non-zero, otherwise it is left untouched.
1009 *
1010 * hllCount() supports a special internal-only encoding of HLL_RAW, that
1011 * is, hdr->registers will point to an uint8_t array of HLL_REGISTERS element.
1012 * This is useful in order to speedup PFCOUNT when called against multiple
1013 * keys (no need to work with 6-bit integers encoding). */
1014uint64_t hllCount(struct hllhdr *hdr, int *invalid) {
1015 double m = HLL_REGISTERS;
1016 double E;
1017 int j;
1018 /* Note that reghisto size could be just HLL_Q+2, because HLL_Q+1 is
1019 * the maximum frequency of the "000...1" sequence the hash function is
1020 * able to return. However it is slow to check for sanity of the
1021 * input: instead we history array at a safe size: overflows will
1022 * just write data to wrong, but correctly allocated, places. */
1023 int reghisto[64] = {0};
1024
1025 /* Compute register histogram */
1026 if (hdr->encoding == HLL_DENSE) {
1027 hllDenseRegHisto(hdr->registers,reghisto);
1028 } else if (hdr->encoding == HLL_SPARSE) {
1029 hllSparseRegHisto(hdr->registers,
1030 sdslen((sds)hdr)-HLL_HDR_SIZE,invalid,reghisto);
1031 } else if (hdr->encoding == HLL_RAW) {
1032 hllRawRegHisto(hdr->registers,reghisto);
1033 } else {
1034 serverPanic("Unknown HyperLogLog encoding in hllCount()");
1035 }
1036
1037 /* Estimate cardinality from register histogram. See:
1038 * "New cardinality estimation algorithms for HyperLogLog sketches"
1039 * Otmar Ertl, arXiv:1702.01284 */
1040 double z = m * hllTau((m-reghisto[HLL_Q+1])/(double)m);
1041 for (j = HLL_Q; j >= 1; --j) {
1042 z += reghisto[j];
1043 z *= 0.5;
1044 }
1045 z += m * hllSigma(reghisto[0]/(double)m);
1046 E = llroundl(HLL_ALPHA_INF*m*m/z);
1047
1048 return (uint64_t) E;
1049}
1050
1051/* Call hllDenseAdd() or hllSparseAdd() according to the HLL encoding. */
1052int hllAdd(robj *o, unsigned char *ele, size_t elesize) {
1053 struct hllhdr *hdr = o->ptr;
1054 switch(hdr->encoding) {
1055 case HLL_DENSE: return hllDenseAdd(hdr->registers,ele,elesize);
1056 case HLL_SPARSE: return hllSparseAdd(o,ele,elesize);
1057 default: return -1; /* Invalid representation. */
1058 }
1059}
1060
1061/* Merge by computing MAX(registers[i],hll[i]) the HyperLogLog 'hll'
1062 * with an array of uint8_t HLL_REGISTERS registers pointed by 'max'.
1063 *
1064 * The hll object must be already validated via isHLLObjectOrReply()
1065 * or in some other way.
1066 *
1067 * If the HyperLogLog is sparse and is found to be invalid, C_ERR
1068 * is returned, otherwise the function always succeeds. */
1069int hllMerge(uint8_t *max, robj *hll) {
1070 struct hllhdr *hdr = hll->ptr;
1071 int i;
1072
1073 if (hdr->encoding == HLL_DENSE) {
1074 uint8_t val;
1075
1076 for (i = 0; i < HLL_REGISTERS; i++) {
1077 HLL_DENSE_GET_REGISTER(val,hdr->registers,i);
1078 if (val > max[i]) max[i] = val;
1079 }
1080 } else {
1081 uint8_t *p = hll->ptr, *end = p + sdslen(hll->ptr);
1082 long runlen, regval;
1083
1084 p += HLL_HDR_SIZE;
1085 i = 0;
1086 while(p < end) {
1087 if (HLL_SPARSE_IS_ZERO(p)) {
1088 runlen = HLL_SPARSE_ZERO_LEN(p);
1089 i += runlen;
1090 p++;
1091 } else if (HLL_SPARSE_IS_XZERO(p)) {
1092 runlen = HLL_SPARSE_XZERO_LEN(p);
1093 i += runlen;
1094 p += 2;
1095 } else {
1096 runlen = HLL_SPARSE_VAL_LEN(p);
1097 regval = HLL_SPARSE_VAL_VALUE(p);
1098 if ((runlen + i) > HLL_REGISTERS) break; /* Overflow. */
1099 while(runlen--) {
1100 if (regval > max[i]) max[i] = regval;
1101 i++;
1102 }
1103 p++;
1104 }
1105 }
1106 if (i != HLL_REGISTERS) return C_ERR;
1107 }
1108 return C_OK;
1109}
1110
1111/* ========================== HyperLogLog commands ========================== */
1112
1113/* Create an HLL object. We always create the HLL using sparse encoding.
1114 * This will be upgraded to the dense representation as needed. */
1115robj *createHLLObject(void) {
1116 robj *o;
1117 struct hllhdr *hdr;
1118 sds s;
1119 uint8_t *p;
1120 int sparselen = HLL_HDR_SIZE +
1121 (((HLL_REGISTERS+(HLL_SPARSE_XZERO_MAX_LEN-1)) /
1122 HLL_SPARSE_XZERO_MAX_LEN)*2);
1123 int aux;
1124
1125 /* Populate the sparse representation with as many XZERO opcodes as
1126 * needed to represent all the registers. */
1127 aux = HLL_REGISTERS;
1128 s = sdsnewlen(NULL,sparselen);
1129 p = (uint8_t*)s + HLL_HDR_SIZE;
1130 while(aux) {
1131 int xzero = HLL_SPARSE_XZERO_MAX_LEN;
1132 if (xzero > aux) xzero = aux;
1133 HLL_SPARSE_XZERO_SET(p,xzero);
1134 p += 2;
1135 aux -= xzero;
1136 }
1137 serverAssert((p-(uint8_t*)s) == sparselen);
1138
1139 /* Create the actual object. */
1140 o = createObject(OBJ_STRING,s);
1141 hdr = o->ptr;
1142 memcpy(hdr->magic,"HYLL",4);
1143 hdr->encoding = HLL_SPARSE;
1144 return o;
1145}
1146
1147/* Check if the object is a String with a valid HLL representation.
1148 * Return C_OK if this is true, otherwise reply to the client
1149 * with an error and return C_ERR. */
1150int isHLLObjectOrReply(client *c, robj *o) {
1151 struct hllhdr *hdr;
1152
1153 /* Key exists, check type */
1154 if (checkType(c,o,OBJ_STRING))
1155 return C_ERR; /* Error already sent. */
1156
1157 if (!sdsEncodedObject(o)) goto invalid;
1158 if (stringObjectLen(o) < sizeof(*hdr)) goto invalid;
1159 hdr = o->ptr;
1160
1161 /* Magic should be "HYLL". */
1162 if (hdr->magic[0] != 'H' || hdr->magic[1] != 'Y' ||
1163 hdr->magic[2] != 'L' || hdr->magic[3] != 'L') goto invalid;
1164
1165 if (hdr->encoding > HLL_MAX_ENCODING) goto invalid;
1166
1167 /* Dense representation string length should match exactly. */
1168 if (hdr->encoding == HLL_DENSE &&
1169 stringObjectLen(o) != HLL_DENSE_SIZE) goto invalid;
1170
1171 /* All tests passed. */
1172 return C_OK;
1173
1174invalid:
1175 addReplyError(c,"-WRONGTYPE Key is not a valid "
1176 "HyperLogLog string value.");
1177 return C_ERR;
1178}
1179
1180/* PFADD var ele ele ele ... ele => :0 or :1 */
1181void pfaddCommand(client *c) {
1182 robj *o = lookupKeyWrite(c->db,c->argv[1]);
1183 struct hllhdr *hdr;
1184 int updated = 0, j;
1185
1186 if (o == NULL) {
1187 /* Create the key with a string value of the exact length to
1188 * hold our HLL data structure. sdsnewlen() when NULL is passed
1189 * is guaranteed to return bytes initialized to zero. */
1190 o = createHLLObject();
1191 dbAdd(c->db,c->argv[1],o);
1192 updated++;
1193 } else {
1194 if (isHLLObjectOrReply(c,o) != C_OK) return;
1195 o = dbUnshareStringValue(c->db,c->argv[1],o);
1196 }
1197 /* Perform the low level ADD operation for every element. */
1198 for (j = 2; j < c->argc; j++) {
1199 int retval = hllAdd(o, (unsigned char*)c->argv[j]->ptr,
1200 sdslen(c->argv[j]->ptr));
1201 switch(retval) {
1202 case 1:
1203 updated++;
1204 break;
1205 case -1:
1206 addReplyError(c,invalid_hll_err);
1207 return;
1208 }
1209 }
1210 hdr = o->ptr;
1211 if (updated) {
1212 signalModifiedKey(c,c->db,c->argv[1]);
1213 notifyKeyspaceEvent(NOTIFY_STRING,"pfadd",c->argv[1],c->db->id);
1214 server.dirty += updated;
1215 HLL_INVALIDATE_CACHE(hdr);
1216 }
1217 addReply(c, updated ? shared.cone : shared.czero);
1218}
1219
1220/* PFCOUNT var -> approximated cardinality of set. */
1221void pfcountCommand(client *c) {
1222 robj *o;
1223 struct hllhdr *hdr;
1224 uint64_t card;
1225
1226 /* Case 1: multi-key keys, cardinality of the union.
1227 *
1228 * When multiple keys are specified, PFCOUNT actually computes
1229 * the cardinality of the merge of the N HLLs specified. */
1230 if (c->argc > 2) {
1231 uint8_t max[HLL_HDR_SIZE+HLL_REGISTERS], *registers;
1232 int j;
1233
1234 /* Compute an HLL with M[i] = MAX(M[i]_j). */
1235 memset(max,0,sizeof(max));
1236 hdr = (struct hllhdr*) max;
1237 hdr->encoding = HLL_RAW; /* Special internal-only encoding. */
1238 registers = max + HLL_HDR_SIZE;
1239 for (j = 1; j < c->argc; j++) {
1240 /* Check type and size. */
1241 robj *o = lookupKeyRead(c->db,c->argv[j]);
1242 if (o == NULL) continue; /* Assume empty HLL for non existing var.*/
1243 if (isHLLObjectOrReply(c,o) != C_OK) return;
1244
1245 /* Merge with this HLL with our 'max' HLL by setting max[i]
1246 * to MAX(max[i],hll[i]). */
1247 if (hllMerge(registers,o) == C_ERR) {
1248 addReplyError(c,invalid_hll_err);
1249 return;
1250 }
1251 }
1252
1253 /* Compute cardinality of the resulting set. */
1254 addReplyLongLong(c,hllCount(hdr,NULL));
1255 return;
1256 }
1257
1258 /* Case 2: cardinality of the single HLL.
1259 *
1260 * The user specified a single key. Either return the cached value
1261 * or compute one and update the cache.
1262 *
1263 * Since a HLL is a regular Redis string type value, updating the cache does
1264 * modify the value. We do a lookupKeyRead anyway since this is flagged as a
1265 * read-only command. The difference is that with lookupKeyWrite, a
1266 * logically expired key on a replica is deleted, while with lookupKeyRead
1267 * it isn't, but the lookup returns NULL either way if the key is logically
1268 * expired, which is what matters here. */
1269 o = lookupKeyRead(c->db,c->argv[1]);
1270 if (o == NULL) {
1271 /* No key? Cardinality is zero since no element was added, otherwise
1272 * we would have a key as HLLADD creates it as a side effect. */
1273 addReply(c,shared.czero);
1274 } else {
1275 if (isHLLObjectOrReply(c,o) != C_OK) return;
1276 o = dbUnshareStringValue(c->db,c->argv[1],o);
1277
1278 /* Check if the cached cardinality is valid. */
1279 hdr = o->ptr;
1280 if (HLL_VALID_CACHE(hdr)) {
1281 /* Just return the cached value. */
1282 card = (uint64_t)hdr->card[0];
1283 card |= (uint64_t)hdr->card[1] << 8;
1284 card |= (uint64_t)hdr->card[2] << 16;
1285 card |= (uint64_t)hdr->card[3] << 24;
1286 card |= (uint64_t)hdr->card[4] << 32;
1287 card |= (uint64_t)hdr->card[5] << 40;
1288 card |= (uint64_t)hdr->card[6] << 48;
1289 card |= (uint64_t)hdr->card[7] << 56;
1290 } else {
1291 int invalid = 0;
1292 /* Recompute it and update the cached value. */
1293 card = hllCount(hdr,&invalid);
1294 if (invalid) {
1295 addReplyError(c,invalid_hll_err);
1296 return;
1297 }
1298 hdr->card[0] = card & 0xff;
1299 hdr->card[1] = (card >> 8) & 0xff;
1300 hdr->card[2] = (card >> 16) & 0xff;
1301 hdr->card[3] = (card >> 24) & 0xff;
1302 hdr->card[4] = (card >> 32) & 0xff;
1303 hdr->card[5] = (card >> 40) & 0xff;
1304 hdr->card[6] = (card >> 48) & 0xff;
1305 hdr->card[7] = (card >> 56) & 0xff;
1306 /* This is considered a read-only command even if the cached value
1307 * may be modified and given that the HLL is a Redis string
1308 * we need to propagate the change. */
1309 signalModifiedKey(c,c->db,c->argv[1]);
1310 server.dirty++;
1311 }
1312 addReplyLongLong(c,card);
1313 }
1314}
1315
1316/* PFMERGE dest src1 src2 src3 ... srcN => OK */
1317void pfmergeCommand(client *c) {
1318 uint8_t max[HLL_REGISTERS];
1319 struct hllhdr *hdr;
1320 int j;
1321 int use_dense = 0; /* Use dense representation as target? */
1322
1323 /* Compute an HLL with M[i] = MAX(M[i]_j).
1324 * We store the maximum into the max array of registers. We'll write
1325 * it to the target variable later. */
1326 memset(max,0,sizeof(max));
1327 for (j = 1; j < c->argc; j++) {
1328 /* Check type and size. */
1329 robj *o = lookupKeyRead(c->db,c->argv[j]);
1330 if (o == NULL) continue; /* Assume empty HLL for non existing var. */
1331 if (isHLLObjectOrReply(c,o) != C_OK) return;
1332
1333 /* If at least one involved HLL is dense, use the dense representation
1334 * as target ASAP to save time and avoid the conversion step. */
1335 hdr = o->ptr;
1336 if (hdr->encoding == HLL_DENSE) use_dense = 1;
1337
1338 /* Merge with this HLL with our 'max' HLL by setting max[i]
1339 * to MAX(max[i],hll[i]). */
1340 if (hllMerge(max,o) == C_ERR) {
1341 addReplyError(c,invalid_hll_err);
1342 return;
1343 }
1344 }
1345
1346 /* Create / unshare the destination key's value if needed. */
1347 robj *o = lookupKeyWrite(c->db,c->argv[1]);
1348 if (o == NULL) {
1349 /* Create the key with a string value of the exact length to
1350 * hold our HLL data structure. sdsnewlen() when NULL is passed
1351 * is guaranteed to return bytes initialized to zero. */
1352 o = createHLLObject();
1353 dbAdd(c->db,c->argv[1],o);
1354 } else {
1355 /* If key exists we are sure it's of the right type/size
1356 * since we checked when merging the different HLLs, so we
1357 * don't check again. */
1358 o = dbUnshareStringValue(c->db,c->argv[1],o);
1359 }
1360
1361 /* Convert the destination object to dense representation if at least
1362 * one of the inputs was dense. */
1363 if (use_dense && hllSparseToDense(o) == C_ERR) {
1364 addReplyError(c,invalid_hll_err);
1365 return;
1366 }
1367
1368 /* Write the resulting HLL to the destination HLL registers and
1369 * invalidate the cached value. */
1370 for (j = 0; j < HLL_REGISTERS; j++) {
1371 if (max[j] == 0) continue;
1372 hdr = o->ptr;
1373 switch(hdr->encoding) {
1374 case HLL_DENSE: hllDenseSet(hdr->registers,j,max[j]); break;
1375 case HLL_SPARSE: hllSparseSet(o,j,max[j]); break;
1376 }
1377 }
1378 hdr = o->ptr; /* o->ptr may be different now, as a side effect of
1379 last hllSparseSet() call. */
1380 HLL_INVALIDATE_CACHE(hdr);
1381
1382 signalModifiedKey(c,c->db,c->argv[1]);
1383 /* We generate a PFADD event for PFMERGE for semantical simplicity
1384 * since in theory this is a mass-add of elements. */
1385 notifyKeyspaceEvent(NOTIFY_STRING,"pfadd",c->argv[1],c->db->id);
1386 server.dirty++;
1387 addReply(c,shared.ok);
1388}
1389
1390/* ========================== Testing / Debugging ========================== */
1391
1392/* PFSELFTEST
1393 * This command performs a self-test of the HLL registers implementation.
1394 * Something that is not easy to test from within the outside. */
1395#define HLL_TEST_CYCLES 1000
1396void pfselftestCommand(client *c) {
1397 unsigned int j, i;
1398 sds bitcounters = sdsnewlen(NULL,HLL_DENSE_SIZE);
1399 struct hllhdr *hdr = (struct hllhdr*) bitcounters, *hdr2;
1400 robj *o = NULL;
1401 uint8_t bytecounters[HLL_REGISTERS];
1402
1403 /* Test 1: access registers.
1404 * The test is conceived to test that the different counters of our data
1405 * structure are accessible and that setting their values both result in
1406 * the correct value to be retained and not affect adjacent values. */
1407 for (j = 0; j < HLL_TEST_CYCLES; j++) {
1408 /* Set the HLL counters and an array of unsigned byes of the
1409 * same size to the same set of random values. */
1410 for (i = 0; i < HLL_REGISTERS; i++) {
1411 unsigned int r = rand() & HLL_REGISTER_MAX;
1412
1413 bytecounters[i] = r;
1414 HLL_DENSE_SET_REGISTER(hdr->registers,i,r);
1415 }
1416 /* Check that we are able to retrieve the same values. */
1417 for (i = 0; i < HLL_REGISTERS; i++) {
1418 unsigned int val;
1419
1420 HLL_DENSE_GET_REGISTER(val,hdr->registers,i);
1421 if (val != bytecounters[i]) {
1422 addReplyErrorFormat(c,
1423 "TESTFAILED Register %d should be %d but is %d",
1424 i, (int) bytecounters[i], (int) val);
1425 goto cleanup;
1426 }
1427 }
1428 }
1429
1430 /* Test 2: approximation error.
1431 * The test adds unique elements and check that the estimated value
1432 * is always reasonable bounds.
1433 *
1434 * We check that the error is smaller than a few times than the expected
1435 * standard error, to make it very unlikely for the test to fail because
1436 * of a "bad" run.
1437 *
1438 * The test is performed with both dense and sparse HLLs at the same
1439 * time also verifying that the computed cardinality is the same. */
1440 memset(hdr->registers,0,HLL_DENSE_SIZE-HLL_HDR_SIZE);
1441 o = createHLLObject();
1442 double relerr = 1.04/sqrt(HLL_REGISTERS);
1443 int64_t checkpoint = 1;
1444 uint64_t seed = (uint64_t)rand() | (uint64_t)rand() << 32;
1445 uint64_t ele;
1446 for (j = 1; j <= 10000000; j++) {
1447 ele = j ^ seed;
1448 hllDenseAdd(hdr->registers,(unsigned char*)&ele,sizeof(ele));
1449 hllAdd(o,(unsigned char*)&ele,sizeof(ele));
1450
1451 /* Make sure that for small cardinalities we use sparse
1452 * encoding. */
1453 if (j == checkpoint && j < server.hll_sparse_max_bytes/2) {
1454 hdr2 = o->ptr;
1455 if (hdr2->encoding != HLL_SPARSE) {
1456 addReplyError(c, "TESTFAILED sparse encoding not used");
1457 goto cleanup;
1458 }
1459 }
1460
1461 /* Check that dense and sparse representations agree. */
1462 if (j == checkpoint && hllCount(hdr,NULL) != hllCount(o->ptr,NULL)) {
1463 addReplyError(c, "TESTFAILED dense/sparse disagree");
1464 goto cleanup;
1465 }
1466
1467 /* Check error. */
1468 if (j == checkpoint) {
1469 int64_t abserr = checkpoint - (int64_t)hllCount(hdr,NULL);
1470 uint64_t maxerr = ceil(relerr*6*checkpoint);
1471
1472 /* Adjust the max error we expect for cardinality 10
1473 * since from time to time it is statistically likely to get
1474 * much higher error due to collision, resulting into a false
1475 * positive. */
1476 if (j == 10) maxerr = 1;
1477
1478 if (abserr < 0) abserr = -abserr;
1479 if (abserr > (int64_t)maxerr) {
1480 addReplyErrorFormat(c,
1481 "TESTFAILED Too big error. card:%llu abserr:%llu",
1482 (unsigned long long) checkpoint,
1483 (unsigned long long) abserr);
1484 goto cleanup;
1485 }
1486 checkpoint *= 10;
1487 }
1488 }
1489
1490 /* Success! */
1491 addReply(c,shared.ok);
1492
1493cleanup:
1494 sdsfree(bitcounters);
1495 if (o) decrRefCount(o);
1496}
1497
1498/* Different debugging related operations about the HLL implementation.
1499 *
1500 * PFDEBUG GETREG <key>
1501 * PFDEBUG DECODE <key>
1502 * PFDEBUG ENCODING <key>
1503 * PFDEBUG TODENSE <key>
1504 */
1505void pfdebugCommand(client *c) {
1506 char *cmd = c->argv[1]->ptr;
1507 struct hllhdr *hdr;
1508 robj *o;
1509 int j;
1510
1511 o = lookupKeyWrite(c->db,c->argv[2]);
1512 if (o == NULL) {
1513 addReplyError(c,"The specified key does not exist");
1514 return;
1515 }
1516 if (isHLLObjectOrReply(c,o) != C_OK) return;
1517 o = dbUnshareStringValue(c->db,c->argv[2],o);
1518 hdr = o->ptr;
1519
1520 /* PFDEBUG GETREG <key> */
1521 if (!strcasecmp(cmd,"getreg")) {
1522 if (c->argc != 3) goto arityerr;
1523
1524 if (hdr->encoding == HLL_SPARSE) {
1525 if (hllSparseToDense(o) == C_ERR) {
1526 addReplyError(c,invalid_hll_err);
1527 return;
1528 }
1529 server.dirty++; /* Force propagation on encoding change. */
1530 }
1531
1532 hdr = o->ptr;
1533 addReplyArrayLen(c,HLL_REGISTERS);
1534 for (j = 0; j < HLL_REGISTERS; j++) {
1535 uint8_t val;
1536
1537 HLL_DENSE_GET_REGISTER(val,hdr->registers,j);
1538 addReplyLongLong(c,val);
1539 }
1540 }
1541 /* PFDEBUG DECODE <key> */
1542 else if (!strcasecmp(cmd,"decode")) {
1543 if (c->argc != 3) goto arityerr;
1544
1545 uint8_t *p = o->ptr, *end = p+sdslen(o->ptr);
1546 sds decoded = sdsempty();
1547
1548 if (hdr->encoding != HLL_SPARSE) {
1549 sdsfree(decoded);
1550 addReplyError(c,"HLL encoding is not sparse");
1551 return;
1552 }
1553
1554 p += HLL_HDR_SIZE;
1555 while(p < end) {
1556 int runlen, regval;
1557
1558 if (HLL_SPARSE_IS_ZERO(p)) {
1559 runlen = HLL_SPARSE_ZERO_LEN(p);
1560 p++;
1561 decoded = sdscatprintf(decoded,"z:%d ",runlen);
1562 } else if (HLL_SPARSE_IS_XZERO(p)) {
1563 runlen = HLL_SPARSE_XZERO_LEN(p);
1564 p += 2;
1565 decoded = sdscatprintf(decoded,"Z:%d ",runlen);
1566 } else {
1567 runlen = HLL_SPARSE_VAL_LEN(p);
1568 regval = HLL_SPARSE_VAL_VALUE(p);
1569 p++;
1570 decoded = sdscatprintf(decoded,"v:%d,%d ",regval,runlen);
1571 }
1572 }
1573 decoded = sdstrim(decoded," ");
1574 addReplyBulkCBuffer(c,decoded,sdslen(decoded));
1575 sdsfree(decoded);
1576 }
1577 /* PFDEBUG ENCODING <key> */
1578 else if (!strcasecmp(cmd,"encoding")) {
1579 char *encodingstr[2] = {"dense","sparse"};
1580 if (c->argc != 3) goto arityerr;
1581
1582 addReplyStatus(c,encodingstr[hdr->encoding]);
1583 }
1584 /* PFDEBUG TODENSE <key> */
1585 else if (!strcasecmp(cmd,"todense")) {
1586 int conv = 0;
1587 if (c->argc != 3) goto arityerr;
1588
1589 if (hdr->encoding == HLL_SPARSE) {
1590 if (hllSparseToDense(o) == C_ERR) {
1591 addReplyError(c,invalid_hll_err);
1592 return;
1593 }
1594 conv = 1;
1595 server.dirty++; /* Force propagation on encoding change. */
1596 }
1597 addReply(c,conv ? shared.cone : shared.czero);
1598 } else {
1599 addReplyErrorFormat(c,"Unknown PFDEBUG subcommand '%s'", cmd);
1600 }
1601 return;
1602
1603arityerr:
1604 addReplyErrorFormat(c,
1605 "Wrong number of arguments for the '%s' subcommand",cmd);
1606}
1607
1608