Airflow at Grab

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.

• Core Concepts: How Things Actually Work · 8 minTime, clocks and ordering of eventsWhy you cannot trust timestamps across machines, and how logical clocks give a safe ordering.Read hereClose

  Why time is hard

  On one machine, order is easy: the clock only goes forward (mostly). Across machines, there is no shared clock.

  • Each machine's clock drifts, and synchronisation (NTP) is only accurate to some milliseconds, sometimes much worse.
  • Clocks can jump (corrections, leap seconds, virtual machine pauses).
  • Messages take unpredictable time, so "A happened before B" cannot be read from two clocks.

  So never use wall-clock timestamps from different machines to order important events (or to decide who wins a conflict, or to measure the timeout of a lock).

  Image: National Institute of Standards and Technology (NIST) · Public domain · Source · Wikimedia Commons: NIST-F2 cesium fountain atomic clock

  What we can know: happened-before

  Event A happened before B if A could have caused B: same process in order, or a message sent at A and received at B (and transitivity). Events with no such chain are concurrent.

  Logical clocks

  Lamport clock

  Each process keeps a counter. Increase it on each event; attach it to messages; on receiving, set it to max(local, received) + 1. Guarantee: if A happened before B, then clock(A) < clock(B). The reverse does not hold, so equal-looking order does not prove causality.

  Vector clock

  Each process keeps a vector of counters, one per process. Comparing two vectors tells you whether one event happened before the other or whether they are concurrent. Used by Dynamo-style stores to detect conflicting writes.

  100%

  Figure SDA-CORE-17-1 · Vector clock · © forcsguy.com

  Practical choices

  Need	Tool
  A total order of events	A single leader, or consensus (Raft, Paxos), or a log such as Kafka partitions
  Detect concurrent updates	Version vectors, or version numbers with conditional writes
  Merge concurrent edits	CRDTs, operational transformation, application-level merge
  Unique, roughly time-ordered ids	Snowflake-style ids (accepting small skew)
  Real-time bounds	Databases that use atomic clocks and wait out uncertainty (such as Spanner)

  Rules of thumb

  • Use monotonic clocks (not wall time) to measure durations on one machine.
  • Treat timestamps as approximate and for humans; use versions for correctness.
  • Make operations idempotent and commutative where possible, so arrival order matters less.

  More on this site

  Related reading

  • Time, Clocks, and the Ordering of Events in a Distributed System (paper)Leslie Lamport · Microsoft ResearchPapers
  • Spanner: Google's Globally Distributed Database (paper)Corbett et al. · GooglePapers
  • The Raft Consensus Algorithm (site and visualisation)Diego Ongaro and community · raft.github.ioDocumentation
  • In Search of an Understandable Consensus Algorithm (Raft paper)Ongaro and Ousterhout · Stanford UniversityPapers

  Show 6 moreShow fewer

  • How Ringpop from Uber Engineering Helps Distribute Your ApplicationUber Engineering · UberCase Studies
  • Google SRE Book: Managing Critical State (Distributed Consensus)Google SRE team · GoogleBlogs
  • The Chubby Lock Service (paper)Mike Burrows · GooglePapers
  • Clock Skew when Syncing Password Payloads at DrobboxDrobbox engineers · DrobboxCase Studies
  • Airflow at GrabGrab engineers · GrabCase Studies
  • OpenTable BlogOpenTable engineers · OpenTableBlogs

  Open this lesson with its quiz and exercise