Rafael Romão's Coding Labs

Lab L16 · Java + Go

Implementing a time-indexed key-value store

Build a versioned key-value store. put(key, timestamp, value) records what a key's value was from a given time, and get(key, at) answers “what was the value as of time at?” — the value with the greatest timestamp that is <= at. Writes may arrive in any time order.

The task

Each city zone has a surge multiplier that changes over time. To audit a trip priced at 18:04, you need the multiplier that was in effect at 18:04, not the current one. Updates can reach the store late or out of order. The natural structure is one sorted map per key and a floor lookup (Java's TreeMap.floorEntry), giving O(log n) reads and writes.

history of key z (puts arrived 10, 30, 20)1.01.41.8102030get(z,5) → emptyget(z,25) → 1.4get(z,99) → 1.8
Each write starts a value that holds until the next timestamp. A query reads that step function at its own time: the nearest write at or to the left of it wins.

What you implement

public final class TemporalStore<K, V> {
    public void put(K key, long timestamp, V value);   // same timestamp -> replace
    public Optional<V> get(K key, long at);            // value at greatest timestamp <= at
}

Rules

  • get returns the value whose timestamp is the greatest one <= at.
  • Unknown key, or at earlier than the key's first timestamp → empty.
  • Puts may arrive out of order; ordering is by timestamp, not arrival.
  • A put at an existing timestamp replaces that value.
  • Timestamps are signed longs in caller-chosen units; negative values are valid.
  • Null key or value → NullPointerException. Thread-safe.

Worked example

  1. put(z, 10, 1.0), put(z, 30, 1.8), put(z, 20, 1.4) (out of order).
  2. get(z, 5) → empty. get(z, 10) → 1.0. get(z, 25) → 1.4. get(z, 99) → 1.8.
  3. put(z, 20, 1.5) → get(z, 25) → 1.5.

Files and commands

Read the tests first, then replace each TODO in the starter until they pass. Java starter: TemporalStore.java · tests: TemporalStoreTest.java. Go starter: store.go · tests: store_test.go.

cd java
./gradlew test --tests 'labs.temporalstore.*'

cd go
go test -race -count=1 ./temporalstore
Reveal the reference solutions

Java: TemporalStore.java
Go: store.go

When to use

Use this lab for a local, in-memory history that answers: what was the latest recorded value at or before this timestamp? A timestamp is a signed integer in a unit selected consistently by the caller, not an automatically synchronized wall clock. Each key has an ordered history. Writes may arrive out of order; a write at an existing timestamp replaces its value. Missing keys and times before the first record return a miss.

This is not a durable database, a distributed ordering service, or a bounded history. There is no retention, deletion, snapshot isolation across operations, or deep copy of values. The caller owns mutable values and must establish a memory limit or retention policy before adopting this design for unbounded traffic.

Steps

  1. Specify the boundary. A query at exactly a stored timestamp includes that record. If versions exist at ten and twenty, a query at nineteen returns the value at ten; a query at twenty returns the value at twenty.
  2. Choose a representation. Java maps keys to ordered trees and uses a floor-entry lookup. Go maps keys to sorted slices, uses binary search to find the first timestamp greater than the query, and returns its predecessor. The insertion search finds the first timestamp greater than or equal to the new timestamp.
  3. Handle replacement and disorder. Replace an equal timestamp rather than inserting a duplicate. Otherwise insert at the search position, shifting later Go slice elements. Test an older insertion after a newer insertion, followed by replacement at the same timestamp.
  4. Protect the state. Each operation holds a lock for its complete search and update. The implementations are safe for concurrent operations, but the locks do not protect caller-owned objects. Java rejects null keys and values. Go permits nil where the types permit it, uses a Boolean to distinguish misses from zero values, and rejects keys that are dynamically uncomparable or not equal to themselves.
  5. State complexity and growth. For a history of n values, Java tree lookup and insertion are O(log n); Go lookup is O(log n), but insertion is O(n) in the worst case due to shifting. These ignore key-hashing cost and contention. Memory grows with the number of distinct key and timestamp pairs.
  6. Test independently. Cover missing keys, before-first, exact boundaries, between versions, after-last, replacement, negative timestamps and out-of-order writes. A useful extension generates random operations and compares results to a simple linear-scan model. Concurrency tests are evidence for exercised schedules, not a proof of all possible histories.

Checklist

Recall and variation

Rebuild predecessor search before reading Go or Java. Variation: replace a duplicate timestamp after inserting a later timestamp. Acceptance: exact-time and between-time queries return the specified replacement without changing the later value.

  • Queries include a version exactly at the requested time
  • Out-of-order writes preserve ordering and duplicate timestamps replace
  • Missing and zero-valued results are distinguishable
  • History growth, value ownership, and lack of durability are explicit
  • The unit and interpretation of timestamps belong to the caller

Signals

Working: boundary tests select the expected predecessor, and repeated writes at one timestamp return the replacement.

Going wrong: a query before the first entry returns that future entry, an older write breaks sorting, or an unbounded history is described as a bounded cache.

Related