In-Memory Key-Hash Database: Design and Implementation
Context
Design and implement a single-process, in-memory data store that supports a Redis-like hash model. This store must include per-field Time-To-Live (TTL), lexicographic scans (including prefix scans), and a simple backup/restore counter mechanism. All read operations must be evaluated "as of" a supplied timestamp.
Assume timestamps are monotonically increasing logical times (e.g., epoch milliseconds as 64-bit integers). If multiple writes occur to the same field at different timestamps, reads at time t should observe the latest write with write_timestamp ≤ t, subject to TTL.
Requirements
1. Data Model and Basic Operations
- Data Structure: Store data as
key -> { field -> value }with per-field TTL. set(key, field, value, write_timestamp, ttl):- A field expires at
expiry = write_timestamp + ttl. - Define behavior when
ttlisnullor non-positive.
- A field expires at
get(key, field, timestamp) -> value or null:- Return the value visible and unexpired at the provided
timestamp(adhering to "as of" semantics).
- Return the value visible and unexpired at the provided
2. Scans
scan(key, timestamp) -> list of (field, value): Returns all fields unexpired attimestampfor the givenkey.scanPrefix(key, prefix, timestamp) -> list of (field, value): Similar toscan, but only for fields whose field name starts with the specifiedprefix.- Ordering: Results must be sorted lexicographically by the raw field names.
- Special Characters: Ensure correct ordering when prefixes or stored field names contain special characters (parentheses, punctuation, delimiters). Clearly describe how you will normalize or tokenize inputs to avoid incorrect lexicographic order.
3. TTL Semantics
- All read operations (
get,scan,scanPrefix) must filter out expired entries as of the providedtimestamp. - Describe how to store per-field expiry and how to garbage-collect or lazily purge expired data.
4. Backup/Restore Counters
backup(timestamp) -> count:- Returns the count of unexpired fields in the entire database at the specified
timestamp. - Each field is counted at most once per key.
- Returns the count of unexpired fields in the entire database at the specified
restore(timestamp) -> count:- Returns the count from the most recent backup.
- Clarify how the provided
timestampis used in this operation.
- Edge Cases: Clarify behavior for no prior backup, concurrent writes during backup, and whether backup/restore affect persistence or are purely metadata operations.
5. Performance and Design
- Complexity: Specify time and space complexities for
set,get,scan,scanPrefix,backup, andrestore. - Data Structures: Propose and justify choices for data structures (e.g., per-key hash map plus per-key sorted index or trie for field names; min-heap or time wheel for expirations).
- Discussion Points: Discuss concurrency, memory footprint, and how to test corner cases (special characters in prefixes, very large numbers of fields, and mass expirations).
AI interview prep
Core dilemma
Designing an in-memory data store that simultaneously supports 'as of' timestamp-based reads (implying versioning), per-field TTL with efficient expiration, and lexicographical prefix scans, all while maintaining high performance and managing memory within a single-process, concurrent environment.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
In-Memory Key-Hash Database: Design and Implementation
Context
Design and implement a single-process, in-memory data store that supports a Redis-like hash model. This store must include per-field Time-To-Live (TTL), lexicographic scans (including prefix scans), and a simple backup/restore counter mechanism. All read operations must be evaluated "as of" a supplied timestamp.
Assume timestamps are monotonically increasing logical times (e.g., epoch milliseconds as 64-bit integers). If multiple writes occur to the same field at different timestamps, reads at time t should observe the latest write with write_timestamp ≤ t, subject to TTL.
Requirements
1. Data Model and Basic Operations
- Data Structure: Store data as
key -> { field -> value }with per-field TTL. set(key, field, value, write_timestamp, ttl):- A field expires at
expiry = write_timestamp + ttl. - Define behavior when
ttlisnullor non-positive.
- A field expires at
get(key, field, timestamp) -> value or null:- Return the value visible and unexpired at the provided
timestamp(adhering to "as of" semantics).
- Return the value visible and unexpired at the provided
2. Scans
scan(key, timestamp) -> list of (field, value): Returns all fields unexpired attimestampfor the givenkey.scanPrefix(key, prefix, timestamp) -> list of (field, value): Similar toscan, but only for fields whose field name starts with the specifiedprefix.- Ordering: Results must be sorted lexicographically by the raw field names.
- Special Characters: Ensure correct ordering when prefixes or stored field names contain special characters (parentheses, punctuation, delimiters). Clearly describe how you will normalize or tokenize inputs to avoid incorrect lexicographic order.
3. TTL Semantics
- All read operations (
get,scan,scanPrefix) must filter out expired entries as of the providedtimestamp. - Describe how to store per-field expiry and how to garbage-collect or lazily purge expired data.
4. Backup/Restore Counters
backup(timestamp) -> count:- Returns the count of unexpired fields in the entire database at the specified
timestamp. - Each field is counted at most once per key.
- Returns the count of unexpired fields in the entire database at the specified
restore(timestamp) -> count:- Returns the count from the most recent backup.
- Clarify how the provided
timestampis used in this operation.
- Edge Cases: Clarify behavior for no prior backup, concurrent writes during backup, and whether backup/restore affect persistence or are purely metadata operations.
5. Performance and Design
- Complexity: Specify time and space complexities for
set,get,scan,scanPrefix,backup, andrestore. - Data Structures: Propose and justify choices for data structures (e.g., per-key hash map plus per-key sorted index or trie for field names; min-heap or time wheel for expirations).
- Discussion Points: Discuss concurrency, memory footprint, and how to test corner cases (special characters in prefixes, very large numbers of fields, and mass expirations).