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 | |
182 | struct 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 | |
208 | static 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). */ |
396 | REDIS_NO_SANITIZE("alignment" ) |
397 | uint64_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. */ |
452 | int 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. */ |
494 | int 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. */ |
512 | int 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. */ |
520 | void 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. */ |
585 | int 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. */ |
655 | int 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 | |
839 | updated: |
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 | |
882 | promote: /* 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. */ |
904 | int 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. */ |
912 | void 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. */ |
946 | void 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 */ |
972 | double 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 */ |
989 | double 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). */ |
1014 | uint64_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. */ |
1052 | int 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. */ |
1069 | int 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. */ |
1115 | robj *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. */ |
1150 | int 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 | |
1174 | invalid: |
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 */ |
1181 | void 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. */ |
1221 | void 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 */ |
1317 | void 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 |
1396 | void 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 | |
1493 | cleanup: |
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 | */ |
1505 | void 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 | |
1603 | arityerr: |
1604 | addReplyErrorFormat(c, |
1605 | "Wrong number of arguments for the '%s' subcommand" ,cmd); |
1606 | } |
1607 | |
1608 | |