Storing values with expiry
Step 5 of 10. Step 4 ended at the tag mini-ch04 with a server that serves many connections at
once: one Tokio task per client, one Arc<Db> shared between them, and SET, GET, DEL,
LPUSH and LRANGE on top of PING and ECHO. This step starts from that tag and ends at
mini-ch05: every key can carry a deadline, EXPIRE and TTL answer for it, the read path
expires keys lazily, and a background task sweeps the ones nobody reads again.
Where the deadline lives
Section titled “Where the deadline lives”A time to live is a moment, not a duration. EXPIRE key 100 does not store “100 seconds”; it
stores the instant 100 seconds from now, and every later answer is a subtraction against the
clock. The store’s value type grows one field:
/// One key in the store: the value, and the instant it stops being/// there.////// The deadline is an `Instant`, not a wall-clock time. It is monotonic,/// so adjusting the system clock cannot move a key's expiry, and it is/// process-relative, so a deadline has to become something else on its/// way to disk — that is step 6's problem.struct Entry { value: Value, /// `None` is a key with no deadline: it lives until it is /// overwritten or deleted, which is what `SET` leaves behind. expires_at: Option<Instant>,}The Option is the part the command layer cares about: None is what SET leaves behind, and
it is why TTL answers -1 rather than 0 for a key nobody has expired.
One rename came with it. The store code already imported std::collections::hash_map::Entry for
LPUSH’s vacant-or-occupied match, and the store’s own entry type takes that name now, so the
import became Entry as Slot. Nothing else in the file moved.
The model at work. Value, Entry, expired and ttl_of below are the tag’s, byte for byte;
the main around them prints what TTL would answer for four keys:
use std::collections::VecDeque;use std::time::{Duration, Instant};
/// What a key holds: a string, or a list of strings.enum Value { String(Vec<u8>), List(VecDeque<Vec<u8>>),}
/// One key in the store: the value, and the instant it stops being/// there.////// The deadline is an `Instant`, not a wall-clock time. It is monotonic,/// so adjusting the system clock cannot move a key's expiry, and it is/// process-relative, so a deadline has to become something else on its/// way to disk — that is step 6's problem.struct Entry { value: Value, /// `None` is a key with no deadline: it lives until it is /// overwritten or deleted, which is what `SET` leaves behind. expires_at: Option<Instant>,}
/// Whether `entry`'s deadline has arrived. A deadline of exactly `now`/// counts as arrived, the way the real server treats a key whose/// millisecond timestamp has passed.fn expired(entry: &Entry, now: Instant) -> bool { matches!(entry.expires_at, Some(at) if now >= at)}/// The seconds left on `entry`, the way `TTL` reports them: the/// remaining time rounded to the nearest second. `None` is a key with/// no deadline at all.////// The rounding is the real server's — a key with 100 seconds left/// answers 100, and one with under half a second left answers 0, which/// is not "expired": -2 is what that is for. Captured on redis-server/// 7.2.4.fn ttl_of(entry: &Entry, now: Instant) -> Option<i64> { let at = entry.expires_at?; let left = at.saturating_duration_since(now).as_millis() as i64; Some((left + 500) / 1000)}fn main() { let now = Instant::now(); let entries = [ ("forever", Entry { value: Value::String(b"kept".to_vec()), expires_at: None }), ("session", Entry { value: Value::String(b"token".to_vec()), expires_at: Some(now + Duration::from_secs(100)) }), ("almost", Entry { value: Value::String(b"flash".to_vec()), expires_at: Some(now + Duration::from_millis(400)) }), ("gone", Entry { value: Value::String(b"stale".to_vec()), expires_at: Some(now - Duration::from_millis(1)) }), ]; for (name, entry) in &entries { let ttl = if expired(entry, now) { -2 } else { ttl_of(entry, now).unwrap_or(-1) }; println!("{name:<9} {ttl}"); }}forever -1session 100almost 0gone -2Four rows, and they are the whole reply surface: -1 for a key with no deadline, the seconds left otherwise, 0 when under half a second is left, and -2 for a key that is already gone. The rounding behind that third row is not a Rust convention — it is the real server’s, captured below. A key with 400 ms left answers 0 and is still readable; “expired” is what -2 is for.
What the real server answers
Section titled “What the real server answers”Every reply in this table was captured off the real redis-server 7.2.4 over a raw socket, before the Rust was written:
| Request | Real server replies |
|---|---|
TTL k, no deadline set |
:-1\r\n |
TTL missing |
:-2\r\n |
EXPIRE k 100 |
:1\r\n |
EXPIRE k 100 again |
:1\r\n — the deadline moves |
EXPIRE missing 100 |
:0\r\n |
EXPIRE k abc |
-ERR value is not an integer or out of range |
EXPIRE k 1 2 |
-ERR Unsupported option 2 |
EXPIRE k 0 or EXPIRE k -1 |
:1\r\n — and the key is gone |
SET k v over a key with a deadline |
+OK\r\n, then TTL k answers -1 |
GET k after the deadline |
$-1\r\n |
DEL k after the deadline |
:0\r\n — the active cycle got there first |
LPUSH k x after the deadline |
:1\r\n — a new list, not WRONGTYPE |
EXPIRE k 9223370243862175 |
:1\r\n |
EXPIRE k 9223370243862176 |
-ERR invalid expire time in 'expire' command |
Three of those are not obvious. A non-positive TTL is a delete, not a deadline in the past. An
overwrite drops the deadline, so SET is the one command that quietly cancels an expiry. And the
range check runs before the key is looked at: EXPIRE missing 9223372036854775 answers the range
error, not :0.
The rounding deserves its own line. TTL on a key with 100 seconds left answers 100; 0.6 s
later it answers 99; under half a second left it answers 0. That is nearest-second rounding —
(milliseconds + 500) / 1000 — and the clone copies it exactly, which is the whole of ttl_of
above.
EXPIRE and TTL in the command layer
Section titled “EXPIRE and TTL in the command layer”Two new commands:
enum Command { Ping, Echo(Vec<u8>), Set(Vec<u8>, Vec<u8>), Get(Vec<u8>), Del(Vec<Vec<u8>>), LPush(Vec<u8>, Vec<Vec<u8>>), LRange(Vec<u8>, i64, i64), Expire(Vec<u8>, i64), Ttl(Vec<u8>),}Their arms, and the cap EXPIRE puts on its argument:
b"EXPIRE" => match args { [key, seconds] => { let seconds = parse_int(seconds).ok_or_else(not_an_integer)?; // The range check belongs to the argument, and it // runs before the key is looked at: the real server // answers the range error for a missing key too, // and refuses both ends — `EXPIRE k -9223372036854775808` // is the error, not a delete. Captured on // redis-server 7.2.4. if seconds.unsigned_abs() > MAX_EXPIRE_SECONDS as u64 { return Err(invalid_expire_time()); } Ok(Command::Expire(key.to_vec(), seconds)) } // Extra arguments are a divergence, not an oversight: // the real server reads them as NX/XX/GT/LT options and // answers `Unsupported option <arg>`. The clone has no // SET-style flags, so it answers the arity error. // Captured on redis-server 7.2.4. _ => Err(wrong_args(name)), }, b"TTL" => match args { [key] => Ok(Command::Ttl(key.to_vec())), _ => Err(wrong_args(name)), },The cap and the error reply live next to the parser:
/// The largest `EXPIRE` argument the clone takes, in either direction:/// `i64::MAX / 1000` seconds, the point where `seconds × 1000` stops/// fitting in an i64. The real server's cutoff is the same idea one/// layer up — a value whose millisecond form would not fit beside the/// current time — and it moves with the server's clock: measured here/// at 9223370243862175 seconds, accepted, with one more refused./// Captured on redis-server 7.2.4.const MAX_EXPIRE_SECONDS: i64 = i64::MAX / 1000;
fn invalid_expire_time() -> Frame { Frame::Error("ERR invalid expire time in 'expire' command".to_string())}The seconds argument goes through the same parse_int as LRANGE’s indices: +5 and 007 are
refused, and anything outside i64 is refused, because that is what the real server does with
them. The extra check is the range one, and it is the first thing anyone gets wrong:
use std::time::{Duration, Instant};
/// `EXPIRE`'s seconds arrive as an i64 — `parse_int` hands back an i64, the/// way the real server's own integer reader does — and this is the first/// thing anyone writes with them.fn deadline(seconds: i64) -> Instant { Instant::now() + Duration::from_secs(seconds)}
fn main() { let _ = deadline(100);}error[E0308]: mismatched types --> src/main.rs:7:42 | 7 | Instant::now() + Duration::from_secs(seconds) | ------------------- ^^^^^^^ expected `u64`, found `i64` | | | arguments to this function are incorrect |note: associated function defined here --> /Users/rango/.rustup/toolchains/1.99.0-aarch64-apple-darwin/lib/rustlib/src/rust/library/core/src/time.rs:224:18 |224 | pub const fn from_secs(secs: u64) -> Duration { | ^^^^^^^^^help: you can convert an `i64` to a `u64` and panic if the converted value doesn't fit | 7 | Instant::now() + Duration::from_secs(seconds.try_into().unwrap()) | ++++++++++++++++++++
For more information about this error, try `rustc --explain E0308`.parse_int hands back an i64 and from_secs wants a u64. The cast is easy; what makes it safe
is the range check that ran in from_frame, because without it the arithmetic does this:
use std::time::{Duration, Instant};
fn main() { // The value the real server refuses outright — `-ERR invalid expire // time in 'expire' command`, captured on redis-server 7.2.4 — fed // straight into the deadline arithmetic the clone would do without // its range check. let _ = Instant::now() + Duration::from_secs(i64::MAX as u64);}thread 'main' (3893536) panicked at src/main.rs:8:13:overflow when adding duration to instantnote: run with `RUST_BACKTRACE=1` environment variable to display a backtraceThe clone’s cutoff is i64::MAX / 1000 — 9223372036854775 seconds, about 292 million years —
which is where seconds × 1000 stops fitting in an i64, and it keeps ttl_of’s millisecond
arithmetic exact. The real server’s cutoff is the same idea one layer up: a value whose
millisecond form would not fit beside the current time, so it moves with the server’s clock. It
measured 9223370243862175 here, accepted, with one more refused. The band between the two lines
was 1,792,992,600 seconds wide when this was captured — the server’s own clock reading, since
that is the quantity the real rule subtracts and the clone’s does not. A fixed line cannot copy a
moving one, so the clone takes its own and names the difference.
The extra-arguments divergence is the other one. EXPIRE k 1 2 is read by the real server as
NX/XX/GT/LT options and answered Unsupported option 2; the clone has no SET-style
flags, so it answers the wrong-arity error.
Expiry on the read path
Section titled “Expiry on the read path”Expiry has two halves, and the real server has both. The lazy half runs on every read:
/// Drop `key` if its deadline has passed.////// This is lazy expiry, and the real server does it on every read: a key/// that has expired is gone whether or not the sweeper has reached it./// Captured on redis-server 7.2.4 — `GET` on an expired key answers/// nil, and a `TTL` afterwards answers -2.fn expire_if_needed(store: &mut HashMap<Vec<u8>, Entry>, key: &[u8], now: Instant) { if let Some(entry) = store.get(key) { if expired(entry, now) { store.remove(key); } }}GET calls it before it looks at the key, so a key whose deadline has passed answers nil even
if the sweeper has not run yet — the arm became Some(entry) => match &entry.value { … } when
Entry arrived, with the call above it. LPUSH calls it too, before its vacant-or-occupied
match: pushing onto an expired key starts a new list, exactly as it does on a key that was never
there, and the real server answers :1 there, not WRONGTYPE.
DEL is the one read that does not expire first, and the difference is a window rather than a
bug: between a deadline and the next sweep the clone still holds the key, so DEL answers 1
where the real server’s active cycle has usually reclaimed it and answers 0.
The sweeper
Section titled “The sweeper”The active half. Lazy expiry only reclaims keys that somebody reads again; this task reclaims the rest, once a second, for as long as the server runs:
/// How often the sweeper runs. Once a second is coarse next to the real/// server's active-expiry cycle, which runs ten times a second and/// samples the keyspace rather than reading all of it.const SWEEP_INTERVAL: Duration = Duration::from_secs(1);
/// One pass of the sweeper: every key whose deadline has passed, out./// Returns how many went.////// The lock is taken and dropped inside, like every command's: a guard/// held across the `interval.tick().await` below would make this future/// non-`Send`, and `tokio::spawn` refuses those.fn sweep(db: &Db, now: Instant) -> usize { let mut store = db.lock().unwrap(); let before = store.len(); store.retain(|_, entry| !expired(entry, now)); before - store.len()}/// The active half of expiry. Lazy expiry on the read path only/// reclaims keys that somebody reads again; this is the task that/// reclaims the rest, once a second, for as long as the server runs.////// `tokio::time::interval`'s first tick completes immediately, so the/// first pass runs at startup — against an empty store, which costs/// nothing.async fn sweeper(db: Db) { let mut interval = tokio::time::interval(SWEEP_INTERVAL); loop { interval.tick().await; let removed = sweep(&db, Instant::now()); if removed > 0 { println!("swept {removed} expired key(s)"); } }}And main grows one line, next to the store it shares:
let db = new_db(); // The sweeper is one more owner of the store, like every connection // task: what moves into it is a clone of the `Arc`. tokio::spawn(sweeper(db.clone()));The block below is the tag’s sweep, with the store types it needs and a main that runs one
pass over five keys:
use std::collections::{HashMap, VecDeque};use std::sync::{Arc, Mutex};use std::time::{Duration, Instant};
/// What a key holds: a string, or a list of strings.enum Value { String(Vec<u8>), List(VecDeque<Vec<u8>>),}
/// One key in the store: the value, and the instant it stops being/// there.////// The deadline is an `Instant`, not a wall-clock time. It is monotonic,/// so adjusting the system clock cannot move a key's expiry, and it is/// process-relative, so a deadline has to become something else on its/// way to disk — that is step 6's problem.struct Entry { value: Value, /// `None` is a key with no deadline: it lives until it is /// overwritten or deleted, which is what `SET` leaves behind. expires_at: Option<Instant>,}
/// The store, shared by every connection's task.////// A standard-library `Mutex`, not a Tokio one. Every critical section in/// `execute` is a couple of hash-map operations with no `.await` inside,/// so a synchronous lock is both the cheaper choice and the one that/// cannot be held across a suspension point — a guard that outlives its/// statement here makes the future non-`Send`, and `tokio::spawn` refuses/// it at compile time. The failure mode of a long critical section is/// different: it blocks the worker thread, and every task on it.type Db = Arc<Mutex<HashMap<Vec<u8>, Entry>>>;
fn new_db() -> Db { Arc::new(Mutex::new(HashMap::new()))}
/// Whether `entry`'s deadline has arrived. A deadline of exactly `now`/// counts as arrived, the way the real server treats a key whose/// millisecond timestamp has passed.fn expired(entry: &Entry, now: Instant) -> bool { matches!(entry.expires_at, Some(at) if now >= at)}/// One pass of the sweeper: every key whose deadline has passed, out./// Returns how many went.////// The lock is taken and dropped inside, like every command's: a guard/// held across the `interval.tick().await` below would make this future/// non-`Send`, and `tokio::spawn` refuses those.fn sweep(db: &Db, now: Instant) -> usize { let mut store = db.lock().unwrap(); let before = store.len(); store.retain(|_, entry| !expired(entry, now)); before - store.len()}fn main() { let now = Instant::now(); let db = new_db(); { let mut store = db.lock().unwrap(); let value = |expires_at| Entry { value: Value::String(b"v".to_vec()), expires_at, }; store.insert(b"forever".to_vec(), value(None)); store.insert(b"session".to_vec(), value(Some(now + Duration::from_secs(100)))); store.insert(b"cache".to_vec(), value(Some(now + Duration::from_secs(1)))); store.insert(b"flash".to_vec(), value(Some(now + Duration::from_millis(400)))); store.insert(b"stale".to_vec(), value(Some(now - Duration::from_secs(1)))); } // One pass, taken a second later than the deadlines above: cache and // flash have passed, and stale passed long ago. let removed = sweep(&db, now + Duration::from_secs(2)); let mut remaining: Vec<String> = db .lock() .unwrap() .keys() .map(|key| String::from_utf8_lossy(key).into_owned()) .collect(); remaining.sort(); println!("swept {removed}"); println!("remaining: {}", remaining.join(", "));}swept 3remaining: forever, sessionTwo things about the task itself. tokio::time::interval’s first tick completes immediately, so
the first pass runs at startup — against an empty store, which costs nothing. And the lock is
taken and dropped inside sweep, like every command’s: a guard held across the
interval.tick().await would make this future non-Send, and tokio::spawn refuses those.
The real server’s active-expiry cycle runs ten times a second and samples the keyspace rather
than reading all of it. The clone reads the whole map once a second, which at this size is one
retain pass per second and nothing more — but it is a difference in kind, not in degree, and it
is the first thing to change if the store ever grows.
Fifty tests, up from thirty-two: the step-4 set carried over unchanged, plus eighteen for the new
behaviour. The reply matrix is pinned against the captures above — TTL answers -1 without a
deadline and -2 for a missing key, a non-positive EXPIRE deletes and answers 1, SET drops the
deadline, an expired key is gone on the next read, LPUSH onto an expired key starts a new list,
and TTL rounds to the nearest second. The sweeper is tested at both levels: sweep removes
exactly the three keys whose deadline has passed out of five, and the spawned task reclaims an
already-expired key without anybody reading it.
$ cargo test Compiling mini-redis v0.1.0 Finished `test` profile [unoptimized + debuginfo] target(s) in 0.64s Running unittests src/main.rs (/Volumes/RustBuild/tracks/debug/deps/mini_redis-be061b86284cc959)
running 50 teststest tests::an_empty_array_is_not_a_command ... oktest tests::an_expire_time_past_the_cutoff_is_refused ... oktest tests::a_frame_in_two_pieces_is_incomplete_not_invalid ... oktest tests::an_unknown_command_caps_its_argument_list_at_128_bytes ... oktest tests::a_deadline_that_has_arrived_expires_the_key_on_read ... oktest tests::a_key_with_no_deadline_answers_minus_one ... oktest tests::a_non_positive_ttl_on_a_missing_key_answers_zero ... oktest tests::a_non_positive_ttl_deletes_the_key ... oktest tests::a_buffered_second_frame_needs_no_read ... oktest tests::an_unknown_command_lists_its_arguments ... oktest tests::bytes_that_are_not_resp_are_invalid ... oktest tests::del_counts_only_the_keys_that_existed ... oktest tests::echo_round_trips_through_the_codec ... oktest tests::a_protocol_error_ends_the_connection_without_a_reply ... oktest tests::a_half_sent_command_does_not_block_another_connection ... oktest tests::echo_with_the_wrong_number_of_arguments_is_refused ... oktest tests::error_messages_quote_the_command_name_as_it_was_sent ... oktest tests::every_argument_must_be_a_bulk_string ... oktest tests::every_frame_type_round_trips ... oktest tests::expire_on_a_missing_key_answers_zero ... oktest tests::expire_reads_its_argument_the_way_the_real_server_does ... oktest tests::expire_replaces_an_earlier_deadline ... oktest tests::expire_then_ttl_reports_the_seconds_left ... oktest tests::expire_with_the_wrong_number_of_arguments_is_refused ... oktest tests::expire_works_on_a_list_key ... oktest tests::get_on_a_list_is_a_wrongtype_error ... oktest tests::get_on_a_missing_key_answers_null ... oktest tests::lpush_needs_at_least_one_value ... oktest tests::lpush_on_a_string_key_is_a_wrongtype_error ... oktest tests::lpush_on_an_expired_key_starts_a_new_list ... oktest tests::lpush_prepends_each_value_in_order ... oktest tests::lrange_on_a_missing_key_answers_an_empty_array ... oktest tests::lrange_on_a_string_key_is_a_wrongtype_error ... oktest tests::lrange_reads_a_slice_the_way_the_real_server_clamps_it ... oktest tests::one_decode_consumes_exactly_one_frame ... oktest tests::lrange_with_a_non_integer_index_is_refused ... oktest tests::ping_with_an_argument_echoes_it ... oktest tests::set_clears_the_deadline ... oktest tests::set_replaces_a_list_without_an_error ... oktest tests::set_then_get_round_trips ... oktest tests::the_exact_bytes_the_real_redis_cli_sends_for_ping ... oktest tests::the_sweeper_removes_only_the_keys_whose_deadline_has_passed ... oktest tests::ping_over_a_real_socket ... oktest tests::pipelined_commands_are_all_answered ... oktest tests::ttl_on_a_missing_key_answers_minus_two ... oktest tests::ttl_rounds_to_the_nearest_second ... oktest tests::ttl_with_the_wrong_number_of_arguments_is_refused ... oktest tests::two_connections_share_one_store ... oktest tests::a_frame_split_across_two_reads_is_reassembled ... oktest tests::the_sweeper_task_reclaims_an_expired_key_on_its_own ... ok
test result: ok. 50 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.11sThe order the tests print in varies between runs; the set does not. The Running line names this
machine’s shared build cache; elsewhere it reads target/debug/deps/mini_redis-….
Seeing it run
Section titled “Seeing it run”cargo run stops before it listens, because a real redis-server already owns 127.0.0.1:6379:
$ cargo run Running `/Volumes/RustBuild/tracks/debug/mini-redis`Error: Os { code: 48, kind: AddrInUse, message: "Address already in use" }To check the clone without disturbing the server that owns the port, the same binary was rebuilt on a scratch port and the real redis-cli pointed at it:
$ redis-cli -p 7781 set session tokenOK
$ redis-cli -p 7781 ttl session(integer) -1
$ redis-cli -p 7781 expire session 100(integer) 1
$ redis-cli -p 7781 ttl session(integer) 100
$ redis-cli -p 7781 expire session abc(error) ERR value is not an integer or out of range
$ redis-cli -p 7781 expire missing 100(integer) 0
$ redis-cli -p 7781 ttl missing(integer) -2
$ redis-cli -p 7781 set flash soonOK
$ redis-cli -p 7781 expire flash 1(integer) 1
$ redis-cli -p 7781 get flash"soon"
$ redis-cli -p 7781 ttl flash(integer) 1
$ redis-cli -p 7781 expire session 0(integer) 1
$ redis-cli -p 7781 get session(nil)
$ redis-cli -p 7781 expire session 1 2(error) ERR wrong number of arguments for 'expire' command
$ redis-cli -p 7781 set far 1OK
$ redis-cli -p 7781 expire far 9223372036854775(integer) 1
$ redis-cli -p 7781 ttl far(integer) 9223372036854775
$ redis-cli -p 7781 del far(integer) 1
# ... a second and a half passes, and the sweeper runs ...$ redis-cli -p 7781 get flash(nil)
$ redis-cli -p 7781 ttl flash(integer) -2The last two lines are the sweep at work. flash was given one second, and by the time anything
asked about it again it was gone. The client cannot tell whether the read or the sweep removed it
— the server’s own stdout can:
listening on 127.0.0.1:7781swept 1 expired key(s)What is deliberately not here
Section titled “What is deliberately not here”PERSIST. The sixteen commands from step 1 have no way to remove a deadline; overwriting the key withSETis how a client cancels one.SETflags. NoEX,NX,XXorKEEPTTL;EXPIREis the only way to set a deadline, which is why extra arguments above answer the wrong-arity error instead of being read as flags.- A sampled sweep. The real server’s cycle reads a sample of the keyspace; the clone reads
all of it, one
retainpass a second. The cost of that is stated above. - A matching cutoff. The clone’s fixed
i64::MAX / 1000against the real server’s clock-moving one, with the band between them measured above. - Deadlines across a restart. An
Instantis process-relative. A snapshot has to store something else, which is step 6’s problem.
Step 6, Persistence with a snapshot, writes the store to disk and reads it back, deadlines included. It is not written yet, so it gets no link — the track overview carries the full list as articles land.
Related
Section titled “Related”- Handling concurrent connections — step 4, the store this step puts deadlines into.
- Sharing state between threads —
Arc,Mutex, and why the guard never crosses an await, the sweeper included. - Async in practice — what
spawnandinterval.tick()are doing under the sweeper task.