Concevoir un limiteur de débit et un fil Twitter
Appliquez le cadre à deux problèmes classiques de conception : la limitation de débit par seau de jetons ou fenêtre glissante, et un fil d’actualités avec diffusion à l’écriture ou à la lecture.
Concevoir un limiteur de débit et un fil Twitter est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.
Pourquoi la limitation du débit est essentielle
La limitation du débit contrôle le nombre de requêtes qu’un client peut envoyer à une interface de programmation pendant une fenêtre temporelle donnée. Sans elle, un seul client défaillant (ou une attaque par déni de service distribué) peut saturer les ressources du serveur et dégrader le service pour tous les utilisateurs. La limitation du débit protège également contre les attaques par force brute, empêche l’extraction automatisée de données et impose une utilisation équitable des ressources partagées.
Granularités courantes de limitation : par ID utilisateur, par clé d’interface de programmation, par adresse IP, par point d’accès ou selon une combinaison de ces critères. Limites typiques : 100 requêtes par minute et par utilisateur, 1000 par heure et par clé d’interface de programmation. Le limiteur de débit doit être rapide (ajouter une surcharge de <1ms) et réparti (cohérent sur toutes les répliques des serveurs d’interface de programmation).
# 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}')Algorithme de limitation 1 : seau de jetons
L’algorithme du seau de jetons maintient un seau d’une capacité maximale de N jetons. Les jetons sont ajoutés à un débit constant (par exemple, 10 par seconde). Chaque requête consomme un jeton. Si le seau est vide, la requête est rejetée. Si le nombre de jetons est inférieur à la capacité, la requête est acceptée et le jeton est consommé.
Le seau de jetons autorise les pics de trafic : si aucune requête n’arrive pendant 5 secondes, le seau se remplit jusqu’à N jetons, puis N requêtes peuvent arriver immédiatement. Cette méthode convient aux interfaces de programmation où des pics occasionnels sont acceptables. Les deux paramètres sont la capacité (taille du pic) et le débit de rechargement.
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 requestsAlgorithme de limitation 2 : journal de fenêtre glissante
Le journal de fenêtre glissante stocke un horodatage pour chaque requête dans un ensemble trié. Pour chaque nouvelle requête, il faut effectuer remove (supprimer) les horodatages antérieurs au début de la fenêtre, puis vérifier si le nombre d’horodatages restants est inférieur à la limite. Si c’est le cas, ajouter l’horodatage actuel et appeler allow (autoriser) ; sinon, rejeter.
Cette méthode est précise : elle compte exactement le nombre de requêtes survenues au cours des N dernières secondes. Le compromis est une utilisation élevée de la mémoire (une entrée par requête et par utilisateur). Pour une limite de 1000 requêtes par minute avec 100K utilisateurs, le pire cas atteint 100M entrées de journal. Cette méthode ne convient pas à un trafic très élevé, sauf si elle est associée au partitionnement.
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)Algorithme de limitation 3 : compteur de fenêtre glissante
Le compteur de fenêtre glissante approxime la fenêtre glissante à l’aide de deux seaux — la minute actuelle et la minute précédente — pondérés selon la progression dans la minute actuelle. Cela réduit la mémoire de O(requests) à O(1) par utilisateur, tout en approchant étroitement le décompte exact de la fenêtre glissante.
Formule : estimated_count = prev_count × (1 - fraction_of_window_elapsed) + curr_count. Si ce décompte estimé dépasse la limite, rejeter. Il s’agit de l’algorithme utilisé par Cloudflare et Kong à grande échelle, grâce à sa mémoire en O(1) par utilisateur et à sa grande précision.
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)Limitation du débit répartie avec Redis
Dans un système réparti comportant plusieurs serveurs applicatifs, la limitation du débit doit être centralisée ; sinon, chaque serveur suit son propre décompte et les limites sont effectivement multipliées par le nombre de serveurs. Redis et ses opérations atomiques constituent la solution standard : utiliser INCR et EXPIRE pour un compteur à fenêtre fixe, ou ZADD et ZCOUNT pour un journal de fenêtre glissante.
L’approche par script Lua rend plusieurs opérations Redis atomiques et empêche les conditions de concurrence dans lesquelles deux serveurs incrémentent simultanément le compteur juste en dessous de la limite. Redis traite les scripts Lua comme une seule commande, ce qui garantit l’atomicité sans verrous répartis.
# 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')Conception d’un fil Twitter : exigences
Concevons un système de fil d’actualités comparable à Twitter. Exigences fonctionnelles : les utilisateurs peuvent publier des messages (jusqu’à 280 caractères), suivre d’autres utilisateurs et consulter un fil de messages des personnes qu’ils suivent, classé par récence. Exigences non fonctionnelles : 300 millions d’utilisateurs actifs quotidiennement, 500 millions de messages par jour, chargement du fil en <2 secondes, ratio lecture/écriture d’environ 100:1.
Estimations de capacité : 500 millions de messages par jour ÷ 86400 ≈ 5800 messages par seconde. Lectures ≈ 580K par seconde. Chaque message fait environ 300 octets ; 500 millions × 300 octets = 150 GB de nouveau stockage de messages par jour. L’agrégation du fil constitue le principal défi d’ingénierie.
# 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()Propagation à l’écriture : fils précalculés
Dans la propagation à l’écriture, lorsqu’un utilisateur A publie un message, le système le distribue immédiatement dans le fil de chacun de ses abonnés. Lorsqu’un abonné demande son fil, celui-ci est déjà précalculé et stocké dans Redis : il suffit de lire une liste Redis en O(k), où k est la taille du fil (généralement limitée à 1000 messages).
Le défi vient des célébrités comptant des millions d’abonnés, qui créent des opérations de propagation massives. Lorsque Justin Bieber publie un message, il faut l’écrire simultanément dans les fils de plus de 100 millions d’abonnés — un problème réel auquel Twitter a été confronté et qu’il a appelé le « problème des célébrités ». Le service de propagation des écritures doit être asynchrone et fondé sur une file d’attente pour gérer ces pics.
# 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')Propagation hybride : résolution du problème des célébrités
L’approche hybride combine la propagation à l’écriture pour les utilisateurs ordinaires et la propagation à la lecture pour les célébrités. Un utilisateur est classé comme célébrité si son nombre d’abonnés dépasse un seuil (par exemple, 1 million d’abonnés). Pour les utilisateurs ordinaires, les messages sont envoyés dans tous les fils d’abonnés au moment de leur publication. Pour les célébrités, leurs messages sont marqués NOT et ne sont pas propagés ; à la place, lorsqu’un abonné consulte son fil, le système récupère les messages récents de la célébrité et les fusionne avec le fil précalculé.
Ce modèle hybride est proche de celui qu’utilise réellement Twitter. L’étape de fusion est rapide, car les célébrités publient rarement et la fusion est en O(f), où f est le nombre de comptes de célébrités suivis par l’utilisateur (généralement peu élevé).
# 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)Fil Twitter : architecture complète
L’architecture complète du fil Twitter combine plusieurs systèmes :
- Service de messages : écrit les messages dans Cassandra (débit d’écriture élevé, séries temporelles)
- Service de propagation : travailleurs asynchrones (consommateurs Kafka) qui envoient les identifiants de messages dans les fils des abonnés sur Redis
- Service de fil : lit le fil depuis Redis, transforme les identifiants de messages en objets de messages complets et fusionne les messages des célébrités
- Service des abonnements : gère le graphe social (qui suit qui) dans une base de données de graphes ou une base SQL partitionnée
- Service de chronologie : fournit les messages d’un utilisateur (séparément du fil d’accueil)
# 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)En-têtes du limiteur de débit et réponses d’erreur
Un limiteur de débit bien conçu communique ses limites aux clients au moyen d’en-têtes de réponse du protocole de transfert hypertexte. Cela permet aux clients d’implémenter une logique de nouvelle tentative et aux tableaux de bord d’afficher l’utilisation. En-têtes standard :
X-RateLimit-Limit: nombre maximal de requêtes autorisées dans la fenêtreX-RateLimit-Remaining: nombre de requêtes restantes dans la fenêtre actuelleX-RateLimit-Reset: horodatage Unix auquel la fenêtre est réinitialiséeRetry-After: nombre de secondes à attendre avant une nouvelle tentative (pour une réponse 429)
Le code d’état du protocole de transfert hypertexte pour les réponses limitées est 429 Trop de requêtes.
# 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}')Comparaison des algorithmes de limitation du débit
Comparaison récapitulative de tous les algorithmes de limitation du débit pour vous aider à choisir lors des entretiens :
- Seau de jetons : autorise les rafales et offre un taux de remplissage régulier. Idéal pour les interfaces de programmation d'applications où les rafales occasionnelles sont acceptables (l'option la plus courante).
- Seau percé : traite les requêtes à un débit de sortie fixe, quelle que soit la rafale. Idéal pour façonner le trafic en un flux constant.
- Compteur à fenêtre fixe : le plus simple, avec un espace O(1). Problème : une rafale égale au double de la limite à la frontière de la fenêtre (par exemple, 100 à 11:59 + 100 à 12:00).
- Journal de fenêtre glissante : le plus précis, sans pic à la frontière. Problème : mémoire en O(requêtes).
- Compteur à fenêtre glissante : approxime le journal de fenêtre glissante avec un espace O(1). Utilisé par 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}')Vérification rapide
Vérifiez votre compréhension des concepts de structures de données et d'algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris : les limiteurs de débit utilisent un seau de jetons (qui autorise les rafales), un compteur à fenêtre glissante (mémoire O(1)) ou un journal de fenêtre glissante (le plus précis) pour contrôler le débit des requêtes, et les opérations atomiques de Redis permettent la limitation distribuée du débit ; le fil Twitter utilise une diffusion à l'écriture pour précalculer les fils des abonnés dans Redis afin d'accélérer les lectures, avec un modèle hybride de récupération pour les comptes de célébrités afin d'éviter une amplification massive des écritures. Nous allons ensuite entrer dans la section finale avec une fiche mémo de reconnaissance des motifs qui associe les signaux des problèmes aux motifs algorithmiques qui les résolvent le plus rapidement.
Apprends Python avec un tuteur IA — gratuit
Écris et exécute du vrai code dans ton navigateur, obtiens de l'aide instantanée d'un tuteur IA disponible 24h/24, et reprends là où tu t'es arrêté sur le web ou dans l'app.
- Cours
- 30
- Leçons
- 120
Questions Fréquemment Posées
La leçon « Concevoir un limiteur de débit et un fil Twitter » est-elle gratuite ?
Oui — le texte complet de « Concevoir un limiteur de débit et un fil Twitter » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Concevoir un limiteur de débit et un fil Twitter » ?
Appliquez le cadre à deux problèmes classiques de conception : la limitation de débit par seau de jetons ou fenêtre glissante, et un fil d’actualités avec diffusion à l’écriture ou à la lecture. Tu pratiques DSA Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer DSA Interview Prep ?
Aucune expérience préalable n'est requise. DSA Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.
Combien de temps prend la leçon « Concevoir un limiteur de débit et un fil Twitter » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon DSA Interview Prep ?
Oui. Chaque leçon DSA Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Cadre d’entretien de conception de systèmes
- Stockage de données évolutif : SQL ou NoSQL
- Mise en cache, CDN et équilibrage de charge
- Concevoir un limiteur de débit et un fil Twitter