Day 4 · Traits & Generics

The Project 2 overview promised a store you can put behind a network and share across threads. None of that matters if the core engine isn’t reusable and honest about its contract first. So Day 4 builds the bottom of the stack: a trait that says what a store is, a generic struct that implements it over a HashMap, and a REPL to poke at it. Two big Rust ideas show up because the design needs them — traits to separate “what” from “how”, generics so one engine serves any key/value type — plus a first, gentle brush with lifetimes.

A trait is a contract, not a class

In Rust you don’t start from a class hierarchy; you start by writing down the behaviour you require, as a trait. Here is kvlite’s:

   pub trait Store<K, V> {
       fn set(&mut self, key: K, value: V) -> Result<Option<V>>;
       fn get(&self, key: &K) -> Option<V>;
       fn delete(&mut self, key: &K) -> Result<Option<V>>;
       fn len(&self) -> usize;

       // A *default method*: implementors get it for free, in terms of len().
       fn is_empty(&self) -> bool {
           self.len() == 0
       }
   }

Read it as a promise: “anything that is a Store can set, get, delete, and report its size.” It says nothing about how — HashMap, B-tree, a file, a remote server; all are allowed. Code written against the trait (fn report<S: Store<K, V>>(s: &S)) works with every implementation, forever. That separation is the whole point: the Day 7 server will talk to a Store, never to a specific struct, so swapping the engine never touches the network code.

&self vs &mut self — the trait encodes the borrow rule

Notice get takes &self (a shared borrow — reads don’t change anything) but set/delete take &mut self (exclusive — they mutate). That isn’t decoration: it’s the “shared XOR mutable” rule from The Rust Mindset, written into the contract. The compiler will later use exactly these signatures to decide a read lock is enough for get but a write lock is needed for set. The trait is already telling the truth about concurrency.

Generics: one engine, any key and value

We don’t want a StringStore and an IntStore and a BytesStore. We want one engine, generic over the key type K and value type V. The implementation is just a HashMap in a struct:

   use std::collections::HashMap;
   use std::hash::Hash;

   #[derive(Debug, Default, Clone)]
   pub struct MemStore<K, V> {
       map: HashMap<K, V>,
   }

   impl<K, V> Store<K, V> for MemStore<K, V>
   where
       K: Eq + Hash,   // a HashMap key must be hashable and comparable
       V: Clone,       // get() hands back an owned copy (see below)
   {
       fn set(&mut self, key: K, value: V) -> Result<Option<V>> {
           Ok(self.map.insert(key, value))   // insert returns the old value
       }
       fn get(&self, key: &K) -> Option<V> {
           self.map.get(key).cloned()
       }
       fn delete(&mut self, key: &K) -> Result<Option<V>> {
           Ok(self.map.remove(key))
       }
       fn len(&self) -> usize {
           self.map.len()
       }
   }

The where clause is the interesting part. K: Eq + Hash are trait bounds — they say “this code only makes sense for key types that can be hashed and compared for equality,” which is precisely what a hash table needs. The compiler enforces it: try to use a key type that isn’t Hash and you get a clear error at the call site, not a mystery at runtime. Bounds are how generics stay safe — a generic function can only do to a T what its bounds permit.

By the numbers — why a HashMap, not a Vec

The data model is a dictionary, so lookup cost is everything. Find a key among N entries:

   Vec<(K, V)> linear scan : compares ≈ N/2 on average
   HashMap<K, V>           : compares ≈ 1   (hash to a bucket, check it)

At N = 1,000,000 keys that’s ~500,000 comparisons per GET versus ~1. The HashMap’s O(1)-average lookup is the reason a KV store can answer in microseconds while holding millions of keys.

Under the hood — generics are zero-cost (monomorphization)

A generic in Rust is not a runtime trick. When you actually use MemStore<String, String> and MemStore<u64, Vec<i32>>, the compiler stamps out a separate, specialized copy of the code for each concrete pair — a process called monomorphization. The generated machine code is identical to what you’d write by hand for that exact type: no boxing, no vtable, no per-call type checks. You get the ergonomics of “write once, use for any type” with the speed of hand-specialized code. The cost is paid at compile time (more code to compile) and in binary size, never at runtime. This is what Rust means by zero-cost abstraction: the abstraction compiles away.

It actually happened — HashDoS, and why Rust seeds its hasher randomly

In December 2011 (28C3), Alexander Klink and Julian Wälde showed that many web platforms could be knocked over by hash-collision denial of service: an attacker sends keys engineered to land in the same hash bucket, collapsing the HashMap’s O(1) lookups into O(n) and pinning the CPU. Rust’s standard HashMap defends against this by default — it uses SipHash with a random per-instance seed, so an attacker can’t predict which keys collide. The trade-off: SipHash is slightly slower than a trivial hash, which is why performance-sensitive code sometimes opts into a faster hasher when the keys are trusted. The default protects you; you give it up deliberately, in code you can see.

Lifetimes, in context: get clones, but it didn’t have to

Why does get return an owned Option<V> (a clone) instead of a cheaper borrow, Option<&V>? Add the borrowing version as an inherent method and the answer becomes visible:

   impl<K, V> MemStore<K, V> {
       pub fn get_ref(&self, key: &K) -> Option<&V>
       where
           K: Eq + Hash,
       {
           self.map.get(key)
       }
   }

There are no 'a annotations here, yet a lifetime is absolutely present — the compiler infers it by lifetime elision. The signature desugars to:

   fn get_ref<'a>(&'a self, key: &K) -> Option<&'a V>

The rule: when a method takes &self, the returned reference is tied to self’s lifetime. Plain English: the borrowed &V is only valid as long as the MemStore it came from is alive and unchanged. That’s exactly what you want single-threaded — it’s free and safe.

So why does the trait’s get clone instead? Foreshadowing Day 5: once the map lives inside a lock, a borrow into it would have to outlive the lock guard — and the compiler won’t allow that, because reading freed-or-changing data is the very bug it exists to stop. Returning an owned clone lets us release the lock before the caller touches the value. The clone isn’t waste; it’s the price of letting go of the lock early. The lifetime rules made a design decision for us, on purpose.

Closures: iterate without exposing the map

We keep map private, but callers still need to walk the contents. A method that takes a closure lets them, without handing out the HashMap:

   pub fn for_each<F: FnMut(&K, &V)>(&self, mut f: F) {
       for (k, v) in &self.map {
           f(k, v);
       }
   }
   // caller: let mut total = 0; store.for_each(|_k, v| total += *v);

F: FnMut(&K, &V) is a trait bound again — this time on a closure type. FnMut means “callable, and allowed to mutate what it captured” (here, total). Closures are just types that implement one of the Fn/FnMut/FnOnce traits, so everything you learned about generics applies to them too.

Build it: a single-threaded store + a REPL

That’s enough engine to do real work. Wire it to standard input as a tiny REPL (read-eval-print loop) so you can drive it by hand — this is the Day 4 deliverable, and it’s already in the crate as kvlite repl:

   $ cargo run -- repl
   kvlite repl — replayed 0 record(s) from kvlite.wal
   commands: SET k v | GET k | DEL k | PING | QUIT
   SET name ada
   OK
   GET name
   VALUE ada
   GET nope
   NIL

The loop is ordinary: read a line, parse the first word into a command, dispatch to set/get/delete, print the reply.

   stdin ──▶ read line ──▶ parse ──▶ MemStore::{set,get,delete} ──▶ print
              ▲                                                       │
              └───────────────────── loop ◀───────────────────────────┘

Run it, then try to break it: feed it SET with no value, a GET for a missing key, a blank line. Each edge is a Result or an Option you have to handle — and the compiler made you handle them, which is the recurring lesson: what does building this force you to understand, and what is the compiler protecting you from? Here it’s protecting you from a forgotten case and from a borrow that outlives its data — both turned into errors you fix in seconds.

In the crate, the real REPL routes through the same parse → execute path the network server will use on Day 7, so the protocol is written exactly once. Next, we make the store safe to share.

→ Next: Day 5 · Concurrency · Back to the Project 2 overview

Check your understanding

1. A trait and a struct play different roles here. State, in one sentence each, what Store<K, V> is responsible for versus what MemStore<K, V> is responsible for.
2. The impl has where K: Eq + Hash, V: Clone. Why does the HashMap require K: Eq + Hash, and why does our get require V: Clone?
3. What is monomorphization, and why does it mean Rust generics have no runtime cost?
4. get_ref has no 'a written anywhere, yet returns a borrowed Option<&V>. What lifetime does elision give the result, and in plain English what does that lifetime guarantee?
5. The trait’s get returns an owned clone instead of a reference. Give the concrete reason this matters the moment the map is put behind a lock (Day 5).

Show answers

1. Store<K, V> is the contract — it names the behaviour (set/get/delete/len) any store must provide, with no commitment to how. MemStore<K, V> is one implementation of that contract, backed by a HashMap.
2. A HashMap finds keys by hashing them into buckets and comparing for equality on collision, so the key type must be Hash (to bucket) and Eq (to compare) — K: Eq + Hash. Our get returns an owned value by calling .cloned(), which requires the value type to be duplicable — V: Clone.
3. Monomorphization is the compiler generating a separate specialized copy of generic code for each concrete type it’s used with. Because each copy is hand-specialized machine code (no vtable, no boxing, no runtime type checks), the abstraction compiles away — the cost is paid at compile time and in binary size, not at runtime.
4. Elision reads it as fn get_ref<'a>(&'a self, key: &K) -> Option<&'a V>: the result borrows from self. It guarantees the returned &V is valid only as long as the MemStore it came from is alive and not mutated — you can’t keep using it after the store changes or drops.
5. Once the HashMap lives inside a lock, a returned &V would borrow data owned by the lock guard; the borrow would have to outlive the guard, which the compiler forbids (it would be reading data the lock no longer protects). Returning an owned clone lets the lock be released before the caller uses the value — so cloning is what makes early unlock possible.