Design an In-Memory Database with TTL and History

You are tasked with designing a simplified in-memory database, to be implemented in four progressive levels. Each level builds upon the previous one, unlocking after successful completion and testing of the current level. The system must operate entirely in-memory within a single-process environment. Focus on a clear, incremental design with well-defined APIs, data structures, and semantics.

Assumptions

• Keys: Records are uniquely identified by a string record_id.
• Fields: Each record is a map of field_name (string) to value. Values can be typed (e.g., string, number, boolean). Define clear type handling rules for comparisons and filtering.
• Time: Use a monotonic millisecond clock abstraction for deterministic testing. An Clock interface should be exposed, with production implementations using a wall-clock.
• Concurrency: Assume single-threaded by default. Optionally, discuss multi-threading guards.

Level 1: CRUD Operations

Implement fundamental Create, Read, Update, and Delete operations for records, fields, and values. Define precise behavior for non-existent records/fields and idempotency.

Required APIs:

1. create_record(record_id) -> bool created
2. delete_record(record_id) -> bool deleted
3. upsert_field(record_id, field, value) -> void (The state after this call must reflect the new value. Specify if this operation auto-creates a record if record_id is missing.)
4. delete_field(record_id, field) -> bool deleted
5. read_record(record_id) -> map[field -> value] or NotFound
6. read_field(record_id, field) -> value or NotFound

Definitions Required:

• Behavior when operating on non-existent records or fields.
• Idempotency guarantees for create, delete, upsert, and delete_field.

Level 2: Filtered Field View

Extend the database to support listing fields of a given record that satisfy specified filter predicates.

Required API:

• list_fields(record_id, filter_expr) -> list[field_name]

Definitions Required:

• Filter Expression Format: Must support equality/inequality, numeric comparisons, and substring/regex matching on strings. Include logical AND/OR/NOT operators.
• Type and Error Semantics: Define behavior for operations like comparing strings to numbers, or handling invalid regex patterns.

Level 3: Per-Record TTL

Introduce support for a Time-To-Live (TTL) mechanism per record, causing records to automatically expire after their TTL duration elapses.

Required APIs:

• set_ttl(record_id, ttl_ms) -> void
• get_ttl(record_id) -> expire_at_ms or None

Definitions Required:

• Time Source Abstraction: How time is managed for TTL.
• Expiry Checks and Cleanup Strategy: Propose a strategy (e.g., lazy vs. background sweeper) that targets efficient expiry (O(log n) per update or better).
• Semantics: Define behavior for reads and writes on records that have already expired.

Level 4: Look-back Queries (Time Travel)

Add the capability to query record and field values as they existed at a past timestamp.

Required APIs:

• read_record_as_of(record_id, ts_ms) -> map[field -> value] or NotFound
• read_field_as_of(record_id, field, ts_ms) -> value or NotFound

Definitions Required:

• Interaction with History: How create, update, field delete, record delete, and TTL operations interact with historical reads.
• Storage Approach: Propose a storage strategy (e.g., per-field versioning, append-only log, optional snapshots) and its impact on API design.
• Trade-offs: Discuss time and space complexity, and any retention policies.

Deliverables for Each Level:

For each of the four levels, you must provide:

• API signatures
• Core data structures and algorithms
• Complexity analysis (time and space)
• Key edge cases
• A minimal test plan

Optional Discussion Points:

• Concurrency assumptions (single-threaded vs. multi-threaded)
• Persistence scope (in-memory only)