Hyperloglog avoid allocate more than 'server.hll_sparse_max_bytes' bytes of memory for sparse representation (#11438)

Before this PR, we use sdsMakeRoomFor() to expand the size of hyperloglog
string (sparse representation). And because sdsMakeRoomFor() uses a greedy
strategy (allocate about twice what we need), the memory we allocated for the
hyperloglog may be more than `server.hll_sparse_max_bytes` bytes.
The memory more than` server.hll_sparse_max_bytes` will be wasted.

In this pull request, tone down the greediness of the allocation growth, and also
make sure it'll never request more than `server.hll_sparse_max_bytes`.

This could in theory mean the size of the hyperloglog string is insufficient for the
increment we need, should be ok since in this case we promote the hyperloglog
to dense representation, an assertion was added to make sure.

This PR also add some tests and fixes some typo and indentation issues.

1 files changed, 30 insertions, 0 deletions

diff --git a/tests/unit/hyperloglog.tcl b/tests/unit/hyperloglog.tcl
index 0103b2ab9..ee437189f 100644
--- a/tests/unit/hyperloglog.tcl
+++ b/tests/unit/hyperloglog.tcl
@@ -59,6 +59,36 @@ start_server {tags {"hll"}} {
         }
     } {} {needs:pfdebug}
 
+    test {Change hll-sparse-max-bytes} {
+        r config set hll-sparse-max-bytes 3000
+        r del hll
+        r pfadd hll a b c d e d g h i j k
+        assert {[r pfdebug encoding hll] eq {sparse}}
+        r config set hll-sparse-max-bytes 30
+        r pfadd hll new_element
+        assert {[r pfdebug encoding hll] eq {dense}}
+    } {} {needs:pfdebug}
+
+    test {Hyperloglog promote to dense well in different hll-sparse-max-bytes} {
+        set max(0) 100
+        set max(1) 500
+        set max(2) 3000
+        for {set i 0} {$i < [array size max]} {incr i} {
+            r config set hll-sparse-max-bytes $max($i)
+            r del hll
+            r pfadd hll
+            set len [r strlen hll]
+            while {$len <= $max($i)} {
+                assert {[r pfdebug encoding hll] eq {sparse}}
+                set elements {}
+                for {set j 0} {$j < 10} {incr j} { lappend elements [expr rand()]}
+                r pfadd hll {*}$elements
+                set len [r strlen hll]
+            }
+            assert {[r pfdebug encoding hll] eq {dense}}
+        }
+    } {} {needs:pfdebug}
+
     test {HyperLogLog sparse encoding stress test} {
         for {set x 0} {$x < 1000} {incr x} {
             r del hll1