Fix random element selection for large hash tables. (#8133)

When a database on a 64 bit build grows past 2^31 keys, the underlying hash table expands to 2^32 buckets. After this point, the algorithms for selecting random elements only return elements from half of the available buckets because they use random() which has a range of 0 to 2^31 - 1. This causes problems for eviction policies which use dictGetSomeKeys or dictGetRandomKey. Over time they cause the hash table to become unbalanced because, while new keys are spread out evenly across all buckets, evictions come from only half of the available buckets. Eventually this half of the table starts to run out of keys and it takes longer and longer to find candidates for eviction. This continues until no more evictions can happen.

This solution addresses this by using a 64 bit PRNG instead of libc random().

Co-authored-by: Greg Femec <gfemec@google.com>

1 files changed, 2 insertions, 0 deletions

diff --git a/src/redis-benchmark.c b/src/redis-benchmark.c
index 18e19b0e0..a955c0d4c 100644
--- a/src/redis-benchmark.c
+++ b/src/redis-benchmark.c
@@ -59,6 +59,7 @@
 #include "crc16_slottable.h"
 #include "hdr_histogram.h"
 #include "cli_common.h"
+#include "mt19937-64.h"
 
 #define UNUSED(V) ((void) V)
 #define RANDPTR_INITIAL_SIZE 8
@@ -1677,6 +1678,7 @@ int main(int argc, const char **argv) {
     client c;
 
     srandom(time(NULL) ^ getpid());
+    init_genrand64(ustime() ^ getpid());
     signal(SIGHUP, SIG_IGN);
     signal(SIGPIPE, SIG_IGN);