Design Rate Limiter and Design Twitter Feed
Apply the framework to two canonical design problems: token-bucket/sliding-window rate limiting and a fan-out-on-write vs fan-out-on-read news feed.
Design Rate Limiter and Design Twitter Feed is a free DSA Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Why Rate Limiting Is Essential
Rate limiting controls the number of requests a client can make to an API in a given time window. Without it, a single misbehaving client (or a DDoS attack) can saturate server resources, degrading service for all users. Rate limiting also protects against brute-force attacks, prevents API scraping, and enforces fair use of shared resources.
Common rate-limiting granularities: per user ID, per API key, per IP address, per endpoint, or a combination. Typical limits: 100 requests per minute per user, 1000 per hour per API key. The rate limiter must be fast (adding <1ms overhead) and distributed (consistent across all API server replicas).
# Rate limiting scenarios
use_cases = [
('API authentication endpoint', '5 attempts per 15 min per IP', 'Brute-force protection'),
('Public search API', '100 requests per minute per key', 'Fair use enforcement'),
('Email sending', '50 emails per hour per user', 'Spam prevention'),
('Payment processing', '10 transactions per second per account', 'Fraud prevention'),
('File upload', '5 uploads per minute per user', 'Resource quota'),
('Notification service', '1000 pushes per second globally', 'Cost control'),
]
print(f'{'Endpoint/Feature':35s} {'Limit':40s} {'Reason'}')
print('-'*95)
for endpoint, limit, reason in use_cases:
print(f'{endpoint:35s} {limit:40s} {reason}')Rate Limiting Algorithm 1: Token Bucket
The token bucket algorithm maintains a bucket with a maximum capacity of N tokens. Tokens are added at a fixed rate (e.g., 10 per second). Each request consumes one token. If the bucket is empty, the request is rejected. If below capacity, it is accepted and the token is consumed.
Token bucket allows bursting: if no requests come in for 5 seconds, the bucket fills up to N tokens, and then N requests can come in immediately. This is appropriate for APIs where occasional bursts are acceptable. The two parameters are capacity (burst size) and refill rate.
import time
class TokenBucket:
def __init__(self, capacity, refill_rate):
self.capacity = capacity # max tokens (burst size)
self.refill_rate = refill_rate # tokens added per second
self.tokens = capacity # start full
self.last_refill = time.time()
def allow(self):
now = time.time()
elapsed = now - self.last_refill
# Refill tokens based on elapsed time
self.tokens = min(self.capacity,
self.tokens + elapsed * self.refill_rate)
self.last_refill = now
if self.tokens >= 1:
self.tokens -= 1
return True # request allowed
return False # rate limited
bucket = TokenBucket(capacity=5, refill_rate=2) # 2 tokens/sec, burst=5
for i in range(8):
allowed = bucket.allow()
print(f'Request {i+1}: {"ALLOWED" if allowed else "REJECTED"} (tokens={bucket.tokens:.1f})')
time.sleep(0.1) # 0.1s between requestsRate Limiting Algorithm 2: Sliding Window Log
The sliding window log stores a timestamp for every request in a sorted set. For each new request, remove timestamps older than the window start, then check if the count of remaining timestamps is below the limit. If yes, add the current timestamp and allow; otherwise reject.
This is precise — it counts exactly how many requests occurred in the last N seconds. The trade-off: high memory usage (one entry per request per user). For a limit of 1000 requests/minute with 100K users, the worst case is 100M log entries. Not suitable for very high traffic unless combined with sharding.
import time
from collections import deque
class SlidingWindowLog:
def __init__(self, limit, window_seconds):
self.limit = limit
self.window = window_seconds
self.logs = {} # user_id -> deque of timestamps
def allow(self, user_id):
now = time.time()
if user_id not in self.logs:
self.logs[user_id] = deque()
log = self.logs[user_id]
window_start = now - self.window
# Remove expired timestamps
while log and log[0] <= window_start:
log.popleft()
# Check limit
if len(log) < self.limit:
log.append(now)
return True
return False
limiter = SlidingWindowLog(limit=3, window_seconds=10)
for i in range(5):
allowed = limiter.allow('user123')
print(f'Request {i+1}: {"ALLOWED" if allowed else "REJECTED"}')
time.sleep(0.5)Rate Limiting Algorithm 3: Sliding Window Counter
The sliding window counter approximates the sliding window using two buckets — the current minute and the previous minute — weighted by how far into the current minute we are. This reduces memory from O(requests) to O(1) per user while closely approximating the exact sliding window count.
Formula: estimated_count = prev_count × (1 - fraction_of_window_elapsed) + curr_count. If this estimated count exceeds the limit, reject. This is the algorithm used by Cloudflare and Kong at scale due to its O(1) memory per user and high accuracy.
import time
import math
class SlidingWindowCounter:
def __init__(self, limit, window_seconds=60):
self.limit = limit
self.window = window_seconds
self.buckets = {} # user_id -> {prev_count, curr_count, curr_window_start}
def allow(self, user_id):
now = time.time()
window_start = int(now // self.window) * self.window
if user_id not in self.buckets or self.buckets[user_id]['window'] < window_start - self.window:
self.buckets[user_id] = {'prev': 0, 'curr': 0, 'window': window_start}
elif self.buckets[user_id]['window'] < window_start:
self.buckets[user_id] = {'prev': self.buckets[user_id]['curr'], 'curr': 0, 'window': window_start}
b = self.buckets[user_id]
fraction = (now - window_start) / self.window
estimated = b['prev'] * (1 - fraction) + b['curr']
if estimated < self.limit:
b['curr'] += 1
return True
return False
limiter = SlidingWindowCounter(limit=5, window_seconds=10)
for i in range(7):
print(f'Request {i+1}: {"OK" if limiter.allow("user1") else "RATE LIMITED"}')
time.sleep(0.3)Distributed Rate Limiting with Redis
For a distributed system with multiple app servers, rate limiting must be centralised — otherwise each server tracks its own count and the limits are effectively multiplied by the server count. Redis with atomic operations is the standard solution: use INCR and EXPIRE for a fixed-window counter, or ZADD and ZCOUNT for a sliding-window log.
The Lua script approach makes multiple Redis operations atomic, preventing race conditions where two servers increment simultaneously just below the limit. Redis processes Lua scripts as a single command, ensuring atomicity without distributed locks.
# Distributed rate limiting with Redis (pseudocode / simulation)
# Fixed window counter using Redis INCR + EXPIRE
def redis_fixed_window(redis_client, user_id, limit, window_sec):
key = f'rl:{user_id}:{int(time.time() // window_sec)}'
count = redis_client.incr(key) # atomic increment
if count == 1:
redis_client.expire(key, window_sec) # set TTL on first request
return count <= limit
# Sliding window with sorted set
def redis_sliding_window(redis_client, user_id, limit, window_sec):
now = time.time()
key = f'rl:{user_id}'
# Remove old entries, count recent, add current
# Atomic with Lua: multi-step operation
lua_script = '''
local key = KEYS[1]
local now = ARGV[1]
local window = ARGV[2]
local limit = ARGV[3]
redis.call('ZREMRANGEBYSCORE', key, '-inf', now - window)
local count = redis.call('ZCARD', key)
if count < tonumber(limit) then
redis.call('ZADD', key, now, now)
redis.call('EXPIRE', key, window)
return 1 -- allowed
end
return 0 -- rejected
'''
print('Redis Lua script ensures atomicity across ZREM + ZCARD + ZADD')Designing Twitter Feed: Requirements
Let us design a Twitter-like news feed system. Functional requirements: users can post tweets (up to 280 characters), follow other users, and view a feed of tweets from people they follow, ordered by recency. Non-functional: 300M daily active users, 500M tweets/day, feed must load in <2 seconds, read:write ratio ~100:1.
Capacity estimates: 500M tweets/day ÷ 86400 ≈ 5800 tweets/second. Reads ≈ 580K/second. Each tweet ≈ 300 bytes; 500M × 300B = 150 GB/day of new tweet storage. Feed aggregation is the core engineering challenge.
# Twitter feed requirements and estimates
reqs = {
'Functional': [
'Post tweet (text, image, video)',
'Follow/unfollow users',
'View home feed (tweets from followees, newest first)',
'View user timeline (all tweets by one user)',
'Like and retweet',
'Search tweets (basic keyword)',
],
'Non-functional': [
'300M DAU, 500M tweets/day => 5800 writes/sec',
'100:1 read:write => 580K feed reads/sec',
'Feed load < 2 seconds (p95)',
'99.99% availability',
'Tweets retained indefinitely (tweets never deleted by default)',
],
'Estimates': [
'Storage: 500M tweets * 300B = 150 GB/day, 54 TB/year',
'Media: separate object store (S3), CDN-served',
'Feed cache: 300M users * top-100-tweets * 100B = 3 TB (hot feeds in Redis)',
],
}
for category, items in reqs.items():
print(f'{category}:')
for item in items: print(f' - {item}')
print()Fan-Out on Write: Precomputed Feeds
In fan-out on write, when user A posts a tweet, the system immediately distributes it to the feed of every follower. When a follower requests their feed, it is already precomputed and stored in Redis — a simple Redis list read with O(k) where k is the feed size (typically capped at 1000 tweets).
The challenge: celebrities with millions of followers create massive fan-out operations. Justin Bieber posting a tweet requires writing to 100M+ follower feeds simultaneously — a real problem Twitter faced and called the 'celebrity problem'. The write fan-out service must be async and queue-based to handle these spikes.
# Fan-out on write (push model)
fan_out_steps = [
'1. User posts tweet => write to tweets table (source of truth)',
'2. Publish event to message queue (Kafka topic: tweet-created)',
'3. Fan-out workers consume from queue:',
' a. Fetch list of followers from follows table',
' b. For each follower: LPUSH feed:{follower_id} tweet_id',
' c. Trim feed to last 1000 tweets: LTRIM feed:{follower_id} 0 999',
'4. Feed read: LRANGE feed:{user_id} 0 99 => hydrate tweet_ids => response',
]
for step in fan_out_steps:
print(step)
print('\nPros:')
print(' - Feed reads are O(1): just read from Redis list')
print(' - Feed is always sorted by recency automatically')
print('\nCons:')
print(' - Celebrities with 100M followers => 100M Redis writes per tweet')
print(' - Fan-out lag: followers may see tweet 10-30 seconds late at peak')
print(' - Inactive users waste Redis storage for precomputed feeds')Hybrid Fan-Out: Solving the Celebrity Problem
The hybrid approach combines fan-out on write for regular users and fan-out on read for celebrities. A user is classified as a celebrity if their follower count exceeds a threshold (e.g., 1 million followers). For regular users, tweets are pushed to all follower feeds at post time. For celebrities, their tweets are NOT pushed; instead, when a follower reads their feed, the system fetches the celebrity's recent tweets and merges them with the precomputed feed.
This hybrid model is close to what Twitter actually uses. The merge step is fast because celebrities post rarely and the merge is O(f) where f is the number of celebrity accounts the user follows (typically small).
# Hybrid fan-out implementation sketch
CELEBRITY_THRESHOLD = 1_000_000 # followers > 1M => celebrity
def on_post_tweet(user_id, tweet_id, follower_count):
if follower_count <= CELEBRITY_THRESHOLD:
# Fan-out to all followers (async via Kafka)
print(f'User {user_id}: fan-out tweet {tweet_id} to {follower_count} followers')
# => queue to fan-out workers
else:
print(f'Celebrity {user_id}: tweet {tweet_id} stored in timeline only')
# => only write to tweets table + user timeline
# => followers get it on demand when reading feed
def get_home_feed(user_id, followees):
# 1. Get precomputed feed (fan-out on write tweets)
precomputed = f'LRANGE feed:{user_id} 0 499' # up to 500 tweets
# 2. Find celebrity followees
celebrity_followees = [u for u in followees if is_celebrity(u)]
# 3. Fetch recent tweets from celebrities (fan-out on read)
celebrity_tweets = []
for celeb in celebrity_followees:
tweets = f'GET tweets WHERE user_id={celeb} ORDER BY created_at DESC LIMIT 20'
celebrity_tweets.extend(tweets)
# 4. Merge and sort by recency
combined = merge_and_sort(precomputed, celebrity_tweets)
return combined[:100]
print('on_post_tweet for regular user:')
on_post_tweet('user123', 'tweet_abc', 500)
print('on_post_tweet for celebrity:')
on_post_tweet('celebrity456', 'tweet_xyz', 50_000_000)Twitter Feed: Complete Architecture
The complete Twitter feed architecture combines several systems:
- Tweet service: writes tweets to Cassandra (high write throughput, time-series)
- Fan-out service: async workers (Kafka consumers) that push tweet IDs to follower feeds in Redis
- Feed service: reads from Redis feed, hydrates tweet IDs to full tweet objects, merges celebrity tweets
- Follow service: manages the social graph (who follows whom) in a graph DB or sharded SQL
- Timeline service: serves a user's own tweets (separate from home feed)
# Twitter architecture summary
architecture = '''
[User] --> [API Gateway + Load Balancer]
|
+-----------+-----------+
| | |
[Tweet Svc] [Feed Svc] [Follow Svc]
| | |
[Cassandra] [Redis Feeds] [Graph DB]
| |
[Kafka] <-- [Fan-out
| Workers]
[S3 + CDN] (tweet_ids
(media) => follower
feed lists)
Key design choices:
- Tweets stored in Cassandra (PRIMARY KEY (user_id, created_at))
- Feed stored in Redis as list of tweet_ids per user (LPUSH/LTRIM/LRANGE)
- Fan-out via Kafka + workers (decoupled, retryable, scalable)
- Hybrid: regular users = push; celebrities = pull-on-read
- Hydration: tweet_ids -> full tweet objects via Cassandra read
'''
print(architecture)Rate Limiter Headers and Error Responses
A well-designed rate limiter communicates its limits to clients via HTTP response headers. This allows clients to implement retry-after logic and dashboards to display usage. Standard headers:
X-RateLimit-Limit: maximum requests allowed in the windowX-RateLimit-Remaining: requests remaining in current windowX-RateLimit-Reset: Unix timestamp when the window resetsRetry-After: seconds to wait before retrying (on 429 response)
The HTTP status code for rate-limited responses is 429 Too Many Requests.
# Rate limit response headers
def build_rate_limit_headers(limit, remaining, reset_timestamp, retry_after=None):
headers = {
'X-RateLimit-Limit': str(limit),
'X-RateLimit-Remaining': str(max(0, remaining)),
'X-RateLimit-Reset': str(int(reset_timestamp)),
}
if retry_after is not None:
headers['Retry-After'] = str(retry_after)
return headers
import time
# Simulated response for allowed request
headers = build_rate_limit_headers(
limit=100,
remaining=73,
reset_timestamp=time.time() + 45
)
print('Allowed request headers:')
for k, v in headers.items():
print(f' {k}: {v}')
# Rate limited response
headers_429 = build_rate_limit_headers(
limit=100,
remaining=0,
reset_timestamp=time.time() + 30,
retry_after=30
)
print('\n429 Too Many Requests headers:')
for k, v in headers_429.items():
print(f' {k}: {v}')Comparing Rate Limiting Algorithms
Summary comparison of all rate limiting algorithms to help you choose in interviews:
- Token Bucket: allows bursting, smooth refill rate. Best for APIs where occasional bursts are acceptable (most common choice).
- Leaky Bucket: processes requests at a fixed output rate regardless of burst. Best for shaping traffic to a constant stream.
- Fixed Window Counter: simplest, O(1) space. Problem: double-the-limit burst at window boundary (e.g., 100 at 11:59 + 100 at 12:00).
- Sliding Window Log: most accurate, no boundary spike. Problem: O(requests) memory.
- Sliding Window Counter: approximates sliding log with O(1) space. Used by Cloudflare.
# Algorithm comparison matrix
comparison = [
('Token Bucket', 'Allows bursts', 'O(1)', 'Most APIs, default choice'),
('Leaky Bucket', 'Smooth output rate', 'O(1)', 'Traffic shaping, message queues'),
('Fixed Window Counter', 'Very simple', 'O(1)', 'Low-traffic, approximate OK'),
('Sliding Window Log', 'Most accurate', 'O(requests)', 'High-accuracy, low traffic'),
('Sliding Window Counter','Approximate+fast', 'O(1)', 'High-traffic, Cloudflare-style'),
]
print(f'{'Algorithm':30s} {'Burst Handling':20s} {'Memory':15s} {'Use Case'}')
print('-'*85)
for name, burst, mem, use in comparison:
print(f'{name:30s} {burst:20s} {mem:15s} {use}')Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: rate limiters use token bucket (allows bursting), sliding window counter (O(1) memory), or sliding window log (most accurate) to control request rates, and Redis atomic operations enable distributed rate limiting, Twitter feed uses fan-out on write to pre-compute follower feeds in Redis for fast reads, with a hybrid pull model for celebrity accounts to avoid massive write amplification. Next up we enter the capstone section with a pattern recognition cheat sheet that maps problem signals to the algorithm patterns that solve them fastest.
Frequently asked questions
Is the “Design Rate Limiter and Design Twitter Feed” lesson free?
Yes — the full text of “Design Rate Limiter and Design Twitter Feed” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Design Rate Limiter and Design Twitter Feed”?
Apply the framework to two canonical design problems: token-bucket/sliding-window rate limiting and a fan-out-on-write vs fan-out-on-read news feed. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Design Rate Limiter and Design Twitter Feed” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- The System Design Interview Framework
- Scalable Data Storage: SQL vs NoSQL
- Caching, CDNs, and Load Balancing
- Design Rate Limiter and Design Twitter Feed