Implement a versioned in-memory DB with CAS and history

Implement an in-memory database keyed by (key, field) supporting TTL, conditional updates, scans, and historical queries.

Data model / rules

For each (key, field) store:
- value
- expire_at (integer; +∞ means never expires)
A record is visible at time t iff t < expire_at.
All operations are given a timestamp. You may assume operations are provided in non-decreasing timestamp order.
You must also support historical queries: retrieve what value was valid at some earlier time.

API

set(timestamp, key, field, value) -> void
- Set with no TTL (expire_at = +∞).
set_with_ttl(timestamp, key, field, value, ttl) -> void
- Set with expire_at = timestamp + ttl.
get(timestamp, key, field) -> value | null
- Return current value if exists and not expired at timestamp, else null.
compare_and_set(timestamp, key, field, expected_value, new_value) -> bool
- If (key, field) exists and is not expired at timestamp and its current value equals expected_value, update it to new_value (expire_at = +∞) and return true.
- Otherwise return false.
compare_and_set_with_ttl(timestamp, key, field, expected_value, new_value, ttl) -> bool
- Same as above, but sets expire_at = timestamp + ttl.
compare_and_delete(timestamp, key, field, expected_value) -> bool
- If current visible value equals expected_value, delete it and return true, else return false.
scan(timestamp, key) -> list<string>
- Return all non-expired fields for key at timestamp.
- Sort by field ascending.
- Format each item as "field(value)".
scan_by_prefix(timestamp, key, prefix) -> list<string>
- Like scan, but only fields starting with prefix.
get_value_at(timestamp, key, field, at_timestamp) -> value | null
- Return the value that was valid for (key, field) at time at_timestamp.
- Return null if it did not exist, was deleted, or was expired at at_timestamp.

Notes

You will likely need to keep a per-(key,field) history of changes to answer get_value_at efficiently.
Assume up to ~1e5 operations.

Solution

import java.util.*;

/**

============================================================================

VERSIONED IN-MEMORY DATABASE  –  Meta Take-Home (Full Solution)

============================================================================


DATA MODEL (ASCII art)

──────────────────────


db: HashMap<String, TreeMap<String, List<Record>>>


┌──────────────────────────────────────────────────────────────────┐

│  db (outer map)                                                 │

│  key ──► { field ──► [ Record₀, Record₁, Record₂, ... ] }      │

│                        ▲ sorted by timestamp (append-only)      │

│                                                                 │

│  Each Record = { timestamp, value (null=deleted), expireAt }    │

└──────────────────────────────────────────────────────────────────┘


WHY THIS STRUCTURE?

───────────────────

• HashMap<key> ──► O(1) key lookup

• TreeMap<field> ──► O(log F) field lookup + prefix scan via subMap

• List<Record>  ──► append-only history; binary search for historical

                  queries in O(log H) where H = history length



VISIBILITY RULE

───────────────

A record is visible at time t  iff:

record.value != null  AND  t &lt; record.expireAt



TIMELINE EXAMPLE

────────────────

time ──► 0    5         10        15        20

       │    │          │         │         │


set(5, "k","f","A")     │         │         │

       │    ├──── A visible ────►│         │


       │    │          │  set_with_ttl(10,"k","f","B",5)


       │    │          │  expireAt=15      │


       │    │          │  ├── B visible ──►│  (expired at 15)


       │    │          │         │         │


get_value_at(20,"k","f",12) → "B"  (B was valid at t=12)

get_value_at(20,"k","f",7)  → "A"  (A was valid at t=7)

get_value_at(20,"k","f",16) → null  (B expired at 15)


COMPLEXITY SUMMARY

──────────────────

| Operation          | Time            | Space  |

|--------------------|-----------------|--------|

| set / set_with_ttl | O(log F)        | O(1)*  |

| get                | O(log F)        | O(1)   |

| compare_and_set    | O(log F)        | O(1)*  |

| compare_and_delete | O(log F)        | O(1)*  |

| scan               | O(F)            | O(F)   |

| scan_by_prefix     | O(log F + M)    | O(M)   |

| get_value_at       | O(log F + log H)| O(1)   |

*amortised; each op appends one Record to history

F = fields per key, H = history length, M = matching prefix fields
 */
public class VersionedInMemoryDB {
// ── Inner record: one snapshot in the history of a (key, field) ──
private static class Record {
final int timestamp;   // when this write happened
final String value;    // null means "deleted"
final long expireAt;   // record visible while t < expireAt

Record(int timestamp, String value, long expireAt) {
    this.timestamp = timestamp;
    this.value = value;
    this.expireAt = expireAt;
}
}
private static final long INF = Long.MAX_VALUE; // "never expires"
// key  →  (field  →  append-only history of Records)
private final Map<String, TreeMap<String, List<Record>>> db = new HashMap<>();
// ════════════════════════════════════════════════════════════════
//  CORE HELPERS
// ════════════════════════════════════════════════════════════════
/** Get or create the field map for a key. */
private TreeMap<String, List<Record>> fieldsOf(String key) {
return db.computeIfAbsent(key, k -> new TreeMap<>());
}
/** Get or create the history list for a (key, field). */
private List<Record> historyOf(String key, String field) {
return fieldsOf(key).computeIfAbsent(field, f -> new ArrayList<>());
}
/**

Return the latest record for (key, field), or null.
"Latest" = last element in the append-only list.
 */
private Record latest(String key, String field) {
 TreeMap<String, List<Record>> fields = db.get(key);
 if (fields == null) return null;
 List<Record> hist = fields.get(field);
 return (hist == null || hist.isEmpty()) ? null : hist.get(hist.size() - 1);
}

/**

Check if record r is visible (alive) at time t.

visible(r, t) = r != null  &&  r.value != null  &&  t < r.expireAt
 */
private boolean isVisible(Record r, int t) {
return r != null && r.value != null && t < r.expireAt;
}

// ════════════════════════════════════════════════════════════════
//  API 1 & 2: SET / SET_WITH_TTL
// ════════════════════════════════════════════════════════════════
/** set(timestamp, key, field, value) – no TTL (never expires). */
public void set(int timestamp, String key, String field, String value) {
    historyOf(key, field).add(new Record(timestamp, value, INF));
}
/** set_with_ttl – expires at timestamp + ttl. */
public void setWithTtl(int timestamp, String key, String field,
                       String value, int ttl) {
    historyOf(key, field).add(new Record(timestamp, value, (long) timestamp + ttl));
}
// ════════════════════════════════════════════════════════════════
//  API 3: GET
// ════════════════════════════════════════════════════════════════
/** Return current value if alive at timestamp, else null. */
public String get(int timestamp, String key, String field) {
    Record r = latest(key, field);
    return isVisible(r, timestamp) ? r.value : null;
}
// ════════════════════════════════════════════════════════════════
//  API 4 & 5: COMPARE-AND-SET  (CAS)
// ════════════════════════════════════════════════════════════════
/**

CAS without TTL.

┌─────────────────────────────────────────────────────┐
│  if current value == expected:                      │
│      append Record(timestamp, newValue, +∞)         │
│      return true                                    │
│  else:                                              │
│      return false   (no mutation)                   │
└─────────────────────────────────────────────────────┘
 */
public boolean compareAndSet(int timestamp, String key, String field,
                     String expectedValue, String newValue) {
Record r = latest(key, field);
if (isVisible(r, timestamp) && r.value.equals(expectedValue)) {
historyOf(key, field).add(new Record(timestamp, newValue, INF));
return true;
}
return false;
}

/** CAS with TTL – same logic but expire_at = timestamp + ttl. */
public boolean compareAndSetWithTtl(int timestamp, String key, String field,
                                    String expectedValue, String newValue, int ttl) {
    Record r = latest(key, field);
    if (isVisible(r, timestamp) && r.value.equals(expectedValue)) {
        historyOf(key, field).add(
                new Record(timestamp, newValue, (long) timestamp + ttl));
        return true;
    }
    return false;
}
// ════════════════════════════════════════════════════════════════
//  API 6: COMPARE-AND-DELETE
// ════════════════════════════════════════════════════════════════
/**

If current visible value equals expectedValue, mark deleted
by appending a Record with value = null.
 */
public boolean compareAndDelete(int timestamp, String key, String field,
                         String expectedValue) {
 Record r = latest(key, field);
 if (isVisible(r, timestamp) && r.value.equals(expectedValue)) {
 // A "tombstone" record: value=null means deleted
 historyOf(key, field).add(new Record(timestamp, null, INF));
 return true;
 }
 return false;
}

// ════════════════════════════════════════════════════════════════
//  API 7: SCAN
// ════════════════════════════════════════════════════════════════
/**

Return all non-expired fields for key, sorted ascending.

Format: "field(value)"
 */
public List<String> scan(int timestamp, String key) {
 List<String> result = new ArrayList<>();
 TreeMap<String, List<Record>> fields = db.get(key);
 if (fields == null) return result;
 // TreeMap iteration is already sorted by field name
 for (var entry : fields.entrySet()) {
 List<Record> hist = entry.getValue();
 Record r = hist.get(hist.size() - 1);
 if (isVisible(r, timestamp)) {
     result.add(entry.getKey() + "(" + r.value + ")");
 }
 }
 return result;


}
// ════════════════════════════════════════════════════════════════
//  API 8: SCAN_BY_PREFIX
// ════════════════════════════════════════════════════════════════
/**

Like scan but only fields starting with prefix.


Uses TreeMap.subMap to efficiently jump to the prefix range:


fields:  a, ab, abc, b, ba, bb, c

prefix = "ab"

subMap("ab", "ac") → { ab, abc }   ← O(log F) to find start


The upper bound is computed by incrementing the last char of prefix.
 */
public List<String> scanByPrefix(int timestamp, String key, String prefix) {
 List<String> result = new ArrayList<>();
 TreeMap<String, List<Record>> fields = db.get(key);
 if (fields == null) return result;
 // Upper bound: prefix with last char incremented
 // e.g. "ab" → "ac", so subMap covers "ab" .. "abzzz..."
 String upper = prefix.substring(0, prefix.length() - 1)
     + (char) (prefix.charAt(prefix.length() - 1) + 1);
 for (var entry : fields.subMap(prefix, upper).entrySet()) {
 List<Record> hist = entry.getValue();
 Record r = hist.get(hist.size() - 1);
 if (isVisible(r, timestamp)) {
     result.add(entry.getKey() + "(" + r.value + ")");
 }
 }
 return result;


}
// ════════════════════════════════════════════════════════════════
//  API 9: GET_VALUE_AT  (Historical Query)
// ════════════════════════════════════════════════════════════════
/**

Return the value that was valid at atTimestamp.


BINARY SEARCH on the history list:

──────────────────────────────────

History (sorted by timestamp):


idx:   0       1       2       3

ts:    5      10      15      20

val:  "A"    "B"     null    "C"

exp:   ∞      15      ∞       ∞


Query: atTimestamp = 12


Step 1: Binary search for rightmost record with ts ≤ 12

     → idx 1  (ts=10, val="B", exp=15)



Step 2: Check visibility: 12 < 15 and val != null → visible

     → return "B"



Query: atTimestamp = 16

Step 1: → idx 2  (ts=15, val=null)  → deleted → return null
 */
public String getValueAt(int timestamp, String key, String field,
                 int atTimestamp) {
TreeMap<String, List<Record>> fields = db.get(key);
if (fields == null) return null;
List<Record> hist = fields.get(field);
if (hist == null || hist.isEmpty()) return null;
// Binary search: find the last record with ts <= atTimestamp
int lo = 0, hi = hist.size() - 1, pos = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (hist.get(mid).timestamp <= atTimestamp) {
    pos = mid;
    lo = mid + 1;
} else {
    hi = mid - 1;
}
}
if (pos == -1) return null; // no record existed yet at atTimestamp
Record r = hist.get(pos);
return isVisible(r, atTimestamp) ? r.value : null;


}
// ════════════════════════════════════════════════════════════════
//  FOLLOW-UP 1: COUNT KEYS WITH NON-EMPTY FIELDS
// ════════════════════════════════════════════════════════════════
/**

"How many keys have at least one living field at time t?"
Brute-force O(K·F) — acceptable for ~1e5 ops.
 */
public int countActiveKeys(int timestamp) {
 int count = 0;
 for (var entry : db.entrySet()) {
 for (var hist : entry.getValue().values()) {
     Record r = hist.get(hist.size() - 1);
     if (isVisible(r, timestamp)) { count++; break; }
 }
 }
 return count;
}

// ════════════════════════════════════════════════════════════════
//  FOLLOW-UP 2: BATCH / MULTI-SET
// ════════════════════════════════════════════════════════════════
/**

Atomically set multiple (field, value) pairs under one key.
All share the same timestamp and TTL.
 */
public void multiSet(int timestamp, String key,
              Map<String, String> fieldValues, int ttl) {
 long exp = (ttl <= 0) ? INF : (long) timestamp + ttl;
 for (var e : fieldValues.entrySet()) {
 historyOf(key, e.getKey()).add(
         new Record(timestamp, e.getValue(), exp));
 }
}

// ════════════════════════════════════════════════════════════════
//  FOLLOW-UP 3: RANGE QUERY ON FIELD NAMES
// ════════════════════════════════════════════════════════════════
/**

Return visible fields in [startField, endField) at timestamp.
Efficient because TreeMap supports subMap in O(log F + M).
 */
public List<String> scanRange(int timestamp, String key,
                       String startField, String endField) {
 List<String> result = new ArrayList<>();
 TreeMap<String, List<Record>> fields = db.get(key);
 if (fields == null) return result;
 for (var entry : fields.subMap(startField, endField).entrySet()) {
 List<Record> hist = entry.getValue();
 Record r = hist.get(hist.size() - 1);
 if (isVisible(r, timestamp)) {
     result.add(entry.getKey() + "(" + r.value + ")");
 }
 }
 return result;
}

// ════════════════════════════════════════════════════════════════
//  FOLLOW-UP 4: GARBAGE COLLECTION (COMPACT HISTORY)
// ════════════════════════════════════════════════════════════════
/**

Remove history entries older than minTimestamp.
Keep at most one record before minTimestamp (the "anchor")
so get_value_at still works for queries ≥ minTimestamp.

Before GC (minTimestamp=10):
ts:  2  5  8  12  15
   ──────────────────


   remove these ↑ but keep ts=8 as anchor



After GC:
ts:  8  12  15
 */
public void gc(int minTimestamp) {
for (var fields : db.values()) {
   for (var hist : fields.values()) {
   if (hist.size() <= 1) continue;
   // Find the last record with ts <= minTimestamp (anchor)
   int anchorIdx = -1;
   for (int i = hist.size() - 1; i >= 0; i--) {
       if (hist.get(i).timestamp <= minTimestamp) {
           anchorIdx = i;
           break;
       }
   }
   // Remove everything before the anchor
   if (anchorIdx > 0) {
       hist.subList(0, anchorIdx).clear();
   }
   }
}
}

// ════════════════════════════════════════════════════════════════
//  DEMO / TEST
// ════════════════════════════════════════════════════════════════
public static void main(String[] args) {
    VersionedInMemoryDB db = new VersionedInMemoryDB();
// ── Basic set &amp; get ──
db.set(1, "user", "name", "Alice");
db.set(2, "user", "age", "30");
System.out.println("get name @3: " + db.get(3, "user", "name")); // Alice

// ── TTL ──
db.setWithTtl(5, "session", "token", "abc123", 10); // expires at 15
System.out.println("token @10: " + db.get(10, "session", "token")); // abc123
System.out.println("token @15: " + db.get(15, "session", "token")); // null (expired)

// ── CAS ──
db.set(10, "config", "version", "1.0");
boolean ok = db.compareAndSet(11, "config", "version", "1.0", "2.0");
System.out.println("CAS 1.0→2.0: " + ok);   // true
ok = db.compareAndSet(12, "config", "version", "1.0", "3.0");
System.out.println("CAS 1.0→3.0: " + ok);   // false (current is 2.0)

// ── Compare-and-delete ──
db.set(20, "cache", "item", "data");
boolean del = db.compareAndDelete(21, "cache", "item", "data");
System.out.println("CAD: " + del);                              // true
System.out.println("after CAD: " + db.get(22, "cache", "item")); // null

// ── Scan ──
db.set(30, "row", "col_a", "1");
db.set(30, "row", "col_b", "2");
db.set(30, "row", "col_c", "3");
System.out.println("scan: " + db.scan(31, "row"));
// [col_a(1), col_b(2), col_c(3)]

// ── Prefix scan ──
db.set(40, "metrics", "cpu_user", "50");
db.set(40, "metrics", "cpu_sys", "10");
db.set(40, "metrics", "mem_free", "2048");
System.out.println("prefix cpu_: " + db.scanByPrefix(41, "metrics", "cpu_"));
// [cpu_sys(10), cpu_user(50)]

// ── Historical query ──
db.set(50, "price", "btc", "40000");
db.set(55, "price", "btc", "42000");
db.set(60, "price", "btc", "38000");
System.out.println("btc @52: " + db.getValueAt(61, "price", "btc", 52)); // 40000
System.out.println("btc @57: " + db.getValueAt(61, "price", "btc", 57)); // 42000
System.out.println("btc @60: " + db.getValueAt(61, "price", "btc", 60)); // 38000

System.out.println("\n✅ All operations passed.");

}


}

Implement a versioned in-memory DB with CAS and history

Data model / rules

API

Notes

Comments

Coding & Algorithms

Maximize the longest vacation using PTO

More from this blog

Using the Agrona library (Part 7)

Using the Agrona library (Part 6)

Using the Agrona library (Part 5)

Using the Agrona library (Part 4)

Using the Agrona library (Part 3)

Command Palette

Data model / rules

API

Notes

Comments

Coding & Algorithms

Maximize the longest vacation using PTO

More from this blog