valkey-io / valkey-doc

Content for website and man pages
Other
23 stars 37 forks source link

EXPIRE command docs incorrect says active expire uses random sampling #185

Open zuiderkwast opened 3 weeks ago

zuiderkwast commented 3 weeks ago

The EXPIRE command manual (commands/expire.md) says that active expiry uses random sampling. This was changed some years ago (Redis 6?) to a scan based approach, i.e. an incremental sweep over all keys with expire.

This is the incorrect part of the page:

   How Valkey expires keys
       Valkey  keys  are  expired  in two ways: a passive way, and an active
       way.

       A key is passively expired simply when some client  tries  to  access
       it, and the key is found to be timed out.

       Of course this is not enough as there are expired keys that will nev‐
       er  be accessed again.  These keys should be expired anyway, so peri‐
       odically Valkey tests a few keys at random among keys with an  expire
       set.  All the keys that are already expired are deleted from the key‐
       space.

       Specifically this is what Valkey does 10 times per second:

       1. Test  20  random  keys from the set of keys with an associated ex‐
          pire.

       2. Delete all the keys found expired.

       3. If more than 25% of keys were expired, start again from step 1.

       This is a trivial probabilistic algorithm, basically  the  assumption
       is  that  our sample is representative of the whole key space, and we
       continue to expire until the percentage of keys that are likely to be
       expired is under 25%

       This means that at any given moment the maximum amount  of  keys  al‐
       ready  expired that are using memory is at max equal to max amount of
       write operations per second divided by 4.
zuiderkwast commented 3 weeks ago

Details about how it really works are in src/expire.c, but I don't think we need to document this in detail. Let's just remove the quoted text and instead just say that Valkey uses an incremental sweep to remove keys that are expired.

Let's also refer to the active-expire-effort config, which is documented in the valkey.conf file in the code repo.

We have yet to copy this documentation from the comments in the config file to the documentation page for configs: topics/valkey.conf.md. (See #154.)

zuiderkwast commented 3 weeks ago

See also #68, about documenting expiration and TTL in general