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

LRU rework: protected quotas #90

Open
g2p opened this issue Oct 12, 2020 · 0 comments
Open

LRU rework: protected quotas #90

g2p opened this issue Oct 12, 2020 · 0 comments

Comments

@g2p
Copy link
Collaborator

g2p commented Oct 12, 2020

The LRU contains two kinds of items: evictable nodes, which can always be
dropped, and protected items. The latter are either dirty nodes that can't be
dropped from the cache, pending a flush, or nodes being otherwise accessed,
like a parent chain during tree traversal.

We want to preserve an overall order, but this is currently done by raising
an exception when cache eviction would drop a protected item from the LRU.

A better design would involve dropping only evictable items. This could have
the drawback of protected items piling up from the inactive end of the cache,
finally ending up with no room for caching reads. So, we add a quota for
protected items not to grow beyond (allowing a reserved area of evictable nodes
to stay filled once enough blocks have been read).

Implementation-wise, dropping works better by separating the data into two
heaps, instead of having to skip items from the inactive end. Total order can
be kept using a clock.

Spec:

  • keep a single order for all items. A clock will work.
  • keep two heaps, of protected and unprotected items
  • limit total size of both heaps by cache_size
  • limit size of the protected set, making sure it doesn't grow beyond
    cache_size-unprotected_quota.
    The reverse isn't necessary, since unprotected items can always
    make room for protected items.
  • unprotect items without necessarily reordering them (flushing will
    touch many nodes and shouldn't reorder)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant