1. 20 Mar, 2024 1 commit
    • Yanqi Lv's avatar
      Fix dict use-after-free problem in kvs->rehashing (#13154) · e64d91c3
      Yanqi Lv authored
      
      
      In ASAN CI, we find server may crash because of NULL ptr in `kvstoreIncrementallyRehash`.
      the reason is that we use two phase unlink in `dbGenericDelete`. After `kvstoreDictTwoPhaseUnlinkFind`,
      the dict may be in rehashing and only have one element in ht[0] of `db->keys`.
      
      When we delete the last element in `db->keys` meanwhile `db->keys` is in rehashing, we may free the
      dict in `kvstoreDictTwoPhaseUnlinkFree` without deleting the node in `kvs->rehashing`. Then we may
      use this freed ptr in `kvstoreIncrementallyRehash` in the `serverCron` and cause the crash.
      This is indeed a use-after-free problem.
      
      The fix is to call rehashingCompleted in dictRelease and dictEmpty, so that every call for
      rehashingStarted is always matched with a rehashingCompleted.
      
      Adding a test in the unit test to catch it consistently
      
      ---------
      Co-authored-by: default avatarOran Agra <oran@redislabs.com>
      Co-authored-by: default avatardebing.sun <debing.sun@redis.com>
      e64d91c3
  2. 05 Feb, 2024 1 commit
    • guybe7's avatar
      Refactor the per-slot dict-array db.c into a new kvstore data structure (#12822) · 8cd62f82
      guybe7 authored
      # Description
      Gather most of the scattered `redisDb`-related code from the per-slot
      dict PR (#11695) and turn it to a new data structure, `kvstore`. i.e.
      it's a class that represents an array of dictionaries.
      
      # Motivation
      The main motivation is code cleanliness, the idea of using an array of
      dictionaries is very well-suited to becoming a self-contained data
      structure.
      This allowed cleaning some ugly code, among others: loops that run twice
      on the main dict and expires dict, and duplicate code for allocating and
      releasing this data structure.
      
      # Notes
      1. This PR reverts the part of https://github.com/redis/redis/pull/12848
      where the `rehashing` list is global (handling rehashing `dict`s is
      under the responsibility of `kvstore`, and should not be managed by the
      server)
      2. This PR also replaces the type of `server.pubsubshard_channels` from
      `dict**` to `kvstore` (original PR:
      https://github.com/redis/redis/pull/12804). After that was done,
      server.pubsub_channels was also chosen to be a `kvstore` (with only one
      `dict`, which seems odd) just to make the code cleaner by making it the
      same type as `server.pubsubshard_channels`, see
      `pubsubtype.serverPubSubChannels`
      3. the keys and expires kvstores are currenlty configured to allocate
      the individual dicts only when the first key is added (unlike before, in
      which they allocated them in advance), but they won't release them when
      the last key is deleted.
      
      Worth mentioning that due to the recent change the reply of DEBUG
      HTSTATS changed, in case no keys were ever added to the db.
      
      before:
      ```
      127.0.0.1:6379> DEBUG htstats 9
      [Dictionary HT]
      Hash table 0 stats (main hash table):
      No stats available for empty dictionaries
      [Expires HT]
      Hash table 0 stats (main hash table):
      No stats available for empty dictionaries
      ```
      
      after:
      ```
      127.0.0.1:6379> DEBUG htstats 9
      [Dictionary HT]
      [Expires HT]
      ```
      8cd62f82
  3. 29 Jan, 2024 1 commit
    • Chen Tianjie's avatar
      Optimize resizing hash table to resize not only non-empty dicts. (#12819) · af7ceeb7
      Chen Tianjie authored
      The function `tryResizeHashTables` only attempts to shrink the dicts
      that has keys (change from #11695), this was a serious problem until the
      change in #12850 since it meant if all keys are deleted, we won't shrink
      the dick.
      But still, both dictShrink and dictExpand may be blocked by a fork child
      process, therefore, the cron job needs to perform both dictShrink and
      dictExpand, for not just non-empty dicts, but all dicts in DBs.
      
      What this PR does:
      
      1. Try to resize all dicts in DBs (not just non-empty ones, as it was
      since #12850)
      2. handle both shrink and expand (not just shrink, as it was since
      forever)
      3. Refactor some APIs about dict resizing (get rid of `htNeedsShrink`
      `htNeedsShrink` `dictShrinkToFit`, and expose `dictShrinkIfNeeded`
      `dictExpandIfNeeded` which already contains all the code of those
      functions we get rid of, to make APIs more neat)
      4. In the `Don't rehash if redis has child process` test, now that cron
      would do resizing, we no longer need to write to DB after the child
      process got killed, and can wait for the cron to expand the hash table.
      af7ceeb7
  4. 27 Jan, 2024 1 commit
    • Roshan Khatri's avatar
      Reduce performance impact of dict rehashing and make it shorter. (#12899) · 5358bd7c
      Roshan Khatri authored
      
      
      #### Problem Statement:
      For any read/update operation during rehashing, we're doing ~10+ random
      DRAM lookups to do the rehashing, as we are using the `rehashidx` to
      rehash 10 buckets, whose dict entries most likely aren't cached in the
      CPU or near the bucket we are operating on. If these random bucket are
      empty, the rehashing process during that command execution is skipped.
      
      #### Implementation:
      For reducing the performance recession while dict is rehashing, we
      determine the index at which the key would be stored in the 0th HT, we
      check if that index has already been rehashed, if not we will rehash the
      bucket containing the key and the bucket will be moved from 0th HT to
      the 1st HT.
      
      If the key has already been rehashed, we perform the random access
      bucket rehash (using `rehashidx`) and we again verify if rehashing is
      still ongoing and look up the key in the respective HT.
      
      This ensures rehashing is not skipped in any command call and that we
      rehash a particular bucket or random bucket in each call.
      
      #### Changes in this PR:
      - Added a new method `dictBucketRehash` to perform rehash on a single
      bucket.
      - Helper function `moveKeysInBucketOldtoNew` for `dictRehash` and
      `dictBucketRehash` to move all the keys in a bucket from the old to the
      new hash HT.
      - Helper function `verifyMoreRehashRequired` for `dictRehash` and
      `dictBucketRehash` to check if we have already rehashed the whole table
      and if more rehashing is required.
      
      ### Benchmark:
      - This PR still shows **~13%** improvement in the latency during
      rehashing.
      
      - Rehashing is now **~2%** faster for this PR when compared to unstable.
      
      ---------
      Co-authored-by: default avatarOran Agra <oran@redislabs.com>
      Co-authored-by: default avatarMadelyn Olson <34459052+madolson@users.noreply.github.com>
      5358bd7c
  5. 19 Jan, 2024 1 commit
    • Yanqi Lv's avatar
      Change the threshold of dict expand, shrink and rehash (#12948) · b07174af
      Yanqi Lv authored
      Before this change (most recently modified in
      https://github.com/redis/redis/pull/12850#discussion_r1421406393), The
      trigger for normal expand threshold was 100% utilization and the trigger
      for normal shrink threshold was 10% (HASHTABLE_MIN_FILL).
      While during fork (DICT_RESIZE_AVOID), when we want to avoid rehash, the
      trigger thresholds were multiplied by 5 (`dict_force_resize_ratio`),
      meaning 500% for expand and 2% (100/10/5) for shrink.
      
      However, in `dictRehash` (the incremental rehashing), the rehashing
      threshold for shrinking during fork (DICT_RESIZE_AVOID) was 20% by
      mistake.
      This meant that if a shrinking is triggered when `dict_can_resize` is
      `DICT_RESIZE_ENABLE` which the threshold is 10%, the rehashing can
      continue when `dict_can_resize` is `DICT_RESIZE_AVOID`.
      This would cause unwanted CopyOnWrite damage.
      
      It'll make sense to change the thresholds of the rehash trigger and the
      thresholds of the incremental rehashing the same, however, in one we
      compare the size of the hash table to the number of records, and in the
      other we compare the size of ht[0] to the size of ht[1], so the formula
      is not exactly the same.
      
      to make things easier we change all the thresholds to powers of 2, so
      the normal shrinking threshold is changed from 100/10 (i.e. 10%) to
      100/8 (i.e. 12.5%), and we change the threshold during forks from 5 to
      4, i.e. from 500% to 400% for expand, and from 2% (100/10/5) to 3.125%
      (100/8/4)
      b07174af
  6. 18 Jan, 2024 3 commits
    • Chen Tianjie's avatar
      Optimize dictTypeResizeAllowed to avoid mistaken OOM judgement. (#12950) · f81c3fd8
      Chen Tianjie authored
      When doing dict resizing, dictTypeResizeAllowed is used to judge whether
      the new allocated memory for rehashing would cause OOM.
      
      However when shrinking, we alloc `_dictNextExp(d->ht_used[0])` bytes of
      memory, while in `dictTypeResizeAllowed` we still use
      `_dictNextExp(d->ht_used[0]+1)` as the new allocated memory size. This
      will overestimate the memory used by shrinking at special conditions,
      causing a false OOM judgement.
      f81c3fd8
    • Binbin's avatar
      Fix minor memory leaks in dictTest (#12962) · 1c7eb0ad
      Binbin authored
      Introduced in #12952, reported by valgrind.
      1c7eb0ad
    • Binbin's avatar
      Fix dict resize ratio checks, avoid precision loss from integer division (#12952) · 14b1edfd
      Binbin authored
      In the past we used integers to compare ratios, let us assume that
      we have the following data in expanding:
      ```
      used / size > 5
      `80 / 16 > 5` is false
      `81 / 16 > 5` is false
      `95 / 16 > 5` is false
      `96 / 16 > 5` is true
      ```
      
      Because the integer result is rounded, our resize breaks the ratio
      constraint, this has existed since the beginning, which resulted in
      us not strictly following the ratio (shrink also has the same issue).
      
      This PR change it to multiplication to avoid floating point
      calculations.
      14b1edfd
  7. 15 Jan, 2024 2 commits
    • Binbin's avatar
      Updated comments on dictResizeEnable for new dict shrink (#12946) · ecc31bc6
      Binbin authored
      The new shrink was added in #12850.
      Also updated outdated comments, see #11692.
      ecc31bc6
    • Yanqi Lv's avatar
      Shrink dict when deleting dictEntry (#12850) · e2b7932b
      Yanqi Lv authored
      When we insert entries into dict, it may autonomously expand if needed.
      However, when we delete entries from dict, it doesn't shrink to the
      proper size. If there are few entries in a very large dict, it may cause
      huge waste of memory and inefficiency when iterating.
      
      The main keyspace dicts (keys and expires), are shrinked by cron
      (`tryResizeHashTables` calls `htNeedsResize` and `dictResize`),
      And some data structures such as zset and hash also do that (call
      `htNeedsResize`) right after a loop of calls to `dictDelete`,
      But many other dicts are completely missing that call (they can only
      expand).
      
      In this PR, we provide the ability to automatically shrink the dict when
      deleting. The conditions triggering the shrinking is the same as
      `htNeedsResize` used to have. i.e. we expand when we're over 100%
      utilization, and shrink when we're below 10% utilization.
      
      Additionally:
      * Add `dictPauseAutoResize` so that flows that do mass deletions, will
      only trigger shrinkage at the end.
      * Rename `dictResize` to `dictShrinkToFit` (same logic as it used to
      have, but better name describing it)
      * Rename `_dictExpand` to `_dictResize` (same logic as it used to have,
      but better name describing it)
       
      related to discussion
      https://github.com/redis/redis/pull/12819#discussion_r1409293878
      
      
      
      ---------
      Co-authored-by: default avatarOran Agra <oran@redislabs.com>
      Co-authored-by: default avatarzhaozhao.zz <zhaozhao.zz@alibaba-inc.com>
      e2b7932b
  8. 15 Dec, 2023 1 commit
    • zhaozhao.zz's avatar
      Unified db rehash method for both standalone and cluster (#12848) · d8a21c57
      zhaozhao.zz authored
      After #11695, we added two functions `rehashingStarted` and
      `rehashingCompleted` to the dict structure. We also registered two
      handlers for the main database's dict and expire structures. This allows
      the main database to record the dict in `rehashing` list when rehashing
      starts. Later, in `serverCron`, the `incrementallyRehash` function is
      continuously called to perform the rehashing operation. However,
      currently, when rehashing is completed, `rehashingCompleted` does not
      remove the dict from the `rehashing` list. This results in the
      `rehashing` list containing many invalid dicts. Although subsequent cron
      checks and removes dicts that don't require rehashing, it is still
      inefficient.
      
      This PR implements the functionality to remove the dict from the
      `rehashing` list in `rehashingCompleted`. This is achieved by adding
      `metadata` to the dict structure, which keeps track of its position in
      the `rehashing` list, allowing for quick removal. This approach avoids
      storing duplicate dicts in the `rehashing` list.
      
      Additionally, there are other modifications:
      
      1. Whether in standalone or cluster mode, the dict in database is
      inserted into the rehashing linked list when rehashing starts. This
      eliminates the need to distinguish between standalone and cluster mode
      in `incrementallyRehash`. The function only needs to focus on the dicts
      in the `rehashing` list that require rehashing.
      2. `rehashing` list is moved from per-database to Redis server level.
      This decouples `incrementallyRehash` from the database ID, and in
      standalone mode, there is no need to iterate over all databases,
      avoiding unnecessary access to databases that do not require rehashing.
      In the future, even if unsharded-cluster mode supports multiple
      databases, there will be no risk involved.
      3. The insertion and removal operations of dict structures in the
      `rehashing` list are decoupled from `activerehashing` config.
      `activerehashing` only controls whether `incrementallyRehash` is
      executed in serverCron. There is no need for additional steps when
      modifying the `activerehashing` switch, as in #12705.
      d8a21c57
  9. 10 Dec, 2023 1 commit
    • Binbin's avatar
      Fix rehashingStarted miscalculating bucket_count in dict initialization (#12846) · e6423b7a
      Binbin authored
      In the old dictRehashingInfo implementation, for the initialization
      scenario,
      it mistakenly directly set to_size to DICTHT_SIZE(DICT_HT_INITIAL_EXP),
      which
      is 4 in our code by default.
      
      In scenarios where dictExpand directly passes the target size as
      initialization,
      the code will calculate bucket_count incorrectly. For example, in DEBUG
      POPULATE
      or RDB load scenarios, it will cause the final bucket_count to be
      initialized to
      65536 (16384 * 4), see:
      ```
      before:
      DB 0: 10000000 keys (0 volatile) in 65536 slots HT.
      
      it should be:
      DB 0: 10000000 keys (0 volatile) in 16777216 slots HT.
      ```
      
      In PR, new ht will also be initialized before calling rehashingStarted
      in
      _dictExpand, so that the calls in dictRehashingInfo can be unified.
      
      Bug was introduced in #12697.
      e6423b7a
  10. 08 Dec, 2023 1 commit
    • Yanqi Lv's avatar
      Optimize dictExpand of empty dict (#12847) · 15b993f1
      Yanqi Lv authored
      If a dict is empty before `dictExpand`, we don't need to do rehashing
      actually. We can just create a new dict and set it as ht_table[0] to
      skip incremental rehashing and free the memory quickly.
      15b993f1
  11. 30 Nov, 2023 1 commit
  12. 29 Nov, 2023 1 commit
    • Binbin's avatar
      Use CLZ in _dictNextExp to get the next power of two (#12815) · 22cc9b51
      Binbin authored
      In the past, we did not call _dictNextExp frequently. It was only
      called when the dictionary was expanded.
      
      Later, dictTypeExpandAllowed was introduced in #7954, which is 6.2.
      For the data dict and the expire dict, we can check maxmemory before
      actually expanding the dict. This is a good optimization to avoid
      maxmemory being exceeded due to the dict expansion.
      
      And in #11692, we moved the dictTypeExpandAllowed check before the
      threshold check, this caused a bit of performance degradation, every
      time a key is added to the dict, dictTypeExpandAllowed is called to
      check.
      
      The main reason for degradation is that in a large dict, we need to
      call _dictNextExp frequently, that is, every time we add a key, we
      need to call _dictNextExp once. Then the threshold is checked to see
      if the dict needs to be expanded. We can see that the order of checks
      here can be optimized.
      
      So we moved the dictTypeExpandAllowed check back to after the threshold
      check in #12789. In this way, before the dict is actually expanded (that
      is, before the threshold is reached), we will not do anything extra
      compared to before, that is, we will not call _dictNextExp frequently.
      
      But note we'll still hit the degradation when we over the thresholds.
      When the threshold is reached, because #7954, we may delay the dict
      expansion due to maxmemory limitations. In this case, we will call
      _dictNextExp every time we add a key during this period.
      
      This PR use CLZ in _dictNextExp to get the next power of two. CLZ (count
      leading zeros) can easily give you the next power of two. It should be
      noted that we have actually introduced the use of __builtin_clzl in
      #8687,
      which is 7.0. So i suppose all the platforms we use have it (even if the
      CPU doesn't have an instruction).
      
      We build 67108864 (2**26) keys through DEBUG POPULTE, which will use
      approximately 5.49G memory (used_memory:5898522936). If expansion is
      triggered, the additional hash table will consume approximately 1G
      memory (2 ** 27 * 8). So we set maxmemory to 6871947673 (that is, 6.4G),
      which will be less than 5.49G + 1G, so we will delay the dict rehash
      while addint the keys.
      
      After that, each time an element is added to the dict, an allow check
      will be performed, that is, we can frequently call _dictNextExp to test
      the comparison before and after the optimization. Using DEBUG HTSTATS 0
      to
      check and make sure that our dict expansion is dealyed.
      
      Using `./src/redis-server redis.conf --save "" --maxmemory 6871947673`.
      Using `./src/redis-benchmark -P 100 -r 1000000000 -t set -n 5000000`.
      After ten rounds of testing:
      ```
      unstable:           this PR:
      769585.94           816860.00
      771724.00           818196.69
      775674.81           822368.44
      781983.12           822503.69
      783576.25           828088.75
      784190.75           828637.75
      791389.69           829875.50
      794659.94           835660.69
      798212.00           830013.25
      801153.62           833934.56
      ```
      
      We can see there is about 4-5% performance improvement in this case.
      22cc9b51
  13. 22 Nov, 2023 1 commit
    • Binbin's avatar
      Optimize dict expand check, move allow check after the thresholds check (#12789) · 46347693
      Binbin authored
      dictExpandAllowed (for the main db dict and the expire dict) seems to
      involve a few function calls and memory accesses, and we can do it only
      after the thresholds checks and can get some performance improvements.
      
      A simple benchmark test: there are 11032768 fixed keys in the database,
      start a redis-server with `--maxmemory big_number --save ""`,
      start a redis-benchmark with `-P 100 -r 1000000000 -t set -n 5000000`,
      collect `throughput summary: n requests per second` result.
      
      After five rounds of testing:
      ```
      unstable     this PR
      848032.56    897988.56
      854408.69    913408.88
      858663.94    914076.81
      871839.56    916758.31
      882612.56    920640.75
      ```
      
      We can see a 5% performance improvement in general condition.
      But note we'll still hit the degradation when we over the thresholds.
      46347693
  14. 31 Oct, 2023 1 commit
  15. 27 Oct, 2023 1 commit
    • Harkrishn Patro's avatar
      Reduce dbBuckets operation time complexity from O(N) to O(1) (#12697) · 4145d628
      Harkrishn Patro authored
      
      
      As part of #11695 independent dictionaries were introduced per slot.
      Time complexity to discover total no. of buckets across all dictionaries
      increased to O(N) with straightforward implementation of iterating over
      all dictionaries and adding dictBuckets of each.
      
      To optimize the time complexity, we could maintain a global counter at
      db level to keep track of the count of buckets and update it on the start
      and end of rehashing.
      
      ---------
      Co-authored-by: default avatarRoshan Khatri <rvkhatri@amazon.com>
      4145d628
  16. 15 Oct, 2023 1 commit
    • Vitaly's avatar
      Replace cluster metadata with slot specific dictionaries (#11695) · 0270abda
      Vitaly authored
      This is an implementation of https://github.com/redis/redis/issues/10589
      
       that eliminates 16 bytes per entry in cluster mode, that are currently used to create a linked list between entries in the same slot.  Main idea is splitting main dictionary into 16k smaller dictionaries (one per slot), so we can perform all slot specific operations, such as iteration, without any additional info in the `dictEntry`. For Redis cluster, the expectation is that there will be a larger number of keys, so the fixed overhead of 16k dictionaries will be The expire dictionary is also split up so that each slot is logically decoupled, so that in subsequent revisions we will be able to atomically flush a slot of data.
      
      ## Important changes
      * Incremental rehashing - one big change here is that it's not one, but rather up to 16k dictionaries that can be rehashing at the same time, in order to keep track of them, we introduce a separate queue for dictionaries that are rehashing. Also instead of rehashing a single dictionary, cron job will now try to rehash as many as it can in 1ms.
      * getRandomKey - now needs to not only select a random key, from the random bucket, but also needs to select a random dictionary. Fairness is a major concern here, as it's possible that keys can be unevenly distributed across the slots. In order to address this search we introduced binary index tree). With that data structure we are able to efficiently find a random slot using binary search in O(log^2(slot count)) time.
      * Iteration efficiency - when iterating dictionary with a lot of empty slots, we want to skip them efficiently. We can do this using same binary index that is used for random key selection, this index allows us to find a slot for a specific key index. For example if there are 10 keys in the slot 0, then we can quickly find a slot that contains 11th key using binary search on top of the binary index tree.
      * scan API - in order to perform a scan across the entire DB, the cursor now needs to not only save position within the dictionary but also the slot id. In this change we append slot id into LSB of the cursor so it can be passed around between client and the server. This has interesting side effect, now you'll be able to start scanning specific slot by simply providing slot id as a cursor value. The plan is to not document this as defined behavior, however. It's also worth nothing the SCAN API is now technically incompatible with previous versions, although practically we don't believe it's an issue.
      * Checksum calculation optimizations - During command execution, we know that all of the keys are from the same slot (outside of a few notable exceptions such as cross slot scripts and modules). We don't want to compute the checksum multiple multiple times, hence we are relying on cached slot id in the client during the command executions. All operations that access random keys, either should pass in the known slot or recompute the slot. 
      * Slot info in RDB - in order to resize individual dictionaries correctly, while loading RDB, it's not enough to know total number of keys (of course we could approximate number of keys per slot, but it won't be precise). To address this issue, we've added additional metadata into RDB that contains number of keys in each slot, which can be used as a hint during loading.
      * DB size - besides `DBSIZE` API, we need to know size of the DB in many places want, in order to avoid scanning all dictionaries and summing up their sizes in a loop, we've introduced a new field into `redisDb` that keeps track of `key_count`. This way we can keep DBSIZE operation O(1). This is also kept for O(1) expires computation as well.
      
      ## Performance
      This change improves SET performance in cluster mode by ~5%, most of the gains come from us not having to maintain linked lists for keys in slot, non-cluster mode has same performance. For workloads that rely on evictions, the performance is similar because of the extra overhead for finding keys to evict. 
      
      RDB loading performance is slightly reduced, as the slot of each key needs to be computed during the load.
      
      ## Interface changes
      * Removed `overhead.hashtable.slot-to-keys` to `MEMORY STATS`
      * Scan API will now require 64 bits to store the cursor, even on 32 bit systems, as the slot information will be stored.
      * New RDB version to support the new op code for SLOT information. 
      
      ---------
      Co-authored-by: default avatarVitaly Arbuzov <arvit@amazon.com>
      Co-authored-by: default avatarHarkrishn Patro <harkrisp@amazon.com>
      Co-authored-by: default avatarRoshan Khatri <rvkhatri@amazon.com>
      Co-authored-by: default avatarMadelyn Olson <madelyneolson@gmail.com>
      Co-authored-by: default avatarOran Agra <oran@redislabs.com>
      0270abda
  17. 16 Aug, 2023 1 commit
    • WangYu's avatar
      skip the rehashed entries in dictNext (#12386) · 17904780
      WangYu authored
      
      
      If dict is rehashing, the  entries in the head of table[0] is moved to table[1]
      and all entries in `table[0][0:rehashidx]` is NULL.
      
      `dictNext` start looking for non-NULL entry from table 0 index 0, and the first call
      of `dictNext` on a rehashing dict will Iterate many times to skip those NULL entries.
      We can easily skip those entries by setting `iter->index` as `iter->d->rehashidx` when
      dict is rehashing and it's the first call of dictNext (`iter->index == -1 && iter->table == 0`).
      Co-authored-by: default avatarsundb <sundbcn@gmail.com>
      17904780
  18. 16 Jun, 2023 1 commit
    • sundb's avatar
      Use Reservoir Sampling for random sampling of dict, and fix hang during fork (#12276) · b00a2351
      sundb authored
      
      
      ## Issue:
      When a dict has a long chain or the length of the chain is longer than
      the number of samples, we will never be able to sample the elements
      at the end of the chain using dictGetSomeKeys().
      This could mean that SRANDMEMBER can be hang in and endless loop.
      The most severe case, is the pathological case of when someone uses SCAN+DEL
      or SSCAN+SREM creating an unevenly distributed dict.
      This was amplified by the recent change in #11692 which prevented a
      down-sizing rehashing while there is a fork.
      
      ## Solution
      1. Before, we will stop sampling when we reach the maximum number
        of samples, even if there is more data after the current chain.
        Now when we reach the maximum we use the Reservoir Sampling
        algorithm to fairly sample the end of the chain that cannot be sampled
      2. Fix the rehashing code, so that the same as it allows rehashing for up-sizing
        during fork when the ratio is extreme, it will allow it for down-sizing as well.
      
      Issue was introduced (or became more severe) by #11692
      Co-authored-by: default avatarOran Agra <oran@redislabs.com>
      b00a2351
  19. 24 May, 2023 1 commit
    • Oran Agra's avatar
      Make a light weight version (default) of DEBUG HTSTATS (#12212) · 3ca451c4
      Oran Agra authored
      The light version only shows the table sizes, while the pre-existing
      version that shows chain length stats is reachable with the `full` argument.
      
      This should allow looking into rehashing state, even on huge dicts, on
      which we're afraid to run the command for fear of causing a server freeze.
      
      Also, fix a possible overflow in dictGetStats.
      3ca451c4
  20. 18 Apr, 2023 1 commit
  21. 20 Jan, 2023 1 commit
    • Viktor Söderqvist's avatar
      Key as dict entry - memory optimization for sets (#11595) · f3f6f7c0
      Viktor Söderqvist authored
      If a dict has only keys, and no use of values, then a key can be stored directly in a
      dict's hashtable. The key replaces the dictEntry. To distinguish between a key and
      a dictEntry, we only use this optimization if the key is odd, i.e. if the key has the least
      significant bit set. This is true for sds strings, since the sds header is always an odd
      number of bytes.
      
      Dict entries are used as a fallback when there is a hash collision. A special dict entry
      without a value (only key and next) is used so we save one word in this case too.
      
      This saves 24 bytes per set element for larges sets, and also gains some speed improvement
      as a side effect (less allocations and cache misses).
      
      A quick test adding 1M elements to a set using the command below resulted in memory
      usage of 28.83M, compared to 46.29M on unstable.
      That's 18 bytes per set element on average.
      
          eval 'for i=1,1000000,1 do redis.call("sadd", "myset", "x"..i) end' 0
      
      Other changes:
      
      Allocations are ensured to have at least 8 bits alignment on all systems. This affects 32-bit
      builds compiled without HAVE_MALLOC_SIZE (not jemalloc or glibc) in which Redis
      stores the size of each allocation, after this change in 8 bytes instead of previously 4 bytes
      per allocation. This is done so we can reliably use the 3 least significant bits in a pointer to
      encode stuff.
      f3f6f7c0
  22. 11 Jan, 2023 3 commits
    • Viktor Söderqvist's avatar
      Remove the bucket-cb from dictScan and move dictEntry defrag to dictScanDefrag · b60d33c9
      Viktor Söderqvist authored
      This change deletes the dictGetNext and dictGetNextRef functions, so the
      dict API doesn't expose the next field at all.
      
      The bucket function in dictScan is deleted. A separate dictScanDefrag function
      is added which takes a defrag alloc function to defrag-reallocate the dict entries.
      
      "Dirty" code accessing the dict internals in active defrag is removed.
      
      An 'afterReplaceEntry' is added to dictType, which allows the dict user
      to keep the dictEntry metadata up to date after reallocation/defrag/move.
      
      Additionally, for updating the cluster slot-to-key mapping, after a dictEntry
      has been reallocated, we need to know which db a dict belongs to, so we store
      a pointer to the db in a new metadata section in the dict struct, which is
      a new mechanism similar to dictEntry metadata. This adds some complexity but
      provides better isolation.
      b60d33c9
    • Viktor Söderqvist's avatar
      activeDefragSdsDict use scan instead of iterator and drop dictSetNext · d4e9e0ae
      Viktor Söderqvist authored
      Also delete unused function activeDefragSdsListAndDict
      d4e9e0ae
    • Viktor Söderqvist's avatar
      Make dictEntry opaque · c84248b5
      Viktor Söderqvist authored
      Use functions for all accesses to dictEntry (except in dict.c). Dict abuses
      e.g. in defrag.c have been replaced by support functions provided by dict.
      c84248b5
  23. 10 Jan, 2023 1 commit
  24. 30 Nov, 2022 1 commit
    • Huang Zhw's avatar
      Add a special notification unlink available only for modules (#9406) · c8181314
      Huang Zhw authored
      
      
      Add a new module event `RedisModule_Event_Key`, this event is fired
      when a key is removed from the keyspace.
      The event includes an open key that can be used for reading the key before
      it is removed. Modules can also extract the key-name, and use RM_Open
      or RM_Call to access key from within that event, but shouldn't modify anything
      from within this event.
      
      The following sub events are available:
        - `REDISMODULE_SUBEVENT_KEY_DELETED`
        - `REDISMODULE_SUBEVENT_KEY_EXPIRED`
        - `REDISMODULE_SUBEVENT_KEY_EVICTED`
        - `REDISMODULE_SUBEVENT_KEY_OVERWRITE`
      
      The data pointer can be casted to a RedisModuleKeyInfo structure
      with the following fields:
      ```
           RedisModuleKey *key;    // Opened Key
       ```
      
      ### internals
      
      * We also add two dict functions:
        `dictTwoPhaseUnlinkFind` finds an element from the table, also get the plink of the entry.
        The entry is returned if the element is found. The user should later call `dictTwoPhaseUnlinkFree`
        with it in order to unlink and release it. Otherwise if the key is not found, NULL is returned.
        These two functions should be used in pair. `dictTwoPhaseUnlinkFind` pauses rehash and
        `dictTwoPhaseUnlinkFree` resumes rehash.
      * We change `dbOverwrite` to `dbReplaceValue` which just replaces the value of the key and
        doesn't fire any events. The "overwrite" part (which emits events) is just when called from `setKey`,
        the other places that called dbOverwrite were ones that just update the value in-place (INCR*, SPOP,
        and dbUnshareStringValue). This should not have any real impact since `moduleNotifyKeyUnlink` and
        `signalDeletedKeyAsReady` wouldn't have mattered in these cases anyway (i.e. module keys and
        stream keys didn't have direct calls to dbOverwrite)
      * since we allow doing RM_OpenKey from withing these callbacks, we temporarily disable lazy expiry.
      * We also temporarily disable lazy expiry when we are in unlink/unlink2 callback and keyspace 
        notification callback.
      * Move special definitions to the top of redismodule.h
        This is needed to resolve compilation errors with RedisModuleKeyInfoV1
        that carries a RedisModuleKey member.
      Co-authored-by: default avatarOran Agra <oran@redislabs.com>
      c8181314
  25. 26 Nov, 2022 1 commit
    • Viktor Söderqvist's avatar
      Shrink dict without rehashing (#11540) · abf70309
      Viktor Söderqvist authored
      When we're shrinking the hash table, we don't need to hash the keys. 
      Since the table sizes are powers of two, we can simply mask the bucket 
      index in the larger table to get the bucket index in the smaller table. We 
      avoid loading the keys into memory and save CPU time.
      abf70309
  26. 08 Sep, 2022 1 commit
  27. 18 Jul, 2022 1 commit
    • ranshid's avatar
      Avoid using unsafe C functions (#10932) · eacca729
      ranshid authored
      replace use of:
      sprintf --> snprintf
      strcpy/strncpy  --> redis_strlcpy
      strcat/strncat  --> redis_strlcat
      
      **why are we making this change?**
      Much of the code uses some unsafe variants or deprecated buffer handling
      functions.
      While most cases are probably not presenting any issue on the known path
      programming errors and unterminated strings might lead to potential
      buffer overflows which are not covered by tests.
      
      **As part of this PR we change**
      1. added implementation for redis_strlcpy and redis_strlcat based on the strl implementation: https://linux.die.net/man/3/strl
      2. change all occurrences of use of sprintf with use of snprintf
      3. change occurrences of use of  strcpy/strncpy with redis_strlcpy
      4. change occurrences of use of strcat/strncat with redis_strlcat
      5. change the behavior of ll2string/ull2string/ld2string so that it will always place null
        termination ('\0') on the output buffer in the first index. this was done in order to make
        the use of these functions more safe in cases were the user will not check the output
        returned by them (for example in rdbRemoveTempFile)
      6. we added a compiler directive to issue a deprecation error in case a use of
        sprintf/strcpy/strcat is found during compilation which will result in error during compile time.
        However keep in mind that since the deprecation attribute is not supported on all compilers,
        this is expected to fail during push workflows.
      
      
      **NOTE:** while this is only an initial milestone. We might also consider
      using the *_s implementation provided by the C11 Extensions (however not
      yet widly supported). I would also suggest to start
      looking at static code analyzers to track unsafe use cases.
      For example LLVM clang checker supports security.insecureAPI.DeprecatedOrUnsafeBufferHandling
      which can help locate unsafe function usage.
      https://clang.llvm.org/docs/analyzer/checkers.html#security-insecureapi-deprecatedorunsafebufferhandling-c
      The main reason not to onboard it at this stage is that the alternative
      excepted by clang is to use the C11 extensions which are not always
      supported by stdlib.
      eacca729
  28. 14 Jun, 2022 1 commit
  29. 19 Dec, 2021 1 commit
    • Binbin's avatar
      Fix some nonsense came from LGTM (#9962) · 0fb1aa06
      Binbin authored
      1. Local variable 's' hides a parameter of the same name.
      ```
      int anetTcpAccept(char *err, int s, char *ip, size_t ip_len, int *port) {
          if ((fd = anetGenericAccept(err,s,(struct sockaddr*)&sa,&salen)) == ANET_ERR){}
      }
      ```
      Change the parameter name from `s` to `serversock`,
      also unified with the header file definition.
      
      2. Comparison is always false because i <= 48.
      ```
      for (i = 0; i < DICT_STATS_VECTLEN-1; i++) {  // i < 49
          (i == DICT_STATS_VECTLEN-1)?">= ":"",  // i == 49
      }
      ```
      `i == DICT_STATS_VECTLEN-1` always result false, it is a dead code.
      
      3. Empty block without comment.
      `else if (!strcasecmp(opt,"ch")) {}`, add a comment to avoid warnings.
      
      4. Bit field fill of type int should have explicitly unsigned integral, explicitly signed integral, or enumeration type.
      Modify `int fill: QL_FILL_BITS;` to `unsigned int fill: QL_FILL_BITS;`
      
      5. The result of this call to reconnectingRedisCommand is not checked for null, but 80% of calls to reconnectingRedisCommand check for null.
      Just a cleanup job like others.
      0fb1aa06
  30. 13 Dec, 2021 1 commit
    • yoav-steinberg's avatar
      Fix possible int overflow when hashing an sds. (#9916) · c7dc17fc
      yoav-steinberg authored
      This caused a crash when adding elements larger than 2GB to a set (same goes for hash keys). See #8455.
      
      Details:
      * The fix makes the dict hash functions receive a `size_t` instead of an `int`. In practice the dict hash functions
        call siphash which receives a `size_t` and the callers to the hash function pass a `size_t` to it so the fix is trivial.
      * The issue was recreated by attempting to add a >2gb value to a set. Appropriate tests were added where I create
        a set with large elements and check basic functionality on it (SADD, SCARD, SPOP, etc...).
      * When I added the tests I also refactored a bit all the tests code which is run under the `--large-memory` flag.
        This removed code duplication for the test framework's `write_big_bulk` and `write_big_bulk` code and also takes
        care of not allocating the test frameworks helper huge string used by these tests when not run under `--large-memory`.
      * I also added the _violoations.tcl_ unit tests to be part of the entire test suite and leaned up non relevant list related
        tests that were in there. This was done in this PR because most of the _violations_ tests are "large memory" tests.
      c7dc17fc
  31. 07 Dec, 2021 1 commit
  32. 16 Nov, 2021 1 commit
  33. 11 Nov, 2021 1 commit
    • Ozan Tezcan's avatar
      Add sanitizer support and clean up sanitizer findings (#9601) · b91d8b28
      Ozan Tezcan authored
      - Added sanitizer support. `address`, `undefined` and `thread` sanitizers are available.  
      - To build Redis with desired sanitizer : `make SANITIZER=undefined`
      - There were some sanitizer findings, cleaned up codebase
      - Added tests with address and undefined behavior sanitizers to daily CI.
      - Added tests with address sanitizer to the per-PR CI (smoke out mem leaks sooner).
      
      Basically, there are three types of issues : 
      
      **1- Unaligned load/store** : Most probably, this issue may cause a crash on a platform that
      does not support unaligned access. Redis does unaligned access only on supported platforms.
      
      **2- Signed integer overflow.** Although, signed overflow issue can be problematic time to time
      and change how compiler generates code, current findings mostly about signed shift or simple
      addition overflow. For most platforms Redis can be compiled for, this wouldn't cause any issue
      as far as I can tell (checked generated code on godbolt.org).
      
       **3 -Minor leak** (redis-cli), **use-after-free**(just before calling exit());
      
      UB means nothing guaranteed and risky to reason about program behavior but I don't think any
      of the fixes here worth backporting. As sanitizers are now part of the CI, preventing new issues
      will be the real benefit. 
      b91d8b28
  34. 31 Aug, 2021 1 commit
    • Viktor Söderqvist's avatar
      Slot-to-keys using dict entry metadata (#9356) · f24c63a2
      Viktor Söderqvist authored
      
      
      * Enhance dict to support arbitrary metadata carried in dictEntry
      Co-authored-by: default avatarViktor Söderqvist <viktor.soderqvist@est.tech>
      
      * Rewrite slot-to-keys mapping to linked lists using dict entry metadata
      
      This is a memory enhancement for Redis Cluster.
      
      The radix tree slots_to_keys (which duplicates all key names prefixed with their
      slot number) is replaced with a linked list for each slot. The dict entries of
      the same cluster slot form a linked list and the pointers are stored as metadata
      in each dict entry of the main DB dict.
      
      This commit also moves the slot-to-key API from db.c to cluster.c.
      Co-authored-by: default avatarJim Brunner <brunnerj@amazon.com>
      f24c63a2
  35. 15 Aug, 2021 1 commit