设计限流器与 Twitter 信息流
将该框架应用于两个经典设计问题：令牌桶或滑动窗口限流，以及写时扇出与读时扇出的信息流。
设计限流器与 Twitter 信息流 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
限流为何至关重要
限流用于控制客户端在给定时间窗口内可以向接口发送的请求数量。如果没有限流，单个行为异常的客户端（或分布式拒绝服务攻击）就可能耗尽服务器资源，导致所有用户的服务质量下降。限流还可以防范暴力破解攻击、阻止接口抓取，并确保共享资源得到公平使用。
常见的限流粒度包括：按用户 ID、按接口密钥、按 IP 地址、按端点，或采用这些条件的组合。典型限制为：每位用户每分钟 100 个请求、每个接口密钥每小时 1000 个请求。限流器必须足够快速（增加的开销小于 1 毫秒），并且必须是分布式的（在所有接口服务器副本之间保持一致）。
# 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}')限流算法 1：令牌桶
令牌桶算法维护一个最多可容纳 N 个令牌的桶。令牌以固定速率添加（例如每秒 10 个）。每个请求消耗一个令牌。如果桶为空，请求就会被拒绝；如果尚未达到容量上限，请求就会被接受，并消耗一个令牌。
令牌桶允许突发请求：如果连续 5 秒没有请求到来，桶就会填充到 N 个令牌，此时可以立即处理 N 个请求。这适用于偶尔出现突发流量也可以接受的接口。两个参数分别是容量（突发请求数量）和补充速率。
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 requests限流算法 2：滑动窗口日志
滑动窗口日志会在有序集合中为每个请求保存一个时间戳。每当有新请求到来时，先移除早于窗口起点的时间戳，然后检查剩余时间戳的数量是否低于限制。如果是，则添加当前时间戳并允许请求；否则拒绝请求。
这种方法非常精确，能够准确统计最近 N 秒内发生的请求数量。代价是内存使用量较高（每位用户的每个请求都需要一个条目）。对于每分钟 1000 个请求、共 10 万名用户的限制，最坏情况下会产生 1 亿条日志记录。除非结合分片，否则不适合流量非常高的场景。
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)限流算法 3：滑动窗口计数器
滑动窗口计数器使用两个桶来近似滑动窗口：当前分钟和上一分钟的桶，并根据当前分钟已经经过的时间比例为上一分钟的计数加权。这样可以将每位用户的内存占用从 O(requests) 降低到 O(1)，同时非常接近精确的滑动窗口计数。
公式：estimated_count = prev_count × (1 - fraction_of_window_elapsed) + curr_count。如果估算计数超过限制，就拒绝请求。由于每位用户只需 O(1) 的内存且准确率很高，Cloudflare 和 Kong 在大规模场景中都采用了这一算法。
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)使用 Redis 实现分布式限流
对于包含多台应用服务器的分布式系统，限流必须集中执行，否则每台服务器都会分别跟踪自己的计数，实际限制会被服务器数量成倍放大。使用带有原子操作的 Redis 是标准方案：固定窗口计数器使用 INCR 和 EXPIRE，滑动窗口日志使用 ZADD 和 ZCOUNT。
使用 Lua 脚本可以让多个 Redis 操作保持原子性，避免两台服务器同时在刚好低于限制时递增计数而产生竞争条件。Redis 会将 Lua 脚本作为单个命令处理，因此无需分布式锁即可确保原子性。
# 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')设计 Twitter 信息流：需求
让我们设计一个类似 Twitter 的新闻信息流系统。功能需求：用户可以发布推文（最多 280 个字符）、关注其他用户，并按时间新旧查看所关注用户发布的推文信息流。非功能需求：每日活跃用户 3 亿，日发布推文 5 亿条，信息流必须在 2 秒内加载完成，读写比例约为 100:1。
容量估算：每天 5 亿条推文 ÷ 86400 ≈ 每秒 5800 条推文。读取请求约为每秒 58 万次。每条推文约 300 字节；5 亿 × 300B = 每天新增 150 GB 的推文存储空间。信息流聚合是核心工程挑战。
# 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()写入时扇出：预计算信息流
在写入时扇出模式中，用户 A 发布推文后，系统会立即将这条推文分发到每位关注者的信息流中。当关注者请求自己的信息流时，信息流已经预先计算好并存储在 Redis 中，只需读取 Redis 列表即可，复杂度为 O(k)，其中 k 是信息流大小（通常上限为 1000 条推文）。
挑战在于：拥有数百万关注者的名人用户会产生规模巨大的扇出操作。Justin Bieber 发布一条推文，就需要同时写入 1 亿多个关注者的信息流，这是真实困扰过 Twitter 的问题，被称为“名人问题”。写入扇出服务必须采用异步、基于队列的方式来处理这类峰值流量。
# 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')混合扇出：解决名人问题
混合方案将普通用户的写入时扇出与名人用户的读取时扇出结合起来。当某个用户的关注者数量超过阈值（例如 100 万名关注者）时，就会将其归类为名人用户。对于普通用户，推文会在发布时推送到所有关注者的信息流中。对于名人用户，其推文 NOT 会被推送；相反，当关注者读取自己的信息流时，系统会获取该名人用户最近的推文，并将其与预计算的信息流合并。
这种混合模型与 Twitter 实际采用的方式较为接近。合并步骤很快，因为名人用户很少发布推文，而且合并复杂度为 O(f)，其中 f 是用户所关注的名人账号数量（通常很少）。
# 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 信息流：完整架构
完整的 Twitter 信息流架构由多个系统组成：
- 推文服务：将推文写入 Cassandra（写入吞吐量高，适合时序数据）
- 扇出服务：异步工作进程（Kafka 消费者），将推文 ID 推送到 Redis 中的关注者信息流
- 信息流服务：从 Redis 信息流中读取数据，将推文 ID 补全为完整的推文对象，并合并名人用户的推文
- 关注服务：在图数据库或分片 SQL 数据库中管理社交关系图（谁关注谁）
- 时间线服务：提供用户自己的推文（与首页信息流分开）
# 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)限流器标头和错误响应
设计良好的限流器会通过 HTTP 响应标头向客户端传达限流信息。这样，客户端就能实现重试等待逻辑，仪表板也能显示用量。标准标头包括：
X-RateLimit-Limit：当前窗口内允许的最大请求数X-RateLimit-Remaining：当前窗口中剩余的请求数X-RateLimit-Reset：窗口重置时的 Unix 时间戳Retry-After：再次尝试前需要等待的秒数（响应状态为 429 时）
限流响应使用的 HTTP 状态码是429 请求过多。
# 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}')比较限流算法
所有限流算法的总结性比较，帮助您在面试中进行选择：
- 令牌桶：允许突发流量，补充速率平滑。最适合偶尔允许突发流量的应用程序接口（最常见的选择）。
- 漏桶：无论是否出现突发流量，都以固定的输出速率处理请求。最适合将流量整形成恒定的数据流。
- 固定窗口计数器：最简单，空间复杂度为 O(1)。问题：窗口边界处可能出现两倍于限制的突发流量（例如，11:59 时 100 个请求 + 12:00 时 100 个请求）。
- 滑动窗口日志：最准确，不会出现边界峰值。问题：需要 O(请求数) 的内存。
- 滑动窗口计数器：以 O(1) 的空间复杂度近似滑动窗口日志。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}')快速检查
测试您对本课中数据结构与算法——编程面试准备相关概念的理解。
课程回顾
您在本课中学到了：限流器使用令牌桶（允许突发流量）、滑动窗口计数器（O(1) 内存）或滑动窗口日志（最准确）来控制请求速率，而 Redis 的原子操作支持分布式限流，Twitter 信息流使用写入时扇出，在 Redis 中预先计算关注者的信息流以实现快速读取；对于名人账号，则采用混合式拉取模型，避免巨大的写放大。接下来我们将进入压轴部分，学习一份模式识别速查表，它会将问题信号映射到能最快解决问题的算法模式。
常见问题解答
「设计限流器与 Twitter 信息流」课时是免费的吗？
是的 — 「设计限流器与 Twitter 信息流」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「设计限流器与 Twitter 信息流」这节课中我会学到什么？
将该框架应用于两个经典设计问题：令牌桶或滑动窗口限流，以及写时扇出与读时扇出的信息流。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「设计限流器与 Twitter 信息流」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 系统设计面试框架
- 可扩展数据存储：SQL 与 NoSQL
- 缓存、CDN 与负载均衡
- 设计限流器与 Twitter 信息流