Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
zuiderkwast opened this issue Oct 31, 2024 · 2 comments
Open
Labels
help wanted Extra attention is needed

Comments

@zuiderkwast
Copy link
Contributor

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
Copy link
Contributor Author

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 zuiderkwast added the help wanted Extra attention is needed label Oct 31, 2024
@zuiderkwast
Copy link
Contributor Author

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
help wanted Extra attention is needed
Projects
None yet
Development

No branches or pull requests

1 participant