search

isaacs / node-lru-cache

A fast cache that automatically deletes the least recently used items
http://isaacs.github.io/node-lru-cache/
ISC License
5.38k stars 353 forks source link

Clarification around TTL Guarantees #220

Closed JagandeepBrar closed 2 years ago

JagandeepBrar commented 2 years ago

Our team is looking into upgrading our old usage of this package (lru-cache@6.0.0) to the latest version (lru-cache@7.5.1) but noticed an addition to the README with the release of v7 that we would love some clarification on:

This is not primarily a TTL cache, and does not make strong TTL guarantees. There is no preemptive pruning of expired items, but you may set a TTL on the cache or on a single set. If you do so, it will treat expired items as missing, and delete them when fetched.

Just wanted to ask a few questions regarding that:

  1. When you mention a lack of strong guarantees, is this primarily in regards to the lack of preemptive pruning of expired items or is there a further lack of guarantees when using TTLs (for example, a lack of trust in the accuracy of the TTL calculation)?
  2. If the cache reaches the maximum capacity and there are expired keys, are the expired keys evicted first or is it purely on the LRU algorithm when passing maximum capacity?
  3. Are the performance impacts of using TTLs comparable or roughly the same to using TTLs in v6.0.0, or was there a regression in TTL usage performance with the release of v7?

Apologies for making an issue to ask these questions, but couldn't find another channel to ask.

Thanks in advanced!

isaacs commented 2 years ago

When you mention a lack of strong guarantees, is this primarily in regards to the lack of preemptive pruning of expired items or is there a further lack of guarantees when using TTLs (for example, a lack of trust in the accuracy of the TTL calculation)?

The TTL algorithm itself is as trustworthy as node's performance.now() (or Date.now() in versions that did not have the perf_hooks module). It's about as reliable as it gets.

This is more due to the lack of preemptive pruning. If the autoPrune option is not enabled, then items are kept in cache indefinitely, and only pruned when they are next fetched. If autoPrune is used, then items might still remain in cache for longer than expected, due to the lack of precision with setTimeout. In order to get more accurate, a different data structure would have to be used, such that cache entries remain sorted by TTL rather than recency of use, and could be efficiently pruned in that way. And this would only be necessary if you care about pruning down to a fixed capacity; if you want your cache to be unbounded, and only prune based on TTL, then you can't get much better performance than just using a Map and setTimeout().

If the cache reaches the maximum capacity and there are expired keys, are the expired keys evicted first or is it purely on the LRU algorithm when passing maximum capacity?

Eviction for passing max (or maxSize) capacity is solely based on recency of use, not TTL expiration. So, for example, you might have many expired entries causing a not-expired entry to be evicted, if the expired entries were used more recently.

In order to do this efficiently, the list would have to be kept sorted by expiration time, rather than by recency of use.

Are the performance impacts of using TTLs comparable or roughly the same to using TTLs in v6.0.0, or was there a regression in TTL usage performance with the release of v7?

This is a tricky question. The performance impact of using TTLs is quite a bit greater in v7, simply because v7 is about an order of magnitude faster in general, so the extra work of checking the time is a bigger relative delta. But the absolute performance of v7 with TTLs is still much better than v6 without TTLs.

I added the note in the readme for v7 simply because I got tired of explaining why I would not fix TTL-related edge cases that people found, which could not be properly fixed while still remaining a well behaved and performant LRU cache, or doing apples-to-oranges with this module with TTLs enabled vs other modules lacking TTL features.

Apologies for making an issue to ask these questions, but couldn't find another channel to ask.

No problem, this is the best channel to ask such things :)