Transit and Peering: How Your Requests Reach GitHub

Ideas you will meet

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.

• Low-Level Design Practice · 11 minElevator systemRequests, directions and scheduling: a state machine per car and a dispatcher that decides which car answers which call.Read hereClose

  The problem

  A building has several elevators. People press a button on a floor (a hall call with direction) and a floor button inside the car (a car request). The system moves cars, opens doors and decides which car should answer each call.

  Entities

  100%

  Figure SDA-LLD-07-1 · Elevator classes · © forcsguy.com

  One elevator as a state machine

  100%

  Figure SDA-LLD-07-2 · Elevator car states · © forcsguy.com

  A simple and effective scheduling rule is the elevator (scan) algorithm: keep two sorted sets of stops (above and below); continue in the current direction, serving stops in order; reverse only when none are left in that direction.

  class Elevator {
    floor = 0; dir: "UP" | "DOWN" | "IDLE" = "IDLE";
    up = new SortedSet<number>(); down = new SortedSet<number>();   // pending stops
  
    addStop(f: number) { (f >= this.floor ? this.up : this.down).add(f); if (this.dir === "IDLE") this.pick(); }
    private pick() { this.dir = this.up.size ? "UP" : this.down.size ? "DOWN" : "IDLE"; }
    step() {                                   // called once per tick
      if (this.dir === "UP") { this.floor++; if (this.up.deleteIfPresent(this.floor)) this.openDoors(); if (!this.up.size) this.pick(); }
      if (this.dir === "DOWN") { this.floor--; if (this.down.deleteIfPresent(this.floor)) this.openDoors(); if (!this.down.size) this.pick(); }
    }
  }
  

  Many cars: the dispatcher

  100%

  Figure SDA-LLD-07-3 · Assigning a hall call · © forcsguy.com

  Make the dispatcher a strategy so you can swap "nearest car" for "least loaded" or a smarter estimate without touching Elevator.

  Design notes

  • Concurrency: calls arrive while cars move. Use one event loop per elevator, or a queue per car, so state changes happen one at a time.
  • Safety: doors must not close on a blocked sensor; weight limits stop a car from moving.
  • Peak modes: morning (send idle cars to the lobby) and evening patterns are policies.
  • Extensions: express cars, destination dispatch (people enter their destination at the hall), emergency and maintenance modes.

  Real-world reading

  Related reading

  • Apple Machine Learning BlogApple engineers · AppleBlogs
  • AWS Machine Learning BlogAmazon Web Services engineers · Amazon Web ServicesBlogs
  • Machine Learning for Ranking Answers End-to-End at QuoraQuora engineers · QuoraCase Studies
  • Machine Learning (2 parts) at Condé NastCondé Nast engineers · Condé NastCase Studies

  Show 6 moreShow fewer

  • Google SRE Book: Distributed Periodic Scheduling with CronGoogle SRE team · GoogleBlogs
  • Please stop calling databases CP or APMartin Kleppmann · martin.kleppmann.comBlogs
  • Large-Scale Machine Learning Pipeline for Job Recommendations at IndeedIndeed engineers · IndeedCase Studies
  • Machine Learning Platform at YelpYelp engineers · YelpCase Studies
  • Engineering at QuoraQuora engineers · QuoraCase Studies
  • Distributed SchedulingUmbcPapers

  Open this lesson with its quiz and exercise