Size Aware Eviction: First-In-First-Out, or evicting largest items first?

[rpivo]

This issue is not really a problem with Moka, but more an ask for clarification in the documentation.

Does the size aware eviction evict items on a first-in-first-out basis, or does it evict the largest items in the cache first?

(I am going to try to test this out, and If I can identify the answer, I will make a pull request.

[tatsuya6502]

Does the size aware eviction evict items on a first-in-first-out basis, or does it evict the largest items in the cache first?

It evicts least recently used (LRU) item. Item sizes do not affect the eviction order.

It uses a slightly modified version of "Aggregated Victims (AV)" algorithm. AV was introduced by this paper:

• Lightweight Robust Size Aware Cache Management by Gil Einziger, Ohad Eytan, Roy Friedman, Ben Manes.
  • Download PDF

and here are the details of the modifications in moka:

https://github.com/moka-rs/moka/blob/v0.12.7/src/future/base_cache.rs#L1913-L1929

    /// Performs size-aware admission explained in the paper:
    /// [Lightweight Robust Size Aware Cache Management][size-aware-cache-paper]
    /// by Gil Einziger, Ohad Eytan, Roy Friedman, Ben Manes.
    ///
    /// [size-aware-cache-paper]: https://arxiv.org/abs/2105.08770
    ///
    /// There are some modifications in this implementation:
    /// - To admit to the main space, candidate's frequency must be higher than
    ///   the aggregated frequencies of the potential victims. (In the paper,
    ///   `>=` operator is used rather than `>`)  The `>` operator will do a better
    ///   job to prevent the main space from polluting.
    /// - When a candidate is rejected, the potential victims will stay at the LRU
    ///   position of the probation access-order queue. (In the paper, they will be
    ///   promoted (to the MRU position?) to force the eviction policy to select a
    ///   different set of victims for the next candidate). We may implement the
    ///   paper's behavior later?

---

(I am going to try to test this out, and If I can identify the answer, I will make a pull request.

That would be great. Thanks!

FYI, currently, the doc only mentions the followings:

https://docs.rs/moka/latest/moka/sync/struct.Cache.html#example-size-based-eviction

Note that weighted sizes are not used when making eviction selections.

[rpivo]

@tatsuya6502 thank you for this amazing answer! I will read the paper you linked to as well and follow up.