In-Memory Key-Value Store

An in-memory key-value store (modeled after Redis and Memcached) stores key-value records with optional Time-To-Live (TTL) expiration, atomic integer increments (INCRBY), prefix scans, and a Write-Ahead Log (WAL) / command snapshot format.

In-Memory KV Store with Lazy + Active TTL Expiration:

  `Command::Set { key, val, ttl }`
          |
          v
  `HashMap<String, Record { value: Vec<u8>, expires_at: Option<u64> }>`
          |
          +-- `get(key, now_ms)`:
          |   If `expires_at <= Some(now_ms)` ---> Expired! Return `None` (Lazy Eviction)
          |
          +-- `purge_expired(now_ms)`:
              `map.retain(|_, rec| !rec.is_expired(now_ms))` (Active Compaction)

Core Commands and TTL Architecture

Passing a monotonic or epoch millisecond timestamp now_ms: u64 (or Clock trait) into operations keeps TTL expiration 100% deterministic in tests and production replay logs:

Complete Runnable Implementation

use std::collections::HashMap;

#[derive(Debug, Clone, PartialEq, Eq)]
struct Record {
    value: String,
    expires_at_ms: Option<u64>,
}

impl Record {
    #[inline]
    fn is_expired(&self, now_ms: u64) -> bool {
        self.expires_at_ms.is_some_and(|exp| now_ms >= exp)
    }
}

#[derive(Debug, PartialEq, Eq)]
pub enum KvError {
    NotAnInteger(String),
    Overflow,
}

#[derive(Default)]
pub struct KvStore {
    entries: HashMap<String, Record>,
}

impl KvStore {
    pub fn new() -> Self {
        Self::default()
    }

    pub fn set(
        &mut self,
        key: impl Into<String>,
        value: impl Into<String>,
        ttl_ms: Option<u64>,
        now_ms: u64,
    ) {
        let expires_at_ms = ttl_ms.map(|ttl| now_ms.saturating_add(ttl));
        self.entries.insert(
            key.into(),
            Record {
                value: value.into(),
                expires_at_ms,
            },
        );
    }

    /// Retrieves `key` if present and not expired; lazily evicts `key` if expired!
    pub fn get(&mut self, key: &str, now_ms: u64) -> Option<&str> {
        if self.entries.get(key).is_some_and(|r| r.is_expired(now_ms)) {
            self.entries.remove(key);
            return None;
        }
        self.entries.get(key).map(|r| r.value.as_str())
    }

    pub fn delete(&mut self, key: &str) -> bool {
        self.entries.remove(key).is_some()
    }

    /// Atomically increments an integer value stored at `key` (initializing to 0 if absent/expired).
    pub fn incr_by(&mut self, key: &str, delta: i64, now_ms: u64) -> Result<i64, KvError> {
        let current_rec = self.entries.get(key).filter(|r| !r.is_expired(now_ms));

        let (current_val, preserved_expiry) = match current_rec {
            Some(rec) => {
                let parsed = rec
                    .value
                    .parse::<i64>()
                    .map_err(|_| KvError::NotAnInteger(rec.value.clone()))?;
                (parsed, rec.expires_at_ms)
            }
            None => (0i64, None),
        };

        let next_val = current_val.checked_add(delta).ok_or(KvError::Overflow)?;
        self.entries.insert(
            key.to_string(),
            Record {
                value: next_val.to_string(),
                expires_at_ms: preserved_expiry,
            },
        );
        Ok(next_val)
    }

    /// Actively sweeps all expired keys, returning the number of keys evicted.
    pub fn purge_expired(&mut self, now_ms: u64) -> usize {
        let before = self.entries.len();
        self.entries.retain(|_, rec| !rec.is_expired(now_ms));
        before - self.entries.len()
    }
}

fn main() {
    let mut store = KvStore::new();
    let t0 = 1_000u64;

    // 1. Set a session token with a 500ms TTL:
    store.set("session:alice", "tok_xyz", Some(500), t0);
    assert_eq!(store.get("session:alice", t0 + 499), Some("tok_xyz"));
    // At t0 + 500ms, the key has expired and is lazily evicted:
    assert_eq!(store.get("session:alice", t0 + 500), None);

    // 2. Test atomic `incr_by` counter:
    assert_eq!(store.incr_by("views:home", 1, t0), Ok(1));
    assert_eq!(store.incr_by("views:home", 10, t0), Ok(11));
    assert_eq!(store.get("views:home", t0), Some("11"));

    println!("Counter views:home = {:?}", store.get("views:home", t0));
}

Counter views:home = Some("11")