Operating Systems: Three Easy Pieces

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 minChess gameBoard, pieces and rules: polymorphic pieces that generate moves, validating turns and check, and keeping the board model separate from the UI.Read hereClose

  The problem

  Two players take turns on an 8 by 8 board. The system validates moves, detects check, checkmate and stalemate, and records the game.

  Entities

  100%

  Figure SDA-LLD-12-1 · Chess classes · © forcsguy.com

  Inheritance is justified here: each piece type is a real kind of piece with its own movement rule.

  Pieces know their own movement

  abstract class Piece {
    constructor(readonly color: "W" | "B") {}
    abstract legalMoves(board: Board, from: Pos): Pos[];     // ignoring check
  }
  
  class Rook extends Piece {
    legalMoves(board: Board, from: Pos): Pos[] {
      return slide(board, from, [[1,0],[-1,0],[0,1],[0,-1]], this.color);   // along rank and file until blocked
    }
  }
  class Knight extends Piece {
    legalMoves(board: Board, from: Pos): Pos[] {
      return [[1,2],[2,1],[-1,2],[-2,1],[1,-2],[2,-1],[-1,-2],[-2,-1]]
        .map(([dx, dy]) => ({ x: from.x + dx, y: from.y + dy }))
        .filter((p) => board.inside(p) && board.pieceAt(p)?.color !== this.color);
    }
  }
  

  A helper slide is shared by rook, bishop and queen so the logic is not repeated.

  Validating a move

  100%

  Figure SDA-LLD-12-2 · Validating a move · © forcsguy.com

  Game status: check if the opponent's king is attacked; checkmate if in check with no legal move; stalemate if not in check but no legal move.

  Moves as objects

  class Move {
    constructor(readonly from: Pos, readonly to: Pos, readonly captured?: Piece, readonly kind: "normal" | "castle" | "enPassant" | "promotion" = "normal") {}
  }
  class History { done: Move[] = []; undone: Move[] = [];
    play(m: Move, b: Board) { b.apply(m); this.done.push(m); this.undone = []; }
    undo(b: Board) { const m = this.done.pop(); if (m) { b.revert(m); this.undone.push(m); } }
  }
  

  A move object makes undo, redo, history and notation straightforward: this is the Command pattern.

  Design notes

  • Special rules: castling (neither piece has moved, path clear and not attacked), en passant (needs the previous move), promotion (choose a piece). Each needs a little extra state: hasMoved on pieces, last move on the game.
  • Model and view stay separate; an AI or network player implements the same Player interface.
  • Clocks are a separate component observing the turn.
  • Extensions: a move-suggestion engine, saved games, variants with different boards, online play with a server validating every move (never trust the client).

  Real-world reading

  Related reading

  • Operating Systems: Three Easy PiecesRemzi and Andrea Arpaci-Dusseau · University of WisconsinBooks
  • Ambry: Distributed Immutable Object Store at LinkedInLinkedIn engineers · LinkedInCase Studies
  • Cloud Object Store at YahooYahoo engineers · YahooCase Studies
  • Netflix: What Happens When You Press Play?High Scalability engineers · High ScalabilityBlogs

  Show 6 moreShow fewer

  • 8 Things You Need to Know Before a System Design InterviewGainlo engineers · GainloBlogs
  • The Dataflow Model (paper)Akidau et al. · GooglePapers
  • Atomic Object Engineering BlogAtomic Object engineers · Atomic ObjectBlogs
  • Cloud Bouncer: Distributed Rate Limiting at YahooYahoo engineers · YahooCase Studies
  • Object StorageDatacenterknowledge engineers · DatacenterknowledgeCase Studies
  • Remind Engineering BlogRemind engineers · RemindBlogs

  Open this lesson with its quiz and exercise