1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

#![warn(clippy::all)]
#![warn(rust_2018_idioms)]

//! Moka is a fast, concurrent cache library for Rust. Moka is
//! inspired by [Caffeine][caffeine-git] (Java) and
//! [Ristretto][ristretto-git] (Go).
//!
//! This crate provides in-memory concurrent cache implementations
//! [`Cache`][cache-struct] and [`SegmentedCache`][seg-cache-struct].
//! They support full concurrency of retrievals and a high expected
//! concurrency for updates.
//! <!-- They support full concurrency of retrievals, a high expected
//! concurrency for updates, and multiple ways to bound the cache. -->
//!
//! Both `Cache` and `SegmentedCache` utilize a lock-free concurrent
//! hash table `cht::SegmentedHashMap` from the [cht][cht-crate] crate
//! for the central key-value storage. These caches perform a
//! best-effort bounding of a map using an entry replacement algorithm
//! to determine which entries to evict when the capacity is exceeded.
//!
//! While `Cache` will be good for general use cases, `SegmentedCache`
//! may yield better performance under heavy concurrent updates.
//! However, `SegmentedCache` has little overheads on
//! retrievals/updates for managing multiple internal segments.
//!
//! [caffeine-git]: https://github.com/ben-manes/caffeine
//! [ristretto-git]: https://github.com/dgraph-io/ristretto
//! [cache-struct]: ./struct.Cache.html
//! [seg-cache-struct]: ./struct.SegmentedCache.html
//! [cht-crate]: https://crates.io/crates/cht
//!
//! ## Status
//!
//! Moka is currently in a very early stage of development (design and PoC). Many
//! features are not implemented and the API will change very often.
//!
//! ## Example
//!
//! TODO
//!
//! ## Concurrency
//!
//! The entry replacement algorithms are kept eventually consistent
//! with the map. While updates to the cache are immediately applied
//! to the map, recording of reads and writes may not be immediately
//! reflected on the cache policy's data structures.
//!
//! These structures are guarded by a lock and operations are applied
//! in batches to avoid lock contention. There are bounded
//! inter-thread channels to hold these operations. These channels are
//! drained at the first opportunity when:
//!
//! - The numbers of read/write recordings reach to the configured
//!   amounts.
//! - Or, the certain time past from the last draining.
//!
//! In a `Cache`, this draining and batch application is handled by a
//! single worker thread. So under heavy concurrent operations from
//! clients, draining may not be able to catch up and the bounded
//! channels can become full.
//!
//! When read or write channel becomes full, one of the followings
//! will occur:
//!
//! - For the read channel, recordings of new reads will be discarded,
//!   so that retrievals will never be blocked. This behavior may have
//!   some impact to the hit rate of the cache.
//! - For the write channel, updates from clients to the cache will be
//!   blocked until the draining task catches up.
//!
//! `Cache` does its best to avoid blocking updates by adjusting the
//! interval of draining and throttling updates from clients. But
//! since it has only one worker thread, it cannot always avoid
//! blocking. If this happens very often in your cache (in the future,
//! you can check the statistics of the cache), you may want to
//! switch to `SegmentedCache`. It has multiple internal cache
//! segments and each segment has dedicated draining thread.
//!
//! ## Admission and Eviction
//!
//! Every time a client tries to retrieve an item from the cache, that
//! activity is retained in a historic popularity estimator. This
//! estimator has a tiny memory footprint as it uses hashing to
//! probabilistically estimate an item's frequency.
//!
//! Both `Cache` and `SegmentedCache` employ [TinyLFU] (Least
//! Frequently Used) as the admission policy. When a new entry is
//! inserted to the cache, it is temporary admitted to the cache, and
//! a recording of this insertion is added to the write queue. When
//! the write queue is drained and the main space of the cache is
//! already full, then the historic popularity estimator determines to
//! evict one of the following entries:
//!
//! - The newly admitted entry
//! - Or, the victim entry that is selected from the main space by LRU
//!   (Least Recently Used) eviction policy
//!
//! In a future release of this crate, TinyLFU admission policy will
//! be replaced by Window TinyLFU (W-TinyLFU) policy. W-TinyLFU has an
//! admission window in front of the main space. A new entry starts in
//! the admission window and remains there as long as it has high
//! temporal locality (recency). Eventually an entry will slip off
//! from the window, then TinyLFU comes in play to determine whether
//! or not to admit the entry to the main space based on its
//! popularity (frequency).
//!
//! [TinyLFU]: https://dl.acm.org/citation.cfm?id=3149371
//!
//! ## Expiration
//!
//! Current release supports the following cache expiration policies:
//!
//! - The time-to-live policy
//! - The time-to-idle policy
//!
//! A future release will support the following:
//!
//! - The variable expiration
//!
//! These policies are provided with O(1) time complexity:
//!
//! - The time-to-live policy uses a write-order queue.
//! - The time-to-idle policy uses an access-order queue.
//! - The variable expiration will use a
//!   [hierarchical timer wheel][timer-wheel].
//!
//! [timer-wheel]: http://www.cs.columbia.edu/~nahum/w6998/papers/ton97-timing-wheels.pdf
//!

pub mod sync;

pub(crate) mod common;