Bullet: Forward-Looking Query Engine for Streaming Data at Yahoo

Ideas you will meet

Event Driven Architecture

Loosely coupled services reacting to events.

Distributed Systems

Consensus, time, failure and the fundamentals of scale-out.

What we already know about this

Our own lessons on these ideas. Read them here before you start, so it makes sense.

• Real-World Systems · 13 minDesign a stock exchangeAn order book, a matching engine and a sequencer: how an exchange matches buyers and sellers fairly in microseconds.Read hereClose

  The problem

  An exchange lets buyers and sellers trade. Participants submit orders; the exchange matches them and reports the trades.

  Key properties:

  • Fairness: orders are handled in a strict, auditable order.
  • Very low latency: microseconds from order to acknowledgment.
  • High throughput: hundreds of thousands to millions of orders per second at peaks.
  • Correctness and durability: money is involved. No lost or duplicated trades.
  • Availability: an exchange outage halts a market.

  The order book

  For each symbol the order book holds resting orders:

  • Bids (buy orders), highest price first.
  • Asks (sell orders), lowest price first.
  • Within a price level, orders queue by arrival time.

  Common order types: limit (a worst price you accept; unmatched part rests in the book) and market (take the best available now).

  Matching: price-time priority

  An incoming buy matches the lowest-priced asks it can afford; among equal prices the earliest order matches first. Matching repeats until the order is filled or no longer matches, and any remainder rests in the book.

  Image: Thomas J. O'Halloran · Public domain · Source · Wikimedia Commons: NY stock exchange traders floor LC-U9-10548-6

  Architecture

  100%

  Figure SDA-RWS-05-1 · Exchange: gateway, sequencer, matching engine · © forcsguy.com

  1. Gateways authenticate participants, validate orders, and run pre-trade risk checks (limits, available funds).
  2. The sequencer gives every event a sequence number: one agreed total order, the basis of fairness and recovery.
  3. A matching engine applies events in order to the in-memory order book and emits trades.
  4. Everything is written to a durable event log. Executions go to participants, and a market data stream tells everyone about prices and depth.
  5. Clearing and settlement later move money and securities between accounts.

  100%

  Figure SDA-RWS-05-2 · An order book with a buy order sweeping the sell side · © forcsguy.com

  How it gets so fast

  • In-memory order books and no database in the critical path.
  • Single-threaded matching per symbol group: no locks, deterministic behaviour. Parallelism comes from partitioning symbols across engines.
  • Event sourcing: state is the result of applying an ordered log. Persist the event first (to a memory-mapped file or replicated log), then process.
  • Pre-allocated memory, ring buffers, no garbage-collection pauses, and careful cache-friendly data structures.
  • Hardware and network: servers co-located in the exchange's data centre, fast network cards and kernel-bypass networking, precise time sources.

  100%

  Figure SDA-RWS-05-3 · A fast engine on one machine: shared log and busy loops · © forcsguy.com

  Reliability

  • A hot standby applies the same event log and can take over within moments. Use sequence numbers to detect gaps and avoid duplicate processing.
  • Replicate the log across machines or sites before acknowledging, trading a little latency for durability.
  • Idempotent order identifiers prevent a resubmitted order executing twice.
  • Circuit breakers halt trading when prices move too fast.

  Market data fairness

  Everyone should see the same information at about the same time. Exchanges publish through multicast feeds, give all participants equal-length cables inside the data centre, and timestamp events at the matching engine. A separate, slower snapshot and retransmission service helps receivers that miss packets.

  What is out of scope here

  Clearing houses, settlement cycles, regulation and surveillance are large systems of their own. The core design is the sequencer plus deterministic matching engine plus durable log.

  Real-world reading

  Related reading

  • Event SourcingMartin FowlerBlogs
  • Monolith FirstMartin FowlerBlogs
  • Rewriting the heart of our sync engineDropboxCase Studies
  • Cape: Event Stream Processing Framework at DropboxDropbox engineers · DropboxCase Studies

  Show 6 moreShow fewer

  • Improving Search Engine Efficiency by over 25% at eBayeBay engineers · eBayCase Studies
  • Finding Kafka throughput limit in infrastructure at DropboxDropbox engineers · DropboxCase Studies
  • Bullet: Forward-Looking Query Engine for Streaming Data at YahooYahoo engineers · YahooCase Studies
  • MicroservicesJames Lewis and Martin Fowler · Martin FowlerBlogs
  • The LMAX ArchitectureMartin FowlerCase Studies
  • Microservices and OrchestrationMartinfowler engineers · MartinfowlerCase Studies

  Open this lesson with its quiz and exercise

• Big Data and Cloud Data Platforms · 12 minBatch and stream processingMapReduce and Spark for large batch jobs, and streaming concepts: event time, windows, watermarks and exactly-once results.Read hereClose

  Two ways to process data

  • Batch: process a bounded dataset (yesterday's logs) as a job that starts, runs and finishes. High throughput, results later.
  • Stream: process an unbounded flow of events continuously as they arrive. Low latency, harder to get right.

  Most platforms need both: stream for fresh insight, batch for heavy recomputation and history.

  Before: batch: a big job on a schedule

  100%

  After: stream: process each event

  100%

  What changed

  • Results arrive in seconds instead of hours
  • Late and duplicate events must be handled
  • Batch stays useful for reprocessing history

  Batch: the MapReduce idea

  Word count is the classic example.

  100%

  Figure SDA-BDP-02-1 · MapReduce word count flow · © forcsguy.com

  1. Map: each worker reads a slice and emits key-value pairs (("system", 1)).
  2. Shuffle: the framework groups all pairs with the same key and sends them to the same reducer. This is the expensive step (network and sorting).
  3. Reduce: each reducer combines the values for its keys (("system", 4812)).

  Failures are handled by re-running tasks, which is possible because inputs are immutable and tasks have no side effects.

  Spark improved this model: it keeps intermediate data in memory, expresses jobs as chains of transformations on DataFrames (with a query optimiser), and offers SQL, machine learning and streaming APIs on one engine. Today you usually write Spark or SQL, not raw MapReduce.

  Image: Unknown authorUnknown author · Public domain · Source · Wikimedia Commons: Ford assembly line - 1913

  Stream processing

  A stream processor reads events from a log (such as Kafka), transforms them, and writes results to another log, a database or a dashboard.

  Common operations: filter and enrich, aggregate, join streams, and detect patterns.

  Time is the hard part

  • Processing time: when the system sees the event.
  • Event time: when it actually happened.

  Phones go offline, networks lag, and events arrive late and out of order. Computing "clicks per minute" by arrival time gives wrong answers. Use event time.

  Windows

  Aggregations need boundaries:

  Window	Meaning
  Tumbling	Fixed, non-overlapping (every minute)
  Sliding	Overlapping (last 5 minutes, updated each minute)
  Session	Grouped by activity, closed by a gap of inactivity

  Watermarks and late data

  A watermark is the system's estimate of "we have seen everything up to event time T". When it passes the end of a window, the window can close and emit a result. Choosing the delay trades latency against completeness. Events arriving after the watermark are late: drop them, send them to a side output, or update the earlier result.

  State and failures

  Windows and joins need state. Engines such as Flink keep state locally and checkpoint it periodically to durable storage, together with the position in the input log. After a failure they restore the checkpoint and replay from that position.

  Delivery guarantees

  • At-most-once: may lose events.
  • At-least-once: may duplicate on replay.
  • Exactly-once effect: achieved by replayable sources, checkpointed state and idempotent or transactional sinks, so a replay does not change results.

  Architectures that combine both

  • Lambda architecture: a batch layer computes accurate views from all data, a speed layer gives fast approximations; the two are merged. Powerful but means writing logic twice.
  • Kappa architecture: treat everything as a stream. Keep the log long enough to replay history through the same code when logic changes. Simpler, if your log and engine can handle it.
  • Modern engines and the dataflow model increasingly unify batch and streaming under one API.

  100%

  Figure SDA-BDP-02-2 · Lambda and Kappa architectures · © forcsguy.com

  Choosing

  Need	Choice
  Nightly reports, big joins, model training on history	Batch (Spark, SQL warehouse)
  Fraud detection, live dashboards, alerting, real-time features	Streaming (Flink, Kafka Streams, Spark Structured Streaming)
  Both with minimal duplication	Streaming core with replayable log, or a unified engine

  Real-world reading

  Related reading

  • MapReduce: Simplified Data Processing on Large Clusters (paper)Dean and Ghemawat · GooglePapers
  • Cape: Event Stream Processing Framework at DropboxDropbox engineers · DropboxCase Studies
  • Pagelets Parallelize Server-side Processing at YelpYelp engineers · YelpCase Studies
  • Optimizing CAL Report Hadoop MapReduce Jobs at eBayeBay engineers · eBayCase Studies

  Show 6 moreShow fewer

  • Bullet: Forward-Looking Query Engine for Streaming Data at YahooYahoo engineers · YahooCase Studies
  • Samza: Stream Processing System for Latency Insighs at LinkedInLinkedIn engineers · LinkedInCase Studies
  • Netflix: What Happens When You Press Play?High Scalability engineers · High ScalabilityBlogs
  • CMU Database GroupCarnegie Mellon UniversityYouTube
  • Omid: Transaction Processing Platform at YahooYahoo engineers · YahooCase Studies
  • Big Data Processing at UberUberPapers

  Open this lesson with its quiz and exercise

• Big Data and Cloud Data Platforms · 11 minData lakes, warehouses and lakehousesWhere analytical data lives and why: OLTP versus OLAP, columnar files, ETL versus ELT, and open table formats.Read hereClose

  Two kinds of workload

  	OLTP (transactions)	OLAP (analytics)
  Purpose	Run the application	Understand the business
  Queries	Many small reads and writes of single rows	Few large scans and aggregations over many rows
  Storage layout	Row oriented	Column oriented
  Examples	PostgreSQL, MySQL for an order system	A warehouse for revenue by region and month

  Running heavy analytics on the production database slows the application, so analytical data is copied into systems built for it.

  Columnar storage and file formats

  Analytical queries typically read a few columns across millions of rows. Storing data by column means:

  • A query reads only the columns it needs.
  • Values in one column are similar, so they compress extremely well.
  • Engines can skip chunks using min/max statistics.

  Parquet and ORC are the standard open columnar file formats. Compared with CSV or JSON they are much smaller and faster to query.

  Three architectures

  100%

  Figure SDA-BDP-03-1 · Three architectures · © forcsguy.com

  Data warehouse

  A curated, structured store optimised for SQL analytics, with a defined schema (often a star schema: a central fact table of events such as sales, surrounded by dimension tables such as customer, product and date). Reliable and fast, but historically costly and rigid with raw or unstructured data.

  Data lake

  Raw files of any format kept cheaply in object storage, with schema applied when read. Flexible and cheap, and good for machine learning and unstructured data. Risks: no transactions, inconsistent data and "data swamps" nobody trusts.

  Lakehouse

  The two combined: files in open formats on object storage, with a table format adding the warehouse features.

  • Delta Lake, Apache Iceberg, Apache Hudi: a transaction log or metadata layer that provides ACID transactions, schema evolution, time travel (query data as it was), and efficient updates and deletes.
  • One copy of data serves BI, SQL, streaming and machine learning, using different engines (Spark, Trino, warehouses) on the same tables.

  Moving data: ETL and ELT

  • ETL: extract, transform, then load. Transformation happens before the data reaches the warehouse.
  • ELT: extract, load raw, then transform inside the warehouse or lake engine. Common today, since storage is cheap, compute is elastic, and you keep the raw data to reprocess.
  • Change data capture (CDC) streams database changes into the lake continuously, instead of nightly dumps.

  Organising data: layers

  A common pattern, sometimes called medallion layers:

  1. Raw (bronze): exactly as received.
  2. Cleaned (silver): deduplicated, typed, validated.
  3. Business-ready (gold): modelled tables and aggregates for reports.

  Good practice

  • Partition large tables (by date, for example) so queries scan less.
  • Keep files a sensible size (hundreds of MB); many tiny files slow everything.
  • Enforce data quality checks and schemas at ingestion.
  • Provide a catalogue (what data exists, who owns it, lineage) and access controls (row, column and table level).
  • Track cost: scanning unpartitioned petabytes is expensive.
  • Separate storage from compute so different teams scale their engines independently.

  Real-world reading

  Related reading

  • Cassandra: A Decentralized Structured Storage System (paper)Lakshman and Malik · FacebookPapers
  • The Architecture of Open Source ApplicationsVarious authors · aosabook.orgBooks
  • HaloDB: Embedded Key-Value Storage Engine at YahooYahoo engineers · YahooCase Studies
  • Bullet: Forward-Looking Query Engine for Streaming Data at YahooYahoo engineers · YahooCase Studies

  Show 6 moreShow fewer

  • Improving Stream Data Quality With Protobuf Schema Validation at DeliverooDeliveroo engineers · DeliverooCase Studies
  • Continuous Load Testing at SlackSlack engineers · SlackCase Studies
  • Druid - Real-time Analytics DatabaseApache engineers · ApacheDocumentation
  • MPH: Fast and Compact Immutable Key-Value Stores at IndeedIndeed engineers · IndeedCase Studies
  • Venice: Distributed Key-Value Database at LinkedinLinkedin engineers · LinkedinCase Studies
  • Data Wrangling at SlackSlack engineers · SlackCase Studies

  Open this lesson with its quiz and exercise