2 unstable releases
0.13.0 | Nov 24, 2024 |
---|---|
0.12.9 | Oct 31, 2024 |
#35 in Caching
1,108 downloads per month
Used in hitdns
1MB
22K
SLoC
Moka
note
v0.12.0
had major breaking changes on the API and internal behavior. Please read the MIGRATION-GUIDE.md for the details.
Moka is a fast, concurrent cache library for Rust. Moka is inspired by the Caffeine library for Java.
Moka provides cache implementations on top of hash maps. They support full concurrency of retrievals and a high expected concurrency for updates.
All caches perform a best-effort bounding of a hash map using an entry replacement algorithm to determine which entries to evict when the capacity is exceeded.
Features
Moka provides a rich and flexible feature set while maintaining high hit ratio and a high level of concurrency for concurrent access.
- Thread-safe, highly concurrent in-memory cache implementations:
- Synchronous caches that can be shared across OS threads.
- An asynchronous (futures aware) cache.
- A cache can be bounded by one of the followings:
- The maximum number of entries.
- The total weighted size of entries. (Size aware eviction)
- Maintains near optimal hit ratio by using an entry replacement algorithms inspired
by Caffeine:
- Admission to a cache is controlled by the Least Frequently Used (LFU) policy.
- Eviction from a cache is controlled by the Least Recently Used (LRU) policy.
- More details and some benchmark results are available here.
- Supports expiration policies:
- Time to live.
- Time to idle.
- Per-entry variable expiration.
- Supports eviction listener, a callback function that will be called when an entry is removed from the cache.
Choosing the right cache for your use case
No cache implementation is perfect for every use cases. Moka is a complex software and can be overkill for your use case. Sometimes simpler caches like Mini Moka or Quick Cache might be a better fit.
The following table shows the trade-offs between the different cache implementations:
Feature | Moka v0.12 | Mini Moka v0.10 | Quick Cache v0.6 |
---|---|---|---|
Thread-safe, sync cache | ✅ | ✅ | ✅ |
Thread-safe, async cache | ✅ | ❌ | ✅ |
Non-concurrent cache | ❌ | ✅ | ✅ |
Bounded by the maximum number of entries | ✅ | ✅ | ✅ |
Bounded by the total weighted size of entries | ✅ | ✅ | ✅ |
Near optimal hit ratio | ✅ TinyLFU | ✅ TinyLFU | ✅ S3-FIFO |
Per-key, atomic insertion. (e.g. get_with method) |
✅ | ❌ | ✅ |
Cache-level expiration policies (time-to-live and time-to-idle) | ✅ | ✅ | ❌ |
Per-entry variable expiration | ✅ | ❌ | ❌ |
Eviction listener | ✅ | ❌ | ✅ (via lifecycle hook) |
Lock-free, concurrent iterator | ✅ | ❌ | ❌ |
Lock-per-shard, concurrent iterator | ❌ | ✅ | ❌ |
Performance, etc. | Moka v0.12 | Mini Moka v0.10 | Quick Cache v0.6 |
---|---|---|---|
Small overhead compared to a concurrent hash table | ❌ | ❌ | ✅ |
Does not use background threads | ❌ → ✅ Removed from v0.12 | ✅ | ✅ |
Small dependency tree | ❌ | ✅ | ✅ |
Moka in Production
Moka is powering production services as well as embedded Linux devices like home routers. Here are some highlights:
- crates.io: The official crate registry has been using Moka in its API service to reduce the loads on PostgreSQL. Moka is maintaining cache hit rates of ~85% for the high-traffic download endpoint. (Moka used: Nov 2021 — present)
- aliyundrive-webdav: This WebDAV gateway for a cloud drive may have been deployed in hundreds of home Wi-Fi routers, including inexpensive models with 32-bit MIPS or ARMv5TE-based SoCs. Moka is used to cache the metadata of remote files. (Moka used: Aug 2021 — present)
Recent Changes
Note
v0.12.0
had major breaking changes on the API and internal behavior. Please read the MIGRATION-GUIDE.md for the details.
Table of Contents
- Features
- Moka in Production
- Change Log
- Supported Platforms
- Usage
- Examples (Part 1)
- Avoiding to clone the value at
get
- Example (Part 2)
- Expiration Policies
- Minimum Supported Rust Versions
- Troubleshooting
- Developing Moka
- Road Map
- About the Name
- Credits
- License
Supported Platforms
Moka should work on most 64-bit and 32-bit platforms if Rust std
library is
available with threading support. However, WebAssembly (Wasm) and WASI targets are
not supported.
The following platforms are tested on CI:
- Linux 64-bit (x86_64, arm aarch64)
- Linux 32-bit (i646, armv7, armv5, mips)
- If you get compile errors on 32-bit platforms, see troubleshooting.
The following platforms are not tested on CI but should work:
- macOS (arm64)
- Windows (x86_64 msvc and gnu)
- iOS (arm64)
The following platforms are not supported:
- WebAssembly (Wasm) and WASI targets are not supported. (See this project task)
nostd
environment (platforms withoutstd
library) are not supported.- 16-bit platforms are not supported.
Usage
To add Moka to your dependencies, run cargo add
as the followings:
# To use the synchronous cache:
cargo add moka --features sync
# To use the asynchronous cache:
cargo add moka --features future
If you want to use the cache under an async runtime such as tokio
or async-std
, you should specify the future
feature. Otherwise, specify the sync
feature.
Example: Synchronous Cache
The thread-safe, synchronous caches are defined in the sync
module.
Cache entries are manually added using insert
or get_with
method, and
are stored in the cache until either evicted or manually invalidated.
Here's an example of reading and updating a cache by using multiple threads:
// Use the synchronous cache.
use moka::sync::Cache;
use std::thread;
fn value(n: usize) -> String {
format!("value {n}")
}
fn main() {
const NUM_THREADS: usize = 16;
const NUM_KEYS_PER_THREAD: usize = 64;
// Create a cache that can store up to 10,000 entries.
let cache = Cache::new(10_000);
// Spawn threads and read and update the cache simultaneously.
let threads: Vec<_> = (0..NUM_THREADS)
.map(|i| {
// To share the same cache across the threads, clone it.
// This is a cheap operation.
let my_cache = cache.clone();
let start = i * NUM_KEYS_PER_THREAD;
let end = (i + 1) * NUM_KEYS_PER_THREAD;
thread::spawn(move || {
// Insert 64 entries. (NUM_KEYS_PER_THREAD = 64)
for key in start..end {
my_cache.insert(key, value(key));
// get() returns Option<String>, a clone of the stored value.
assert_eq!(my_cache.get(&key), Some(value(key)));
}
// Invalidate every 4 element of the inserted entries.
for key in (start..end).step_by(4) {
my_cache.invalidate(&key);
}
})
})
.collect();
// Wait for all threads to complete.
threads.into_iter().for_each(|t| t.join().expect("Failed"));
// Verify the result.
for key in 0..(NUM_THREADS * NUM_KEYS_PER_THREAD) {
if key % 4 == 0 {
assert_eq!(cache.get(&key), None);
} else {
assert_eq!(cache.get(&key), Some(value(key)));
}
}
}
You can try the synchronous example by cloning the repository and running the following cargo instruction:
$ cargo run --example sync_example
If you want to atomically initialize and insert a value when the key is not present,
you might want to check the document for other insertion methods
get_with
and try_get_with
.
Example: Asynchronous Cache
The asynchronous (futures aware) cache is defined in the future
module.
It works with asynchronous runtime such as Tokio,
async-std or actix-rt.
To use the asynchronous cache, enable a crate feature called "future".
Cache entries are manually added using an insert method, and are stored in the cache until either evicted or manually invalidated:
- Inside an async context (
async fn
orasync
block), useinsert
orinvalidate
method for updating the cache andawait
them. - Outside any async context, use
blocking
method to access blocking version ofinsert
orinvalidate
methods.
Here is a similar program to the previous example, but using asynchronous cache with Tokio runtime:
// Cargo.toml
//
// [dependencies]
// moka = { version = "0.12", features = ["future"] }
// tokio = { version = "1", features = ["rt-multi-thread", "macros" ] }
// futures-util = "0.3"
// Use the asynchronous cache.
use moka::future::Cache;
#[tokio::main]
async fn main() {
const NUM_TASKS: usize = 16;
const NUM_KEYS_PER_TASK: usize = 64;
fn value(n: usize) -> String {
format!("value {n}")
}
// Create a cache that can store up to 10,000 entries.
let cache = Cache::new(10_000);
// Spawn async tasks and write to and read from the cache.
let tasks: Vec<_> = (0..NUM_TASKS)
.map(|i| {
// To share the same cache across the async tasks, clone it.
// This is a cheap operation.
let my_cache = cache.clone();
let start = i * NUM_KEYS_PER_TASK;
let end = (i + 1) * NUM_KEYS_PER_TASK;
tokio::spawn(async move {
// Insert 64 entries. (NUM_KEYS_PER_TASK = 64)
for key in start..end {
// insert() is an async method, so await it.
my_cache.insert(key, value(key)).await;
// get() returns Option<String>, a clone of the stored value.
assert_eq!(my_cache.get(&key).await, Some(value(key)));
}
// Invalidate every 4 element of the inserted entries.
for key in (start..end).step_by(4) {
// invalidate() is an async method, so await it.
my_cache.invalidate(&key).await;
}
})
})
.collect();
// Wait for all tasks to complete.
futures_util::future::join_all(tasks).await;
// Verify the result.
for key in 0..(NUM_TASKS * NUM_KEYS_PER_TASK) {
if key % 4 == 0 {
assert_eq!(cache.get(&key).await, None);
} else {
assert_eq!(cache.get(&key).await, Some(value(key)));
}
}
}
You can try the asynchronous example by cloning the repository and running the following cargo instruction:
$ cargo run --example async_example --features future
If you want to atomically initialize and insert a value when the key is not present,
you might want to check the document for other insertion methods
get_with
and try_get_with
.
Avoiding to clone the value at get
For the concurrent caches (sync
and future
caches), the return type of get
method is Option<V>
instead of Option<&V>
, where V
is the value type. Every
time get
is called for an existing key, it creates a clone of the stored value V
and returns it. This is because the Cache
allows concurrent updates from threads so
a value stored in the cache can be dropped or replaced at any time by any other
thread. get
cannot return a reference &V
as it is impossible to guarantee the
value outlives the reference.
If you want to store values that will be expensive to clone, wrap them by
std::sync::Arc
before storing in a cache. Arc
is a thread-safe
reference-counted pointer and its clone()
method is cheap.
use std::sync::Arc;
let key = ...
let large_value = vec![0u8; 2 * 1024 * 1024]; // 2 MiB
// When insert, wrap the large_value by Arc.
cache.insert(key.clone(), Arc::new(large_value));
// get() will call Arc::clone() on the stored value, which is cheap.
cache.get(&key);
Example: Size Aware Eviction
If different cache entries have different "weights" — e.g. each entry has
different memory footprints — you can specify a weigher
closure at the cache
creation time. The closure should return a weighted size (relative size) of an entry
in u32
, and the cache will evict entries when the total weighted size exceeds its
max_capacity
.
use moka::sync::Cache;
fn main() {
let cache = Cache::builder()
// A weigher closure takes &K and &V and returns a u32 representing the
// relative size of the entry. Here, we use the byte length of the value
// String as the size.
.weigher(|_key, value: &String| -> u32 {
value.len().try_into().unwrap_or(u32::MAX)
})
// This cache will hold up to 32MiB of values.
.max_capacity(32 * 1024 * 1024)
.build();
cache.insert(0, "zero".to_string());
}
Note that weighted sizes are not used when making eviction selections.
You can try the size aware eviction example by cloning the repository and running the following cargo instruction:
$ cargo run --example size_aware_eviction
Expiration Policies
Moka supports the following expiration policies:
- Cache-level expiration policies:
- Cache-level policies are applied to all entries in the cache.
- Time to live (TTL): A cached entry will be expired after the specified
duration past from
insert
. - Time to idle (TTI): A cached entry will be expired after the specified
duration past from
get
orinsert
.
- Per-entry expiration policy:
- The per-entry expiration lets you sets a different expiration time for each entry.
For details and examples of above policies, see the "Example: Time-based Expiration"
section (sync::Cache
,
future::Cache
) of the document.
Minimum Supported Rust Versions
Moka's minimum supported Rust versions (MSRV) are the followings:
Feature | MSRV |
---|---|
default features | Rust 1.65.0 (Nov 3, 2022) |
future |
Rust 1.65.0 (Nov 3, 2022) |
It will keep a rolling MSRV policy of at least 6 months. If only the default features
are enabled, MSRV will be updated conservatively. When using other features, like
future
, MSRV might be updated more frequently, up to the latest stable. In both
cases, increasing MSRV is not considered a semver-breaking change.
Troubleshooting
Compile Errors on Some 32-bit Platforms
On some 32-bit target platforms including the followings, you may encounter compile errors:
armv5te-unknown-linux-musleabi
mips-unknown-linux-musl
mipsel-unknown-linux-musl
error[E0432]: unresolved import `std::sync::atomic::AtomicU64`
--> ... /moka-0.5.3/src/sync.rs:10:30
|
10 | atomic::{AtomicBool, AtomicU64, Ordering},
| ^^^^^^^^^
| |
| no `AtomicU64` in `sync::atomic`
Such errors can occur because std::sync::atomic::AtomicU64
is not provided on these
platforms but Moka uses it.
You can resolve the errors by disabling atomic64
feature, which is one of the
default features of Moka. Edit your Cargo.toml to add default-features = false
to the dependency declaration.
[dependencies]
moka = { version = "0.12", default-features = false, features = ["sync"] }
# Or
moka = { version = "0.12", default-features = false, features = ["future"] }
This will make Moka to switch to a fall-back implementation, so it will compile.
Developing Moka
Running All Tests
To run all tests including future
feature and doc tests on the README, use the
following command:
$ RUSTFLAGS='--cfg trybuild' cargo test --all-features
Running All Tests without Default Features
$ RUSTFLAGS='--cfg trybuild' cargo test \
--no-default-features --features 'future, sync'
Generating the Doc
$ cargo +nightly -Z unstable-options --config 'build.rustdocflags="--cfg docsrs"' \
doc --no-deps --features 'future, sync'
Roadmap
See the project roadmap for the updated and detailed plans.
But here are some highlights:
- Size-aware eviction. (
v0.7.0
via #24) - API stabilization. (Smaller core API, shorter names for frequently used
methods) (
v0.8.0
via #105)- e.g.
get_or_insert_with(K, F)
→get_with(K, F)
get_or_try_insert_with(K, F)
→try_get_with(K, F)
time_to_live()
→policy().time_to_live()
- Notifications on eviction. (
v0.9.0
via #145) - Variable (per-entry) expiration, using hierarchical timer wheels.
(
v0.11.0
via #248) - Remove background threads. (
v0.12.0
via #294 and #316) - Add upsert and compute methods. (
v0.12.3
via #370) - Cache statistics (Hit rate, etc.). (details)
- Upgrade TinyLFU to Window-TinyLFU. (details)
- Restore cache from a snapshot. (details)
About the Name
Moka is named after the moka pot, a stove-top coffee maker that brews espresso-like coffee using boiling water pressurized by steam.
This name would imply the following facts and hopes:
- Moka is a part of the Java Caffeine cache family.
- It is written in Rust. (Many moka pots are made of aluminum alloy or stainless steel. We know they don't rust though)
- It should be fast. ("Espresso" in Italian means express)
- It should be easy to use, like a moka pot.
Credits
Caffeine
Moka's architecture is heavily inspired by the Caffeine library for Java. Thanks go to Ben Manes and all contributors of Caffeine.
cht
The source files of the concurrent hash table under moka::cht
module were copied
from the cht crate v0.4.1 and modified by us. We did so for better
integration. cht v0.4.1 and earlier are licensed under the MIT license.
Thanks go to Gregory Meyer.
License
Moka is distributed under either of
- The MIT license
- The Apache License (Version 2.0)
at your option.
See LICENSE-MIT and LICENSE-APACHE for details.
Dependencies
~3–10MB
~104K SLoC