← all topics Top-K events board · say it in this order 1 Problem2 Entities + API 3 High-level design4 Deep dives 5 Final + levelsreset

Design a user tracking event system with a top-K API

10B events a day · 1,000 event types · getTopK(start, end, k) · Hello Interview flow, board rules, one idea per line
SAY THIS SENTENCE FIRST

"This looks like a heavy-hitters problem and it is not one. There are only a thousand event types, so an entire minute of the firehose is a thousand counters, about eight kilobytes, which means I can keep the counts exact and answer top-k with a partial sort instead of a sketch. The genuinely hard parts are somewhere else: the ten billion raw events I still have to store and erase on request, and the one event type that is forty percent of the traffic."

STEP 1 OF 5

Understanding the problem

5 min

Functional Requirements

  1. Clients should be able to emit tracking events, at high volume, without the system losing them.
  2. A caller should be able to ask for the top k event types by count within [start, end).
  3. New event types should be able to appear, and old ones retire, without a deploy.
  4. A user should be able to have their tracking data erased and exported.

Below the line (out of scope):

  • Arbitrary group-bys and filters on event properties. That is a full OLAP warehouse and it is a different system with a different storage engine. Say the cut out loud, because "top k by type" is a single fixed query shape and that is the only reason any of this is cheap.
  • Sessionization, funnels, and per-user journeys. They need the raw events joined and ordered per user, which the counting path deliberately never does.
  • Real-time alerting on thresholds, bot and fraud filtering, and billing-grade accuracy. Ad billing would change the durability bar from "do not lose events" to "prove you did not lose events".

Non-Functional Requirements

Do the scale math first, because it shows which part of the system is expensive
  • Cardinality comes first: 1,000 event types is the entire key space, so the counts can be exact.
    • The key space is fixed by the product, not by the traffic, and it decides everything below it.
    • One minute of the whole firehose collapses to 1,000 counts. At 8 bytes a count that is 8 KB a minute and 11.5 MB a day, so a year would be about 4 GB at minute grain if you kept one, and retention means you never do.
    • So the counts are EXACT. Count-Min Sketch, Space-Saving, and lossy counting are answers to a problem I do not have here. Say this deliberately, because the interviewer is expecting you to reach for a sketch and the point is that you knew not to.
    • Name the condition that would flip it, because that is what shows you understand why: if the "type" became a URL, a productId, or a userId, cardinality goes to 10^8 and the exact-counts plan dies.
  • Volume sizes a different system: 10B events a day, about 350K a second at peak, 5 TB a day of raw data.
    • 10B events a day is about 115K events/sec average, and call it 350K/sec at peak with a 3x diurnal factor.
    • At roughly 500 bytes an event that is 5 TB a day of raw data, so 450 TB at 90 days retention, before replication.
    • The two numbers point at two different systems. The raw bytes are the expensive one to store, replicate, and erase. The counting is almost free. Most candidates spend the whole hour on the cheap half.
  • Reads are rare, writes are constant, which is the inverse of a feed. Dashboards and scheduled reports, order of tens to hundreds of requests a second against 17.5K write requests a second, which is 350K events a second. Nothing here should be designed as if reads were the load.
  1. Query latency p99 under about 100 ms, and the cost must not grow with the traffic.
    • Ten billion events a day and a hundred billion a day should cost the same to answer, because the answer is 1,000 numbers either way.
  2. Freshness: a minute's counts are readable about three minutes after that minute began, and the API says so.
    • Readable is not the same as final, and conflating them is the mistake. A minute's count can still change until the next day.
    • The tradeoff is explicit: exact once a window has settled, versus instant and approximate. Pick exact and settled, and make the incompleteness visible rather than silent.
  3. Durability: no event is silently dropped, and no event is counted twice.
  4. Correctness under replay: reprocessing a window must produce the same number it produced the first time. This is a design constraint on the sink, not a property you get for free from the framework.
  5. GDPR: erasure honoured inside the statutory month, which the design runs as a 30 day internal SLA, export on request, and personal data confined to a small, named set of stores rather than sprinkled across every derived table.
DONE WHEN: the interviewer has heard "a thousand types means I can be exact" and "the expensive system is the raw event store, not the counter". Those two sentences license exact counting and the whole privacy section.
STEP 2 OF 5

Entities + API

5 min

Defining the Core Entities

  • Event is one tracked action: eventId, eventType, userId, eventTime, receivedAt, and a properties blob.
    • eventId is a UUID the client generates before its first attempt, and it is the idempotency key. Nothing else can make a retry safe.
    • There are two timestamps and choosing between them is a design decision, not a detail.
      • eventTime is the client's clock: it is what the user actually did and when, and it is wrong, skewed, and user-settable.
      • receivedAt is the server's clock: it is trustworthy and it is not what anybody is asking about.
      • Count by eventTime, because a dashboard asking "what happened between 9 and 10" means the user's 9 to 10. That choice is what creates the late-event problem, and taking it knowingly is the point.
  • EventType is a registry row: typeId (a small int, under 1,000 today), name, schema version, owner, piiFlag, and status (active or deprecated).
    • The small integer is load-bearing: it is the slot index into the count vector, so a type is one array position rather than a string key.
  • CountBucket is the aggregate: key (granularity, bucketStart), value a slot vector of counts plus a monotonic revision.
    • One row per bucket, not a thousand rows per bucket. This is the single most important storage decision on the page and it falls straight out of the cardinality number.
  • UserKey is the key store: keyId = HMAC(secret, userId) to a wrapped per-user data key. Keying it by the HMAC rather than the raw userId means the table itself holds no plaintext identifier. It exists so erasure can be a key delete instead of a rewrite of a petabyte-scale lake.
  • DeletionRequest records userId, requestedAt, completedAt. It is the audit trail a regulator asks for, and it is also what makes a restored backup re-converge.

API or System Interface

POST   /v1/events                              // { events: [ { eventId, eventType, userId, eventTime, properties } ] }
                                               // → 202 { accepted, warned: [ { eventId, reason } ],
                                               //              rejected: [ { eventId, reason } ] }

GET    /v1/stats/top?start=&end=&k=            // → 200 { window, complete, results: [ { eventType, count } ] }
GET    /v1/stats/series?type=&start=&end=&granularity=  // one type over time, same buckets, no new storage

GET    /v1/event-types                         // the registry, cacheable
POST   /v1/event-types                         // { name, schema, piiFlag } → 201, no deploy needed

POST   /v1/privacy/erasure                     // { userId } → 202 { requestId, dueBy }
GET    /v1/privacy/export?userId=              // → 202, delivered out of band
  • The write path is a batch endpoint, and that is a capacity decision rather than a convenience.
    • 350K events/sec as individual calls is 350K RPS of TLS handshakes, headers, and auth checks, where the overhead dwarfs the 500-byte payload.
    • At 20 events a batch it is 17.5K RPS, which is an ordinary fleet.
    • The cost is latency at the edge: the SDK holds events for a few seconds, so a user who closes the tab loses that buffer. Accept it and say so, because tracking is not transactional.
  • The write returns 202, not 200, because the batch is durably accepted but not yet counted. The server has taken responsibility for it. It has not counted it yet, and pretending otherwise would be a lie the freshness section then has to walk back.
  • Partial rejection is in the response shape, and rejected means malformed, not unfamiliar.
    • One bad event in a batch of twenty must not fail the other nineteen, and the client needs to know which one and why.
    • A schema violation or a nonsense timestamp is rejected. An unknown eventType is not: it is accepted and returned in warned rather than rejected, for reasons covered when event-type handling gets its own dive.
  • The read snaps start and end to minute boundaries and says so in the response, or rejects anything finer with a 400. The finest bucket is a minute, so the API must not accept a precision it cannot honour.
  • The read returns complete (can this number still change) and asOf (a version that moves when it does) as first-class fields. When each one moves is the late-events dive.
  • No userId appears anywhere in the query path. That is deliberate: it is what keeps the aggregate store outside the scope of an erasure request, and it is worth saying out loud when you get to GDPR.
  • The two halves have different threat models on purpose. The write endpoint is public and takes data from untrusted clients, so it needs validation. The read endpoint is internal and authenticated. Same system, and treating them the same is how a cardinality attack gets in.
DONE WHEN: you have said "one row per bucket holding all thousand counts" and "eventId comes from the client so retries are free".
STEP 3 OF 5

High-level design

10 min, end to end, no dives yet

1) Clients should be able to emit events without the system losing them

Ingest: 10B events a day land in a durable log before anything counts them TrackingSDKs POST batches to the Collector, which checks each eventType against EventTypeRegistry and appends the batch to EventStream before returning 202. Two consumer groups read EventStream at their own offsets: ArchiveSink writes the raw events to RawEventLake, and the Aggregator counts the stream. Ingest: 10B events a day land in a durable log before anything counts them 115K events a second on average, 350K at peak. only 1,000 distinct event types, which is what makes exact counting possible later. TrackingSDKs web, mobile, serverbatch 20 events per POST Collector caches per-user data keysencrypts, then stamps receivedAt EventTypeRegistry 1,000 approved typesPOST /v1/event-types adds one EventStream many partitionsRF 3, acks=all evt evt evt evt RawEventLake S3 hourly Parquetabout 5 TB a day90 day retention ArchiveSink consumer group: archivehourly Parquet rollup Aggregator counts the streamnext diagram 1. TrackingSDKs POST batches of events to the Collector 2. Collector checks each eventType against the registry 3. Collector appends the batch to EventStream and only then returns 202 4. ArchiveSink writes the raw events to the lake for replay and audit reads at its own offset 5. Aggregator reads the same stream independently of the archive front: consumers read here append-only, offsetsadvance this way the not-so-happy paths: the SDK generates eventId before the first attempt, so a retry after a lost 202 carries the same id.EventStream unavailable? the Collector returns 503 and the SDK retries with backoff, it never drops the batch on the floor.the ORDERING is the trick: the Collector encrypts userId and properties with the user's data key BEFORE the append,so EventStream and the lake only ever hold ciphertext. the key cache TTL is therefore the real erasure latency.
  • The Collector authenticates, validates, encrypts and stamps each event before appending the batch to the log, and does nothing else. In detail: authenticate the writing key, validate each event against the registry, encrypt userId and the properties blob with the user's data key, and stamp receivedAt before appending the batch to the log.
    • It stamps receivedAt and it does not enrich, join, or count. Everything it might do instead is something that can fail, and this is the one component that must not.
    • The encrypt step is the one that spoils the clean story, so own it rather than hiding it. It means the Collector is not truly stateless: it holds a TTL-bounded cache of per-user data keys, because a KMS call per event at 350K/sec is not a thing.
    • That cache is a dependency inside the component that must not fail, so it fails open in the only safe direction: a key that cannot be fetched means the batch is 503'd and retried, never written in the clear.
    • The cache TTL is also the real erasure latency, which is why it is short and measured. It is the number to quote when someone asks how fast erasure takes effect.
  • The durable log is the contract between ingest and everything downstream.
    • The Collector returns 202 only after the append is acknowledged with acks=all, so an ack means the data survives a broker loss.
    • The log is split into many partitions. One event type is 40 percent of the traffic, so the partition key is where this strains; the hot event type dive picks it.
    • Two independent consumers read the same stream at their own offsets: the archive and the aggregator. Neither can block the other, and adding a third later costs nothing.
  • The raw lake is the system of record for its 90-day retention, and it is what the counts are rebuilt from.
    • Hourly Parquet in object storage, partitioned by date and hour, about 5 TB a day, 90 days hot.
    • It exists for three reasons that are worth naming separately: replay after an aggregation bug, backfill of late data, and the legal obligations in requirement 4.
  • The registry (requirement 3) sits behind POST /v1/event-types, so a new type is an API call, not a deploy. The Collector checks each event's type against it. What happens to a type nobody registered, and what stops a client registering thousands, is the event-type dive.
  • Loss and duplication are handled by two different mechanisms. The log plus acks=all is what stops loss. The client-generated eventId is what stops a retry becoming a second event. Conflating them is the most common mistake here.

2) Counting the stream exactly

Counting: each minute of the stream becomes one row of 1,000 counts The Aggregator reads events from EventStream and counts them per eventType in one-minute windows by eventTime. When a minute's window closes it writes that minute's counts as one CountBucket row in MinuteCounts. Three places strain, each handled by its own deep dive. Counting: each minute of the stream becomes one row of 1,000 counts 350K events a second at peak, but only 1,000 event types, so a minute of the whole stream is at most 1,000 counters. EventStream the durable log from ingest evt evt evt evt Aggregator one-minute windows by eventTimeat most 1,000 countersper open minute MinuteCounts one CountBucket row per minuteholding all 1,000 counts 1. Aggregator reads events from EventStream 2. when the minute closes, Aggregator writes its counts as one row // the 12:31 row{ page_view: 8400000, click: 2210000, ... // 1,000 slots} where this strains, each with its own deep dive: - page_view is about 40 percent of all events, so how the counting is split across tasks matters: the hot event type dive.- a crashed task replays from the log and an SDK retries a batch, so the same event can arrive twice: the exactly-once dive.- a phone that was offline for an hour sends events for a minute that already closed: the late-events dive.
  • The Aggregator reads the log and counts events per type in one-minute windows by eventTime. Its state for the open minute is at most 1,000 counters.
  • When a minute's window closes, it writes that minute's counts as one CountBucket row in MinuteCounts.
  • Three places strain, each with its own dive.
    • page_view is about 40 percent of all events, so how the counting is split across tasks matters. The naive split, keyBy(eventType) on the raw stream, puts all of it on one task; the hot event type dive handles it.
    • A crashed task replays from the log and an SDK retries a batch, so the same event can reach the Aggregator twice; the exactly-once dive handles it.
    • A phone that was offline for an hour sends events for a minute that already closed; the late-events dive handles it.

3) Answering topK(start, end, k)

Answering topK(start, end, k) from the minute rows A dashboard calls getTopK on the QueryService. QueryService reads the minute rows that cover the range from MinuteCounts, sums them into one array of 1,000 counts, partial-sorts for the top k and returns them. A long range is where this strains. Answering topK(start, end, k) from the minute rows every row holds all 1,000 counts, so the answer is arithmetic over the rows in the range. Dashboard internal, authenticatedtens to hundreds a second QueryService sums the rows into 1,000 countspartial-sorts for the top k MinuteCounts one row per minuteall 1,000 counts 1. Dashboard calls getTopK(start, end, k) 2. QueryService reads the minute rows in [start, end) 3. QueryService returns the k types with their counts // sum then selecttotal[slot] += row[slot] // every rowtop k of total // 1,000 entries where this strains: - a 30-day range reads 43,200 minute rows: the range-query dive.
  • The QueryService reads the minute buckets that cover [start, end) from MinuteCounts, one row per minute.
  • Then sum the vectors elementwise into one 1,000-entry array and take the top k, which is arithmetic, not a database problem. Use a partial selection. At 1,000 entries a full sort is also fine, and saying "I would just sort a thousand numbers" is a better answer than reciting a heap.
  • A long range is where this strains: a 30-day query reads 43,200 minute rows. The range-query dive handles it.

4) Erasing a user's data on request

GDPR erasure by deleting the key, not by rewriting the lake A user asks PrivacyService for erasure. PrivacyService destroys that user's data key in KeyStore, which leaves every RawEventLake row for that user undecryptable without rewriting a file, appends a tombstone to DeletionLedger, and confirms to the user inside 30 days. The count tables never held a userId, so there is nothing to erase there. GDPR erasure by deleting the key, not by rewriting the lake one data key per user. destroy the key and every row that user ever wrote stops being readable. User right to erasure request PrivacyService the erasure workflow30 day SLA clock KeyStore one data key per userkeyId = HMAC(secret, userId)envelope encryption for the lake RawEventLake S3 Parquet, by date and houruserId and propertiesencrypted per usereventType and eventTime in clear DeletionLedger append only, survives the erasurereplicas and restored backupsreplay it and re-delete the key one Parquet row, before and after before {userId: enc(k_u, 8812), eventType: checkout}after {userId: <no key>, eventType: checkout} the file is byte for byte identical. only thekey that decrypts userId and properties is gone. key destroyed one row deleted, nothing else moves 1 User asks for erasure through the privacy portal 2 PrivacyService destroys that user's data key in the KeyStore 3 the destroyed key leaves every Parquet row for that user undecryptable, no file rewritten 4 PrivacyService appends a tombstone so a restored backup erases the key again 5 PrivacyService confirms inside the 30 day SLA, within the statutory month not personal data MinuteCounts / HourCounts / DayCounts no userId, no propertiesaggregate counts, untouched by erasure10B events a day collapse to 1,000 counts nothing to erase here: these tablesnever held a userId the limit of that argument: a count of 1 in a one minute window is close to identifying,so narrow windows are width- and count-suppressed. that is a query rule, not a reason to edit history. the not-so-happy paths: - compaction drops the dead ciphertext on the normal 90 day retention cycle. the key delete is what meets the deadline.- a backup restored from before the erasure brings the key back, so the DeletionLedger is replayed after every restore.- an export taken before the erasure is already outside the system, which is why exports are logged and time limited.- one key delete covers every replica and every region, because none of them can read the ciphertext without it.- not instant: Collectors cache data keys, so erasure takes effect once that TTL expires. keep it short, measure it, quote it.- the export index (keyId to files), and any raw type-name store the event-type dive adds, are erased with the request; the DeletionLedger, keyId and timestamps only, must survive it.
  • Name exactly where personal data lives: the log and the lake hold it only as ciphertext, and the counts hold none. Be exact, because "one place" is a claim people overreach on.
    • The Collector encrypts userId and properties before the append, so the log and the lake both hold ciphertext and neither is readable without the key. That ordering is the whole trick and it is easy to get backwards.
    • The count vectors hold neither field, in any form.
    • What is not ciphertext, and must be named: the deletion ledger, the export index, and any raw type-name store the event-type dive adds, which is exactly where an identifier-shaped type name would land. The key store is keyed by an HMAC, so it holds no plaintext identifier.
    • Two of those three are deletable by ordinary means; the ledger is not, and the distinction matters. The export index and any such type-name store go with the erasure request. The deletion ledger has to survive it: it is replayed after every restore and it is the audit trail a regulator asks for, so it stores the keyId and the timestamps, never the raw identifier or any event data.
    • Inventory the whole field list, not just userId, because a tracking event is full of personal data people forget: IP address, device id, session id and user agent are all personal data under GDPR. They go inside the encrypted blob with everything else, and saying the list out loud is what convinces a DPO you have actually looked.
    • Confining it deliberately is the design. A system that sprinkles userId into six derived tables has six erasure problems.
  • Deleting rows out of the lake is the obvious plan and it is not viable at this size.
    • The lake is immutable Parquet, so "delete one user" means finding and rewriting every file that touched them, across 450 TB and 90 days.
    • One active user's events can be spread over thousands of files, and you would repeat that work for every request.
  • So encrypt per user at ingest and erase by destroying the key.
    • Each user has a data key, wrapped by a KMS master key, standard envelope encryption. The Collector encrypts userId and properties with it before the row is ever written.
    • Two details decide whether this is real erasure or theatre, and they are the ones people skip.
      • Use a random IV per row. Deterministic ciphertext would leave an identical token on every one of that user's rows, so after the key is destroyed you could still single out one person's entire behavioural trace, which is precisely what erasure is supposed to prevent.
      • Derive the key id as an HMAC under a secret, not a bare hash(userId). User ids are enumerable, so an unsalted hash is a rainbow table away from plaintext and is a reversible pseudonym rather than anonymisation.
    • eventType and eventTime stay in the clear, which is what lets replay, backfill and audit keep working after a mass erasure. It also means an erased user's events keep contributing to the counts, which is consistent with the aggregates argument below.
    • Erasure destroys that one key, which is a single small write. Every row for that user, in every file, in every replica and every region, becomes undecryptable, because none of them can read ciphertext without it.
    • Not literally at the same instant, and the gap is worth owning: Collectors cache data keys, because a KMS call per event at 350K/sec is not a thing. Erasure is effective once the caches expire, so keep that TTL short, measure it, and quote it as the real number.
    • The dead ciphertext is removed later by ordinary compaction on the 90-day retention cycle. The key delete is what meets the deadline, not the cleanup.
    • The cost, which the 5 TB a day figure hides: per-user ciphertext is unique, so the widest column stops dictionary-compressing. That number is wire size, and this design gives up most of the compression a plain Parquet lake would get.
  • Write a tombstone to a deletion ledger, because backups come back.
    • Restoring a snapshot from before the request would otherwise resurrect a live key, so the ledger is replayed after every restore.
    • The backup that matters is the KEY STORE's, not the lake's. Restoring lake files changes nothing, since they are unreadable. Restoring the key store is the only event that can undo an erasure, which is the part usually missed.
  • Export needs its own index of where each user's rows are, because an encrypted userId is not searchable. Admitting that is better than pretending erasure and export are the same shape.
    • Erasure is one key delete. Export has to FIND the rows, and encrypted userId is not searchable, so without help it is a 450 TB scan.
    • So the archive sink maintains a small index from the keyId to the files and row groups that user appears in. Export reads the index, decrypts, and assembles.
    • It has to be the keyId and not a fresh hash of the userId, for two reasons. The sink sits downstream of the log, where the identifier is already ciphertext, so a plaintext hash is not available to it. And a bare hash of an enumerable id is the reversible pseudonym ruled out above. So the keyId, which is already an HMAC under a secret, travels in the clear on the row and is the join key.
    • It is a second store keyed by a pseudonymous id, so it is in scope too and the same request deletes its entries. Say it out loud, because "personal data lives in exactly one store" is the tidy claim candidates leave standing here, and the export index is what makes it false.
  • The aggregates are untouched, and you should defend that rather than apologise for it. A count with no identifier is not personal data, cannot be re-identified at any useful aggregation width, and removing one user's contribution to "page_view: 8,400,000" is neither required nor meaningful. The short dive on small counts covers where that argument runs out.
DONE WHEN: emitting, registering a type, counting, querying and erasing all have an end-to-end path on the board, you have said where each one strains, and you have not yet been dragged into any single one of them.
STEP 4 OF 5

Potential deep dives

~20 min, interviewer steers
TRIGGER: "what if they ask for a whole year" / "how fast is that query really"

1) How is topK fast for any range, from a minute to a year?

ROLLUP TIERS · ALIGNED DECOMPOSITION · ONE ROW PER BUCKET
Bad Solution: scan the raw events at query time
  • Group by eventType over the range and sort.
    • A 30-day range is 300 billion rows. Even at a fantasy 10 GB/sec of scan this is hours, and it burns the entire cluster for one dashboard load.
  • It also scales with traffic rather than with the question, which is backwards: the answer is 1,000 numbers regardless of whether ten billion or ten trillion events went into it.
Good Solution: pre-aggregate into minute buckets and sum them at query time
  • This is the right instinct and it fixes the common case. A one-hour query is 60 buckets and it is instant.
    • But cost is now linear in the range: 43,200 buckets for 30 days, 525,600 for a year.
    • If each bucket is also stored as 1,000 separate rows, that is 43 million rows read for a month, and the p99 requirement is gone.
    • The failure is quiet, which is worse: the demo is fast and the quarterly report times out.
Great Solution: three tiers, aligned decomposition, and a whole bucket in one row
  • Roll up minute into hour into day, with each tier written only from settled data below it.
    • A rollup job folds 60 settled minutes into an hour and 24 settled hours into a day. It reads only buckets past the 15-minute lateness window, and reruns for any bucket a later restatement dirties. A rerun overwrites the same hour row; it never adds to it.
    • Same shape at every tier, so the query code is written once.
    • Retention differs per tier because size differs wildly: minutes for 60 days, hours for 2 years, days forever at 365,000 counts a year.
    • Say what retention does to the query, because it is not free: a range older than 60 days has no minute rows for its ragged edges, so it degrades to whole hours, and past 2 years to whole days. That is a fine answer, but it has to be said rather than discovered.
  • Decompose the range into the fewest aligned buckets that cover it exactly.
    • Ragged minutes at the two edges, whole hours next, whole days in the middle. It is the same idea as a segment tree, but the tree is the calendar so there is nothing to build.
    • For example, 28 days 8 hours 59 minutes splits into 47 minutes, 5 hours, 28 days, 3 hours and 12 minutes: 95 bucket reads.
    • Say whose day, because "aligned" is meaningless without it and nobody asks until it is wrong. Buckets are UTC-aligned, which is what makes "24 hours folds into a day" true all year.
      • Align to a local calendar instead and the rollup breaks twice a year: a US Eastern local day is 23 hours in March and 25 in November, so a 24-hour fold undercounts one and double-counts the other, permanently, because the sink overwrites.
      • The cost of UTC is paid at the product edge: a caller wanting local "yesterday" gets 24 hour buckets instead of 1 day bucket, and a half-hour zone such as India or Nepal can never use the day tier at all. Exact and bounded either way, so it is a product decision, not a correctness one.
    • The edge terms are bounded and tight: at most 59 + 59 minutes and at most 23 + 23 hours, both achievable at once with a range like 00:01 to 23:59 of a later day.
    • The day term is linear, so state the real numbers, and state which range they describe. A ragged span up to a month is about 193 reads and up to a year about 528. Every one is a point read on a key you computed without touching the database, so after the manifest lookup they issue as one parallel batch, not 500 serial round trips.
    • A whole-day-aligned span is much cheaper, because the edges complement: minutes sum to 60 and hours to 23 rather than hitting 118 and 46 independently. Exactly 30 days is at most 112 reads, exactly 365 days at most 447. "The last 30 days" is the aligned case, so quoting 193 for it overstates by 70 percent.
    • If a flatter bound is required, extend the ladder, but do not overclaim what it buys. Adding month and year tiers raises the fixed edge overhead to 118 minutes + 46 hours + 60 days + 22 months = 246 buckets before any year bucket at all, so a decade is about 255 and a century about 345. It flattens the slope; it does not remove it.
    • The reason the ladder still helps is the same reason the first three tiers did: a month rung is 12 rows a year and a year rung is 1, and each turns a linear term into a constant one.
  • Store a bucket as one row: a slot vector indexed by typeId, 1,000 slots wide today.
    • About 193 key reads of 8 KB for a ragged month, roughly 1.5 MB, comfortably inside 100 ms when issued in parallel. 112 reads if the range is day-aligned. A year is about 469 once retention is accounted for, under 4 MB.
    • Fixed slots mean a new type appends a slot and a retired type keeps its own forever. Never renumber, or every historical vector silently means something different.
  • Sum elementwise into 1,000 counters, then partial-sort for k. With 1,000 entries the selection algorithm genuinely does not matter, and claiming a heap is essential here would be theatre.
  • Cache each bucket under a key that changes when the bucket is rewritten. The key is (granularity, bucketStart, revision), where the revision is a number that goes up every time the bucket is rewritten, and the revisions themselves are read from a small per-day manifest so the key is not circular. Past the backfill horizon (24 hours, after which the nightly backfill no longer touches a bucket) a bucket changes only through an explicit restatement, which bumps the revision and so evicts itself from this key; anything younger gets a short TTL, because a late event can still rewrite it.
    • Define "closed" as past the 24-hour backfill horizon, not merely past the window. A bucket can still be rewritten by allowed lateness for 15 minutes, and again by the nightly backfill. "Immutable once the window shuts" is the trap.
    • A restatement bumps the revision, which evicts by construction rather than by invalidation message.
    • The manifest is what stops the key being circular: you cannot build the key without knowing the current revision, and reading the bucket to learn the revision is the read you were trying to avoid. Without the manifest the revision in the key is decorative and you are really just running a TTL.
    • Count its cost honestly: it is one extra round trip before the batch, and one manifest row per day of range, so 30 for a month and 365 for a year on top of the bucket reads.
Answering topK(start, end, k) by decomposing the range into aligned buckets QueryService splits the range into whole days in the middle, hours at the shoulders and minutes at the edges, so 28 days 8 hours 59 minutes is 95 bucket reads. It reads those buckets from DayCounts, HourCounts and MinuteCounts, sums them into one map of 1,000 counts and partial-sorts for the top k. RollupJob folds minutes into hours and hours into days. Answering topK(start, end, k) by decomposing the range into aligned buckets 1,000 event types. counts are pre-aggregated exactly into 1 minute buckets, then rolled up to hours and days. the fewest aligned buckets that exactly cover the range 47 min MinuteCounts47 rows 5 hours HourCounts5 rows 28 days DayCounts28 rows 3 hours HourCounts3 rows 12 min MinuteCounts12 rows start end this range is 28 days 8 hours 59 minutes: 95 buckets, so 95 row reads QueryService getTopK(start, end, k)one map of 1,000 counts in memory DayCounts one row per day, all 1,000 countskept forever, 365K counts a year HourCounts one row per hour,all 1,000 counts2 year retention MinuteCounts one row per minute,all 1,000 counts60 day retention TopKResponse k event types, sorted by countpartial sort: 1,000 log k RollupJob reads only buckets pastthe 15 min lateness window one bucket is ONE row a 1,000 slot vector of counts today, about 8 KBso 193 buckets is 193 key reads,not 193,000 rowsthis is what 1,000 event types buys you 1 QueryService splits the range into whole days in the middle, then hours, then minutes at the edges aligned means a day bucket only ever covers a whole UTC day 2 QueryService reads the day, hour and minute buckets that cover each piece 3 QueryService sums them into one map of 1,000 counts, then partial-sorts for the top k RollupJob folds 60 minute rowsinto one hour row, and 24 hourrows into one day row one pass per settled bucket, idempotent;reruns a bucket a restatement dirties why the rollups exist 43,200 minute buckets x 1,000 types = 43M counts if you read raw minutes.aligned buckets bring it to 193 rows for a RAGGED month: 118 minutes and 46 hoursare the caps for a RAGGED span only. a whole-day span complements to 60+23,so exactly 30 days is 112 rows and exactly a year is 447. the not-so-happy paths: - scanning the raw event lake at query time instead: a 30 day range is 300 billion events, which is the option the rollups exist to avoid.- a minute bucket still open when the query runs is left out; how the response says so is the late-events dive.- RollupJob is idempotent per bucket: a rerun overwrites the same hour row, it never adds to it.- MinuteCounts ages out at 60 days, so a range older than that is answered from HourCounts and DayCounts only.
TRIGGER: "is the traffic evenly spread" / "what is your hottest key"

2) One event type is 40 percent of the traffic. Where does that melt?

NEVER KEY THE LOG BY TYPE · LOCAL PRE-AGGREGATE · SHUFFLE PARTIALS, NOT EVENTS
Bad Solution: partition the log by eventType and keyBy it in the job
  • It looks natural, because the counting is per type, so the data "should" be grouped that way.
    • One partition then takes 140K events/sec, about 70 MB/sec, and more to the point exactly one consumer task has to deserialize and count all of it.
    • One consumer task owns it, and no amount of scaling out helps: adding tasks cannot split a single key. The job does not fall over gracefully, it just develops permanent lag on the one key everybody looks at.
    • It also caps parallelism at 1,000 forever, and the useful parallelism is far lower because the distribution is Zipf.
Good Solution: salt the key
  • Key by (eventType, random 0..15), then sum the 16 partials in a second stage. This does work, and it is the standard answer.
    • The salt factor is a magic number chosen ahead of time: 16 is far too much for a rare type and not enough if one type reaches 80 percent.
    • Every raw event still crosses the shuffle. You have fixed the hotspot and paid full network cost for it, roughly 175 MB/sec.
    • Be fair about the comparison, because a good interviewer will be: a real salted pipeline usually pre-aggregates too, and then it is close to the Great answer. The thing that matters is the local pre-aggregate, not salt versus task index. What the task index adds is that there is no fan-out constant to pick.
Great Solution: local-global aggregation, where the task index is the salt
  • Stage one does not key at all: each task counts its own slice into a local map of at most 1,000 counters for the current minute.
    • Skew is irrelevant, because tasks are fed by hash(eventId), which is uniform by construction. Every task sees roughly the same volume no matter how lopsided the types are.
    • 1,000 counters is nothing. This is only possible because of the cardinality number from step 1.
  • Stage two keys by eventType, but only partials (each task's per-minute counts) cross the shuffle.
    • Stage two REPLACES per task, it does not blindly add. When allowed lateness reopens a minute, stage one re-emits a partial for a window it already reported, and a stage that simply summed arrivals would add the restated partial on top of the original. So its state is keyed by (eventType, minute, taskIndex) holding the latest partial per task, and the emitted count is the sum over tasks of those latest values.
    • At most 3,300 partials/sec instead of 350,000 events/sec, and fewer in practice because Zipf means most tasks do not see all 1,000 types in a given minute.
    • That is roughly 100x fewer messages, and far more in bytes: a partial is a typeId and a count, order of 16 bytes, against a 500-byte event.
    • The hottest second-stage key gets 200 messages a minute.
    • No fan-out constant to tune: parallelism is the fan-out, so it adapts when the job is resized.
  • The cost is that counts only materialise at window close, so the pipeline is minute-granular by construction. Say what it costs, because everything does. If someone wanted per-second freshness, shorten the window and pay in partial volume. That is the actual dial.
  • Guard the input side too: the log is partitioned by hash(eventId), so no producer-side key can create a hot partition even if a single tenant sends everything.
    • Keying the log by event type would send 40 percent of all traffic to a single partition, which is the hot-key problem created on purpose at the one place it is hardest to fix.
Two stage aggregation, because one event type is 40 percent of the traffic EventStream fans its partitions out to 200 PreAgg tasks, each counting its own slice in a local map of 1,000 counters. When the minute closes each task emits one partial per eventType to GlobalCombine, which sums the 200 partials and writes the minute's row to MinuteCounts. Two stage aggregation, because one event type is 40 percent of the traffic page_view alone is about 140K events a second. no keyBy on the raw stream: every task counts locally first, then 200 partials get summed. EventStream partitioned by hash(eventId) evt evt evt 350,000 events a second at peak front: tasks read from here PreAgg task1 no keyBy, just a local map1,000 counters per taskper minutepage_view: 42,180 this minute PreAgg task2 no keyBy, just a local map1,000 counters per taskper minutepage_view: 41,905 this minute PreAgg task3 no keyBy, just a local map1,000 counters per taskper minutepage_view: 42,060 this minute ... 200 tasks in all GlobalCombine keyBy eventTypesums 200 partialspage_view = 8,400,000 MinuteCounts one row per minuteholding all 1,000 countsexact, not sketched12:31 -> page_view 8,400,000 1. EventStream fans its partitions out to the PreAgg tasks // one task, one minute, no shuffle yetcounts = { page_view: 42180, click: 11020, add_to_cart: 3915, ... // 1,000 keys, never more} 2. Each task counts its own slice of the stream in a local 1,000 entry map 3. Each task emits one partial per eventType when the minute closes 3,300 partials a secondreach the shuffleinstead of 350,000events. the task indexdoes the job a randomsalt usually does. 4. GlobalCombine sums 200 partials into one exact count per type per minute 5. GlobalCombine writes the minute's row how that write survives replayis the exactly-once dive A plain keyBy(eventType) on the raw streamsends all of page_view to one task:140K events a second, 70 MB a second,on a single core. the not-so-happy paths: a minute reopens inside allowed lateness? stage two REPLACES that task's partial, it does not add a second one.
TRIGGER: "the job crashes and restarts" / "the SDK retried, is that counted twice"

3) At-least-once delivery, exactly-once counts

OVERWRITE, DO NOT INCREMENT · DEDUPE INSIDE THE WINDOW · CHECKPOINTED OFFSETS
Bad Solution: INCR a counter as each event arrives
  • Every retried batch, every consumer rebalance, every checkpoint restore adds the same events again.
    • The error is silent, permanent, and always in the same direction: counts only ever drift upward.
    • There is no way to detect it after the fact, because the correct number was never written down anywhere.
Good Solution: a global dedupe set on eventId
  • Check every eventId against a set before counting it. Correct in principle.
    • The set is unbounded: 10 billion ids a day, 900 billion at 90 days.
    • It puts a remote lookup in front of every one of 350K events/sec, which is now the slowest thing in the pipeline and a new hard dependency.
    • A Bloom filter shrinks it but false positives silently drop real events, which trades an overcount for an undercount.
Great Solution: make the write idempotent, then dedupe only where duplicates can actually be
  • The sink writes a value, not a delta, and it writes the WHOLE bucket.
    • After GlobalCombine there is a third stage that re-keys by window, so one task assembles the full 1,000-slot vector for a minute and does one atomic put: "the vector for minute M is V".
    • Per-type writes would defeat the whole idea. 1,000 keyed results writing into one shared row is 1,000 read-modify-writes, and read-modify-write is precisely the non-idempotent operation this design exists to avoid.
    • Replaying a window then rewrites the same row with the same vector. Applying it twice is a no-op, and no distributed transaction is required.
    • Fence it with a monotonic revision, conditional on the stored one, because the streaming restatement and the nightly backfill both write this bucket and arrival order is not correctness order. Backfill revisions sort above streaming ones so the recomputation wins.
      • Pure last-writer-wins is ordered by arrival, not by correctness, so a straggling streaming write landing after the backfill makes the worse number permanent. Every put carries a revision and is rejected if it is not greater than the stored one.
      • Note the asymmetry that makes this necessary: with increment a lost update is one wrong number, recoverable. With overwrite a wrong write is permanent by construction. That is the price of idempotence and it has to be paid with a fence.
      • Name the store, because the claim depends on it. Anything with a single-key atomic put of an opaque value works: DynamoDB, Cassandra, or plain Postgres. A conditional put on revision is the one primitive that is actually required, and all three have it.
    • This is also why stage two aggregates a window and emits once, rather than streaming increments out as it goes.
  • Bound the dedupe to the window, because that is where almost every duplicate is.
    • An SDK retry lands within seconds, so the duplicate is inside the same minute as the original in essentially every case.
    • Each task keeps the eventIds it has seen for the window, in local memory, with no remote call.
    • The reason a LOCAL set is sufficient is hash(eventId) partitioning, and this is the second job that choice is doing. A retry carries the same eventId, so it lands in the same partition and therefore the same task as the original. Partition any other way and a local set catches nothing.
    • Size it, since everything else on this page is sized: 350K/sec over 200 tasks is about 105K ids per task per minute, order of 5 MB of task state, and roughly 75 MB if you hold it across the full lateness window.
    • Two preconditions that are easy to state and easy to forget.
      • Colocation only holds while the partition count is fixed, because it is hash(eventId) mod partitions. Adding partitions remaps nearly every key, so do it during a quiet window and accept that in-flight retries can double count across the change.
      • The set has to be checkpointed operator state, not a bare local map, or a rescale mid-window drops it and the duplicates it was holding back get through.
  • Exactly-once still leaks in three places: retries that straddle a window boundary, duplicates during lateness, and the backfill. Name all of them, because "exactly once" is a claim that invites exactly this question.
    • A retry straddling a window boundary is counted once in each minute. Acceptable at analytics precision.
    • A duplicate arriving during the 15-minute lateness window is counted into the restated total if the dedupe set was dropped at window close. Holding the set for the lateness period is the fix, and it costs the 75 MB above.
    • The backfill path has no dedupe at all, and it is the dangerous one: the lake is written by an at-least-once consumer, so it contains duplicates, and because the sink overwrites, a wrong backfill number becomes the permanent value. The backfill must dedupe by eventId over the hour it is rebuilding, which is affordable precisely because it is batch.
  • Checkpoint the source offsets with the window state, so a restart resumes from a consistent point instead of an arbitrary one. The framework provides this; the overwrite sink is what makes it sufficient.
    • Each task's local count map must be part of that checkpointed state, and the reason is the sink. If a task dies mid-window with an uncheckpointed local map, its slice is lost, and because the sink overwrites rather than increments, the too-low number becomes permanent. Increment would have healed itself on replay; overwrite does not. Idempotence on the write side moves the durability burden onto the aggregation state.
  • Replay is deterministic only for the same admitted events, so the lake and the backfill are the real correctness backstop.
    • Bucket ASSIGNMENT is deterministic: eventTime travels in the event, so a replayed event always lands in the window it landed in before.
    • Which events are ADMITTED is not deterministic. Watermark advance and lateness expiry depend on arrival order and wall clock, so a replay can admit an event the first run sent to the side output, or drop one it previously counted.
    • So the honest claim is: identical given the same admitted set, and the lake plus the backfill is what makes the number eventually right regardless. That is the real correctness backstop, not the checkpoint.
TRIGGER: "a phone was offline for an hour" / "clock skew" / "does yesterday's number change"

4) Late and out-of-order events

WATERMARK · ALLOWED LATENESS · SIDE OUTPUT AND BACKFILL · complete=false
Bad Solution: count by arrival time
  • Every problem in this dive disappears, and the product breaks instead.
    • A mobile client that was offline for an hour dumps its buffer into the current minute, so a spike appears where nothing happened.
    • "What happened between 9 and 10" is answered with events from 8, which is the wrong answer delivered confidently.
Good Solution: count by eventTime with a fixed delay before closing a window
  • Hold each minute open for a couple of minutes to let stragglers in, then close and write.
    • Correct for the ordinary case, and it is what the watermark is.
    • But anything later than the delay is now dropped, silently. Mobile buffering makes hour-late events routine, so this is not a rare tail.
    • Trusting client clocks also lets a device with a wrong date write into a window from last year.
Great Solution: a watermark plus allowed lateness, then a side output nothing falls out of
  • A watermark of about two minutes closes the normal case, so a minute becomes readable about three minutes after it began: one minute of window plus the two-minute watermark.
  • An allowed lateness of about 15 minutes restates a window in place when a straggler arrives. The overwrite sink is what makes restating safe: the window is recomputed and rewritten, not adjusted.
  • Anything later goes to a side output, never to the floor.
    • A batch backfill job re-reads the affected hours from the raw lake and rewrites those buckets, typically nightly.
    • The lake is what makes this possible, which is the second time it has paid for itself.
    • Rollups downstream of a restated minute must be recomputed too, so the rollup job is driven by a dirty-bucket marker rather than by a clock.
  • Clamp client clocks at the Collector. Reject or pin eventTime more than a day in the future or more than 90 days old, which is the lake retention and therefore the oldest bucket a backfill could ever restate. Count the rejects as their own metric. Otherwise one broken device rewrites arbitrary history.
  • Expose incompleteness: the read returns complete: false while the range touches anything younger than the 24-hour backfill horizon. Define the flag against that horizon rather than the window.
    • complete: false whenever the range touches anything younger than that horizon, which is the honest boundary because everything younger really can still move.
      • Pin the horizon to a number or the flag is useless. Set it at 24 hours: the nightly backfill closes yesterday and nothing older is restated on the normal path. Leaving it implicitly equal to the 90-day clamp on eventTime would mean complete: true only for ranges entirely older than 90 days, which is no dashboard anyone runs.
    • An event older than the horizon still gets counted, but through an explicit restatement that bumps the revision, so callers see it via asOf rather than silently.
      • complete: true is not a promise the number is frozen for ever, and the response has to admit that, because an event arriving after the horizon still triggers an explicit out-of-band restatement of a bucket that already read complete. Ordinary lateness and the nightly backfill cannot, since both run inside the horizon.
    • Pair it with asOf, the max revision over every bucket read, so a caller can tell a restatement from a disagreement. A newest-bucket-only asOf would miss exactly the case this dive is about.
      • That distinction is the whole point of the field. A late event restates an OLD bucket, which leaves the newest bucket's revision untouched, so a newest-bucket asOf would stay identical while the number changed. Taking the max, or a digest over the revision vector, is what actually detects it.
    • The alternative is a dashboard that quietly contradicts itself between two refreshes, which destroys trust far more effectively than an honest flag ever does.
TRIGGER: "what if a new event type is added" / "what stops someone sending garbage"

5) Event type handling and the cardinality attack

REGISTRY IS THE ALLOWLIST · STABLE typeId · OVERFLOW SLOT · PER-KEY QUOTA
Bad Solution: accept whatever string arrives
  • The 1,000-type assumption is now an assumption about client behaviour, and every guarantee on this page rests on it.
    • One release ships "checkout_" + orderId as a type name and cardinality goes to millions overnight.
    • The local pre-aggregate map is no longer 1,000 entries, so the tasks OOM. The bucket vector is no longer 8 KB. The query no longer sums 1,000 numbers.
    • Say the shape of this out loud: it is not a slow degradation, it is the collapse of the one assumption the design is built on.
Good Solution: a registry allowlist, reject anything unknown
  • Types must be registered before use, and the Collector rejects the rest. This does protect the invariant.
    • But rejection loses data that was genuinely emitted, and the client learns about it from a log nobody reads.
    • Registration becomes a ticket to another team, so people work around it by overloading an existing type, and now the data is wrong in a way that is much harder to see.
Great Solution: self-serve registry, stable ids, and an overflow slot that keeps the invariant
  • Registration is an API call, not a deploy and not a ticket. POST /v1/event-types returns the next typeId. The registry is small and cached in every process with a short refresh.
  • typeId is assigned once and never reused.
    • Deprecating a type marks it inactive and keeps its slot. Reusing slot 42 would make every historical vector silently mean something else, and nothing would ever surface the error.
    • The vector is sized to the registry high-water mark, not to the count of currently active types.
  • Unknown types go to a reserved overflow slot rather than to the floor. It sits alongside the 1,000 registered types rather than taking one of their slots, so the vector is really 1,001 wide and still about 8 KB.
    • The invariant holds because __other is one slot no matter how many distinct unknown names arrive.
    • The traffic is still visible, so a team that shipped before registering sees their volume rather than silence.
    • Sample the distinct unknown names into a side table, capped, so the on-call can see what is arriving without storing millions of strings. This sample is in GDPR scope and is erased with the request, because an identifier-shaped type name lands here.
    • Alert on the overflow slot: a jump there is the early warning for both a bad release and an attack.
    • The write response lists an unknown type in warned, not rejected, so the client finds out without losing the event.
  • Set a quota per writing key on distinct new types per hour, so a single compromised or buggy client cannot exhaust the registry. This is the actual defence against a deliberate cardinality attack, and it belongs at the public write endpoint where the untrusted input arrives.
  • Cap the registry outright as well, because a rate limit only slows growth. The 8 KB row is today's figure and it scales linearly with the high-water mark, so put a hard ceiling on it (say 4,000 slots), alert well before it, and make crossing it a deliberate decision rather than a slow surprise.
    • At the 4,000-slot cap a vector is 32 KB, and every read figure on this page scales with it.
    • Buckets written at different times can have different widths, so the reader treats a short vector as zero-padded rather than assuming a fixed length.

Three more dives, briefly

  • Replicate and partition per store: the log at RF 3 with acks=all, the counts store copied to every region, the lake by date and hour. The answer is different for each.
    • Log: RF 3, acks=all, min.insync.replicas=2, spread across availability zones. It tolerates one broker loss with no acknowledged write lost, and rejects writes rather than accepting unreplicated ones when two are down.
    • Counts store: partition by bucketStart so it is time-ordered and retention is a partition drop rather than a mass delete. The whole thing is small, so replicate it fully to every region and serve reads locally.
      • Full replication is only affordable because of the cardinality number. Worth saying, since it is the third distinct thing that number bought.
    • Raw lake: partitioned by date and hour, which is what makes a backfill read one hour instead of the whole lake. Cross-region replication for durability, and the object store handles the redundancy inside a region.
    • Multi-region ingest: write to the local region and replicate asynchronously, because a tracking event must never wait on a cross-ocean round trip. Aggregate per region, then sum the regional vectors: they are 8 KB each, so the global rollup is trivial.
      • Do the merge once, in a job, not per query. Summing regional vectors at read time multiplies every query's read count by the number of regions. A merge job writes a global bucket whose revision advances only when every region has reported, so the query path stays single-tier.
      • That gives the honest cost: a global number lags the slowest region, and a region that is down leaves the global bucket incomplete rather than silently short. complete: false is doing the work here too.
  • A count of 1 for a rare type can identify a person, so suppress small counts and narrow ranges. This is the privacy edge case that the "aggregates are anonymous" argument does not cover.
    • A count of 1 for a rare type in a one-minute window is close to identifying a single person, especially combined with anything else the caller knows.
    • Suppress or widen: refuse ranges under a minimum width, or drop entries below a minimum count, for any caller without a legitimate reason to see raw precision.
    • Also enforce purpose limitation and consent at ingest: if a user has not consented to analytics, the event should not be written, which is cheaper and safer than erasing it later.
    • Data residency is a partitioning question in disguise: EU events stay in EU storage, so the regional aggregation above is doing double duty.
  • At 100x cardinality the exact vector dies, so keep exact counts for a head of hot keys and a sketch for the tail. This is the most likely follow-up of all.
    • If the key becomes a URL or a productId, 1,000 becomes 10^8 and the vector, the local map, and the full-scan sum all die together.
    • Then you split: keep exact counts for a tracked head of a few thousand known-hot keys, and a Count-Min Sketch or Space-Saving summary for the tail.
    • Top-k over sketches is approximate and, importantly, is not mergeable across buckets without error accumulating, so the rollup design changes too.
    • The reason to have this ready is that it shows the exact-counts choice was a judgement about this problem, not the only tool you have.

How you would know it is wrong

  • A design whose entire pitch is the word "exact" needs a number that goes red, and this is the thing most candidates never bring up.
    • Reconcile, do not assume. A daily job recounts one hour straight from the lake and diffs it against the stored HourCounts. Any non-zero diff is a bug, not a rounding artefact, because both sides claim to be exact.
    • Count at every stage boundary and require them to agree: accepted at the Collector, appended to the log, counted by the aggregator, archived to the lake. A gap between two adjacent counters localises the loss immediately.
    • Alarm on watermark lag and on a stuck rollup, since a bucket that is never written looks exactly like a quiet minute.
    • Alarm on the __other slot, which is the early warning for both a bad release and a cardinality attack.
    • Track the conditional-put rejection rate. It should be near zero; a spike means two writers are fighting over the same bucket.
DONE WHEN: you have opened two or three dives properly rather than five thinly, and the interviewer has heard the cardinality number used as a reason at least three separate times.
FLASHCARDS · THE FIVE HARDEST PROBESshow all (interview mode)
Ten billion events a day. Why are you not using a Count-Min Sketch?
  • Because a sketch solves high cardinality, and there are only 1,000 event types.
  • A full minute of the entire firehose is 1,000 counters, about 8 KB, so a whole minute of exact state is one small array.
  • Exact is strictly better when it is affordable: no error bounds to explain, and the counts are mergeable across buckets without error accumulating, which is what makes the rollup tiers work at all.
  • The volume, 10B a day, sizes the raw storage and the ingest pipeline. It has nothing to do with the size of the counting state, and conflating the two is the trap in the question.
  • What would change my answer: if the key were a URL, a productId, or a userId. Then it is a tracked head of exact counts plus a sketch for the tail.
page_view is 40 percent of your traffic. Where does that melt, and what do you do?
  • It melts at any keyBy on eventType: 140K events/sec, about 70 MB/sec, onto one task, and adding tasks cannot split a single key.
  • First, do not create it upstream: the log is partitioned by hash(eventId), so ingest is uniform by construction.
  • Then local-global aggregation. Stage one keeps a local map of at most 1,000 counters per task with no keyBy, so skew is irrelevant.
  • Stage two keys by eventType, but only per-window partials cross the shuffle: about 3,300 a second instead of 350,000 events a second.
  • The task index is doing the job a random salt usually does, without having to pick a fan-out constant that is wrong for both the hottest and the rarest type.
  • The cost is that counts only materialise at window close, so freshness is minute-granular by construction.
The stream job dies and restarts from a checkpoint five minutes back. Why are the counts still right?
  • Because the sink overwrites rather than increments, and it overwrites a WHOLE bucket: a third stage re-keys by window so one task puts the full 1,000-slot vector for that minute in one atomic write. Applying it twice is a no-op.
  • Per-type writes would have broken it: 1,000 keyed results writing into one shared row is 1,000 read-modify-writes, which is the non-idempotent operation the whole design avoids.
  • The put is fenced on a monotonic revision, because the streaming restatement and the nightly backfill both write this bucket and arrival order is not correctness order. Without the fence a late straggler makes the worse number permanent.
  • Recomputing a window is deterministic because events are assigned by eventTime, which is carried in the event, not by arrival order.
  • Source offsets are checkpointed with the window state, so the replay boundary is consistent rather than arbitrary.
  • Within the window each task holds the eventIds it has seen, in local memory, which catches SDK retries. That works only because hash(eventId) partitioning puts a retry on the same task as the original.
  • The honest gaps: a retry straddling a window boundary is counted in each minute, and the backfill path has to dedupe by eventId itself because the lake is written at-least-once and the sink overwrites.
A user demands erasure. What gets deleted, what does not, and defend leaving the counts alone.
  • The Collector encrypts userId and properties BEFORE the append, so the stream and the lake both hold ciphertext only. The key store is keyed by an HMAC so it holds no plaintext identifier either; what is left is the deletion ledger, the export index, and the sampled unknown-type names.
  • Erasure destroys that user's data key. Every row for them, in every file, replica, and backup, becomes undecryptable in one small write.
  • Two details make it real erasure rather than theatre: a random IV per row, so no stable per-user token survives to single them out, and an HMAC under a secret for the key id, since a bare hash of an enumerable userId is a reversible pseudonym.
  • Rewriting Parquet is not viable: 450 TB, and one active user is spread over thousands of files. Compaction drops the dead ciphertext later on the normal 90-day cycle.
  • A tombstone goes in the deletion ledger, replayed on restore, so a backup from before the request cannot resurrect the key.
  • The count vectors are untouched because they hold no identifier. Removing one person's contribution to "page_view: 8,400,000" is neither required nor meaningful.
  • The gap to own: Collectors cache data keys, so erasure is effective once those caches expire, and it is the KEY STORE's backups, not the lake's, that can undo it.
  • Export is the harder half: encrypted userId is not searchable, so the archive sink keeps a keyId-to-file index, which is itself in scope and erased by the same request. It keys on the HMAC keyId, not a fresh hash, because downstream of the log there is no plaintext userId left to hash.
  • The limit of that argument: a count of 1 for a rare type in a one-minute window approaches identifying. That is handled by minimum-width and minimum-count suppression, not by editing history.
topK for the last 30 days, k equals 10. Count the reads you actually do.
  • Decompose into aligned buckets: ragged minutes at the two edges, whole hours at the shoulders, whole days in the middle.
  • Careful: "the last 30 days" is a WHOLE-DAY-ALIGNED span, so the two edges complement. The minutes sum to 60 and the hours to 23, giving at most 60 + 23 + 29 = 112 reads.
  • 118 and 46 are the caps for a RAGGED span of arbitrary length, which tops out near 193 for a month. Quoting 193 for an aligned 30-day query overstates it by 70 percent, and this is the pencil check an interviewer actually does.
  • Each bucket is ONE row: a 1,000-slot vector indexed by typeId, about 8 KB. So 112 key reads, under a megabyte moved, not 112,000 row reads, and they issue as one parallel batch.
  • Do not overclaim the bound: the minute and hour terms are capped and never grow, but the day term is linear, so a ragged year is about 528, and about 469 once you account for minute rows ageing out at 60 days. Month and year tiers flatten the slope but add 246 buckets of fixed edge overhead.
  • Then sum 1,000-entry vectors elementwise and partial-sort for the top 10. At 1,000 entries a plain sort is fine.
  • Past the backfill horizon a bucket only changes through an explicit restatement, which bumps the revision and evicts itself from a (granularity, bucketStart, revision) key. Anything younger gets a short TTL, because ordinary lateness can still restate it.
  • For contrast: as raw minutes that is 43,200 buckets and 43M counts to sum, and off the raw lake it is 300 billion events.
STEP 5 OF 5

Final design + what is expected at each level

wrap

Final Design

User tracking events: 10B a day in, exact top-k out Ingest: TrackingSDKs POST batches to the Collector, which appends them to EventStream before returning 202; ArchiveSink lands the raw events in RawEventLake. Aggregation: the Aggregator puts one revision-fenced vector per minute into MinuteCounts, RollupJob folds minutes into hours and days, and BackfillJob restates late minutes from the lake. Query: QueryService reads the covering buckets, partly from ResultCache. Privacy: PrivacyService destroys a user's key in KeyStore and records the erasure in DeletionLedger. User tracking events: 10B a day in, exact top-k out 115K events a second on average, 350K at peak, across 1,000 distinct event types. the answer the API returns is exact, never sampled. INGEST accept fast, accept durably, and never trust the client's eventType TrackingSDKs web, mobile, server Collector caches per-user data keysvalidates against the registry EventStream partitioned by hash(eventId)RF 3, acks=all evt evt evt consumers read from the mouth on the right EventTypeRegistry 1,000 approved types ArchiveSink a second consumer group RawEventLake S3 Parquet, 5 TB a day90 days, encrypted per user 1. TrackingSDKs POST batches with a client generated eventId 202 accepted, andthe eventId dedupesthe retry 2. Collector maps an unknown eventType to the __other slot 3. Collector appends to EventStream and then returns 202 tails every partition 4. ArchiveSink lands the raw events for replay, audit and backfill subscribes, one taskper partition AGGREGATION count each event once, then fold the counts, never the events BackfillJob restates a minute whenlate events land Aggregator local PreAgg per task,then GlobalCombine,then one put1 min tumbling windows MinuteCounts one row per minuteholding all 1,000 counts1,440 rows a day,and every one exact RollupJob waits out the 15 minlateness window HourCounts + DayCounts hours for 2 years, days foreverthe cheap path for wide ranges reads that minute of raw rows 7. BackfillJob replays the lake to restate a minute whose events arrived late 5. a third stage putsthe whole vector once,revision-fenced reads only settled minutes 6. RollupJob folds minutes into hours and hours into days PRIVACY erasure that never touches a single count KeyStore one wrapped data keyper user PrivacyService runs the erasure request DeletionLedger what was erased, and when the lake's rows decryptonly with these keys 11. PrivacyService destroys the user's key, so their raw rows stop decrypting records the requestand when it finished QUERY one call, 112 reads for a day-aligned30 days, mostly a cache hit Dashboard / APIClient QueryService splits the range into aligned buckets:112 for aligned 30 days, ~193 raggedsums 1,000 counts, partial-sorts for k ResultCache cached past the backfill horizon;a restatement bumps the revision,short TTL below the horizon 8. APIClient asks fortopK(start, end, k) 10. QueryService reads the day, hour and minute buckets covering the range 9. QueryService serves buckets past the backfill horizon from the cache what one event looks like on the wire, ~500 bytes: { "eventId": "a3f91c...", "eventType": "video_play", "userId": 4711, "eventTime": "2026-08-17T14:03:59Z" } the trick is the ORDERING: the Collector encrypts userId andproperties with the user's data key BEFORE the append, so thestream and the lake only ever hold ciphertext. Counts hold no userId, so erasure does not change them.Nothing in the query path can lose an event: for the last 90 days the lake is the truth and every aggregate can be rebuilt from it.Past 90 days the lake is gone, so the day tier is the truth because it is all that is left.
  • SDKs batch events with a client-generated eventId and POST them to a Collector, which validates against the registry, encrypts the personal fields, and returns 202 only after a durable append. It is stateless apart from a short-TTL cache of per-user data keys.
  • The log is partitioned by hash(eventId) with RF 3 and acks=all, so ingest cannot hot-spot and an ack means the event survives a broker loss.
  • Two independent consumers read it: an archive sink landing hourly Parquet in the raw lake, and the aggregator.
  • The aggregator is local pre-aggregate then global combine over one-minute tumbling windows, and a third stage re-keys by window so one task does a single atomic put of the whole 1,000-slot vector, fenced on a monotonic revision.
  • A rollup job folds settled minutes into hours and hours into days, and a backfill job restates buckets when late events land.
  • The query service decomposes a range into aligned buckets, 112 for a day-aligned 30-day range and about 193 for a ragged one, reads one row per bucket in parallel, sums 1,000 counts, and partial-sorts for k, serving anything past the backfill horizon from cache.
  • The privacy service holds per-user data keys and a deletion ledger, so erasure is a key destroy that never touches the aggregates.
  • The invariant that makes the whole thing defensible, stated with its expiry date: for the last 90 days the lake is the truth and every aggregate is a derived view that can be rebuilt from it, so nothing in the counting or query path can permanently lose data.
  • Past 90 days that invariant is gone, and it is worth saying before the interviewer says it. The lake ages out at 90 days while DayCounts is kept forever, so the old day tier is unrebuildable and unauditable: it is the truth because it is all that is left. If that is unacceptable, the fix is to keep a compacted per-day archive alongside it, which is small, rather than to keep 5 TB a day forever.

What is Expected at Each Level

  • Mid-level candidate:
    • Gets to a working pipeline: collector, queue, stream aggregation into per-minute counts, a query that sums buckets.
    • Names a top-k selection and can implement it.
    • Usually reaches for a sketch without first checking whether the cardinality needs one.
    • Usually stores a row per type per bucket, and does not notice the read amplification that creates.
  • Senior candidate:
    • Does the cardinality arithmetic unprompted and concludes that exact counts are affordable.
    • Goes deep on the dives:
      • Range queries: pre-aggregates into minute buckets, and builds the rollup tiers so a long range does not read every minute.
      • The hot event type: identifies it and fixes it with two-stage aggregation, at least by salting the key and summing the partials.
      • Exactly-once counts: separates at-least-once transport from idempotent counting, and says why they are two mechanisms.
      • Late events: counts by eventTime and handles late events with a watermark rather than ignoring them.
      • Event types: keeps a registry allowlist so an unknown type cannot grow the key space, even if it rejects what it does not know.
  • Staff candidate:
    • Leads with the cardinality number and uses it as the reason for at least three separate decisions: exact counts, one row per bucket, and full replication of the counts store.
    • Separates the two systems in the problem out loud, the cheap counting one and the expensive raw-storage one, and spends time proportional to that rather than to which one the question emphasised.
    • Makes query cost independent of traffic, and is precise that it still grows slowly with the calendar rather than claiming a flat ceiling, including that a day-aligned range is much cheaper than a ragged one.
    • Notices that "overwrite, do not increment" is only a mechanism once there is a single writer per bucket and a revision fence, and that the design has two writers.
    • Brings up reconciliation unprompted, because a system that claims exactness owes you the number that would go red.
    • Treats GDPR as an architecture constraint solved at ingest with crypto-shredding, not as a delete job bolted on afterwards, and can defend leaving the aggregates alone as well as name where that defence stops.
    • Identifies the cardinality attack on the event-type registry as the thing that invalidates the whole design, and defends it with a stable typeId, an overflow slot, and a per-key quota.
    • Names what the design does not do: no arbitrary group-bys, three-minute freshness with restatement after that, a straddling retry counted twice, and export needing an index that erasure does not.
DONE WHEN: you can point at the final diagram and say, in one breath, 1,000 types so exact, one row per bucket, local-global for the hot type, one fenced whole-vector put so overwrite is a mechanism and not a slogan, and erase the key not the lake.