# File-Backed Dictionary Storage Engine
The exercise: build exact lookup for `word -> meaning` with no traditional database. The winning design is a read-optimized storage engine: one large immutable data file plus a small in-memory index.
## Requirements
- Exact word lookup.
- Weekly changelog updates.
- No MySQL, Postgres, MongoDB, Redis, or equivalent database.
- API servers should scale horizontally.
- Data is mostly read-only.
- Data file may be huge; the keyspace is much smaller.
## Why The Obvious Designs Fail
| Design | Failure Mode |
|---|---|
| Full dictionary on every API server | huge replicated storage waste |
| One file per word | operationally messy and hard to ship as one artifact |
| B+ tree over mutable blocks | powerful, but overbuilt for weekly batch updates |
| Linear scan of one file | lookup latency grows with file size |
## Core Layout
```text
index:
apple -> offset=123456, length=781
banana -> offset=124237, length=431
data:
[meaning bytes for apple][meaning bytes for banana]...
```
The data file can live in object storage. API servers load the index into memory on boot.
## Read Flow
```mermaid
sequenceDiagram
participant Client
participant API
participant Index
participant Blob as Blob/object storage
Client->>API: GET /meaning/apple
API->>Index: apple
Index-->>API: offset + length
API->>Blob: byte range read
Blob-->>API: meaning bytes
API-->>Client: response
```
The lookup cost is:
```text
one in-memory hash lookup + one byte-range read
```
## Index Size Math
The transcript estimates roughly:
```text
entry_size ~= average_word_length + separators + offset_int + length_int
```
For hundreds of thousands of words, this is megabytes, not terabytes. That difference makes the design viable.
## Serving Contract
The API server should treat the loaded index and the data object as one versioned snapshot.
| Contract | Reason |
|---|---|
| index contains object path, offset, and length | avoids guessing which blob owns the bytes |
| response validates length/checksum when available | detects truncated or wrong range reads |
| missing key returns a clean not-found | avoids falling back to expensive scans |
| startup refuses mismatched index/data versions | prevents old offsets from reading new bytes |
For a public API, add request limits around maximum key length and maximum returned meaning size. Those limits protect both memory and object-storage egress.
## Update Flow
Weekly updates arrive as a changelog:
```text
word, new_meaning
```
If the existing dictionary and changelog are sorted, generate the next version by merging:
```mermaid
flowchart LR
Old[sorted dictionary v1] --> Merge[merge job]
Change[sorted changelog] --> Merge
Merge --> NewData[dictionary v2]
Merge --> NewIndex[index v2]
```
On conflicts, changelog wins. The merge job produces a new data file and index file.
## Correctness Rule
Never replace the data file in place while old servers hold the old index. That can make an old offset point to unrelated bytes.
Use [[wiki/immutable-versioned-data-files]].
## Where This Pattern Appears
- read-only embedded databases,
- static search dictionaries,
- file formats with internal indexes,
- SSTable-like immutable files,
- CDN/object-storage backed static catalogs.
## Operational Notes
Monitor boot time, index memory, object-storage range latency, and the error rate for short reads. The design is simple, but the production risk is usually artifact mismatch: an API server loads one index version while fetching a different data object.