Problem RestatementProblem
Uber asked: design a system where users create price alerts on securities: "Notify me when AAPL goes above $200", "when TSLA falls below $150", or "when a stock moves 5% today". The system receives a real-time price feed and must notify users when the price crosses their threshold, quickly and without spamming.
RequirementsRequirements
- Create, list and delete alerts (symbol, direction above/below, threshold, one-time or recurring).
- Evaluate against a live price feed (thousands of symbols, many updates per second).
- Notify via push, email or SMS within seconds.
- Don't send duplicates. One-time alerts fire once, and recurring alerts re-arm after the price moves back.
1.1 Scale
- 10M users, 50M active alerts. Price updates: ~10K symbols × several per second.
ArchitectureArchitecture
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
U["Users"] --> API["Alert API"]
API --> DB[("Alerts DB")]
DB -->|"load + changes"| M["Matchers - partitioned by symbol"]
FEED["Market data feed"] --> K[("Kafka - ticks by symbol")]
K --> M
M --> T[("Triggered alerts")]
T --> N["Notification service - dedupe, rate limit"]
N --> UDeep Dive — Matching 50 million alerts against every tickDeep dive
Prices tick thousands of times a second across thousands of symbols, and users have tens of millions of standing alerts. The matching structure is the entire system.
Check every alert on every tick
For each price update, scan the alerts and test each condition.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
T["Tick: AAPL 189.40"] --> SCAN["Test all 50,000,000 alerts"]
SCAN --> IRR["49,900,000 are for other symbols"]
SCAN --> RATE["x thousands of ticks per second"]
RATE --> IMP["Trillions of comparisons per second"]Almost every comparison is against an alert for a different symbol, and the work is repeated for every tick. The arithmetic rules this out before any optimisation is discussed.
Index alerts by symbol
Keep symbol → alerts so a tick only examines that symbol's alerts.
The first and largest reduction — from 50 million to perhaps 100,000 for a popular symbol. It is still a full scan of those alerts on every tick, and a heavily traded symbol ticks many times a second, so the busiest symbols remain the most expensive.
Keep each symbol's alerts sorted by threshold
Thresholds are numbers, and a price move crosses a contiguous range of them:
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
AB["Above-alerts - sorted by threshold ascending"] --> UP["Price moves p0 -> p, up"]
UP --> BS["Binary search for the range p0 < threshold <= p"]
BS --> FIRE["Exactly the alerts that just crossed"]
BE["Below-alerts - sorted descending"] --> DOWN["Price moves down"]
DOWN --> BS2["Binary search for p > threshold >= p"]
BS2 --> FIRE
FIRE --> COST["O(log n + k) - k is the number actually triggered"]- The cost becomes proportional to what fires, not to how many alerts exist. A tick that crosses nothing costs one binary search, which is what makes millions of dormant alerts free.
- Two structures, because direction matters. Above-alerts ascending and below-alerts descending, so each move type maps to a contiguous range from one end.
- Compare against the previous price, not just the current one. Using
p0 < threshold ≤ pfires an alert exactly once on the crossing, instead of repeatedly while the price sits above it.
Partition symbols across matcher nodes, each holding its symbols' structures in memory and consuming that symbol's tick stream — so no lock is needed and capacity grows by adding nodes. The subscription path then has to keep those in-memory structures current as users add and remove alerts, which is the reason the next section exists.
Keeping Matchers in Sync
- On startup, a matcher loads the alerts for its symbols from the DB.
- New, updated or deleted alerts are published as events (CDC), and the matcher updates its in-memory structures.
- If a matcher crashes, another one takes over its partitions and reloads them from the DB.
Notifications
- Triggered alerts go to a queue. The notification service sends push, email or SMS, with an idempotency key
(alert_id, trigger_time)so retries don't double-send. - Rate limits per user (e.g., at most 20 alerts per hour), and batching in volatile markets ("5 of your alerts triggered").
- Percent-change alerts: compare against the previous close (stored per symbol), and index them by their equivalent price threshold for today.
Wrap-UpWrap-up
Store alerts in a DB, and load them into in-memory per-symbol sorted threshold lists on matcher nodes partitioned by symbol, kept current via change events. On each price tick, binary-search the range of thresholds crossed between the previous and new price (O(log n + k)), remove one-time alerts and re-arm recurring ones with hysteresis, and send notifications through an idempotent, rate-limited, batching notification service.