🎓 A1Learner
🔍
0 of 42 lessons completed

A Key-Value Store on One Machine

A key-value store on one machine keeps its writes in a log file and the position of each key in memory. This lesson is the high-level design step for this problem, building that one-machine store.

Each write appends to the log first

A put appends its entry to the log and then records the entry position in the index. A get follows the index straight to the latest entry.

log = []
index = {}

def put(key, value):
    log.append((key, value))
    index[key] = len(log) - 1

put("name", "Ana")
put("city", "Oslo")
put("name", "Ana Lee")

print("log entries:", len(log))
for key in sorted(index):
    print(key, "at position", index[key])
print("get name ->", log[index["name"]][1])

A restart rebuilds the index from the log

The log survives a restart while the in-memory index is lost. Reading the log in order rebuilds the same index.

log = [("name", "Ana"), ("city", "Oslo"), ("name", "Ana Lee")]
index = {}

for position, (key, value) in enumerate(log):
    index[key] = position

for key in sorted(index):
    print(key, "at position", index[key])
print("get name ->", log[index["name"]][1])
print("get city ->", log[index["city"]][1])

Compaction keeps only the latest entry per key

Repeated puts under one key leave older entries behind in the log. Compaction rewrites the log with only the latest entry for each key.

log = [("name", "Ana"), ("city", "Oslo"), ("name", "Ana Lee"), ("job", "cook"), ("city", "Bergen"), ("name", "Ana Lee Fox")]
latest = {}

for key, value in log:
    latest[key] = value

compacted = list(latest.items())
print("log entries before:", len(log))
print("log entries after:", len(compacted))
print("compacted log:", compacted)

Example

log = [("name", "Ana"), ("city", "Oslo"), ("name", "Ana Lee"), ("job", "cook"), ("city", "Bergen"), ("name", "Ana Lee Fox"), ("job", "baker"), ("city", "Oslo")]
index = {}

for position, (key, value) in enumerate(log):
    index[key] = position

print("entries in the log:", len(log))
print("get name after restart ->", log[index["name"]][1])

latest = {}
for key, value in log:
    latest[key] = value

print("entries after compaction:", len(latest))
for key in sorted(latest):
    print(key, "->", latest[key])

Key points

  • Write-ahead log: a file that receives each write first, in order, before the in-memory index changes.
  • Index: the in-memory map from each key to the position of its latest entry in the log.
  • Restart: a restart rebuilds the index by reading the log from the start to the end.
  • Log compaction: the rewrite of the log that keeps only the latest entry for each key.

In this example, a log of 8 entries is rebuilt into an index after a restart and then compacted down to 3 entries. Every key still returns its latest value after both steps.

Note

the log grows with every write, so compaction runs from time to time to keep the log short.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

What does a restart rebuild, and what does it rebuild from?