🥮 mooncakes.io

    moonbitstack/moonkart/policy does not have a README file

    Policy

    source
    pub(open) trait Policy {
      fn hit(self : Self, id : Int64, hash : Int) -> Unit
      fn admit(self : Self, id : Int64, weight : Int64, hash : Int) -> Array[Int64]
      fn forget(self : Self, id : Int64) -> Unit
      fn size(self : Self) -> Int
    }

    A pluggable eviction policy. The cache assigns every entry an opaque numeric id and hands the policy the entry's key hash alongside it. Policies that track frequency use the hash, so a key keeps its history across eviction and re-admission even though every insertion gets a fresh id. A policy never sees a key or a value. Implement this trait of your own type and hand the instance to the cache to use a strategy the library does not ship.

    Admission

    source
    pub(all) enum Admission {
      ByValue
      TakeAll
    }

    How a newcomer earns a place where room is already taken. The in-memory policies decide this themselves; a second tier over a slower medium takes it as a knob, because there a wrong decision costs a write as well.

    IntrusiveList

    source
    pub struct IntrusiveList {
      // private fields
    }

    A doubly linked list keyed by id, with 0 as the empty marker so valid ids (which start at 1) never collide with it. Every mutable piece lives in a Ref so that copying the list (for example passing it to a method that takes self by value) still mutates the one shared list.
    pub struct Link {
      // private fields
    }

    A node of the intrusive doubly linked list used by the LRU-family policies.

    Lru

    source
    pub struct Lru {
      // private fields
    }

    Least-recently-used policy: the entry not touched for the longest time leaves first.
    impl Policy for Lru

    Lru::admit

    source
    fn Lru::admit(self : Lru, id : Int64, weight : Int64, _hash : Int) -> Array[Int64]

    Lru::forget

    source
    fn Lru::forget(self : Lru, id : Int64) -> Unit

    Lru::hit

    source
    fn Lru::hit(self : Lru, id : Int64, _hash : Int) -> Unit

    Lru::size

    source
    fn Lru::size(self : Lru) -> Int

    S3Fifo

    source
    pub struct S3Fifo {
      // private fields
    }

    S3-FIFO-inspired second-chance FIFO: a single FIFO queue with a visited bit per entry. When the queue is over budget, an entry that has been read since it entered is moved back to the tail with its bit cleared, while an entry never read since it entered is evicted. Scan floods and one-hit wonders are evicted on first sight, while repeated keys survive several rounds, at the cost of one boolean per entry.
    impl Policy for S3Fifo

    S3Fifo::admit

    source
    fn S3Fifo::admit(self : S3Fifo, id : Int64, weight : Int64, _hash : Int) -> Array[Int64]

    S3Fifo::forget

    source
    fn S3Fifo::forget(self : S3Fifo, id : Int64) -> Unit

    S3Fifo::hit

    source
    fn S3Fifo::hit(self : S3Fifo, id : Int64, _hash : Int) -> Unit

    S3Fifo::size

    source
    fn S3Fifo::size(self : S3Fifo) -> Int

    Sketch

    source
    pub struct Sketch {
      // private fields
    }

    A frequency sketch: four rows of 4-bit counters, sized from the number of entries the caller wants to remember, with the whole table halved once the sample window fills. It answers "how often has this key been seen lately" from a hash alone, so a key keeps its history after it leaves and comes back.

    The shape follows the sketch behind TinyLFU, as Caffeine and moka implement it: a counter per entry per row (four rows, four times the capacity rounded up to a power of two), counters saturating at 15, and a reset that halves every counter every 10 × capacity records. The reset is what keeps the estimate about recent traffic rather than the whole history.

    Sketch::age

    source
    fn Sketch::age(self : Sketch) -> Unit

    Halves every counter and the sample count. [record] runs this when the window fills; calling it directly forgets old traffic at once.

    Sketch::estimate

    source
    fn Sketch::estimate(self : Sketch, hash : Int) -> Int

    The estimated frequency of the key whose hash is hash: the smallest of its four counters, which is the estimate the collisions cannot inflate.

    Sketch::new

    source
    fn Sketch::new(capacity : Int) -> Sketch

    Creates a sketch sized for capacity keys. A capacity below 16 is treated as 16, which is the smallest table whose rows still spread the hashes.

    Sketch::record

    source
    fn Sketch::record(self : Sketch, hash : Int) -> Unit

    Counts one sighting of the key whose hash is hash, halving the whole table first when the sample window is full.

    Tinylfu

    source
    pub struct Tinylfu {
      // private fields
    }

    W-TinyLFU policy: a small admission window feeds a segmented LRU (probation and protected) that is guarded by a frequency sketch keyed by the entry's key hash, so often-read keys survive even after they age out of recency. This is the cache's default strategy.
    impl Policy for Tinylfu

    Tinylfu::admit

    source
    fn Tinylfu::admit(self : Tinylfu, id : Int64, weight : Int64, hash : Int) -> Array[Int64]

    Tinylfu::forget

    source
    fn Tinylfu::forget(self : Tinylfu, id : Int64) -> Unit

    Tinylfu::hit

    source
    fn Tinylfu::hit(self : Tinylfu, id : Int64, hash : Int) -> Unit

    Tinylfu::size

    source
    fn Tinylfu::size(self : Tinylfu) -> Int

    new_lru

    source
    fn new_lru(cap? : Int64, max_weight? : Int64) -> Lru

    Creates an LRU policy. Set at most one of max_weight (evict by weight) or cap (evict by entry count).

    new_s3fifo

    source
    fn new_s3fifo(cap? : Int64, max_weight? : Int64) -> S3Fifo

    Creates an S3-FIFO-inspired second-chance FIFO. Bound by cap (entry count) or max_weight (total weight).

    new_tinylfu

    source
    fn new_tinylfu(cap? : Int64, max_weight? : Int64, window_ratio? : Double, protected_ratio? : Double) -> Tinylfu

    Creates a W-TinyLFU policy. window_ratio sizes the admission window; protected_ratio sizes the protected segment of the main region.

    tinylfu_protected_ratio

    source
    let tinylfu_protected_ratio : Double

    Fraction of the main region given to the protected segment in W-TinyLFU. Entries read at least once are promoted here, away from the probation queue.

    tinylfu_window_ratio

    source
    let tinylfu_window_ratio : Double

    Fraction of capacity given to the admission window in W-TinyLFU. The window admits new entries before they must earn a place in the main region, so a burst of one-hit wonders does not evict the working set.

    Source Files