In-memory database in levels: scans, TTL, backup and restore

A timed, multi-level exercise building an in-memory store of records with fields: create and read first, then scans and filters, then timestamps with expiry, then backup and restore to an earlier point. Each level builds on the previous one, and earlier tests keep running.

• Level 1: set(key, field, value), get(key, field) (None when missing), delete(key, field) (returns whether a live field was removed).
• Level 2: scan(key) and scan_by_prefix(key, prefix) return ["field(value)", ...] sorted by field.
• Level 3: timed versions of every call (set_at, set_at_with_ttl, get_at, delete_at, scan_at, scan_by_prefix_at). A field with a TTL is alive for timestamp <= t < timestamp + ttl. Timestamps only grow.
• Level 4: backup(timestamp) saves the live state and returns the number of records with a live field. restore(timestamp, timestamp_to_restore) rolls back to the latest backup at or before timestamp_to_restore; each field keeps the TTL it had left at backup time, counted from the restore.

class RecordStore:
    def set(self, key, field, value): ...
    def get(self, key, field): ...
    def delete(self, key, field): ...

    def scan(self, key): ...
    def scan_by_prefix(self, key, prefix): ...

    def set_at(self, key, field, value, timestamp): ...
    def set_at_with_ttl(self, key, field, value, timestamp, ttl): ...
    def get_at(self, key, field, timestamp): ...
    def delete_at(self, key, field, timestamp): ...
    def scan_at(self, key, timestamp): ...
    def scan_by_prefix_at(self, key, prefix, timestamp): ...

    def backup(self, timestamp): ...
    def restore(self, timestamp, timestamp_to_restore): ...

Clarifying questions

• Does set on an existing field overwrite its value and clear any TTL it had?
• After a TTL expires, does delete on that field return False?
• Is a record with no live fields still counted anywhere, for example by backup?
• If no backup exists at or before timestamp_to_restore, does restore do nothing or clear the store?
• After a restore, can later calls use timestamps that keep growing from timestamp?

What a strong answer covers

• One data model from Level 1 on: key -> {field: (value, expires_at)}, with untimed calls as timed calls whose expiry is infinite, so Level 3 doesn't force a rewrite.
• Liveness checked at read time (timestamp < expires_at), with scans filtering expired fields and sorting by field name.
• backup storing a copy of the live state with each field's remaining TTL, in a list ordered by timestamp, and restore finding the latest backup at or before the target with binary search, then re-basing each remaining TTL on the restore time.
• Copying on backup so later writes don't change saved state.
• Tests per level kept running: missing keys and fields, prefix scans that match nothing, a TTL that expires exactly at timestamp + ttl, a restore before any backup, and a restore that brings back a deleted field.

Follow-ups

• Backups are taken often and the store is big: store them more cheaply (copy-on-write or a change log).
• Add a field-level history so get_at works for any past timestamp.
• Make the store safe for concurrent callers.
• How would you test this if timestamps could arrive out of order?