Ratequeue: Core Queueing-And-Rate-Limiting System at Twilio

Ideas you will meet

Rate Limiting

Token bucket, leaky bucket and sliding-window limiters.

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 · 12 minDesigning for failure: reliabilityTimeouts, retries, circuit breakers, rate limiting and redundancy: how systems stay up when parts of them break.Read hereClose

  Failure is normal

  At scale something is always broken: a disk, a network link, a deployment, a dependency having a bad day. Reliable systems do not avoid failure, they expect it and contain it.

  Two words to keep apart:

  • Availability: the fraction of time the system works (99.9% allows about 8.8 hours of downtime a year; 99.99% about 53 minutes).
  • Durability: the chance stored data is not lost.

  Remove single points of failure

  A single point of failure (SPOF) is any component whose failure takes everything down. Hunt for them:

  • Run several application servers behind a load balancer.
  • Replicate databases and plan failover (lesson 5).
  • Spread across availability zones, and for the most critical services, across regions.
  • Do not forget the "invisible" ones: the load balancer, DNS, a certificate that expires, a single queue.

  100%

  Figure SDA-FND-10-1 · Removing single points of failure tier by tier · © forcsguy.com

  Protect calls between services

  Most outages spread through calls between components. Four basic defences:

  1. Timeouts

  Every network call needs a timeout. Without it a slow dependency holds your threads hostage. Set timeouts based on what a healthy call looks like (for example a little above the 99th percentile), and make inner timeouts shorter than outer ones.

  2. Retries, carefully

  Transient errors often succeed on a second try. But retries multiply load on a struggling service, so:

  • Retry only idempotent operations or those with an idempotency key (lesson 8).
  • Use exponential backoff with jitter.
  • Cap the number of attempts, and ideally cap the share of traffic that can be retries.

  3. Circuit breakers

  If a dependency keeps failing, stop calling it for a short time and fail fast.

  Image: Alf van Beem · CC0 · Source · Wikimedia Commons: Circuit breaker, Single pole, Non-tripfree, 20Amp-30Volts, AN 3160 pic1

  100%

  Figure SDA-FND-10-2 · Circuit breaker states · © forcsguy.com

  • Closed: normal operation, failures are counted.
  • Open: calls fail immediately, saving resources.
  • Half-open: a few trial calls check whether the dependency has recovered.

  4. Bulkheads

  Give each dependency its own pool of threads or connections, like watertight compartments in a ship, so one slow dependency cannot use up everything.

  Before: a slow dependency drags everyone down

  100%

  After: a breaker cuts the slow dependency off

  100%

  What changed

  • Callers stop waiting on a failing service
  • Threads and connections are not used up
  • A fallback answer is returned while the service recovers

  Protect yourself from too much traffic

  • Rate limiting caps how many requests a client may make (common algorithms: token bucket, sliding window). It protects against abuse and accidental floods.
  • Load shedding: when overloaded, deliberately reject low-priority work early so important requests still succeed. It is better to serve 80% of requests well than 100% badly.
  • Back pressure: tell producers to slow down instead of letting queues grow without bound.

  Degrade gracefully

  When a non-critical part fails, keep the rest working: show the page without recommendations, serve cached prices, queue the email. Decide in advance which features are essential.

  Practise failure

  • Health checks so traffic leaves broken instances.
  • Chaos testing: deliberately kill instances in a controlled way to prove the system copes.
  • Runbooks and game days so people have rehearsed the response.

  A worked example: the arithmetic of availability

  Downtime in a month. 99% allows about 7.3 hours; 99.9% about 43 minutes; 99.99% about 4.4 minutes; 99.999% about 26 seconds. Each extra nine is ten times harder and usually much more expensive, so choose the target your users need, not the biggest number.

  Dependencies in series multiply. If a request needs three services, each 99.9% available, the request is available only 0.999 x 0.999 x 0.999 = 99.7%, about 2 hours 11 minutes of downtime a month. The more things in the critical path, the worse it gets, which is why teams shorten the critical path and make non-essential calls optional.

  Redundancy in parallel helps. Two independent replicas, each 99% available, are both down only 1% x 1% = 0.01% of the time: 99.99% together. The word "independent" carries all the weight: replicas that share a rack, a deploy, a bug or a dependency fail together, and the formula no longer applies.

  Retries multiply load. If every one of 1,000 requests per second fails and each caller retries 3 times, the failing service sees up to 4,000 requests per second, making recovery harder. And if three layers each retry 3 times, one user request can become 64 attempts at the bottom. Retries need limits, backoff with jitter, and a retry budget (for example, retries may be at most 10% of normal traffic).

  100%

  Figure SDA-FND-10-3 · How availability combines · © forcsguy.com

  Anatomy of a cascading failure

  The classic outage is rarely one failure; it is one failure that spreads.

  1. A database gets slow (a bad query, a noisy neighbour). Responses that took 10 ms now take 5 seconds.
  2. App servers wait on it. Each request holds a thread for 5 seconds, so threads and connections fill up.
  3. The app can no longer accept new requests, even ones that do not need the database. The load balancer sees timeouts and marks servers unhealthy, so the same traffic lands on fewer servers.
  4. Callers time out and retry, which adds load to the already struggling system.
  5. Everything is down, and fixing the original slow query no longer brings it back, because the retry storm keeps it overloaded.

  The defences are cheap compared with the outage:

  • Timeouts on every call, shorter than the caller's own timeout.
  • Circuit breakers that stop calling a failing dependency for a while and fail fast.
  • Bulkheads: separate thread or connection pools per dependency, so one slow one cannot use all of them.
  • Load shedding: when overloaded, reject some requests early to keep serving the rest.
  • Backoff with jitter and retry budgets.

  100%

  Figure SDA-FND-10-4 · A circuit breaker protects both sides · © forcsguy.com

  Mistakes people make

  • No timeouts, or timeouts longer than the caller's. The default in many libraries is "wait forever" or minutes.
  • Retrying everything everywhere. Retry only safe, idempotent operations, at one layer, with backoff, jitter and a budget.
  • Health checks that lie. A server that answers /health but cannot reach its database should fail the check.
  • Untested failover. Failover that has never run is a guess. Practise it on purpose, in business hours.
  • Shared fate. Two "redundant" systems in one zone, on one deploy pipeline, or on one dependency are one system.
  • No graceful degradation. Decide in advance which features can be switched off (recommendations, images, analytics) to protect the critical path.

  Try it yourself

  In the System Builder, lose three servers at peak and find how much spare capacity you need. Read the resilience patterns lesson for circuit breakers and bulkheads in more depth, and build the lease leader election lab to see failover without split brain.

  More on this site

  Related reading

  • Timeouts, retries, and backoff with jitterAmazon Builders' Library · Amazon Web ServicesBlogs
  • Using load shedding to avoid overloadAmazon Builders' Library · Amazon Web ServicesBlogs
  • Maglev: A Fast and Reliable Software Network Load Balancer (paper)Eisenbud et al. · GooglePapers
  • Designing robust and predictable APIs with idempotencyBrandur Leach · StripeBlogs

  Show 6 moreShow fewer

  • Circuit BreakerMartin FowlerBlogs
  • Circuit Breaker patternMicrosoft · Microsoft AzureDocumentation
  • Google SRE Book: Addressing Cascading FailuresGoogle SRE team · GoogleBlogs
  • Google SRE Book: Handling OverloadGoogle SRE team · GoogleBlogs
  • Testing for Disaster Recovery Failover TestingUSENIX engineers · USENIXCase Studies
  • Improved Production Stability with Circuit Breakers at HerokuHeroku engineers · HerokuCase Studies

  Open this lesson with its quiz and exercise

• Low-Level Design Practice · 11 minHotel managementRooms, bookings and availability: modelling date ranges, preventing double booking and pricing by room type and season.Read hereClose

  The problem

  Guests search for a room type and dates, book, check in, check out and pay. Staff manage rooms. The system must never double-book a room for overlapping dates.

  Entities

  100%

  Figure SDA-LLD-04-1 · Hotel classes · © forcsguy.com

  Booking.status moves through reserved, checked in, checked out, cancelled.

  Availability is a range problem

  A room is free for [in, out) if no active booking overlaps it. Two ranges overlap when startA < endB && startB < endA.

  const overlaps = (a: Range, b: Range) => a.start < b.end && b.start < a.end;
  
  function freeRooms(rooms: Room[], bookings: Booking[], want: Range, type: string) {
    return rooms.filter((r) => r.type === type &&
      !bookings.some((b) => b.room === r && b.status !== "CANCELLED" && overlaps(b, want)));
  }
  

  Booking safely

  100%

  Figure SDA-LLD-04-2 · Booking flow · © forcsguy.com

  The check and the insert must be one atomic step. In a database that means a transaction with a lock on the room row (or an exclusion constraint on the date range). In memory it means a lock per room.

  Pricing

  Keep price calculation behind RatePlan: base price per room type, multiplied by season, weekday and demand, with member discounts. A Booking stores the price it was sold at, so later rate changes do not alter old bookings.

  Cancellation, check-in and check-out

  • Cancel: apply a cancellation policy (strategy) to compute the refund from how close the stay is.
  • Check-in: assign a specific room if the booking was for a type, mark checked in, create a folio for extra charges.
  • Check-out: add extras, settle the payment, mark the room "needs cleaning" and release it for new bookings after housekeeping.

  Extensions

  Group bookings, room upgrades, overbooking with a controlled allowance, and housekeeping as a small state machine (dirty, cleaning, ready).

  Real-world reading

  Related reading

  • Scaling Gradient Boosted Trees for Click-Through-Rate Prediction at YelpYelp engineers · YelpCase Studies
  • Improving Search Engine Efficiency by over 25% at eBayeBay engineers · eBayCase Studies
  • Docker Containers that Power Over 100.000 Online Shops at ShopifyShopify engineers · ShopifyCase Studies
  • Ratequeue: Core Queueing-And-Rate-Limiting System at TwilioTwilio engineers · TwilioCase Studies

  Show 6 moreShow fewer

  • Cloud Bouncer: Distributed Rate Limiting at YahooYahoo engineers · YahooCase Studies
  • Reasons for Choosing S3 over HDFS at DatabricksDatabricks engineers · DatabricksCase Studies
  • Improving Web Vulnerability Management through Automation at LyftLyft engineers · LyftCase Studies
  • Distributed Rate Limiting at AllegroAllegro engineers · AllegroCase Studies
  • Galois Engineering BlogGalois engineers · GaloisBlogs
  • Hashrocket Engineering BlogHashrocket engineers · HashrocketBlogs

  Open this lesson with its quiz and exercise

• Advanced Distributed Systems · 13 minDistributed counters, leaderboards and live reactionsThree high-write designs: counting at huge scale without a hot row, ranking millions of players, and broadcasting reactions to millions of viewers.Read hereClose

  The common difficulty

  All three problems involve huge numbers of small writes to shared state that many people read at once. The pattern behind the solutions is the same: do not contend on one place. Spread the writes, combine the results, and accept that some answers can be approximate or slightly late.

  1. Distributed counters

  Counting likes, views or API calls looks trivial until millions of updates per second hit one row.

  100%

  Figure SDA-ADS-10-1 · A sharded counter · © forcsguy.com

  Options, from simple to scalable:

  • One atomic increment in a fast store (Redis INCR): thousands per second per key, fine for many uses.
  • Sharded counter: split one logical counter into N sub-counters; write to a random one; sum on read.
  • Local aggregation then merge: each server counts in memory and sends deltas periodically; a collector merges (the approach of metrics systems).
  • Event log then aggregate: write events to a log, count with a stream job; exact, replayable, slower to show.
  • Mergeable counters (CRDTs): counters that can be updated on several replicas and merged without conflict (see collaborative editing).
  • Approximate counting: for unique counts (distinct viewers) use HyperLogLog, which counts millions of items in a few kilobytes with about one percent error (see the probabilistic structures lesson).

  Decide the accuracy you need: a like count can lag and be approximate; a bill must be exact (use an append-only log and idempotent processing).

  Before: one hot counter

  100%

  After: sharded counters

  100%

  What changed

  • Writes spread over many counters instead of queuing on one
  • A background job adds the pieces together
  • The total can lag slightly behind the truth

  2. Leaderboards

  A leaderboard needs: update a player's score, get their rank, show the top N, and show neighbours around a player.

  100%

  Figure SDA-ADS-10-2 · Leaderboard with a sorted set · © forcsguy.com

  • Redis sorted sets (ZADD, ZRANGE, ZRANK) do this in logarithmic time and handle millions of members on one node.
  • Persistence: keep scores in a database too (the sorted set is a fast view that can be rebuilt).
  • Scale: split by season or time window (daily, weekly boards), by region or game mode, or by score range; compute a global top-N by merging each shard's top results.
  • Approximate ranks for players far from the top are often enough ("you are in the top 12 percent"); exact rank is needed only near the top.
  • Ties: break by earliest time or id so ordering is deterministic.
  • Cheating and fairness: validate scores server-side.

  3. Live comments and reactions

  A live event with millions of viewers sends a flood of reactions that everyone expects to see "live".

  100%

  Figure SDA-ADS-10-3 · Reactions at massive scale · © forcsguy.com

  For live comments (text), you cannot aggregate, so:

  • Moderate and rank: filter spam, show a sampled or top subset to big audiences.
  • Partition by chat room and cap rates per user.
  • Fan-out via a pub/sub layer to connection gateways, which hold the WebSocket connections (see the chat lesson).
  • Store comments in a log or wide-column store ordered by time for replay and history.

  Key tricks across all of these: aggregate before you fan out, sample, throttle clients, batch writes, and accept approximate, eventually consistent displays while keeping money-related counts exact elsewhere.

  Questions to ask in an interview

  How exact must the number be? How fast must it be visible? What is the write rate per key (hot key)? What happens on failure (can we lose a second of counts)? Can we pre-aggregate at the edge? These questions steer you from "a table with a counter column" to a design that survives a viral moment.

  Real-world reading

  Related reading

  • Scale with Redis ClusterRedis · Redis Ltd.Documentation
  • Redis persistenceRedis · Redis Ltd.Documentation
  • Arpit Bhayani: Asli EngineeringArpit Bhayani · Asli EngineeringYouTube
  • Moving Food Feed from Redis to Cassandra at ZomatoZomato engineers · ZomatoCase Studies

  Show 6 moreShow fewer

  • Improving key expiration in Redis at TwitterTwitter engineers · TwitterCase Studies
  • Scaling Redis at TwitterTwitter engineers · TwitterCase Studies
  • Ratequeue: Core Queueing-And-Rate-Limiting System at TwilioTwilio engineers · TwilioCase Studies
  • Scaling (a NSFW site) to 200 Million Views A Day And Beyond - Eric Pickup, Lead Platform Developer at MindGeekMindGeekYouTube
  • How GIPHY Delivers a GIF to 300 Millions Users - Alex Hoang and Nima Khoshini, Services Engineers at GIPHYGIPHY engineers · GIPHYCase Studies
  • UC Berkeley CS 162: Operating SystemsBerkeley EECS · UC BerkeleyCourses

  Open this lesson with its quiz and exercise