Implement an in-memory DB with TTL backup/restore

Problem Statement

Design an in-memory nested key-field-value database with support for time-to-live (TTL) expiration and snapshot backup/restore functionality. All operations receive an explicit non-decreasing integer timestamp representing current system time.

Implement the InMemoryDB class with the following methods:

• set(timestamp: int, key: str, field: str, value: str, ttl: int = 0) -> None: Sets field under key to value. If ttl > 0, the field expires at timestamp + ttl. If ttl == 0, the field persists indefinitely. If the field already exists, overwrite its value and update/clear its expiration time.
• get(timestamp: int, key: str, field: str) -> str | None: Returns the value of field under key at the given timestamp. If the key or field does not exist, or has expired (timestamp >= expire_at), return None.
• delete(timestamp: int, key: str, field: str) -> bool: Removes field under key. Returns True if the field existed and was not expired at timestamp, otherwise False.
• backup(timestamp: int) -> int: Creates a snapshot of the current database state at timestamp and returns a monotonically increasing integer backup_id starting at 1. Note: only active (non-expired) records at timestamp should be captured.
• restore(timestamp: int, backup_id: int) -> bool: Restores the database state from the snapshot identified by backup_id. Returns True on success, or False if backup_id is invalid. When restored, fields retain their original absolute expiration timestamps. If an absolute expiration timestamp is <= timestamp at the time of restoration or subsequent queries, the field is considered expired.

Example

db = InMemoryDB()

# Set a field with TTL of 10 at timestamp 1 (expires at 11)
db.set(1, "user:1", "name", "Alice", ttl=10)
assert db.get(5, "user:1", "name") == "Alice"

# Create backup 1 at timestamp 6
backup_id = db.backup(6)  # returns 1

# Overwrite value at timestamp 8
db.set(8, "user:1", "name", "Bob")
assert db.get(9, "user:1", "name") == "Bob"

# Restore to backup 1 at timestamp 10
assert db.restore(10, backup_id) is True
assert db.get(10, "user:1", "name") == "Alice"

# At timestamp 11, the original TTL has elapsed (1 + 10 = 11)
assert db.get(11, "user:1", "name") is None

Constraints

• Timestamps are non-decreasing integers across all operations: 1 <= timestamp <= 10^9.
• Key, field, and value strings contain alphanumeric characters and colons (1 <= length <= 64).
• 0 <= ttl <= 10^6.
• At most 20,000 total method calls.
• At most 100 calls to backup and restore.