Rewriting the heart of our sync engine

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.

• Classic System Designs · 12 minDesign cloud file storage and syncStore files for millions of users and keep devices in sync: block-level chunking, deduplication, metadata, conflicts and sharing.Read hereClose

  The problem

  A cloud file storage service (think of a personal drive) stores each user's files, makes them available on all their devices, keeps them in sync and lets them share.

  Requirements

  • Upload, download and sync files on web, desktop and mobile.
  • Sync quickly across devices; show file history and allow restore.
  • Sharing with permissions.
  • Reliable: never lose a file; handle large files and flaky connections.
  • Efficient in bandwidth and storage.

  Estimates

  Suppose 50 million users with 10 GB each: about 500 PB of data. That makes storage cost and upload bandwidth central. It also means you must avoid re-uploading unchanged data.

  High-level design

  Separate file content from file metadata:

  100%

  Figure SDA-CSD-11-1 · Metadata and block storage architecture · © forcsguy.com

  • Metadata (names, folders, versions, permissions, ordered list of block hashes): a relational database with strong consistency, since many operations need correct, ordered updates.
  • File content: stored as blocks in distributed object storage, replicated for durability.

  Growing from one server

  100%

  Figure SDA-CSD-11-2 · From one disk to a scalable storage design · © forcsguy.com

  100%

  Figure SDA-CSD-11-3 · Replication within and across regions · © forcsguy.com

  Blocks make everything better

  The client splits each file into fixed-size blocks (for example 4 MB), computes a hash per block, and uploads only the blocks the server does not already have.

  100%

  Figure SDA-CSD-11-4 · File as an ordered list of block hashes · © forcsguy.com

  Benefits:

  • Delta sync: after an edit only the changed blocks are uploaded.
  • Resumable uploads and downloads.
  • Deduplication: blocks with the same hash are stored once, even across users (with care for privacy).
  • Cheap versions: a version is just a list of block hashes, so history costs little.
  • Blocks can be compressed and encrypted before storage.

  Before: upload the whole file

  100%

  After: upload changed blocks only

  100%

  What changed

  • Editing one page of a large file sends a few megabytes, not all of it
  • Identical blocks are stored once
  • A broken upload can resume from the last block

  Sync flow

  1. The client detects a local change, splits, hashes and asks the server which blocks are missing.
  2. It uploads missing blocks, then commits a new file version in the metadata service.
  3. The notification service tells the user's other devices (through a long-lived connection or long polling) that something changed.
  4. Those devices fetch the new metadata and download only blocks they lack.

  100%

  Figure SDA-CSD-11-5 · A sync conflict · © forcsguy.com

  Conflicts

  If two devices change the same file from the same base version, the second commit finds the base is out of date. The safe rule is to keep both: accept the first, and save the second as a "conflicted copy" so nothing is lost. Never overwrite silently.

  Metadata, consistency and notifications

  Data model. A user has devices (each with a push id) and a root namespace; a file row holds the latest state; a file-version table keeps read-only history so past revisions stay trustworthy; a block table maps each version to its ordered blocks. Any version can be rebuilt by joining its blocks in order.

  Strong consistency for metadata. Two clients must never see different file lists. Caches default to eventual consistency, so keep cache replicas in step with the primary and invalidate the cache on every database write. A relational database gives atomic, isolated updates natively, which is why it suits metadata better than a store where you would have to build those guarantees yourself.

  Why long polling can be enough for notifications. Updates flow only server to client and are infrequent, so a persistent two-way channel is more than needed; a client holds a request open, gets told "something changed", fetches metadata, then reopens. (WebSocket is the better fit for chat-like two-way traffic.)

  Upload sequence. Two things happen at once: the client registers metadata (status pending, others are told a file is arriving) and sends blocks through the block servers; when storage confirms the upload, a callback flips the status to uploaded and others are notified so they can pull metadata and then the blocks.

  Failure notes. A notification server may hold a million connections; if it dies, all of them reconnect elsewhere at once, which is slow, so spread reconnects out. Offline clients are served from a backup queue of pending changes. Block servers' unfinished jobs are taken over by others.

  Trade-off: uploading straight to storage is faster (one hop) but means chunking, compression and encryption must be reimplemented and trusted on every client platform, and clients can be tampered with; a central block tier keeps that logic in one place.

  Image: U.S. Department of Agriculture · Public domain · Source · Wikimedia Commons: Magnetic tape library at USDA

  The block pipeline and delta sync

  100%

  Figure SDA-CSD-11-6 · Block server pipeline · © forcsguy.com

  100%

  Figure SDA-CSD-11-7 · Delta sync: only changed blocks · © forcsguy.com

  Reliability and cost

  • Durability: store blocks in several locations, with checksums verified on read and repaired by background scrubbing.
  • Hot and cold tiers: recent files on fast storage, old versions and rarely used data moved to cheaper cold storage.
  • Limit version history (by count or age) to control cost.
  • Metadata scale: shard the metadata database by user id; most operations touch one user's data.
  • Large files: parallel block uploads, resumable and retried independently.

  Upload and download as sequences

  100%

  Figure SDA-CSD-11-8 · Upload with notification to other devices · © forcsguy.com

  100%

  Figure SDA-CSD-11-9 · Download after a change elsewhere · © forcsguy.com

  Sharing and security

  • Permissions (view, edit) stored with the file or folder, checked on every request.
  • Share links with optional expiry and password.
  • Encrypt in transit and at rest; consider client-side encryption for stronger privacy (which limits server-side features such as search and dedup).
  • Audit logs for access and changes.

  Worked numbers: why blocks and deltas matter

  Files are cut into blocks of about 4 MB, each identified by a hash of its content.

  • Editing a large file: a user changes one paragraph in a 1 GB file. Only the block(s) that contain the change differ, so the client uploads about 4 MB instead of 1 GB, roughly 0.4% of the data, and the sync finishes in seconds.
  • Deduplication: if a block's hash already exists in storage (the same file uploaded by another user, or a copy within your account), the server stores nothing new and just records that this file version uses that block. Popular files cost almost nothing to store again.
  • Raw capacity: with 10 million users x 10 GB the system holds about 100 PB. Three full copies would need 300 PB; erasure coding (for example 10 data pieces plus 4 parity pieces, a 1.4x overhead) needs about 140 PB while surviving the loss of any 4 pieces. That difference is tens of millions of dollars a year, so cold data is usually erasure coded, and hot data may be replicated.
  • Metadata (file names, folder trees, versions, block lists) is tiny by comparison but is read and written constantly, so it lives in a separate, strongly consistent database, not with the blocks.

  100%

  Figure SDA-CSD-11-10 · Delta sync: upload only the changed block · © forcsguy.com

  When two devices edit the same file

  A laptop is offline and edits plan.docx; meanwhile a phone edits the same file and syncs first. When the laptop reconnects it has a version based on a now-outdated parent. The server notices because the upload says "I am based on version 7" while the latest is 8.

  For files in general the safe approach is: do not silently overwrite. Keep the first writer's version as current and save the second as a conflicted copy ("plan (Laptop's conflicted copy).docx"), then let the user merge. For real-time collaborative documents, a different technique (operational transforms or CRDTs) merges edits automatically, but that is a separate design.

  100%

  Figure SDA-CSD-11-11 · Detecting a conflict by version · © forcsguy.com

  Mistakes people make

  • Uploading whole files. It wastes bandwidth and makes large files unusable on poor connections. Use blocks, deltas and resumable uploads.
  • Trusting client timestamps to decide the winner. Clocks differ; compare versions, not times.
  • Treating a rename or move as delete plus create. It re-uploads the data. Metadata should record moves without touching blocks.
  • Polling for changes. It wastes battery and server capacity. Use a long-lived notification channel that says "something changed, pull your list".
  • Mixing metadata and block storage. They have different access patterns and consistency needs.
  • Forgetting security. Encrypt in transit and at rest, check permissions on every request, expire share links, and scan uploads for malware if you serve them to others.

  Try it yourself

  Read the consistent hashing lesson for placing blocks across servers, and build the consistent hash ring lab to place block ids on storage nodes. The Builder's write-burst challenge shows why uploads and metadata updates benefit from a queue.

  More on this site

  Related reading

  • How Discord Scaled Elixir to 5,000,000 Concurrent UsersDiscordCase Studies
  • CAP Twelve Years Later: How the Rules Have ChangedEric Brewer · InfoQBlogs
  • Amazon S3 strong consistencyAmazon Web ServicesDocumentation
  • Designing Data-Intensive ApplicationsMartin Kleppmann · O'ReillyBooks

  Show 6 moreShow fewer

  • Concourse: Generating Personalized Content Notifications in Near-Real-Time at LinkedInLinkedIn engineers · LinkedInCase Studies
  • Rewriting the heart of our sync engineDropboxCase Studies
  • Fast Order Search using Data Pipeline and Elasticsearch at YelpYelp engineers · YelpCase Studies
  • Pagelets Parallelize Server-side Processing at YelpYelp engineers · YelpCase Studies
  • Real-time Presence Platform at LinkedInLinkedIn engineers · LinkedInCase Studies
  • GitHub Engineering BlogGitHub engineers · GitHubBlogs

  Open this lesson with its quiz and exercise

• Real-World Systems · 13 minDesign a stock exchangeAn order book, a matching engine and a sequencer: how an exchange matches buyers and sellers fairly in microseconds.Read hereClose

  The problem

  An exchange lets buyers and sellers trade. Participants submit orders; the exchange matches them and reports the trades.

  Key properties:

  • Fairness: orders are handled in a strict, auditable order.
  • Very low latency: microseconds from order to acknowledgment.
  • High throughput: hundreds of thousands to millions of orders per second at peaks.
  • Correctness and durability: money is involved. No lost or duplicated trades.
  • Availability: an exchange outage halts a market.

  The order book

  For each symbol the order book holds resting orders:

  • Bids (buy orders), highest price first.
  • Asks (sell orders), lowest price first.
  • Within a price level, orders queue by arrival time.

  Common order types: limit (a worst price you accept; unmatched part rests in the book) and market (take the best available now).

  Matching: price-time priority

  An incoming buy matches the lowest-priced asks it can afford; among equal prices the earliest order matches first. Matching repeats until the order is filled or no longer matches, and any remainder rests in the book.

  Image: Thomas J. O'Halloran · Public domain · Source · Wikimedia Commons: NY stock exchange traders floor LC-U9-10548-6

  Architecture

  100%

  Figure SDA-RWS-05-1 · Exchange: gateway, sequencer, matching engine · © forcsguy.com

  1. Gateways authenticate participants, validate orders, and run pre-trade risk checks (limits, available funds).
  2. The sequencer gives every event a sequence number: one agreed total order, the basis of fairness and recovery.
  3. A matching engine applies events in order to the in-memory order book and emits trades.
  4. Everything is written to a durable event log. Executions go to participants, and a market data stream tells everyone about prices and depth.
  5. Clearing and settlement later move money and securities between accounts.

  100%

  Figure SDA-RWS-05-2 · An order book with a buy order sweeping the sell side · © forcsguy.com

  How it gets so fast

  • In-memory order books and no database in the critical path.
  • Single-threaded matching per symbol group: no locks, deterministic behaviour. Parallelism comes from partitioning symbols across engines.
  • Event sourcing: state is the result of applying an ordered log. Persist the event first (to a memory-mapped file or replicated log), then process.
  • Pre-allocated memory, ring buffers, no garbage-collection pauses, and careful cache-friendly data structures.
  • Hardware and network: servers co-located in the exchange's data centre, fast network cards and kernel-bypass networking, precise time sources.

  100%

  Figure SDA-RWS-05-3 · A fast engine on one machine: shared log and busy loops · © forcsguy.com

  Reliability

  • A hot standby applies the same event log and can take over within moments. Use sequence numbers to detect gaps and avoid duplicate processing.
  • Replicate the log across machines or sites before acknowledging, trading a little latency for durability.
  • Idempotent order identifiers prevent a resubmitted order executing twice.
  • Circuit breakers halt trading when prices move too fast.

  Market data fairness

  Everyone should see the same information at about the same time. Exchanges publish through multicast feeds, give all participants equal-length cables inside the data centre, and timestamp events at the matching engine. A separate, slower snapshot and retransmission service helps receivers that miss packets.

  What is out of scope here

  Clearing houses, settlement cycles, regulation and surveillance are large systems of their own. The core design is the sequencer plus deterministic matching engine plus durable log.

  Real-world reading

  Related reading

  • Event SourcingMartin FowlerBlogs
  • Monolith FirstMartin FowlerBlogs
  • Rewriting the heart of our sync engineDropboxCase Studies
  • Cape: Event Stream Processing Framework at DropboxDropbox engineers · DropboxCase Studies

  Show 6 moreShow fewer

  • Improving Search Engine Efficiency by over 25% at eBayeBay engineers · eBayCase Studies
  • Finding Kafka throughput limit in infrastructure at DropboxDropbox engineers · DropboxCase Studies
  • Bullet: Forward-Looking Query Engine for Streaming Data at YahooYahoo engineers · YahooCase Studies
  • MicroservicesJames Lewis and Martin Fowler · Martin FowlerBlogs
  • The LMAX ArchitectureMartin FowlerCase Studies
  • Microservices and OrchestrationMartinfowler engineers · MartinfowlerCase Studies

  Open this lesson with its quiz and exercise

• Low-Level Design Practice · 11 minMovie ticket bookingSeats, shows and temporary holds: how to let many people pick seats at once without selling the same seat twice.Read hereClose

  The problem

  A theatre chain runs screens that show movies at set times. Customers browse shows, pick seats, pay and receive a ticket. Many customers pick seats for the same popular show at once. A seat must never be sold twice.

  Entities

  100%

  Figure SDA-LLD-05-1 · Movie booking classes · © forcsguy.com

  The key idea: ShowSeat is a seat in one show. A physical seat exists for all shows; it is available or taken per show. Status values: AVAILABLE, HELD, BOOKED.

  The seat lifecycle

  100%

  Figure SDA-LLD-05-2 · Show seat status · © forcsguy.com

  class ShowSeat {
    status: "AVAILABLE" | "HELD" | "BOOKED" = "AVAILABLE";
    heldBy?: string; heldUntil = 0;
  
    // must be atomic: a lock per seat in memory, a conditional UPDATE in a database
    tryHold(user: string, ms = 10 * 60_000): boolean {
      if (this.status === "HELD" && Date.now() > this.heldUntil) this.status = "AVAILABLE";
      if (this.status !== "AVAILABLE") return false;
      this.status = "HELD"; this.heldBy = user; this.heldUntil = Date.now() + ms;
      return true;
    }
    confirm(user: string): boolean {
      if (this.status !== "HELD" || this.heldBy !== user) return false;
      this.status = "BOOKED"; return true;
    }
  }
  

  In a database this is one statement: UPDATE show_seat SET status='HELD', held_by=?, held_until=? WHERE id=? AND (status='AVAILABLE' OR held_until < now()) and the affected-row count tells you whether you won.

  Booking several seats

  100%

  Figure SDA-LLD-05-3 · Booking flow · © forcsguy.com

  If any seat in the group cannot be held, release the ones you did hold and tell the customer. This avoids a half-booked group.

  Design notes

  • Pricing by seat category, time and day is a strategy or a price table on ShowSeat.
  • Expiry can be a background job or a check at read time (as above). A job keeps the displayed seat map accurate.
  • Hot shows: at huge scale put the seat state in a fast store with atomic operations, and queue requests; this overlaps with the flash-sale design in the real-world systems course.
  • Idempotent payment: a retried payment callback must not issue a second ticket.
  • Extensions: seat recommendations, food add-ons, cancellations with refund policy, and notifications on confirm.

  Real-world reading

  Related reading

  • Rewriting the heart of our sync engineDropboxCase Studies
  • Megastore: Providing Scalable, Highly Available Storage (paper)Baker et al. · GooglePapers
  • Scaling Dropbox - Kevin Modzelewski, Back-end Engineer at DropboxDropboxYouTube
  • Hussein Nasser: Backend Engineering ShowHussein Nasser · Hussein Nasser (YouTube)YouTube

  Show 6 moreShow fewer

  • Uber Engineering — Where the Digital World Meets the Physical OneUber engineers · UberBlogs
  • Handles Millions of Digital Transactions Safely Everyday at PaytmPaytm engineers · PaytmCase Studies
  • Distributed systems theory for the distributed systems engineerHenry Robinson · The Paper TrailBlogs
  • The Pragmatic EngineerGergely Orosz · SubstackPodcasts & Newsletters
  • Soundcloud Engineering BlogSoundcloud engineers · SoundcloudBlogs
  • Pluralsight Engineering BlogPluralsight engineers · PluralsightBlogs

  Open this lesson with its quiz and exercise