Awesome
A thread-safe, expiration-aware, LRU(ish) cache for Zig
// package available using Zig's built-in package manager
const user_cache = @import("cache");
var user_cache = try cache.Cache(User).init(allocator, .{.max_size = 10000});
defer user_cache.deinit();
try user_cache.put("user1", user1, .{.ttl = 300});
...
if (user_cache.get("user1")) |entry| {
defer entry.release();
const user1 = entry.value;
} else {
// not in the cache
}
// del will return true if the item existed
_ = user_cache.del("user1");
get
will return null
if the key is not found, or if the entry associated with the key has expired. If the entry has expired, it will be removed.
getEntry
can be used to return the entry even if it has expired. While getEntry
will return en expired item, it will not promote a expired item in the recency list. The main purpose is to allow the caller to serve a stale value while fetching a new one.
In either case, the entry's ttl() i64
method can be used to return the number of seconds until the entry expires. This will be negative if the entry has already expired. The expired() bool
method will return true
if the entry is expired.
release
must be called on the returned entry.
Implementation
This is a typical LRU cache which combines a hashmap to lookup values and doubly linked list to track recency.
To improve throughput, the cache is divided into a configured number of segments (defaults to 8). Locking only happens at the segment level. Furthermore, items are only promoted to the head of the recency linked list after a configured number of gets. This not only reduces the locking on the linked list, but also introduces a frequency bias to the eviction policy (which I think is welcome addition).
The downside of this approach is that size enforcement and the eviction policy is done on a per-segment basis. Given a max_size
of 8000 and a segment_count
of 8, each segment will enforce its own max_size
of 1000 and maintain its own recency list. Should keys be poorly distributed across segments, the cache will only reach a fraction of its configured max size. Only least-recently used items within a segment are considered for eviction.
Configuration
The 2nd argument to init is a cache.Config
. It's fields with default values are:
{
// The max size of the cache. By default, each value has a size of 1. Thus
// given a `max_size` of 5000, the cache can hold up to 5000 items before
// having to evict entries. The size of a value can be set when using
// `cache.put` or `cache.fetch`.
max_size: u32 = 8000,
// The number of segments to use. Must be a power of 2.
// A value of 1 is valid.
segment_count: u16 = 8,
// The number of times get or getEntry must be called on a key before
// it's promoted to the head of the recency list
gets_per_promote: u8 = 5,
// When a segment is full, the ratio of the segment's max_size to free.
shrink_ratio: f32 = 0.2,
}
Given the above, each segment will enforce its own max_size
of 1000 (i.e. 8000 / 8
). When a segment grows beyond 1000, entries will be removed until its size becomes less than or equal to 800 (i.e. 1000 - (1000 * 0.2)
)
Put
The cache.put(key: []const u8, value: T, config: cache.PutConfig) !void
has a number of consideration.
First, the key will be cloned and managed by the cache. The caller does not have to guarantee its validity after put
returns.
The third parameter is a cache.PutConfig
:
{
.ttl: u32 = 300,
.size: u32 = 1,
}
ttl
is the length, in seconds, to keep the value in the cache.
size
is the size of the value. This doesn't have to be the actual memory used by the value being cached. In many cases, the default of 1
is reasonable. However, if enforcement of the memory used by the cache is important, giving an approximate size (as memory usage or as a weighted value) will help. For example, if you're caching a string, the length of the string could make a reasonable argument for size
.
If T
defines a public method size() u32
, this value will be used instead of the above configured size
. This can be particularly useful with the fetch
method.
Fetch
cache.fetch
can be used to combine get
and put
by providing a custom function to load a missing value:
const user = try cache.fetch(FetchState, "user1", loadUser, .{user_id: 1}, .{.ttl = 300});
...
const FetchState = struct {
user_id: u32,
};
fn loadUser(state: FetchState, key: []const u8) !?User {
const user_id = state.user_id
const user = ... // load a user from the DB?
return user;
}
Because Zig doesn't have closures, and because your custom function will likely need data to load the missing value, you provide a custom state
type and value which will be passed to your function. They cache key is also passed, which, in simple cases, might be all your function needs to load data (in such cases, a void
state can be used).
The last parameter to fetch
is the same as the last parameter to put
.
Fetch does not do duplicate function call suppression. Concurrent calls to fetch
using the same key can result in multiple functions to your callback functions. In other words, fetch is vulnerable to the thundering herd problem. Considering using singleflight.zig within your fetch callback.
The size
of the value might not be known until the value is fetched, this makes passing size
into fetch impossible. If T
defines a public method size() u32
, then T.size(value)
will be called to get the size.
Entry Thread Safety
It's possible for one thread to get
an entry, while another thread deletes it. This deletion could be explicit (a call to cache.del
or replacing a value with cache.put
) or implicit (a call to cache.put
causing the cache to free memory). To ensure that deleted entries can safely be used by the application, atomic reference counting is used. While a deleted entry is immediately removed from the cache, it remains valid until all references are removed.
This is why release
must be called on the entry returned by get
and getEntry
. Calling release
multiple times on a single entry will break the cache.
removedFromCache notification
If T
defines a public method removedFromCache
, T.removedFromCache(Allocator)
will be called when all references are removed but before the entry is destroyed. removedFromCache
will be called regardless of why the entry was removed.
The Allocator
passed to removedFromCache
is the Allocator
that the cache was created with - this may or may not be an allocator that is meaningful to the value.
delPrefix
cache.delPrefix
can be used to delete any entry that starts with the specified prefix. This requires an O(N) scan through the cache. However, some optimizations are done to limit the amount of write-lock this places on the cache.