1. 03 Nov, 2021 2 commits
    • guybe7's avatar
      Fix COMMAND GETKEYS on EVAL without keys (#9733) · f11a2d4d
      guybe7 authored
      Add new no-mandatory-keys flag to support COMMAND GETKEYS of commands
      which have no mandatory keys.
      
      In the past we would have got this error:
      ```
      127.0.0.1:6379> command getkeys eval "return 1" 0
      (error) ERR Invalid arguments specified for command
      ```
      f11a2d4d
    • perryitay's avatar
      fix: lookupKey on SETNX and SETXX only once (#9640) · 77d3c6bf
      perryitay authored
      When using SETNX and SETXX we could end up doing key lookup twice.
      This presents a small inefficiency price.
      Also once we have statistics of write hit and miss they'll be wrong (recording the same key hit twice) 
      77d3c6bf
  2. 02 Nov, 2021 1 commit
    • zhaozhao.zz's avatar
      rebuild replication backlog index when master restart (#9720) · d08f0552
      zhaozhao.zz authored
      After PR #9166 , replication backlog is not a real block of memory, just contains a
      reference points to replication buffer's block and the blocks index (to accelerate
      search offset when partial sync), so we need update both replication buffer's block's
      offset and replication backlog blocks index's offset when master restart from RDB,
      since the `server.master_repl_offset` is changed.
      The implications of this bug was just a slow search, but not a replication failure.
      d08f0552
  3. 25 Oct, 2021 3 commits
    • Wang Yuan's avatar
      Add timestamp annotations in AOF (#9326) · 9ec3294b
      Wang Yuan authored
      Add timestamp annotation in AOF, one part of #9325.
      
      Enabled with the new `aof-timestamp-enabled` config option.
      
      Timestamp annotation format is "#TS:${timestamp}\r\n"."
      TS" is short of timestamp and this method could save extra bytes in AOF.
      
      We can use timestamp annotation for some special functions. 
      - know the executing time of commands
      - restore data to a specific point-in-time (by using redis-check-rdb to truncate the file)
      9ec3294b
    • Oran Agra's avatar
      Improve code doc of allowed_firstargs following #9504 (#9674) · 085615af
      Oran Agra authored
      Improve code doc for allowed_firstargs (used to be allowed_commands before #9504.
      I don't think the text in the code needs to refer to the history (it's not there just for backwards compatibility).
      instead it should just describe what it does.
      085615af
    • Wang Yuan's avatar
      Replication backlog and replicas use one global shared replication buffer (#9166) · c1718f9d
      Wang Yuan authored
      ## Background
      For redis master, one replica uses one copy of replication buffer, that is a big waste of memory,
      more replicas more waste, and allocate/free memory for every reply list also cost much.
      If we set client-output-buffer-limit small and write traffic is heavy, master may disconnect with
      replicas and can't finish synchronization with replica. If we set  client-output-buffer-limit big,
      master may be OOM when there are many replicas that separately keep much memory.
      Because replication buffers of different replica client are the same, one simple idea is that
      all replicas only use one replication buffer, that will effectively save memory.
      
      Since replication backlog content is the same as replicas' output buffer, now we
      can discard replication backlog memory and use global shared replication buffer
      to implement replication backlog mechanism.
      
      ## Implementation
      I create one global "replication buffer" which...
      c1718f9d
  4. 20 Oct, 2021 1 commit
    • guybe7's avatar
      Treat subcommands as commands (#9504) · 43e736f7
      guybe7 authored
      ## Intro
      
      The purpose is to allow having different flags/ACL categories for
      subcommands (Example: CONFIG GET is ok-loading but CONFIG SET isn't)
      
      We create a small command table for every command that has subcommands
      and each subcommand has its own flags, etc. (same as a "regular" command)
      
      This commit also unites the Redis and the Sentinel command tables
      
      ## Affected commands
      
      CONFIG
      Used to have "admin ok-loading ok-stale no-script"
      Changes:
      1. Dropped "ok-loading" in all except GET (this doesn't change behavior since
      there were checks in the code doing that)
      
      XINFO
      Used to have "read-only random"
      Changes:
      1. Dropped "random" in all except CONSUMERS
      
      XGROUP
      Used to have "write use-memory"
      Changes:
      1. Dropped "use-memory" in all except CREATE and CREATECONSUMER
      
      COMMAND
      No changes.
      
      MEMORY
      Used to have "random read-only"
      Changes:
      1. Dropped "random" in PURGE and USAGE
      
      ACL
      Used to have "admin no-script ok-loading ok-stale"
      Changes:
      1. Dropped "admin" in WHOAMI, GENPASS, and CAT
      
      LATENCY
      No changes.
      
      MODULE
      No changes.
      
      SLOWLOG
      Used to have "admin random ok-loading ok-stale"
      Changes:
      1. Dropped "random" in RESET
      
      OBJECT
      Used to have "read-only random"
      Changes:
      1. Dropped "random" in ENCODING and REFCOUNT
      
      SCRIPT
      Used to have "may-replicate no-script"
      Changes:
      1. Dropped "may-replicate" in all except FLUSH and LOAD
      
      CLIENT
      Used to have "admin no-script random ok-loading ok-stale"
      Changes:
      1. Dropped "random" in all except INFO and LIST
      2. Dropped "admin" in ID, TRACKING, CACHING, GETREDIR, INFO, SETNAME, GETNAME, and REPLY
      
      STRALGO
      No changes.
      
      PUBSUB
      No changes.
      
      CLUSTER
      Changes:
      1. Dropped "admin in countkeysinslots, getkeysinslot, info, nodes, keyslot, myid, and slots
      
      SENTINEL
      No changes.
      
      (note that DEBUG also fits, but we decided not to convert it since it's for
      debugging and anyway undocumented)
      
      ## New sub-command
      This commit adds another element to the per-command output of COMMAND,
      describing the list of subcommands, if any (in the same structure as "regular" commands)
      Also, it adds a new subcommand:
      ```
      COMMAND LIST [FILTERBY (MODULE <module-name>|ACLCAT <cat>|PATTERN <pattern>)]
      ```
      which returns a set of all commands (unless filters), but excluding subcommands.
      
      ## Module API
      A new module API, RM_CreateSubcommand, was added, in order to allow
      module writer to define subcommands
      
      ## ACL changes:
      1. Now, that each subcommand is actually a command, each has its own ACL id.
      2. The old mechanism of allowed_subcommands is redundant
      (blocking/allowing a subcommand is the same as blocking/allowing a regular command),
      but we had to keep it, to support the widespread usage of allowed_subcommands
      to block commands with certain args, that aren't subcommands (e.g. "-select +select|0").
      3. I have renamed allowed_subcommands to allowed_firstargs to emphasize the difference.
      4. Because subcommands are commands in ACL too, you can now use "-" to block subcommands
      (e.g. "+client -client|kill"), which wasn't possible in the past.
      5. It is also possible to use the allowed_firstargs mechanism with subcommand.
      For example: `+config -config|set +config|set|loglevel` will block all CONFIG SET except
      for setting the log level.
      6. All of the ACL changes above required some amount of refactoring.
      
      ## Misc
      1. There are two approaches: Either each subcommand has its own function or all
         subcommands use the same function, determining what to do according to argv[0].
         For now, I took the former approaches only with CONFIG and COMMAND,
         while other commands use the latter approach (for smaller blamelog diff).
      2. Deleted memoryGetKeys: It is no longer needed because MEMORY USAGE now uses the "range" key spec.
      4. Bugfix: GETNAME was missing from CLIENT's help message.
      5. Sentinel and Redis now use the same table, with the same function pointer.
         Some commands have a different implementation in Sentinel, so we redirect
         them (these are ROLE, PUBLISH, and INFO).
      6. Command stats now show the stats per subcommand (e.g. instead of stats just
         for "config" you will have stats for "config|set", "config|get", etc.)
      7. It is now possible to use COMMAND directly on subcommands:
         COMMAND INFO CONFIG|GET (The pipeline syntax was inspired from ACL, and
         can be used in functions lookupCommandBySds and lookupCommandByCString)
      8. STRALGO is now a container command (has "help")
      
      ## Breaking changes:
      1. Command stats now show the stats per subcommand (see (5) above)
      43e736f7
  5. 19 Oct, 2021 2 commits
  6. 17 Oct, 2021 1 commit
  7. 08 Oct, 2021 2 commits
  8. 07 Oct, 2021 1 commit
  9. 06 Oct, 2021 1 commit
    • yoav-steinberg's avatar
      Avoid argv memcpy when queuing a multi command. (#9602) · 5725088f
      yoav-steinberg authored
      When queuing a multi command we duplicated the argv (meaning an alloc
      and a memcpy). This isn't needed since we can use the previously allocated
      argv and just reset the client objects argv to NULL. This should saves some
      memory and is a minor optimization in heavy MULTI/EXEC traffic, especially
      if there are lots of arguments.
      5725088f
  10. 04 Oct, 2021 2 commits
    • Oran Agra's avatar
      Fix ziplist and listpack overflows and truncations (CVE-2021-32627, CVE-2021-32628) (#9589) · c5e6a620
      Oran Agra authored
      
      
      - fix possible heap corruption in ziplist and listpack resulting by trying to
        allocate more than the maximum size of 4GB.
      - prevent ziplist (hash and zset) from reaching size of above 1GB, will be
        converted to HT encoding, that's not a useful size.
      - prevent listpack (stream) from reaching size of above 1GB.
      - XADD will start a new listpack if the new record may cause the previous
        listpack to grow over 1GB.
      - XADD will respond with an error if a single stream record is over 1GB
      - List type (ziplist in quicklist) was truncating strings that were over 4GB,
        now it'll respond with an error.
      Co-authored-by: default avatarsundb <sundbcn@gmail.com>
      c5e6a620
    • Oran Agra's avatar
      Prevent unauthenticated client from easily consuming lots of memory (CVE-2021-32675) (#9588) · fba15850
      Oran Agra authored
      This change sets a low limit for multibulk and bulk length in the
      protocol for unauthenticated connections, so that they can't easily
      cause redis to allocate massive amounts of memory by sending just a few
      characters on the network.
      The new limits are 10 arguments of 16kb each (instead of 1m of 512mb)
      fba15850
  11. 03 Oct, 2021 2 commits
    • yoav-steinberg's avatar
      Remove argument count limit, dynamically grow argv. (#9528) · 93e85347
      yoav-steinberg authored
      Remove hard coded multi-bulk limit (was 1,048,576), new limit is INT_MAX.
      When client sends an m-bulk that's higher than 1024, we initially only allocate
      the argv array for 1024 arguments, and gradually grow that allocation as arguments
      are received.
      93e85347
    • Binbin's avatar
      Cleanup typos, incorrect comments, and fixed small memory leak in redis-cli (#9153) · dd3ac97f
      Binbin authored
      1. Remove forward declarations from header files to functions that do not exist:
      hmsetCommand and rdbSaveTime.
      2. Minor phrasing fixes in #9519
      3. Add missing sdsfree(title) and fix typo in redis-benchmark.
      4. Modify some error comments in some zset commands.
      5. Fix copy-paste bug comment in syncWithMaster about `ip-address`.
      dd3ac97f
  12. 26 Sep, 2021 1 commit
    • yoav-steinberg's avatar
      Client eviction ci issues (#9549) · 66002530
      yoav-steinberg authored
      Fixing CI test issues introduced in #8687
      - valgrind warnings in readQueryFromClient when client was freed by processInputBuffer
      - adding DEBUG pause-cron for tests not to be time dependent.
      - skipping a test that depends on socket buffers / events not compatible with TLS
      - making sure client got subscribed by not using deferring client
      66002530
  13. 23 Sep, 2021 3 commits
    • yoav-steinberg's avatar
      Client eviction (#8687) · 2753429c
      yoav-steinberg authored
      
      
      ### Description
      A mechanism for disconnecting clients when the sum of all connected clients is above a
      configured limit. This prevents eviction or OOM caused by accumulated used memory
      between all clients. It's a complimentary mechanism to the `client-output-buffer-limit`
      mechanism which takes into account not only a single client and not only output buffers
      but rather all memory used by all clients.
      
      #### Design
      The general design is as following:
      * We track memory usage of each client, taking into account all memory used by the
        client (query buffer, output buffer, parsed arguments, etc...). This is kept up to date
        after reading from the socket, after processing commands and after writing to the socket.
      * Based on the used memory we sort all clients into buckets. Each bucket contains all
        clients using up up to x2 memory of the clients in the bucket below it. For example up
        to 1m clients, up to 2m clients, up to 4m clients, ...
      * Before processing a command and before sleep we check if we're over the configured
        limit. If we are we start disconnecting clients from larger buckets downwards until we're
        under the limit.
      
      #### Config
      `maxmemory-clients` max memory all clients are allowed to consume, above this threshold
      we disconnect clients.
      This config can either be set to 0 (meaning no limit), a size in bytes (possibly with MB/GB
      suffix), or as a percentage of `maxmemory` by using the `%` suffix (e.g. setting it to `10%`
      would mean 10% of `maxmemory`).
      
      #### Important code changes
      * During the development I encountered yet more situations where our io-threads access
        global vars. And needed to fix them. I also had to handle keeps the clients sorted into the
        memory buckets (which are global) while their memory usage changes in the io-thread.
        To achieve this I decided to simplify how we check if we're in an io-thread and make it
        much more explicit. I removed the `CLIENT_PENDING_READ` flag used for checking
        if the client is in an io-thread (it wasn't used for anything else) and just used the global
        `io_threads_op` variable the same way to check during writes.
      * I optimized the cleanup of the client from the `clients_pending_read` list on client freeing.
        We now store a pointer in the `client` struct to this list so we don't need to search in it
        (`pending_read_list_node`).
      * Added `evicted_clients` stat to `INFO` command.
      * Added `CLIENT NO-EVICT ON|OFF` sub command to exclude a specific client from the
        client eviction mechanism. Added corrosponding 'e' flag in the client info string.
      * Added `multi-mem` field in the client info string to show how much memory is used up
        by buffered multi commands.
      * Client `tot-mem` now accounts for buffered multi-commands, pubsub patterns and
        channels (partially), tracking prefixes (partially).
      * CLIENT_CLOSE_ASAP flag is now handled in a new `beforeNextClient()` function so
        clients will be disconnected between processing different clients and not only before sleep.
        This new function can be used in the future for work we want to do outside the command
        processing loop but don't want to wait for all clients to be processed before we get to it.
        Specifically I wanted to handle output-buffer-limit related closing before we process client
        eviction in case the two race with each other.
      * Added a `DEBUG CLIENT-EVICTION` command to print out info about the client eviction
        buckets.
      * Each client now holds a pointer to the client eviction memory usage bucket it belongs to
        and listNode to itself in that bucket for quick removal.
      * Global `io_threads_op` variable now can contain a `IO_THREADS_OP_IDLE` value
        indicating no io-threading is currently being executed.
      * In order to track memory used by each clients in real-time we can't rely on updating
        these stats in `clientsCron()` alone anymore. So now I call `updateClientMemUsage()`
        (used to be `clientsCronTrackClientsMemUsage()`) after command processing, after
        writing data to pubsub clients, after writing the output buffer and after reading from the
        socket (and maybe other places too). The function is written to be fast.
      * Clients are evicted if needed (with appropriate log line) in `beforeSleep()` and before
        processing a command (before performing oom-checks and key-eviction).
      * All clients memory usage buckets are grouped as follows:
        * All clients using less than 64k.
        * 64K..128K
        * 128K..256K
        * ...
        * 2G..4G
        * All clients using 4g and up.
      * Added client-eviction.tcl with a bunch of tests for the new mechanism.
      * Extended maxmemory.tcl to test the interaction between maxmemory and
        maxmemory-clients settings.
      * Added an option to flag a numeric configuration variable as a "percent", this means that
        if we encounter a '%' after the number in the config file (or config set command) we
        consider it as valid. Such a number is store internally as a negative value. This way an
        integer value can be interpreted as either a percent (negative) or absolute value (positive).
        This is useful for example if some numeric configuration can optionally be set to a percentage
        of something else.
      Co-authored-by: default avatarOran Agra <oran@redislabs.com>
      2753429c
    • YaacovHazan's avatar
      Adding ACL support for modules (#9309) · a56d4533
      YaacovHazan authored
      This commit introduced a new flag to the RM_Call:
      'C' - Check if the command can be executed according to the ACLs associated with it.
      
      Also, three new API's added to check if a command, key, or channel can be executed or accessed
      by a user, according to the ACLs associated with it.
      - RM_ACLCheckCommandPerm
      - RM_ACLCheckKeyPerm
      - RM_ACLCheckChannelPerm
      
      The user for these API's is a RedisModuleUser object, that for a Module user returned by the RM_CreateModuleUser API, or for a general ACL user can be retrieved by these two new API's:
      - RM_GetCurrentUserName - Retrieve the user name of the client connection behind the current context.
      - RM_GetModuleUserFromUserName - Get a RedisModuleUser from a user name
      
      As a result of getting a RedisModuleUser from name, it can now also access the general ACL users (not just ones created by the module).
      This mean the already existing API RM_SetModuleUserACL(), can be used to change the ACL rules for such users.
      a56d4533
    • Binbin's avatar
      Add ZMPOP/BZMPOP commands. (#9484) · 14d6abd8
      Binbin authored
      This is similar to the recent addition of LMPOP/BLMPOP (#9373), but zset.
      
      Syntax for the new ZMPOP command:
      `ZMPOP numkeys [<key> ...] MIN|MAX [COUNT count]`
      
      Syntax for the new BZMPOP command:
      `BZMPOP timeout numkeys [<key> ...] MIN|MAX [COUNT count]`
      
      Some background:
      - ZPOPMIN/ZPOPMAX take only one key, and can return multiple elements.
      - BZPOPMIN/BZPOPMAX take multiple keys, but return only one element from just one key.
      - ZMPOP/BZMPOP can take multiple keys, and can return multiple elements from just one key.
      
      Note that ZMPOP/BZMPOP can take multiple keys, it eventually operates on just on key.
      And it will propagate as ZPOPMIN or ZPOPMAX with the COUNT option.
      
      As new commands, if we can not pop any elements, the response like:
      - ZMPOP: Return a NIL in both RESP2 and RESP3, unlike ZPOPMIN/ZPOPMAX return emptyarray.
      - BZMPOP: Return a NIL in both RESP2 and RESP3 when timeout is reached, like BZPOPMIN/BZPOPMAX.
      
      For the normal response is nested arrays in RESP2 and RESP3:
      ```
      ZMPOP/BZMPOP
      1) keyname
      2) 1) 1) member1
            2) score1
         2) 1) member2
            2) score2
      
      In RESP2:
      1) "myzset"
      2) 1) 1) "three"
            2) "3"
         2) 1) "two"
            2) "2"
      
      In RESP3:
      1) "myzset"
      2) 1) 1) "three"
            2) (double) 3
         2) 1) "two"
            2) (double) 2
      ```
      14d6abd8
  14. 16 Sep, 2021 1 commit
    • Binbin's avatar
      Adds limit to SINTERCARD/ZINTERCARD. (#9425) · f898a9e9
      Binbin authored
      Implements the [LIMIT limit] variant of SINTERCARD/ZINTERCARD.
      Now with the LIMIT, we can stop the searching when cardinality
      reaching the limit, and return the cardinality ASAP.
      
      Note that in SINTERCARD, the old synatx was: `SINTERCARD key [key ...]`
      In order to add a optional parameter, we must break the old synatx.
      So the new syntax of SINTERCARD will be consistent with ZINTERCARD.
      New syntax: `SINTERCARD numkeys key [key ...] [LIMIT limit]`.
      
      Note that this means that SINTERCARD has a different syntax than
      SINTER and SINTERSTORE (taking numkeys argument)
      
      As for ZINTERCARD, we can easily add a optional parameter to it.
      New syntax: `ZINTERCARD numkeys key [key ...] [LIMIT limit]`
      f898a9e9
  15. 15 Sep, 2021 2 commits
    • guybe7's avatar
      Cleanup: propagate and alsoPropagate do not need redisCommand (#9502) · 7759ec7c
      guybe7 authored
      The `cmd` argument was completely unused, and all the code that bothered to pass it was unnecessary.
      This is a prepartion for a future commit that treats subcommands as commands
      7759ec7c
    • guybe7's avatar
      A better approach for COMMAND INFO for movablekeys commands (#8324) · 03fcc211
      guybe7 authored
      Fix #7297
      
      The problem:
      
      Today, there is no way for a client library or app to know the key name indexes for commands such as
      ZUNIONSTORE/EVAL and others with "numkeys", since COMMAND INFO returns no useful info for them.
      
      For cluster-aware redis clients, this requires to 'patch' the client library code specifically for each of these commands or to
      resolve each execution of these commands with COMMAND GETKEYS.
      
      The solution:
      
      Introducing key specs other than the legacy "range" (first,last,step)
      
      The 8th element of the command info array, if exists, holds an array of key specs. The array may be empty, which indicates
      the command doesn't take any key arguments or may contain one or more key-specs, each one may leads to the discovery
      of 0 or more key arguments.
      
      A client library that doesn't support this key-spec feature will keep using the first,last,step and movablekeys flag which will
      obviously remain unchanged.
      
      A client that supports this key-specs feature needs only to look at the key-specs array. If it finds an unrecognized spec, it
      must resort to using COMMAND GETKEYS if it wishes to get all key name arguments, but if all it needs is one key in order
      to know which cluster node to use, then maybe another spec (if the command has several) can supply that, and there's no
      need to use GETKEYS.
      
      Each spec is an array of arguments, first one is the spec name, the second is an array of flags, and the third is an array
      containing details about the spec (specific meaning for each spec type)
      The initial flags we support are "read" and "write" indicating if the keys that this key-spec finds are used for read or for write.
      clients should ignore any unfamiliar flags.
      
      In order to easily find the positions of keys in a given array of args we introduce keys specs. There are two logical steps of
      key specs:
      1. `start_search`: Given an array of args, indicate where we should start searching for keys
      2. `find_keys`: Given the output of start_search and an array of args, indicate all possible indices of keys.
      
      ### start_search step specs
      - `index`: specify an argument index explicitly
        - `index`: 0 based index (1 means the first command argument)
      - `keyword`: specify a string to match in `argv`. We should start searching for keys just after the keyword appears.
        - `keyword`: the string to search for
        - `start_search`: an index from which to start the keyword search (can be negative, which means to search from the end)
      
      Examples:
      - `SET` has start_search of type `index` with value `1`
      - `XREAD` has start_search of type `keyword` with value `[“STREAMS”,1]`
      - `MIGRATE` has start_search of type `keyword` with value `[“KEYS”,-2]`
      
      ### find_keys step specs
      - `range`: specify `[count, step, limit]`.
        - `lastkey`: index of the last key. relative to the index returned from begin_search. -1 indicating till the last argument, -2 one before the last
        - `step`: how many args should we skip after finding a key, in order to find the next one
        - `limit`: if count is -1, we use limit to stop the search by a factor. 0 and 1 mean no limit. 2 means ½ of the remaining args, 3 means ⅓, and so on.
      - “keynum”: specify `[keynum_index, first_key_index, step]`.
        - `keynum_index`: is relative to the return of the `start_search` spec.
        - `first_key_index`: is relative to `keynum_index`.
        - `step`: how many args should we skip after finding a key, in order to find the next one
      
      Examples:
      - `SET` has `range` of `[0,1,0]`
      - `MSET` has `range` of `[-1,2,0]`
      - `XREAD` has `range` of `[-1,1,2]`
      - `ZUNION` has `start_search` of type `index` with value `1` and `find_keys` of type `keynum` with value `[0,1,1]`
      - `AI.DAGRUN` has `start_search` of type `keyword` with value `[“LOAD“,1]` and `find_keys` of type `keynum` with value
        `[0,1,1]` (see https://oss.redislabs.com/redisai/master/commands/#aidagrun)
      
      Note: this solution is not perfect as the module writers can come up with anything, but at least we will be able to find the key
      args of the vast majority of commands.
      If one of the above specs can’t describe the key positions, the module writer can always fall back to the `getkeys-api` option.
      
      Some keys cannot be found easily (`KEYS` in `MIGRATE`: Imagine the argument for `AUTH` is the string “KEYS” - we will
      start searching in the wrong index). 
      The guarantee is that the specs may be incomplete (`incomplete` will be specified in the spec to denote that) but we never
      report false information (assuming the command syntax is correct).
      For `MIGRATE` we start searching from the end - `startfrom=-1` - and if one of the keys is actually called "keys" we will
      report only a subset of all keys - hence the `incomplete` flag.
      Some `incomplete` specs can be completely empty (i.e. UNKNOWN begin_search) which should tell the client that
      COMMAND GETKEYS (or any other way to get the keys) must be used (Example: For `SORT` there is no way to describe
      the STORE keyword spec, as the word "store" can appear anywhere in the command).
      
      We will expose these key specs in the `COMMAND` command so that clients can learn, on startup, where the keys are for
      all commands instead of holding hardcoded tables or use `COMMAND GETKEYS` in runtime.
      
      Comments:
      1. Redis doesn't internally use the new specs, they are only used for COMMAND output.
      2. In order to support the current COMMAND INFO format (reply array indices 4, 5, 6) we created a synthetic range, called
         legacy_range, that, if possible, is built according to the new specs.
      3. Redis currently uses only getkeys_proc or the legacy_range to get the keys indices (in COMMAND GETKEYS for
         example).
      
      "incomplete" specs:
      the command we have issues with are MIGRATE, STRALGO, and SORT
      for MIGRATE, because the token KEYS, if exists, must be the last token, we can search in reverse. it one of the keys is
      actually the string "keys" will return just a subset of the keys (hence, it's "incomplete")
      for SORT and STRALGO we can use this heuristic (the keys can be anywhere in the command) and therefore we added a
      key spec that is both "incomplete" and of "unknown type"
      
      if a client encounters an "incomplete" spec it means that it must find a different way (either COMMAND GETKEYS or have
      its own parser) to retrieve the keys.
      please note that all commands, apart from the three mentioned above, have "complete" key specs
      03fcc211
  16. 14 Sep, 2021 1 commit
    • Viktor Söderqvist's avatar
      Modules: Add remaining list API functions (#8439) · ea36d4de
      Viktor Söderqvist authored
      List functions operating on elements by index:
      
      * RM_ListGet
      * RM_ListSet
      * RM_ListInsert
      * RM_ListDelete
      
      Iteration is done using a simple for loop over indices.
      The index based functions use an internal iterator as an optimization.
      This is explained in the docs:
      
      ```
       * Many of the list functions access elements by index. Since a list is in
       * essence a doubly-linked list, accessing elements by index is generally an
       * O(N) operation. However, if elements are accessed sequentially or with
       * indices close together, the functions are optimized to seek the index from
       * the previous index, rather than seeking from the ends of the list.
       *
       * This enables iteration to be done efficiently using a simple for loop:
       *
       *     long n = RM_ValueLength(key);
       *     for (long i = 0; i < n; i++) {
       *         RedisModuleString *elem = RedisModule_ListGet(key, i);
       *         // Do stuff...
       *     }
      ```
      ea36d4de
  17. 13 Sep, 2021 1 commit
    • zhaozhao.zz's avatar
      PSYNC2: make partial sync possible after master reboot (#8015) · 794442b1
      zhaozhao.zz authored
      The main idea is how to allow a master to load replication info from RDB file when rebooting, if master can load replication info it means that replicas may have the chance to psync with master, it can save much traffic.
      
      The key point is we need guarantee safety and consistency, so there
      are two differences between master and replica:
      
      1. master would load the replication info as secondary ID and
         offset, in case other masters have the same replid.
      2. when master loading RDB, it would propagate expired keys as DEL
         command to replication backlog, then replica can receive these
         commands to delete stale keys.
         p.s. the expired keys when RDB loading is useful for users, so
         we show it as `rdb_last_load_keys_expired` and `rdb_last_load_keys_loaded` in info persistence.
      
      Moreover, after load replication info, master should update
      `no_replica_time` in case loading RDB cost too long time.
      794442b1
  18. 09 Sep, 2021 3 commits
    • sundb's avatar
      Replace all usage of ziplist with listpack for t_zset (#9366) · 3ca6972e
      sundb authored
      Part two of implementing #8702 (zset), after #8887.
      
      ## Description of the feature
      Replaced all uses of ziplist with listpack in t_zset, and optimized some of the code to optimize performance.
      
      ## Rdb format changes
      New `RDB_TYPE_ZSET_LISTPACK` rdb type.
      
      ## Rdb loading improvements:
      1) Pre-expansion of dict for validation of duplicate data for listpack and ziplist.
      2) Simplifying the release of empty key objects when RDB loading.
      3) Unify ziplist and listpack data verify methods for zset and hash, and move code to rdb.c.
      
      ## Interface changes
      1) New `zset-max-listpack-entries` config is an alias for `zset-max-ziplist-entries` (same with `zset-max-listpack-value`).
      2) OBJECT ENCODING will return listpack instead of ziplist.
      
      ## Listpack improvements:
      1) Add `lpDeleteRange` and `lpDeleteRangeWithEntry` functions to delete a range of entries from listpack.
      2) Improve the performance of `lpCompare`, converting from string to integer is faster than converting from integer to string.
      3) Replace `snprintf` with `ll2string` to improve performance in converting numbers to strings in `lpGet()`.
      
      ## Zset improvements:
      1) Improve the performance of `zzlFind` method, use `lpFind` instead of `lpCompare` in a loop.
      2) Use `lpDeleteRangeWithEntry` instead of `lpDelete` twice to delete a element of zset.
      
      ## Tests
      1) Add some unittests for `lpDeleteRange` and `lpDeleteRangeWithEntry` function.
      2) Add zset RDB loading test.
      3) Add benchmark test for `lpCompare` and `ziplsitCompare`.
      4) Add empty listpack zset corrupt dump test.
      3ca6972e
    • Binbin's avatar
      Add LMPOP/BLMPOP commands. (#9373) · c50af0ae
      Binbin authored
      We want to add COUNT option for BLPOP.
      But we can't do it without breaking compatibility due to the command arguments syntax.
      So this commit introduce two new commands.
      
      Syntax for the new LMPOP command:
      `LMPOP numkeys [<key> ...] LEFT|RIGHT [COUNT count]`
      
      Syntax for the new BLMPOP command:
      `BLMPOP timeout numkeys [<key> ...] LEFT|RIGHT [COUNT count]`
      
      Some background:
      - LPOP takes one key, and can return multiple elements.
      - BLPOP takes multiple keys, but returns one element from just one key.
      - LMPOP can take multiple keys and return multiple elements from just one key.
      
      Note that LMPOP/BLMPOP  can take multiple keys, it eventually operates on just one key.
      And it will propagate as LPOP or RPOP with the COUNT option.
      
      As a new command, it still return NIL if we can't pop any elements.
      For the normal response is nested arrays in RESP2 and RESP3, like:
      ```
      LMPOP/BLMPOP 
      1) keyname
      2) 1) element1
         2) element2
      ```
      I.e. unlike BLPOP that returns a key name and one element so it uses a flat array,
      and LPOP that returns multiple elements with no key name, and again uses a flat array,
      this one has to return a nested array, and it does for for both RESP2 and RESP3 (like SCAN does)
      
      Some discuss can see: #766 #8824
      c50af0ae
    • Huang Zhw's avatar
      Add INFO total_active_defrag_time and current_active_defrag_time (#9377) · 216f168b
      Huang Zhw authored
      Add two INFO metrics:
      ```
      total_active_defrag_time:12345
      current_active_defrag_time:456
      ```
      `current_active_defrag_time` if greater than 0, means how much time has
      passed since active defrag started running. If active defrag stops, this metric is reset to 0.
      `total_active_defrag_time` means total time the fragmentation
      was over the defrag threshold since the server started.
      
      This is a followup PR for #9031
      216f168b
  19. 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
  20. 30 Aug, 2021 1 commit
    • Wang Yuan's avatar
      Use sync_file_range to optimize fsync if possible (#9409) · 9a0c0617
      Wang Yuan authored
      We implement incremental data sync in rio.c by call fsync, on slow disk, that may cost a lot of time,
      sync_file_range could provide async fsync, so we could serialize key/value and sync file data at the same time.
      
      > one tip for sync_file_range usage: http://lkml.iu.edu/hypermail/linux/kernel/1005.2/01845.html
      
      Additionally, this change avoids a single large write to be used, which can result in a mass of dirty
      pages in the kernel (increasing the risk of someone else's write to block).
      
      On HDD, current solution could reduce approximate half of dumping RDB time,
      this PR costs 50s for dump 7.7G rdb but unstable branch costs 93s.
      On NVME SSD, this PR can't reduce much time,  this PR costs 40s, unstable branch costs 48s.
      
      Moreover, I find calling data sync every 4MB is better than 32MB.
      9a0c0617
  21. 10 Aug, 2021 2 commits
    • Meir Shpilraien (Spielrein)'s avatar
      Format fixes and naming. SentReplyOnKeyMiss -> addReplyOrErrorObject (#9346) · 8f8117f7
      Meir Shpilraien (Spielrein) authored
      Following the comments on #8659, this PR fix some formatting
      and naming issues.
      8f8117f7
    • sundb's avatar
      Replace all usage of ziplist with listpack for t_hash (#8887) · 02fd76b9
      sundb authored
      
      
      Part one of implementing #8702 (taking hashes first before other types)
      
      ## Description of the feature
      1. Change ziplist encoded hash objects to listpack encoding.
      2. Convert existing ziplists on RDB loading time. an O(n) operation.
      
      ## Rdb format changes
      1. Add RDB_TYPE_HASH_LISTPACK rdb type.
      2. Bump RDB_VERSION to 10
      
      ## Interface changes
      1. New `hash-max-listpack-entries` config is an alias for `hash-max-ziplist-entries` (same with `hash-max-listpack-value`)
      2. OBJECT ENCODING will return `listpack` instead of `ziplist`
      
      ## Listpack improvements:
      1. Support direct insert, replace integer element (rather than convert back and forth from string)
      3. Add more listpack capabilities to match the ziplist ones (like `lpFind`, `lpRandomPairs` and such)
      4. Optimize element length fetching, avoid multiple calculations
      5. Use inline to avoid function call overhead.
      
      ## Tests
      1. Add a new test to the RDB load time conversion
      2. Adding the listpack unit tests. (based on the one in ziplist.c)
      3. Add a few "corrupt payload: fuzzer findings" tests, and slightly modify existing ones.
      Co-authored-by: default avatarOran Agra <oran@redislabs.com>
      02fd76b9
  22. 09 Aug, 2021 1 commit
  23. 07 Aug, 2021 1 commit
  24. 06 Aug, 2021 1 commit
  25. 05 Aug, 2021 3 commits