Your team runs a real-time service dependency graph that is continuously updated by a streaming pipeline — edges appear, disappear, and change weight as services call each other. An incident happened three hours ago, and the on-call engineer needs to see exactly what the dependency graph looked like at the moment the alert fired, not the current graph. Meanwhile, the live dashboard must continue reflecting the present state with sub-minute latency.
Design a storage and query layer that supports both current-state queries (sub-second) and point-in-time 'time-travel' queries (arbitrary historical timestamps, acceptable latency of a few seconds) over a topology that is updated millions of times per day. Walk through how data is written, how time-travel is implemented, what you store versus compute at query time, and what the failure modes and retention trade-offs look like.
Practice against the follow-up probes
- Current-state reads and historical reads have very different access patterns. Should they share the same storage system or use separate systems — what drives that decision?
- Your streaming pipeline processes records in 5-minute windows and may write a batch of edge updates all at once. How does that affect the granularity and accuracy of time-travel queries — and what do you tell the user when they ask for a timestamp that falls inside a window boundary?
- An edge between two services was written at T=0, updated at T=10 min, and deleted at T=25 min. A user queries at T=17 min. Walk me through the exact read path and what you return.
- Retaining full history is expensive. How do you decide how long to keep it, and what compaction or downsampling strategy lets you serve reasonable queries over older data without ballooning storage?
- The streaming pipeline processes a late-arriving flow record that belongs to a window that was already committed and written to the graph. How do you handle corrections to already-persisted topology state?
Show answer guide
What the interviewer is probing
This question tests whether candidates understand the fundamental tension between mutable current-state stores (optimized for point reads and overwrites) and append-only temporal stores (optimized for range scans over time), and whether they can design a write path that feeds both without coupling them. The follow-ups probe granularity reasoning (window boundaries as a source of query imprecision), the mechanics of a versioned or bitemporal read, and operational maturity around late data correction — the hardest part of any streaming system with a historical query requirement.
Strong answer outline
- Frame two distinct query shapes: current-state ('what does the graph look like now?') needs a mutable, indexed graph store with low read latency; time-travel ('what did it look like at T?') needs an immutable, time-indexed log of graph state changes. Trying to serve both from one mutable store forces expensive historical reconstruction; serving both from one append-only store means slow current-state lookups.
- Write path — dual write: the streaming pipeline emits graph mutations (upsert edge, delete edge, update weight) with event timestamps. Each mutation is written (a) as an upsert to the live graph database and (b) as an append to a time-series change log (e.g., columnar storage partitioned by time). These two writes can be async; the live graph is the source of truth for current state, the change log is the source of truth for history.
- Time-travel read path: for a query at timestamp T, scan the change log for all mutations with
event_time ≤ T, reconstruct the graph state by replaying them in order. For efficiency, maintain periodic full snapshots (e.g., every hour) in the change log so reconstruction starts from the nearest snapshot before T rather than time zero. Query latency = snapshot load + replay of delta mutations since snapshot. - Window boundary precision: the pipeline commits in 5-minute windows; mutations within a window share a commit timestamp. A query at T=12min against a window committed at T=10min will see all events in that window, including those that actually occurred up to T=15min. Document this as the system's temporal granularity and surface it in query results ('topology as of window ending T=10min').
- Late data corrections: if a late-arriving record belongs to an already-committed window, append a correction event to the change log with the original event time and a processing timestamp. Time-travel queries replaying the log will incorporate the correction. The live graph may need a compensating write (delta application). Design the mutation log to be idempotent so replaying it twice produces the same result.
- Retention and compaction: full per-mutation history is expensive at millions of mutations/day. Tiered strategy: keep full granularity for recent data (e.g., 7 days); compact to hourly snapshots for 90 days; monthly summaries beyond that. Communicate retention limits clearly — time-travel beyond the retention window returns an error, not silently stale data.
- Failure modes: dual-write creates a consistency gap if the change log write succeeds but the live graph write fails (or vice versa). Mitigate with idempotent writes keyed on (edge-id, window-id) and a reconciliation job that compares the live graph against the most recent change log snapshot. Accept that the two stores may diverge by at most one write cycle.
- Common wrong turns: (1) storing full snapshots on every write — storage explodes; (2) reconstructing current state from the change log on every live query — too slow; (3) overwriting edges in the live graph without any historical record — you lose time-travel entirely; (4) using wall-clock processing time instead of event time as the index — makes historical queries unreliable when processing lags.
The underlying concept
Time-travel queries require separating event time (when something happened in the world) from processing time (when your system observed it) — a distinction the streaming systems literature calls the two-timeline model. The standard pattern is an append-only event log keyed by event time, with periodic snapshots to bound reconstruction cost, alongside a mutable current-state store for low-latency live reads. This is the same design used by version control systems (commits as the log, working tree as current state) and by databases with MVCC (version chains as the log, the latest version as current state). The hard operational problem is late data: records that arrive after their window has been committed force a retroactive correction, and a well-designed system makes those corrections visible to time-travel queries without invalidating the live graph.
Source
Derived from Building Service Topology at Scale: Architecture, Challenges, and Lessons Learned