Skip to content
Select theme

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.

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:

src/main.rs — the value model
/// 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:

forever -1
session 100
almost 0
gone -2

Four 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.

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.

Two new commands:

src/main.rs — the new variants
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:

src/main.rs — parsing
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:

src/main.rs — the cap and the error
/// 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:

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:

thread 'main' (3893536) panicked at src/main.rs:8:13:
overflow when adding duration to instant
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

The 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 has two halves, and the real server has both. The lazy half runs on every read:

src/main.rs — lazy expiry
/// 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 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:

src/main.rs — the sweeper
/// 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:

src/main.rs — main
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:

swept 3
remaining: forever, session

Two 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 tests
test tests::an_empty_array_is_not_a_command ... ok
test tests::an_expire_time_past_the_cutoff_is_refused ... ok
test tests::a_frame_in_two_pieces_is_incomplete_not_invalid ... ok
test tests::an_unknown_command_caps_its_argument_list_at_128_bytes ... ok
test tests::a_deadline_that_has_arrived_expires_the_key_on_read ... ok
test tests::a_key_with_no_deadline_answers_minus_one ... ok
test tests::a_non_positive_ttl_on_a_missing_key_answers_zero ... ok
test tests::a_non_positive_ttl_deletes_the_key ... ok
test tests::a_buffered_second_frame_needs_no_read ... ok
test tests::an_unknown_command_lists_its_arguments ... ok
test tests::bytes_that_are_not_resp_are_invalid ... ok
test tests::del_counts_only_the_keys_that_existed ... ok
test tests::echo_round_trips_through_the_codec ... ok
test tests::a_protocol_error_ends_the_connection_without_a_reply ... ok
test tests::a_half_sent_command_does_not_block_another_connection ... ok
test tests::echo_with_the_wrong_number_of_arguments_is_refused ... ok
test tests::error_messages_quote_the_command_name_as_it_was_sent ... ok
test tests::every_argument_must_be_a_bulk_string ... ok
test tests::every_frame_type_round_trips ... ok
test tests::expire_on_a_missing_key_answers_zero ... ok
test tests::expire_reads_its_argument_the_way_the_real_server_does ... ok
test tests::expire_replaces_an_earlier_deadline ... ok
test tests::expire_then_ttl_reports_the_seconds_left ... ok
test tests::expire_with_the_wrong_number_of_arguments_is_refused ... ok
test tests::expire_works_on_a_list_key ... ok
test tests::get_on_a_list_is_a_wrongtype_error ... ok
test tests::get_on_a_missing_key_answers_null ... ok
test tests::lpush_needs_at_least_one_value ... ok
test tests::lpush_on_a_string_key_is_a_wrongtype_error ... ok
test tests::lpush_on_an_expired_key_starts_a_new_list ... ok
test tests::lpush_prepends_each_value_in_order ... ok
test tests::lrange_on_a_missing_key_answers_an_empty_array ... ok
test tests::lrange_on_a_string_key_is_a_wrongtype_error ... ok
test tests::lrange_reads_a_slice_the_way_the_real_server_clamps_it ... ok
test tests::one_decode_consumes_exactly_one_frame ... ok
test tests::lrange_with_a_non_integer_index_is_refused ... ok
test tests::ping_with_an_argument_echoes_it ... ok
test tests::set_clears_the_deadline ... ok
test tests::set_replaces_a_list_without_an_error ... ok
test tests::set_then_get_round_trips ... ok
test tests::the_exact_bytes_the_real_redis_cli_sends_for_ping ... ok
test tests::the_sweeper_removes_only_the_keys_whose_deadline_has_passed ... ok
test tests::ping_over_a_real_socket ... ok
test tests::pipelined_commands_are_all_answered ... ok
test tests::ttl_on_a_missing_key_answers_minus_two ... ok
test tests::ttl_rounds_to_the_nearest_second ... ok
test tests::ttl_with_the_wrong_number_of_arguments_is_refused ... ok
test tests::two_connections_share_one_store ... ok
test tests::a_frame_split_across_two_reads_is_reassembled ... ok
test 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.11s

The 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-….

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 token
OK
$ 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 soon
OK
$ 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 1
OK
$ 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) -2

The 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:7781
swept 1 expired key(s)
  • PERSIST. The sixteen commands from step 1 have no way to remove a deadline; overwriting the key with SET is how a client cancels one.
  • SET flags. No EX, NX, XX or KEEPTTL; EXPIRE is 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 retain pass a second. The cost of that is stated above.
  • A matching cutoff. The clone’s fixed i64::MAX / 1000 against the real server’s clock-moving one, with the band between them measured above.
  • Deadlines across a restart. An Instant is 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.