Appendix B-Build-From-Scratch Data Structures Reference¶
A working Rust engineer should have implemented each of the following at least once, with property tests, Miri, and (where concurrent) Loom. This appendix sketches the minimal-viable design for each. Full implementations are the labs in Months 3, 4, and 6.
B.1 Single-Threaded Hash Map (Open Addressing, Robin Hood)¶
When: pedagogical only-hashbrown::HashMap is faster than anything you will write.
Design:
- Single Vec<Entry> backing array; entries store (hash, key, value) or a tombstone.
- Robin Hood probing: track each entry's distance from its ideal slot; on insert, swap with any entry whose distance is shorter than the inserter's. This bounds variance in probe length.
- Resize at load factor ~0.875.
- hashbrown (used by std since 1.36) further uses SIMD for parallel probe; that is the next exercise after this one.
Lab outcomes: cache-friendly layout intuition, the cost of generic Hasher, niche optimization in Option<u64> for entry-tag storage.
B.2 B-Tree Map¶
When: ordered iteration, range queries, on-disk indexes (with adapted node sizes).
Design:
- Branching factor B (std uses 6; for cache-line-fit nodes you might use 11–15 depending on key/value sizes).
- Two node kinds: leaf and internal. Implement as enum or as separately-allocated structs with a tag.
- MaybeUninit<K; 2*B-1> for keys; insertions copy-shift, splits move half to a new node.
- Walking the tree mutably is the unsafe-rust master class-see std's BTreeMap source for the canonical handling of NodeRef<BorrowType, K, V, NodeType>.
Lab outcomes: complex unsafe with strong invariants, MaybeUninit for arrays, PhantomData for borrow-type encoding.
B.3 Sharded Concurrent Hash Map¶
When: production reads/writes, when contention is moderate. The pragmatic choice for almost every concurrent map need.
Design:
- N shards, each RwLock<HashMap<K, V>>. N typically 16–64; tune via cargo bench for your contention pattern.
- Hash key, shard_idx = hash % N, lock the shard, perform the op.
- Iteration is delicate: lock shards in order, snapshot or hold the lock for each.
Lab outcomes: the RwLock vs Mutex tradeoff, the cost of Hash + Eq re-evaluation, the dashmap API study.
B.4 Lock-Free Hash Map (Open-Addressed, Epoch-Reclaimed)¶
When: extreme contention, when flurry or dashmap are not enough.
Design:
- Slots are AtomicPtr<Entry> (or tagged atomic word for inline values).
- Insert: probe via CAS, inserting Entry. Failures retry to next slot.
- Delete: tombstone via CAS.
- Resize: allocate new table, transfer entries via help_resize cooperative pattern. Old table reclaimed via crossbeam-epoch once no thread observes it.
- Memory ordering: Acquire/Release on slot CAS; SeqCst only when establishing a total order on resize commits.
Lab outcomes: every paragraph above is its own bug class. This is the hardest data structure in the curriculum and the one that most differentiates expert from journeyman Rust engineers.
B.5 SPSC Lock-Free Ring Buffer¶
When: audio threads, real-time control loops, log producers.
Design:
- Fixed-capacity [UnsafeCell<MaybeUninit<T>>; CAP] (CAP a power of two for cheap modulo).
- head: AtomicUsize, tail: AtomicUsize, each on its own cache line (CachePadded).
- Producer: load tail (Relaxed), check space against head (Acquire), write slot, store tail (Release).
- Consumer: symmetric, swapping head/tail.
- Wait-free per side; needs no CAS, only atomic loads/stores.
Lab outcomes: cache-line awareness, Acquire/Release pairing, the pattern for "check then act" without locks.
B.6 MPMC Bounded Queue (`crossbeam::ArrayQueue - style)¶
When: work-stealing schedulers, bounded work pools.
Design:
- Slot array with AtomicUsize "stamp" per slot encoding (lap, index, occupied flag).
- Producer CAS the stamp from "empty at lap N" to "occupied at lap N".
- Consumer CAS from "occupied at lap N" to "empty at lap N+1".
- The stamp scheme avoids the ABA problem and the need for hazard pointers.
Lab outcomes: encoding state in atomics, lock-free without epoch reclamation, why Vec::reserve is the right initialization shape.
B.7 Intrusive Doubly-Linked List¶
When: kernel code, async runtimes' waker lists, anything that must avoid per-node allocation.
Design:
- The list does not own nodes. Nodes own their Pointers { prev: Option<NonNull<Node>>, next: Option<NonNull<Node>> }.
- Nodes must be Pinned because the list stores raw pointers to them.
- unsafe API: the consumer asserts that nodes outlive the list and are not aliased. This is the pattern in tokio::sync::Notify, parking_lot::WaitQueue, and intrusive-collections.
Lab outcomes: Pin in anger, the safety contract for intrusive structures, why LinkedList in std is rarely the right answer.
B.8 Slab Allocator¶
When: lots of small fixed-size allocations with churn (e.g., per-connection state in a server).
Design:
- A Vec<Slot<T>> where Slot<T> = { value: MaybeUninit<T>, next_free: usize }.
- A free-list head index. Insert: pop free-list, write value, return index. Remove: push index onto free-list, drop value.
- O(1) insert and remove, integer-handle indexing, no per-element allocation.
Lab outcomes: slab crate study, generational indices for ABA defense (see generational-arena), the relationship to ECS storage patterns in game engines.
B.9 Bump Allocator (Arena)¶
When: short-lived per-request allocations, parser ASTs, anything where the lifetime ends together.
Design:
- A Vec<u8> (or chunked list of Vec<u8>s for unbounded growth) and a current offset.
- Allocate: align current, advance, return pointer.
- Drop everything at once (no per-item destructors run by default; see bumpalo::Bump::alloc vs alloc_with).
Lab outcomes: alignment math, pointer arithmetic with provenance, why Rust ASTs and rustc itself use bump allocation.
B.10 Skip List (Concurrent)¶
When: ordered concurrent containers; the foundation of crossbeam-skiplist. Used in RocksDB-style memtables.
Design: - Tower of forward pointers per node, height geometrically distributed. - Concurrent insert: build the new node bottom-up, link levels via CAS. Stale links retry. - Removal: logical (mark deleted) then physical (unlink).
Lab outcomes: lock-free with non-trivial structure, randomization in algorithm design, the alternative to balanced trees in concurrent settings.
B.11 LSM-Tree Memtable + SSTable Pair¶
When: storage engines (RocksDB, LevelDB, Sled-style).
Design: - Memtable: a sorted concurrent map (skip list or sharded BTree) holding recent writes. - WAL (write-ahead log) appended for durability. - On size threshold, flush memtable to an immutable SSTable on disk: sorted key-value pairs with a sparse index and Bloom filter. - Compaction merges SSTables periodically.
Lab outcomes: durability/throughput tradeoffs, memory-mapped vs read-syscall, Bloom filters in practice. Optional capstone-tier.
Difficulty Ranking¶
| Tier | Structures |
|---|---|
| Warmup | Hash map (single-threaded), Slab, Bump |
| Intermediate | B-Tree, Sharded concurrent map, SPSC ring |
| Advanced | MPMC queue, Intrusive list |
| Expert | Lock-free hash map, Skip list, LSM-tree |
Pick at least one from each tier. Ship with property tests, benchmarks, and Miri.