AWS Compute Blog

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.

• System Design Foundations · 9 minBack-of-the-envelope estimationQuick arithmetic that tells you whether you need one server or a thousand, and which resource will run out first.Read hereClose

  Why estimate at all

  You do not need exact numbers. You need to know the order of magnitude: is it 100 requests per second or 100,000? Is the data 10 GB or 10 PB? Those answers change the architecture completely, and you can get them with simple arithmetic.

  Numbers to remember

  Powers of two for sizes:

  Unit	Approx. size
  1 KB	a thousand bytes
  1 MB	a million bytes
  1 GB	a billion bytes
  1 TB	a trillion bytes
  1 PB	a thousand TB

  Time: one day is about 86,400 seconds, which we round to 100,000 (10^5) to make mental maths easy.

  Rough latencies (the exact values change with hardware, the ratios matter):

  Operation	About
  Read from memory	100 ns
  Read 1 MB sequentially from memory	tens of microseconds
  SSD random read	100 microseconds
  Round trip inside one data center	0.5 ms
  Disk seek	10 ms
  Round trip across continents	100 to 150 ms

  Two lessons fall out of this table: memory beats disk by orders of magnitude, and crossing a network or an ocean is expensive, so avoid unnecessary round trips.

  A method

  1. Start from users: daily active users (DAU).
  2. Actions per user per day, giving total requests per day.
  3. Divide by 100,000 for average requests per second (QPS).
  4. Multiply by 2 to 5 for peak QPS.
  5. Size per item times items per day gives storage per day; multiply by retention and replication.

  The method as a picture

  100%

  Figure SDA-FND-03-1 · From users to requests and storage · © forcsguy.com

  Worked example: a short-link service

  • 100 million new links per month.
  • Reads outnumber writes 10 to 1.

  Writes per second: 100,000,000 / (30 x 86,400) is about 40 per second. Reads: about 400 per second. Peak maybe 2,000 reads per second.

  Storage: each record is about 500 bytes (the short key, the long URL, a date). 100 million per month x 12 months x 5 years = 6 billion records x 500 bytes = 3 TB. Easily one modern database over a few years, with replicas for safety.

  What did we learn? The write rate is tiny, reads are modest, and the whole data set is small. This is not a problem that needs exotic technology, so the design should be simple. That conclusion is the point of estimating.

  100%

  Figure SDA-FND-03-2 · Turning users into load and storage · © forcsguy.com

  Rules of thumb

  • Round aggressively. 86,400 becomes 100,000. 2.7 becomes 3.
  • Write units next to every number. Most mistakes are unit mistakes (bits versus bytes, MB versus GB).
  • State your assumptions. If someone disagrees with 10 requests per user, you can change one number and recompute.
  • Sanity check against reality. If your estimate says a small app needs a million servers, an assumption is off.

  Real-world reading

  Related reading

  • Cockroach Labs BlogCockroach Labs engineers · Cockroach LabsBlogs
  • The Architecture Twitter Uses to Deal with 150M Active Users, 300K QPS, a 22 MB/S Firehose, and Send Tweets in Under 5 SecondsHigh Scalability engineers · High ScalabilityCase Studies
  • AWS Database BlogAWS database teams · Amazon Web ServicesBlogs
  • LISA '10 - Operations at Twitter: Scaling Beyond 100 Million UsersYouTubeYouTube

  Show 6 moreShow fewer

  • Instagram Architecture: 14 Million users, Terabytes of Photos, 100s of Instances, Dozens of Technologies - High Scalability -High Scalability engineers · High ScalabilityCase Studies
  • Playfish's Social Gaming Architecture - 50 Million Monthly Users and Growing - High Scalability -High Scalability engineers · High ScalabilityCase Studies
  • CockroachDBCockroach Labs · GitHubGitHub
  • AWS Compute BlogAmazon Web Services engineers · Amazon Web ServicesBlogs
  • Yelp Engineering BlogYelp engineers · YelpBlogs
  • Telstra BlogTelstra engineers · TelstraBlogs

  Open this lesson with its quiz and exercise

• Low-Level Design Practice · 10 minShopping cartCarts, inventory and pricing rules: adding items, applying discounts, checking stock and turning a cart into an order safely.Read hereClose

  The problem

  Shoppers add and remove products, apply coupons, see a total, and check out. The system must check stock, compute the price correctly and create an order.

  Entities

  100%

  Figure SDA-LLD-11-1 · Shopping cart classes · © forcsguy.com

  Cart versus order

  A cart is mutable and may be stale. An order is a frozen record of what was bought, at what price, with which discounts. Checkout converts one into the other.

  100%

  Figure SDA-LLD-11-2 · Checkout flow · © forcsguy.com

  Pricing as ordered rules

  type Line = { sku: string; qty: number; unit: number };
  interface PricingRule { apply(lines: Line[]): { reason: string; cents: number }[] }
  
  const buy2get1: PricingRule = {
    apply: (lines) => lines.filter(l => l.sku === "TSHIRT" && l.qty >= 3)
      .map(l => ({ reason: "Buy 2 get 1", cents: -Math.floor(l.qty / 3) * l.unit })),
  };
  const coupon10: PricingRule = {
    apply: (lines) => [{ reason: "10% coupon", cents: -Math.round(lines.reduce((s, l) => s + l.qty * l.unit, 0) * 0.1) }],
  };
  
  function total(lines: Line[], rules: PricingRule[]) {
    const sub = lines.reduce((s, l) => s + l.qty * l.unit, 0);
    const adj = rules.flatMap(r => r.apply(lines));
    return { subtotal: sub, adjustments: adj, total: sub + adj.reduce((s, a) => s + a.cents, 0) };
  }
  

  Decide and document precedence (do percentage discounts apply before or after fixed ones?) and whether discounts stack. Keep a record of which rules applied so the invoice can explain the price.

  Inventory safely

  // conditional update: succeeds only if enough stock remains
  function reserve(sku: string, qty: number): boolean {
    const row = stock.get(sku)!;
    if (row.available < qty) return false;
    row.available -= qty; row.reserved += qty; return true;   // atomic in a real database: UPDATE ... WHERE available >= qty
  }
  

  Design notes

  • Guest and signed-in carts: merge a guest cart into the user's cart on login.
  • Abandoned carts: stock is not reserved by a cart, only by checkout; reservations expire.
  • Idempotent checkout: a double click must not create two orders (use a checkout key).
  • Money is integer minor units; taxes and shipping are further rules or services.
  • Extensions: wishlists, saved-for-later, per-region pricing, bundles.

  Real-world reading

  Related reading

  • Electronic Arts SEED BlogElectronic Arts engineers · Electronic ArtsBlogs
  • AWS Compute BlogAmazon Web Services engineers · Amazon Web ServicesBlogs
  • PricingNet: Pricing Modelling with Neural Networks at SkyscannerSkyscanner engineers · SkyscannerCase Studies
  • Self-Serve Reporting Platform on Hadoop at LinkedInLinkedInPapers

  Show 6 moreShow fewer

  • Vortex: Monitoring Server Applications at DropboxDropbox engineers · DropboxCase Studies
  • Determinism (4 parts) in League of Legends ServerRiotgames engineers · RiotgamesCase Studies
  • Cassandra for Keeping Counts In Sync at SoundCloudSoundCloud engineers · SoundCloudCase Studies
  • Neural Architecture Search (NAS) for Prohibited Item Detection at MercariMercari engineers · MercariCase Studies
  • Kogan.com Dev BlogKogan.com engineers · Kogan.comBlogs
  • HackerEarth Engineering BlogHackerEarth engineers · HackerEarthBlogs

  Open this lesson with its quiz and exercise