Build a read-only dictionary without a database

Design exact word lookups with one immutable data file and a compact in-memory index, including offsets, startup, and updates.

A file-backed dictionary

Suppose we need an API that returns a word's meaning. Definitions change in a weekly batch, reads dominate, and the exercise excludes a database. The data file may be large, but the words and their locations can fit in memory.

We'll build the read path around that difference, then work through publishing an update. Several API servers should be able to read the same completed dictionary without each holding every definition in RAM.

What belongs on each server?

The workload leaves us several choices:

Arrangement Cost or limitation for this dictionary --- --- Load the complete dictionary Simple lookups, but every server needs RAM for all values One file or object per word Independent updates, but many artifacts to publish and manage Scan one large file per lookup Simple format, but search work grows with the file Mutable B-tree Supports ordered updates; more machinery than a weekly rebuild needs Memory index and immutable data file Small lookup structure, with an extra read for the value

Choose the last option while the full index fits memory and batch rebuilds are affordable. Keep the data file locally if replicated disk space and distribution are acceptable; object storage can instead hold a shared copy and serve selected byte ranges.

A word points to bytes

Build the file and index together. As the builder writes each UTF-8 meaning, it records the starting byte offset and encoded length. This tiny uncompressed example packs two meanings without separators:

text index for dictionary-v1: apple - offset 0, length 5 banana - offset 5, length 12

data bytes: fruityellow fruit

The lengths separate fruit from yellow fruit . A server loads this version's index at startup. For banana it finds (5, 12) , then reads those bytes from dictionary-v1. If the key is absent from the complete index, it returns absence without reading the data file.

That successful uncached lookup uses one memory lookup and one value request, after loading the index. It is not a promise of one physical disk read or fixed latency. Validate the returned version, range and length; wiki/byte-range-indexed-object-storage the byte-range lesson handles the HTTP details.

Budget the index from key bytes, offsets, lengths and the map's own overhead. At an assumed 40 bytes per complete in-memory entry, 500,000 words would need 20 MB. Measure the actual representation: object headers and spare hash-table capacity can make a compact serialized index much larger after loading. Replicating that index across API servers is the cost of keeping lookup local.

Rebuild from the weekly changes

Sort the old dictionary and the week's changes by the same key ordering. Resolve multiple changes to one word before the merge, using an explicit update order. Then walk both sorted inputs: