Katkat
Back

Design a Concurrent, Memory-Bounded Tally Service

MetaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This problem tests the ability to design a high-throughput, memory-efficient data structure for time-series counting that balances concurrency, accuracy, and storage constraints.

Design a Concurrent, Memory-Bounded Tally Service

Design a service that tracks the frequency of incoming events (e.g., page views) tagged with a nanosecond-precision timestamp. The service must support two operations:

  1. record(event_id): Registers an event occurrence at the current system time.
  2. query(start_ts, end_ts): Returns the total number of events that occurred within the closed interval [start_ts, end_ts].

Constraints & Requirements

  • Concurrency: The service must handle thousands of record calls per second from multiple threads.
  • Memory Bounding: You cannot store every individual event. The total memory footprint must remain constant regardless of the number of events recorded over time.
  • Retention: Events older than a configurable retention window (e.g., 24 hours) are evicted to make room for new data.
  • Accuracy: Describe how your design handles the trade-off between exact counts and space-efficient approximations (e.g., histograms, sketches, or bucketing).

Expected Output

  • Define the data structure used to store counts.
  • Explain how you handle concurrent updates to these counts to minimize lock contention.
  • Explain the strategy for handling late-arriving events (events with timestamps significantly older than the current time).
  • Provide a rough API signature for record and query.

Example

If we define buckets of 1-second resolution:

  • record(event_A) at T=100.5 increments the bucket for [100, 101].
  • query(100, 102) would return count(bucket 100) + count(bucket 101) + count(bucket 102).

Edge Cases

  • High volume of events at the exact boundary of a time bucket.
  • Clock skew between servers in a distributed environment.
  • Preventing integer overflow for high-frequency buckets.

Hints

Hint 1

Consider using fixed-size circular buffers or arrays to represent time buckets, where each index maps to a specific time interval.

Hint 2

To mitigate write contention, use atomic primitives (like Compare-And-Swap) or shard the buckets across multiple threads/locks based on the hash of the timestamp or event category.

Hint 3

If exact counts are not required for long-term historical data, consider using a decaying counter or a hierarchical bucket structure to save space for older intervals.

Follow-up questions

  • How would you extend this to a distributed system where multiple instances are receiving events for the same timestamp?
  • If the requirement changed to support 'top-K' event categories rather than simple counts, what data structures would you add?
  • How does your design change if the 'query' operation needs to be performant at the expense of 'record' latency?