kevy_store/lib.rs
1//! kevy-store — the keyspace.
2//!
3//! A single-threaded, multi-type keyspace with lazy expiration. Each Redis data
4//! type is backed by a modern `std` structure — behaviour-compatible, but **not**
5//! Redis's legacy encodings:
6//!
7//! | Type | Backing structure |
8//! |------|-------------------|
9//! | String | `Vec<u8>` |
10//! | Hash / Set | `HashMap` / `HashSet` (hashbrown Swiss table) |
11//! | List | `VecDeque` (ring buffer, O(1) ends) |
12//! | Sorted set | `HashMap` + `BTreeSet<(score, member)>` (a B-tree, not a skiplist) |
13//!
14//! Wrong-type access returns [`StoreError::WrongType`]. The API is `&mut self`
15//! and lock-free, so a thread-per-core runtime ([kevy-rt]) can own one shard per
16//! core with no locking. Part of the [kevy] key–value server.
17//!
18//! `maxmemory` enforcement + 8 eviction policies live in [`evict`]; toggle via
19//! [`Store::set_max_memory`]. With `maxmemory == 0` (the default) the hot-path
20//! cost collapses to a single predicted-not-taken branch, matching the
21//! "unlimited" mode in Redis byte-for-byte.
22//!
23//! [kevy]: https://crates.io/crates/kevy
24//! [kevy-rt]: https://crates.io/crates/kevy-rt
25//!
26//! # Example
27//!
28//! ```
29//! use kevy_store::Store;
30//!
31//! use std::borrow::Cow;
32//! let mut s = Store::new();
33//! s.set(b"greeting", b"hello".to_vec(), None, kevy_store::SetCondition::Always);
34//! assert_eq!(s.get(b"greeting").unwrap(), Some(Cow::Borrowed(&b"hello"[..])));
35//!
36//! s.hset(b"user:1", &[(b"name".as_slice(), b"alice".as_slice())]).unwrap();
37//! assert_eq!(s.hget(b"user:1", b"name").unwrap(), Some(&b"alice"[..]));
38//!
39//! // A string command on a hash key is a type error, as in Redis.
40//! assert_eq!(s.get(b"user:1"), Err(kevy_store::StoreError::WrongType));
41//! ```
42#![forbid(unsafe_code)]
43//! Every public item here is documented, and the lint keeps it that
44//! way: kevy-store is the keyspace, and `[workspace.lints.rust] warnings = "deny"`
45//! turns a new gap into a compile error rather than a number that
46//! drifts. Closed from 65 sites (store) and 7 (vlog) in v6.
47#![warn(missing_docs)]
48#![cfg_attr(not(feature = "std"), no_std)]
49
50#[cfg(all(not(feature = "std"), not(feature = "external-clock")))]
51compile_error!(
52 "kevy-store without `std` needs the `external-clock` feature: the TTL \
53 clock must be host-fed when std::time is unavailable"
54);
55
56extern crate alloc;
57
58/// The alloc-crate slice of the std prelude, for `no_std` builds — glob-
59/// imported per file so the std build stays byte-for-byte untouched.
60#[cfg(not(feature = "std"))]
61pub(crate) mod nostd_prelude {
62 pub(crate) use alloc::boxed::Box;
63 pub(crate) use alloc::format;
64 pub(crate) use alloc::string::{String, ToString};
65 pub(crate) use alloc::vec::Vec;
66}
67#[cfg(not(feature = "std"))]
68use nostd_prelude::*;
69
70/// The two side maps (`hfttl`, `watch_versions`) ride std's table on std
71/// and the self-hosted `KevyMap` without it.
72#[cfg(feature = "std")]
73pub(crate) type SideMap<K, V> = std::collections::HashMap<K, V>;
74#[cfg(not(feature = "std"))]
75pub(crate) type SideMap<K, V> = kevy_map::KevyMap<K, V>;
76
77mod accounting;
78#[cfg(feature = "std")]
79mod bio_drop;
80
81/// Without `std` there is no bio thread (`bio_drop` module is compiled
82/// out) — displaced heavy values drop inline on the caller.
83#[cfg(not(feature = "std"))]
84impl Store {
85 #[inline]
86 pub(crate) fn maybe_offload_drop(&mut self, old: Value) {
87 drop(old);
88 }
89}
90mod bitmap;
91mod clock;
92mod cond;
93pub use cond::{InsertPosition, ListEnd, ScoreCompare, SetCondition};
94mod defrag;
95pub use defrag::{DefragHint, DefragStep};
96mod entry;
97mod error;
98pub use bitmap::BitOp;
99pub use error::{KevyError, KevyResult};
100pub mod evict;
101pub mod expire;
102pub(crate) use entry::Entry;
103pub use expire::ExpireStats;
104pub use store_admin::DetachedEntries;
105mod hash;
106mod hash_read;
107mod hash_weight;
108pub use hash_read::FieldValuePairs;
109mod hash_ttl;
110pub use hash_ttl::{HExpireCode, HExpireCond};
111mod keyspace;
112mod keyspace_load;
113mod keyspace_map;
114mod list;
115mod list_read;
116pub mod list_seg;
117mod notify;
118mod rng;
119mod row_watch;
120mod row_watch_store;
121pub use row_watch::{RowChange, RowChanges, RowWatch};
122mod scan;
123pub mod seg_map;
124pub use notify::KeyspaceEvent;
125mod list_ops;
126mod set;
127mod set_read;
128mod small_set;
129pub use small_set::{SmallSetData, SmallSetIter};
130pub mod packed_row;
131mod small_hash;
132mod value_weight;
133pub use small_hash::{SmallHashData, SmallHashIter};
134mod small_list;
135pub use small_list::{SmallListData, SmallListIter};
136mod small_zset;
137pub use small_zset::{SmallZSetData, SmallZSetIter};
138mod snapshot;
139pub use snapshot::SnapshotView;
140#[cfg(all(feature = "std", not(target_arch = "wasm32")))]
141mod segrows;
142#[cfg(all(feature = "std", not(target_arch = "wasm32")))]
143mod segrows_error;
144#[cfg(all(feature = "std", not(target_arch = "wasm32")))]
145mod segwindow;
146mod stream;
147mod string;
148mod string_rmw;
149mod string_set;
150mod tier;
151#[cfg(all(feature = "std", not(target_arch = "wasm32")))]
152mod tier_batch;
153#[cfg(all(feature = "std", not(target_arch = "wasm32")))]
154mod tier_codec;
155mod tier_demote;
156mod tier_serve;
157#[cfg(all(feature = "std", not(target_arch = "wasm32")))]
158mod tier_state;
159#[cfg(all(feature = "std", not(target_arch = "wasm32")))]
160mod tier_stats;
161#[cfg(all(feature = "std", not(target_arch = "wasm32")))]
162pub use segrows::SealedRows;
163#[cfg(all(feature = "std", not(target_arch = "wasm32")))]
164pub use segrows_error::SegRowsError;
165
166#[cfg(all(feature = "std", not(target_arch = "wasm32")))]
167pub use kevy_vlog::CompressionStats;
168#[cfg(all(feature = "std", not(target_arch = "wasm32")))]
169pub use tier::TierStats;
170#[cfg(all(feature = "std", not(target_arch = "wasm32")))]
171pub use tier_serve::{ColdBatchReader, ColdRead, PeekRow, SyncColdRead};
172mod types;
173pub use types::{EvictionPolicy, RenameOutcome, StoreError};
174mod util;
175mod value;
176mod value_cold;
177mod value_enum;
178mod zset;
179mod zset_algebra;
180mod zset_range;
181pub mod zset_seg;
182pub use zset_algebra::{ZAggregate, zdiff, zinter, zintercard, zunion};
183mod zset_flags;
184pub use stream::{
185 APPROX_TRIM_LIMIT, AckMode, AutoclaimResult, ClaimMode, ConsumerGroup, ConsumerState,
186 EntryBatch, GroupBatch, GroupCreateMode, LoadedGroup, LoadedPelEntry, LoadedStreamEntry,
187 MissingStream, PelEntry, PendingExtended, PendingExtendedRow, PendingSummary, ReadGroupId,
188 StreamData, StreamId, StreamIdError, TrimMode, TrimTo, XAddIdSpec, XClaimOpts, now_unix_ms,
189 parse_explicit_id, parse_range_end, parse_range_start, parse_xadd_id,
190};
191pub use string::{GetReply, GetShared};
192pub use util::glob_match;
193pub use value::*;
194pub use zset_flags::{ZaddFlags, ZaddReport};
195
196/// Feed kevy's monotonic clock on `wasm32-unknown-unknown`, which has no
197/// `Instant`. The embedding host advances time (ns since an arbitrary fixed
198/// epoch, e.g. `Date.now() * 1e6`) before TTL-sensitive ops and once per
199/// reaper tick. No-op concept on native targets, where the OS clock is the
200/// source — hence wasm-only.
201#[cfg(any(feature = "external-clock", all(target_arch = "wasm32", target_os = "unknown")))]
202pub use clock::set_clock_ns;
203/// Feed kevy's wall clock (Unix-epoch millis, e.g. `Date.now()`) on
204/// `wasm32-unknown-unknown`, where `SystemTime::now()` traps. Used by `XADD`
205/// auto-IDs and `EXPIREAT`/`PEXPIREAT`.
206#[cfg(any(feature = "external-clock", all(target_arch = "wasm32", target_os = "unknown")))]
207pub use clock::set_wall_clock_ms;
208pub(crate) use clock::{deadline_at, now_ns, pack_deadline, remaining_ms};
209use kevy_map::KevyMap;
210
211/// A single-database keyspace.
212///
213/// The keyspace map is a [`KevyMap`] — a pure-Rust open-addressing Swiss
214/// table tuned for kevy's per-shard, single-trust-domain keyspace. The
215/// hasher is [`kevy_hash::KevyHash`] (one-call inlinable; no DoS hardening
216/// since the shard is single-threaded with no cross-trust keys). Owning the
217/// table also exposes bucket addresses for software prefetch on the batch
218/// driver.
219///
220/// ```
221/// use core::time::Duration;
222/// use kevy_store::{SetCondition, Store};
223/// let mut s = Store::new();
224/// assert!(s.set(b"k", b"v".to_vec(), Some(Duration::from_secs(60)), SetCondition::Always));
225/// assert_eq!(s.type_of(b"k"), "string");
226/// assert_eq!(s.del(&[b"k".as_slice(), b"missing"]), 1);
227/// assert_eq!(s.type_of(b"k"), "none");
228/// ```
229#[derive(Debug, Default)]
230pub struct Store {
231 pub(crate) map: keyspace_map::Keyspace,
232 pub(crate) defrag: defrag::DefragState,
233 /// The random source. SPOP and SRANDMEMBER promise an ARBITRARY member;
234 /// before this they returned the first one in hash-bucket order, which for
235 /// a given set is the same member every time.
236 pub(crate) rng: rng::Rng,
237 /// Per-field hash TTLs: key → (field → absolute unix-ms
238 /// deadline). Holds ONLY keys with live field TTLs — one
239 /// `is_empty()` branch per hash access when the feature is unused.
240 pub(crate) hfttl: SideMap<SmallBytes, KevyMap<SmallBytes, u64>>,
241 /// Whether a row under a declared prefix may take the packed
242 /// representation. Off means every hash keeps the general form, which is
243 /// what makes the packed row measurable: the same binary answers both
244 /// ways, so a comparison is one flag apart rather than two builds apart.
245 pub(crate) packed_rows: bool,
246 /// The column-name lists packed rows point at, one per table shape.
247 /// A row is packed on its table's list, and a row back from the cold
248 /// tier — whose payload names only the columns it has — is rebuilt on
249 /// the first list here that names all of them, so a table's rows hold
250 /// one list between them instead of a copy each.
251 pub(crate) row_shapes: Vec<packed_row::ColumnNames>,
252 /// Coarse cached monotonic clock (ns since [`epoch`]), refreshed by the
253 /// reactor loop / reaper tick via [`Self::refresh_clock`]. Lazy expiry on
254 /// the read path (`live_entry`) compares deadlines against this instead of
255 /// calling `Instant::now()` per access — the Redis cached-`mstime` model.
256 /// `0` (the `Default`) reads as "epoch" → keys look live until the first
257 /// refresh, the safe direction (expires at most one refresh-interval late,
258 /// never early — writes stamp deadlines from a *fresh* clock).
259 pub(crate) cached_ns: u64,
260 /// Whether lazy expiry trusts `Self::cached_ns` (set by a reactor/reaper
261 /// that calls [`Self::refresh_clock`]) instead of reading a fresh clock per
262 /// access. Enabled by the server reactor and the embedded background
263 /// reaper; left `false` (the `Default`) for manual-reaper / bare-`Store`
264 /// use, where nothing refreshes the cache so each access reads fresh —
265 /// preserving "lazy expiry works without an explicit tick".
266 pub(crate) cached_clock: bool,
267 /// Live byte estimate: the per-entry weights plus the keyspace table at
268 /// its real size. Compared against [`Self::maxmemory`] to drive eviction.
269 pub(crate) used_memory: u64,
270 /// Soft byte ceiling. `0` = unlimited; the entire accounting + eviction
271 /// machinery short-circuits to a single not-taken branch in that case.
272 pub(crate) maxmemory: u64,
273 /// Growing writes refused whatever `maxmemory` says (the tier's hard stop).
274 pub(crate) memory_refused: bool,
275 /// `maxmemory > 0 || memory_refused`: the one field the write path reads.
276 pub(crate) write_gate: bool,
277 /// Active eviction policy. Only consulted when `used_memory > maxmemory`.
278 pub(crate) eviction_policy: EvictionPolicy,
279 /// Total keys evicted by [`Self::try_evict_after_write`] — surfaced via
280 /// `INFO memory` / `MEMORY STATS`.
281 pub(crate) evictions_total: u64,
282 /// Monotonic access counter; the upper 32 bits are unused, the lower 32
283 /// stamp `Entry::lru_clock` on each access while eviction is enabled.
284 pub(crate) clock_counter: u64,
285 /// The keyspace table's bytes as `used_memory` last charged them.
286 pub(crate) keyspace_bytes: u64,
287 /// `used_memory` peak across the shard's lifetime; surfaced as
288 /// `used_memory_peak` in `INFO memory`.
289 pub(crate) used_memory_peak: u64,
290 /// Keys expired since startup (lazy reap path AND
291 /// [`Self::tick_expire`]). Surfaced via `INFO keyspace` / `MEMORY STATS`
292 /// once those fields land.
293 pub(crate) expired_keys_total: u64,
294 /// Which store-origin keyspace events to capture (see
295 /// [`crate::notify`]). All-off default = every hook is one byte
296 /// test.
297 pub(crate) notify_capture: u8,
298 /// Captured events awaiting the serving layer's drain
299 /// ([`Self::take_notify_events`]), in capture order.
300 pub(crate) notify_events: Vec<(notify::KeyspaceEvent, Vec<u8>)>,
301 /// Keys this store dropped because their TTL passed, awaiting the
302 /// serving layer's drain ([`Self::take_expired_keys`]).
303 ///
304 /// Separate from `notify_events` and **always on**, because it
305 /// carries correctness rather than observability: an expiring key
306 /// must still leave every secondary index and invalidate every
307 /// WATCH on it, and neither may depend on whether some client
308 /// happened to subscribe to keyspace notifications.
309 pub(crate) expired_keys: Vec<Vec<u8>>,
310 /// Count of live keys carrying a TTL — the size of Redis's "expire set"
311 /// (`INFO keyspace`'s `expires=`). Maintained in O(1) at every TTL
312 /// transition (`insert_entry` / `remove_entry` deltas + the in-place
313 /// EXPIRE / PERSIST / SET sites) so the gauge never pays an O(n) keyspace
314 /// scan; [`Self::ttl_pending_count`] is the O(n) ground truth used to
315 /// assert this counter never drifts.
316 pub(crate) expires: u64,
317 /// `WATCH` version counters — present only for keys that have been
318 /// `WATCH`-ed at least once. [`Self::record_watch`] inserts the entry
319 /// (version 0 = "never written since first watch"); every subsequent
320 /// write on this shard calls [`Self::bump_if_watched`] which increments
321 /// only if the key is present in the map. Keys never `WATCH`-ed pay
322 /// one empty-map hashmap lookup per write (~10 ns).
323 ///
324 /// The map grows monotonically — entries are never evicted, even
325 /// when no conn is currently watching the key. For high-key-churn
326 /// workloads this can become a memory item; v1.x acceptable since
327 /// the entry is `Vec<u8>` + `u64` (~ 30 B + key length) and only
328 /// touched on writes / WATCH calls.
329 pub(crate) watch_versions: SideMap<Vec<u8>, u64>,
330 /// Optional handle to the runtime's bio thread. Set by
331 /// `kevy-rt::Runtime::run` via [`Self::set_bio_drop_sender`] before
332 /// the shard reactor loop starts. `None` = inline drop (bare-Store
333 /// embedders, snapshots-loader programs, the test harness — anything
334 /// without a kevy-rt runtime around it). Reads on the hot path are
335 /// one `Option::as_ref` branch; the steady-state inline-drop path
336 /// pays nothing beyond that branch.
337 #[cfg(feature = "std")]
338 pub(crate) bio_drop_sender: Option<value::BioDropSender>,
339 /// Batch-send buffer. Heavy `Value`s displaced by SET
340 /// overwrites accumulate here instead of paying one mpsc send per
341 /// drop; flushed in one `mpsc::Sender::send` at the end of every
342 /// reactor iteration (via [`Self::flush_pending_drops`], invoked
343 /// from `kevy-rt`'s epoll + io_uring reactor loops before the AOF
344 /// fsync window). Amortising the channel cost over N drops lets
345 /// the heap-heavy threshold sit at 1 KB — small enough that the
346 /// Axis I 256 B – 16 KB SET tail benefits, big enough that
347 /// sub-µs small-class drops still go inline (the push + flush
348 /// branch would cost more than the inline free).
349 ///
350 /// **Latency window**: drops sit in this buffer ≤ one reactor
351 /// iteration (10s of µs at busy-poll, ≤ park-timeout at idle —
352 /// 50 ms by default). On a reactor with no traffic the buffer
353 /// stays small (no new SETs to displace anything); on a reactor
354 /// with sustained writes the per-iter flush fires fast enough
355 /// that worst-case stall is bounded by `MAX_PENDING_DROPS`.
356 ///
357 /// **Bounded growth**: at `MAX_PENDING_DROPS` items the
358 /// `maybe_offload_drop` path force-flushes — protects against
359 /// pathological "thousand SETs in one iter never flush" cases
360 /// (would otherwise hold thousands of `Box<Value>`s in RAM until
361 /// the iter ends).
362 #[cfg(feature = "std")]
363 pub(crate) pending_drops: Vec<Value>,
364 /// Transparent-tiering state. `None` = off —
365 /// today's paths byte-identical ([`Store::enable_tiering`]).
366 #[cfg(all(feature = "std", not(target_arch = "wasm32")))]
367 pub(crate) tier: Option<tier::TierState>,
368 /// Row-segment directory — the persistent second backing behind
369 /// `Value::Cold` ([`segrows`]). `None` = off, today's paths
370 /// byte-identical.
371 #[cfg(all(feature = "std", not(target_arch = "wasm32")))]
372 pub(crate) segrows: Option<segrows::SegRows>,
373 /// Hot gate for the stub funnels: true iff EITHER cold backing
374 /// (vlog tier / row segments) is enabled. One predictable branch
375 /// keeps tier_serve/tier_resolve at their no-backing cost on
376 /// deployments that never demote — the measured shape of the
377 /// write-path funnels (perfgate legacy angles).
378 #[cfg_attr(any(not(feature = "std"), target_arch = "wasm32"), allow(dead_code))]
379 pub(crate) cold_backing: bool,
380 /// The promotion gate's first-touch serve scratch (`tier_serve`):
381 /// a cold value decoded for ONE read, never installed in the map.
382 #[cfg(all(feature = "std", not(target_arch = "wasm32")))]
383 pub(crate) tier_scratch: Option<Entry>,
384 /// Bulk-read (no-promote peek) mode, scoped by
385 /// [`Store::peek_scope`]: while set, a cold materializing read serves
386 /// via pread WITHOUT setting the probation mark and WITHOUT
387 /// promoting — digest / scope-move / export reads are not access
388 /// signals.
389 #[cfg(all(feature = "std", not(target_arch = "wasm32")))]
390 pub(crate) tier_peek: bool,
391}
392
393mod store_admin;
394
395/// No row-segment backend on this target.
396#[cfg(not(all(feature = "std", not(target_arch = "wasm32"))))]
397impl Store {
398 /// Cfg twin of the segrows accessor: always empty.
399 pub fn row_seg_files(&self) -> Vec<(u32, alloc::string::String)> {
400 Vec::new()
401 }
402}
403
404// Accounting micro-helpers live in `util` (500-LOC split); re-exported
405// so the crate-wide `crate::apply_delta` / `crate::key_heap_bytes_for`
406// paths keep working.
407pub(crate) use util::{apply_delta, key_heap_bytes_for};
408
409const _: () = {
410 const fn send_sync<T: Send + Sync>() {}
411 send_sync::<Store>();
412 send_sync::<StoreError>();
413 send_sync::<KevyError>();
414 send_sync::<RenameOutcome>();
415 send_sync::<EvictionPolicy>();
416 send_sync::<SetCondition>();
417 send_sync::<ListEnd>();
418 send_sync::<InsertPosition>();
419 send_sync::<ScoreCompare>();
420 send_sync::<BitOp>();
421 send_sync::<ExpireStats>();
422 send_sync::<DetachedEntries>();
423 send_sync::<HExpireCond>();
424 send_sync::<KeyspaceEvent>();
425 send_sync::<SnapshotView>();
426 send_sync::<ZAggregate>();
427 send_sync::<StreamData>();
428 send_sync::<StreamId>();
429 send_sync::<StreamIdError>();
430 send_sync::<XAddIdSpec>();
431 send_sync::<XClaimOpts>();
432 send_sync::<MissingStream>();
433 send_sync::<AckMode>();
434 send_sync::<ClaimMode>();
435 send_sync::<ConsumerGroup>();
436 send_sync::<ConsumerState>();
437 send_sync::<PelEntry>();
438 send_sync::<GroupCreateMode>();
439 send_sync::<ReadGroupId>();
440 send_sync::<PendingSummary>();
441 send_sync::<PendingExtended>();
442 send_sync::<AutoclaimResult>();
443 send_sync::<LoadedGroup>();
444 send_sync::<GetReply<'static>>();
445 send_sync::<GetShared>();
446 send_sync::<Value>();
447 send_sync::<Score>();
448 send_sync::<ScoreBound>();
449 send_sync::<ZaddFlags>();
450 send_sync::<ZaddReport>();
451 send_sync::<packed_row::PackedRow>();
452};
453
454#[cfg(all(feature = "std", not(target_arch = "wasm32")))]
455const _: () = {
456 const fn send_sync<T: Send + Sync>() {}
457 send_sync::<SealedRows>();
458 send_sync::<SegRowsError>();
459 send_sync::<TierStats>();
460 send_sync::<ColdRead>();
461 send_sync::<SyncColdRead>();
462};
463
464#[cfg(test)]
465mod tests;
466#[cfg(test)]
467mod tests_list_seg;
468#[cfg(test)]
469mod tests_live_entry;
470#[cfg(test)]
471mod tests_memory;
472#[cfg(test)]
473mod tests_range_past_the_end;
474#[cfg(test)]
475mod tests_row_watch;
476#[cfg(test)]
477mod tests_score_order;
478#[cfg(test)]
479mod tests_seg_map;
480#[cfg(test)]
481mod tests_snapshot;
482#[cfg(test)]
483mod tests_string_encoding;
484#[cfg(all(test, feature = "std", not(target_arch = "wasm32")))]
485mod tests_tier;
486#[cfg(all(test, feature = "std", not(target_arch = "wasm32")))]
487mod tests_tier_budget;
488#[cfg(all(test, feature = "std", not(target_arch = "wasm32")))]
489mod tests_tier_pack;
490#[cfg(all(test, feature = "std", not(target_arch = "wasm32")))]
491mod tests_tier_peek;
492#[cfg(test)]
493mod tests_zadd_same_score;
494#[cfg(test)]
495mod tests_zset_seg;