Scaling Gradient Boosted Trees for Click-Through-Rate Prediction at Yelp

Ideas you will meet

Distributed Systems

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

Machine Learning Systems

Recommendations, ranking, feature stores and serving models at scale.

What we already know about this

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

• Core Concepts: How Things Actually Work · 6 minLatency, throughput and bandwidthThree numbers that are often confused, and why a fast network can still feel slow.Read hereClose

  Three different questions

  • Latency: how long does one request take from start to finish? Measured in milliseconds.
  • Bandwidth: how much could the pipe carry per second? A capacity, measured in bits per second.
  • Throughput: how much actually flows per second, measured in requests or bytes per second. It is at most the bandwidth, and often much less.

  A motorway analogy: bandwidth is the number of lanes, latency is the time one car needs to drive the length, and throughput is how many cars arrive per hour. Widening the road (more lanes) lets more cars through but does not make any single car arrive sooner.

  Why it matters in design

  Many speed problems are really latency problems, and more bandwidth will not fix them:

  Symptom	Likely cause	Lever
  Page makes 80 small requests and feels slow	Round-trip latency adds up	Fewer requests, bundling, HTTP/2, caching
  Users far away complain	Distance	CDN, regional servers
  Big downloads are slow	Throughput or bandwidth	Compression, parallel transfers, bigger pipe
  System is slow only at busy times	Throughput limit	Scale out, queue, shed load

  Image: Syced · CC0 · Source · Wikimedia Commons: Peabird Ethernet switch in 2003

  Where the time goes

  100%

  Figure SDA-CORE-01-1 · A latency budget for one page · © forcsguy.com

  Tail latency

  Averages hide the worst experiences. If 1% of requests take 3 seconds, a page that makes 50 calls will hit one of those slow calls most of the time. Track percentiles (p95, p99), and design to keep the slowest requests under control with timeouts and hedged requests.

  Latency budget

  Break a target (say 300 ms for a page) into a budget: network 80 ms, application 60 ms, database 50 ms, rendering 80 ms, slack 30 ms. When the total exceeds the target you know where to cut.

  Real-world reading

  Related reading

  • Optimizing Web Servers for High Throughput and Low Latency at DropboxDropbox engineers · DropboxCase Studies
  • Natural Language Processing and Content Analysis (2 parts) at Condé NastCondé Nast engineers · Condé NastCase Studies
  • Finding Kafka throughput limit in infrastructure at DropboxDropbox engineers · DropboxCase Studies
  • Scaling Gradient Boosted Trees for Click-Through-Rate Prediction at YelpYelp engineers · YelpCase Studies

  Show 6 moreShow fewer

  • Machine Learning (2 parts) at Condé NastCondé Nast engineers · Condé NastCase Studies
  • DataSift Architecture: Realtime Datamining at 120,000 Tweets Per Second - High Scalability -High Scalability engineers · High ScalabilityCase Studies
  • Deploying Brotli for Static Content at DropboxDropbox engineers · DropboxCase Studies
  • How Twitter Handles 3,000 Images Per Second - High Scalability -High Scalability engineers · High ScalabilityCase Studies
  • ESPN's Architecture at Scale - Operating at 100,000 Duh Nuh Nuhs Per Second - High Scalability -High Scalability engineers · High ScalabilityCase Studies
  • Architecture NotesArchitecture Notes · architecturenotes.coPodcasts & Newsletters

  Open this lesson with its quiz and exercise

• Software Design Essentials · 9 minHow to learn design patternsWhat patterns are, the three families, a map of the classic catalogue, and a practical way to learn them without over-engineering.Read hereClose

  What a pattern is

  A design pattern is a named solution to a recurring design problem, together with when it applies and what it costs. The famous catalogue, Design Patterns (1994) by Gamma, Helm, Johnson and Vlissides ("the Gang of Four"), described 23 patterns in object-oriented software.

  Patterns give you three things:

  1. A shared vocabulary: "use a factory here" communicates a whole idea in a few words.
  2. Proven structures you do not have to invent under pressure.
  3. Awareness of trade-offs, since each pattern comes with consequences.

  They are not copy-paste code, and not a goal in themselves.

  The three families

  100%

  Figure SDA-SDE-01-1 · The three families · © forcsguy.com

  The catalogue at a glance

  Pattern	One-line idea	Typical use
  Factory Method	A method decides which concrete class to create	Create objects without hard-coding the class
  Abstract Factory	Create families of related objects	Themes, platform-specific widget sets
  Builder	Build a complex object step by step	Objects with many optional parts
  Prototype	Create objects by copying an existing one	Costly-to-create objects
  Singleton	Exactly one instance, globally reachable	Rare; often better as dependency injection
  Adapter	Make one interface look like another	Wrap a third-party library
  Bridge	Separate an abstraction from its implementation	Several dimensions of variation
  Composite	Treat a tree of objects like a single object	File systems, UI trees
  Decorator	Add behaviour by wrapping an object	Logging, caching, compression layers
  Facade	A simple front for a complex subsystem	A clean API over messy internals
  Flyweight	Share common state to save memory	Many similar small objects
  Proxy	A stand-in that controls access	Lazy loading, access control, remote calls
  Strategy	Swap algorithms behind an interface	Pricing rules, sorting choices
  Observer	Notify dependants when something changes	Events, UI updates
  Command	Turn a request into an object	Undo, queues, macros
  State	Behaviour changes with internal state	Workflows, connections
  Template Method	A skeleton algorithm with customisable steps	Frameworks, hooks
  Iterator	Walk a collection without exposing its structure	Loops over any collection
  Chain of Responsibility	Pass a request along handlers until one handles it	Middleware, validation chains
  Mediator	One object coordinates others	Chat rooms, form logic
  Memento	Save and restore an object's state	Undo, snapshots
  Visitor	Add operations to a structure without changing it	Compilers, reports over trees
  Interpreter	Evaluate sentences of a small language	Rules, expressions

  The next lessons explain the most useful ones with examples.

  A practical way to learn

  1. Learn the problems first. Each pattern exists because of a pain: rigid code, duplicated code, tangled dependencies. Understand the pain, then the cure.
  2. Start with the ones you already use without naming them: Iterator (every for...of), Observer (event listeners), Decorator and Chain of Responsibility (middleware), Strategy (a function you pass in).
  3. Implement each once, small, in your language, and write what you gave up.
  4. Spot them in real code: frameworks and standard libraries are full of patterns.
  5. Refactor towards a pattern when the code hurts, rather than starting with one.

  Patterns look different in different languages

  In languages with first-class functions, several patterns shrink to a function: Strategy is a function argument, Command is a closure, Observer is a callback list, and Template Method is passing the varying step. In dynamic languages, Factory and Adapter are often trivial. Learn the intent, then use the lightest form your language allows.

  Anti-patterns to avoid

  • Pattern overload: five layers of abstraction for a feature that needs ten lines.
  • Singleton as global state: hides dependencies and makes testing hard.
  • Naming something by the pattern, not by what it does (ManagerFactoryProvider).
  • Applying a pattern "in case": wait until the second or third time you need the flexibility.

  Real-world reading

  Related reading

  • Google SRE Book: Managing Critical State (Distributed Consensus)Google SRE team · GoogleBlogs
  • Paxos Made Simple (paper)Leslie Lamport · Microsoft ResearchPapers
  • Design Patterns CatalogueRefactoring GuruDocumentation
  • The Byzantine Generals Problem (paper)Lamport, Shostak and Pease · Microsoft ResearchPapers

  Show 6 moreShow fewer

  • etcd Raft libraryetcd · CNCF / etcdGitHub
  • Domain-Driven Design ReferenceEric Evans · Domain LanguageBooks
  • Scaling Gradient Boosted Trees for Click-Through-Rate Prediction at YelpYelp engineers · YelpCase Studies
  • Natural Language Processing and Content Analysis (2 parts) at Condé NastCondé Nast engineers · Condé NastCase Studies
  • Building and Deploying MySQL Raft at MetaMeta engineers · MetaCase Studies
  • Lessons of Scale at Facebook - Bobby Johnson, Director of Engineering at FacebookFacebookYouTube

  Open this lesson with its quiz and exercise

• Low-Level Design Practice · 11 minParking lotVehicles, spots, tickets and fees: a classic exercise in allocation, pricing rules and concurrent entry gates.Read hereClose

  The problem

  Design a parking lot with several levels. It accepts motorcycles, cars and buses; assigns the nearest suitable free spot on entry; tracks occupancy; and charges a fee on exit by duration and vehicle type. Several entry and exit gates work at once.

  Entities

  Class	Responsibility
  ParkingLot	Owns the levels and gates; entry point for park and unpark
  Level	A floor holding spots; answers "which free spot fits this vehicle"
  ParkingSpot	Has a type and occupied state; can be reserved and freed
  Vehicle	Base type with subclasses or a type field (motorcycle, car, bus)
  Ticket	Created on entry: vehicle, spot, entry time
  PricingStrategy	Turns a stay (duration, vehicle type) into a fee

  100%

  Figure SDA-LLD-02-1 · Parking lot class structure · © forcsguy.com

  The entry and exit flow

  100%

  Figure SDA-LLD-02-2 · Entry and exit sequence · © forcsguy.com

  Key code

  type SpotType = "MOTORCYCLE" | "COMPACT" | "LARGE";
  const fits: Record<string, SpotType[]> = {
    MOTORCYCLE: ["MOTORCYCLE", "COMPACT", "LARGE"],
    CAR: ["COMPACT", "LARGE"],
    BUS: ["LARGE"],
  };
  
  class ParkingSpot {
    occupied = false;
    constructor(readonly id: string, readonly type: SpotType) {}
    tryReserve(): boolean {        // atomic in a real system (lock or compare-and-set)
      if (this.occupied) return false;
      this.occupied = true; return true;
    }
    free() { this.occupied = false; }
  }
  
  class Level {
    constructor(readonly spots: ParkingSpot[]) {}
    findAndReserve(vehicleType: string): ParkingSpot | null {
      for (const s of this.spots)
        if (fits[vehicleType].includes(s.type) && s.tryReserve()) return s;
      return null;
    }
  }
  

  The important details are tryReserve (one winner per spot) and the fits table (compatibility in one place).

  Pricing as a strategy

  interface PricingStrategy { fee(vehicleType: string, minutes: number): number }
  const hourly: PricingStrategy = {
    fee: (t, m) => Math.ceil(m / 60) * ({ MOTORCYCLE: 1, CAR: 2, BUS: 5 } as any)[t],
  };
  

  Swap in a daily cap, a weekend rate or a subscriber discount without touching ParkingLot.

  Before: pricing hard-coded in the ticket

  100%

  After: pricing as a strategy

  100%

  What changed

  • A new fee rule is a new class, not an edit to old code
  • Each pricing rule can be tested alone
  • The ticket no longer knows how fees are calculated

  Edge cases and extensions

  • Lot full: park returns "no spot" cleanly rather than throwing.
  • Lost ticket: look the vehicle up by plate; charge the maximum rate.
  • Nearest spot: keep free spots in a sorted structure per level (a heap or a set per type) so allocation is not a linear scan at scale.
  • Display boards that show free counts are observers of spot changes.
  • Persistence: if the app restarts, rebuild occupancy from stored tickets.

  Real-world reading

  Related reading

  • Scaling Infrastructure at Twitter - Yao Yue, Staff Software Engineer at TwitterTwitterYouTube
  • Scaling Slack - Bing Wei, Software Engineer (Infrastructure) at SlackSlack engineers · SlackCase Studies
  • Scaling Gradient Boosted Trees for Click-Through-Rate Prediction at YelpYelp engineers · YelpCase Studies
  • Building Real Time Infrastructure at Facebook - Jeff Barber and Shie Erlich, Software Engineer at FacebookFacebook engineers · FacebookCase Studies

  Show 6 moreShow fewer

  • Software Engineering DailySoftware Engineering DailyPodcasts & Newsletters
  • Scaling Pinterest - Marty Weiner, Pinterest’s founding engineerYouTubeYouTube
  • Design Patterns CatalogueRefactoring GuruDocumentation
  • PricingNet: Pricing Modelling with Neural Networks at SkyscannerSkyscanner engineers · SkyscannerCase Studies
  • Software Engineering Advice from Building Large-Scale Distributed Systems - Jeff DeanGooglePapers
  • Software Engineering RadioIEEE Computer Society · SE RadioPodcasts & Newsletters

  Open this lesson with its quiz and exercise