Clock Skew when Syncing Password Payloads at Drobbox

Ideas you will meet

Distributed Systems

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

Web Security

OWASP risks, XSS, CSRF, CORS and secure design.

Time and Ordering

Logical clocks, vector clocks and bounded clock error.

What we already know about this

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

• Classic System Designs · 10 minDesign consistent hashingHow to spread keys over servers so that adding or removing a server moves only a small share of them.Read hereClose

  The problem

  You have a cluster of cache or storage servers and need a rule that says which server holds which key. The first idea is server = hash(key) mod N. It works until N changes, which it always does: a server fails, or you add capacity.

  100%

  Figure SDA-CSD-02-1 · Why mod-N hashing breaks when N changes · © forcsguy.com

  When N changes, almost every key maps somewhere new. A cache suddenly misses on nearly everything and the database behind it is flooded. A storage cluster would have to shuffle most of its data.

  Goal: when a server joins or leaves, only about 1/N of the keys should move.

  The idea: a hash ring

  1. Imagine hash values arranged in a circle (the ring), from 0 up to a maximum and wrapping around.
  2. Hash each server onto the ring.
  3. Hash each key onto the same ring.
  4. A key belongs to the first server clockwise from its position.

  100%

  Figure SDA-CSD-02-2 · Hash ring ownership · © forcsguy.com

  Adding a server D between A and B takes over only the keys that fall between A and D. Everything else stays where it is. Removing a server hands its keys to its clockwise neighbour. Either way, only the neighbouring arc moves.

  Before: hash mod N

  100%

  After: consistent hashing ring

  100%

  What changed

  • Adding a server moves only a small slice of keys
  • Cache hit rate does not collapse after a change
  • Virtual nodes even out the load

  Finding the owner efficiently

  Keep the server positions in a sorted list. To place a key, hash it and use a binary search for the first position greater than or equal to it, wrapping to the first server if you pass the end. That is O(log N) per lookup.

  Two problems with the basic ring

  100%

  Figure SDA-CSD-02-3 · Why a plain ring can be unfair · © forcsguy.com

  Fixing uneven load: virtual nodes

  With only a handful of servers, the arcs between them are uneven, so some servers hold far more keys. And when a server dies, all its load lands on a single neighbour.

  The fix is virtual nodes: each physical server is hashed at many points (say 100 to 200) on the ring.

  100%

  Figure SDA-CSD-02-4 · Virtual nodes per server · © forcsguy.com

  • Keys spread much more evenly.
  • When a server leaves, its load is shared among many others.
  • A bigger server can be given more virtual nodes than a smaller one.

  The cost is a larger ring to store and update.

  Which keys move, exactly

  When a server joins, find the previous server going anticlockwise from it; only the keys between that neighbour and the new server move, and they all move to the new server. When a server leaves, the keys it held (the span back to its anticlockwise neighbour) move to the next server clockwise. Nothing else is touched, which is why the data transfer stays small and predictable.

  Spreading keys evenly also reduces hotspots: without it, several very popular keys can land on the same server and overload it. With many virtual nodes per server, the spread gets tighter (published experiments show the imbalance shrinking from around 10 percent to about 5 percent as virtual nodes per server go from roughly 100 to 200), at the price of more ring metadata to store, so the count is a tuning knob.

  100%

  Figure SDA-CSD-02-5 · Adding a server to the ring · © forcsguy.com

  100%

  Figure SDA-CSD-02-6 · Removing a server from the ring · © forcsguy.com

  Where it is used

  • Distributed caches (so adding a node does not wipe the cache).
  • Partitioned databases such as Dynamo-style stores, where each key is also copied to the next few servers clockwise for replication (next lesson).
  • Load balancing with stickiness, where the same client keeps hitting the same backend.
  • Content delivery to decide which edge server holds an object.

  Things to watch

  • Hot keys: one very popular key still loads its owner. Replicate it or add a local cache.
  • Choose a good hash function: uniform distribution matters more than cryptographic strength.
  • Membership changes must be learned by all clients consistently, through a config service or gossip, otherwise two clients disagree about the owner.

  More on this site

  Related reading

  • Consistent Hashing and Random Trees (paper)Karger et al. · MITPapers
  • NGINX HTTP Load BalancingNGINX · F5 / NGINXDocumentation
  • Time, Clocks, and the Ordering of Events in a Distributed System (paper)Leslie Lamport · Microsoft ResearchPapers
  • Clock Skew when Syncing Password Payloads at DrobboxDrobbox engineers · DrobboxCase Studies

  Show 6 moreShow fewer

  • The System Design PrimerDonne Martin · donnemartinGitHub
  • Solving Remote Build Cache Misses (2 parts) at SoundCloudSoundCloud engineers · SoundCloudCase Studies
  • Load Balancing infrastructure to support more than 1.3 billion users at FacebookFacebook engineers · FacebookCase Studies
  • Meta Engineering BlogMeta Engineering · MetaBlogs
  • XING Engineering BlogXING engineers · XINGBlogs
  • Gusto Engineering BlogGusto engineers · GustoBlogs

  Open this lesson with its quiz and exercise

• Classic System Designs · 9 minDesign a unique ID generatorHow to produce unique, roughly time-ordered IDs across many machines without a central bottleneck.Read hereClose

  The problem

  Distributed systems need identifiers for rows, messages and events. Requirements for a good one:

  • Unique across all machines.
  • Roughly sortable by time, so newer IDs are larger (helps indexes and "latest first" queries).
  • Fits in 64 bits, to stay compact and fast.
  • Generated quickly without asking a central server on every call.

  The options

  Approach	Strength	Weakness
  Auto-increment per database (each server steps by k)	Simple	Hard to scale and add servers, not time-ordered across servers
  UUID (128-bit random)	No coordination at all	Large, not sortable, poor index locality
  Ticket server (one DB hands out ranges)	Simple, ordered	Single point of failure unless replicated
  Time-based composite (Snowflake)	Compact, sortable, no coordination per ID	Depends on clocks

  The simpler options as pictures

  100%

  Figure SDA-CSD-04-1 · Multi-master auto-increment · © forcsguy.com

  100%

  Figure SDA-CSD-04-2 · UUID per server · © forcsguy.com

  100%

  Figure SDA-CSD-04-3 · Ticket server · © forcsguy.com

  A Snowflake-style layout

  Pack several fields into one 64-bit number:

  100%

  Figure SDA-CSD-04-4 · 64-bit ID layout · © forcsguy.com

  • Timestamp (41 bits): milliseconds since a custom start date. That lasts about 69 years, and because it sits in the highest bits, IDs sort by creation time.
  • Machine id (10 bits): unique per generator, so two machines never produce the same ID in the same millisecond. Split it as datacenter plus machine if you like.
  • Sequence (12 bits): a counter that increments within the same millisecond and resets the next one. That allows 4,096 IDs per millisecond per machine.

  To create an ID, a generator reads the current time, and either resets the sequence (new millisecond) or increments it (same millisecond), then combines the three parts with bit shifts.

  Decoding one id

  100%

  Figure SDA-CSD-04-5 · From a Snowflake-style id back to a date · © forcsguy.com

  Assigning machine ids

  Each generator needs a distinct machine id. Hand them out at startup from a small coordination service (for example ZooKeeper or etcd) or from your orchestration system, and never reuse an id for two live generators.

  Hazards

  • Clock going backwards (for example after clock synchronisation): the generator must notice that time has regressed and wait or refuse, otherwise it may repeat an ID.
  • Sequence overflow within one millisecond: wait for the next millisecond.
  • Clock skew between machines means IDs are only roughly ordered across machines, which is fine for most uses but not a strict global order.
  • Predictability: sequential-looking IDs can be guessed. Do not use them as secrets, and hide them if enumeration matters (the URL shortener lesson scrambles them).

  Tuning the layout

  The bit budget is a trade. A custom epoch (a start date close to launch rather than 1970) gives the 41-bit timestamp its full roughly 69 years. If your traffic is low but the system must live long, give more bits to time and fewer to the per-millisecond sequence; if it is bursty, do the reverse. Once the worker and data-center bits are assigned they must not change casually: two generators with the same identity can emit the same id. Keep clocks disciplined with a time-sync protocol (NTP) and remember that cores and machines can still disagree by a little, which is why the generator must detect time moving backwards.

  When a simpler option is fine

  If you have a single database, its own sequence is perfectly good. If you only need uniqueness and not ordering, a random UUID is the least effort. Reach for a Snowflake-style generator when you have many writers and want compact, time-sortable keys.

  Worked numbers: what a 64-bit Snowflake-style id can hold

  Layout: 1 sign bit (unused) + 41 bits timestamp + 10 bits machine + 12 bits sequence.

  • Timestamp, 41 bits of milliseconds: 2^41 = 2.2 trillion ms, about 69.7 years from your chosen start date (epoch). Pick the epoch close to launch so the range lasts.
  • Machine, 10 bits: 2^10 = 1,024 generators. Split it as 5 bits datacentre and 5 bits machine if you want to see location in the id.
  • Sequence, 12 bits: 2^12 = 4,096 ids per millisecond per machine, about 4 million per second per machine. If a machine needs more than that in a single millisecond it must wait for the next millisecond.
  • Cluster capacity: 1,024 machines x 4 million = about 4 billion ids per second, far more than almost any system needs.
  • Ids sort roughly by creation time, so they work as ordered primary keys, and the database keeps inserts at the end of the index.

  100%

  Figure SDA-CSD-04-6 · The bit budget of a 64-bit id · © forcsguy.com

  When the clock misbehaves

  The scheme trusts each machine's clock. Three cases to design for:

  • The clock moves backwards (for example NTP corrects it by a few milliseconds). Issuing ids now could repeat ones already issued. Remember the last timestamp used; if the clock is behind it, either wait until it catches up (fine for small jumps) or refuse and alert (for large ones).
  • Two machines share a machine id (a bug in assigning ids after scaling or a restart). Their ids collide. Assign machine ids through a coordination service or a lease, never by guessing from an IP address.
  • Restart within the same millisecond with the sequence reset to zero. If the last used timestamp was lost, a fast restart could reuse values; persist it or delay start-up slightly.

  100%

  Figure SDA-CSD-04-7 · Handling a clock that went backwards · © forcsguy.com

  Mistakes people make

  • Sending 64-bit ids to JavaScript as numbers. JavaScript numbers are exact only up to 2^53, so the last digits get rounded. Transmit ids as strings.
  • Using random UUIDs as a clustered primary key. Random inserts scatter across the index and fragment it. Prefer time-ordered ids (a Snowflake id, UUIDv7 or ULID) for primary keys.
  • Exposing sequential or time-ordered ids to outsiders. Anyone can estimate your volume or guess neighbouring ids. If that matters, add a separate public random id and do not rely on secrecy of the key.
  • Assuming ids are strictly ordered across machines. They are ordered only to within clock skew; do not use them as the sole proof of event order.
  • A single central counter. Simple and ordered, but it is a bottleneck and a single point of failure unless you hand out ranges.

  Try it yourself

  Build the Snowflake ID lab: it packs these fields with BigInt, waits when the sequence runs out, and refuses when the clock goes backwards, with a check that proves each rule. Read the clocks and ordering lesson for why wall clocks cannot give a global order.

  More on this site

  Related reading

  • Heroic: Time Series Database at SpotifySpotify engineers · SpotifyCase Studies
  • Clock Skew when Syncing Password Payloads at DrobboxDrobbox engineers · DrobboxCase Studies
  • Roshi: Distributed Storage System for Time-Series Event at SoundCloudSoundCloud engineers · SoundCloudCase Studies
  • Protector: Circuit Breaker for Time Series Databases at TrivagoTrivago engineers · TrivagoCase Studies

  Show 6 moreShow fewer

  • Time Series DatabasesInfluxdata engineers · InfluxdataCase Studies
  • MetricsDB: TimeSeries Database for storing metrics at TwitterTwitter engineers · TwitterCase Studies
  • Druid at eBayeBay engineers · eBayCase Studies
  • Druid - Real-time Analytics DatabaseApache engineers · ApacheDocumentation
  • Spotify LabsSpotify engineers · SpotifyBlogs
  • Distributed SearchingWashingtonPapers

  Open this lesson with its quiz and exercise

• 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