Rate limiter and Twitter search

A rate limiter protects a service by refusing excess requests. Search finds the few documents that match among billions. One sits in front of every system and must add almost no delay. The other is a system in its own right whose core idea, the inverted index, powers nearly every search product.

Limiting requests prevents abuse and denial of service, keeps cost under control, and gives every user a fair share. Without it, one buggy client can take down a service for everyone.

It can live in three places: in the client (unreliable, since it can be bypassed), inside each service (duplicated and inconsistent), or at the gateway in front of everything (the common choice, since one place enforces one policy). Rules usually combine a key and a limit: per user, per IP address, or per endpoint, for example 100 requests per minute per user and 10 login attempts per hour per IP.

When a request is refused, reply with status 429 Too Many Requests and headers such as how long to wait, so well-behaved clients can slow down.

Token bucket. A bucket holds up to a maximum number of tokens and refills at a steady rate. Each request takes one token, and with none left the request is refused. It allows short bursts up to the bucket size, then enforces the average rate. Memory is tiny: two numbers per key, the token count and the last refill time.

Leaky bucket. Requests join a queue that drains at a fixed rate. It smooths bursts into a constant output, which suits protecting a fragile backend, but a burst can fill the queue and cause delay or drops.

Fixed window counter. Count requests in each fixed interval, such as each minute, and refuse over the limit. It is very simple, but has a flaw: a client can send the full limit at the end of one window and the full limit again at the start of the next, so twice the limit passes in a short span.

Sliding window log. Store a timestamp for each request and count those in the last interval. It is exact, but stores one entry per request, which is costly.

Sliding window counter. Combine two fixed windows, weighting the previous one by how much of it still overlaps the sliding interval. It is a close approximation with only two counters per key.

Rule of thumb: token bucket for general APIs that allow bursts, sliding window counter when accuracy at the boundary matters, and avoid the sliding log at high volume.

For sizing: 10 million users, each with a token bucket of about 16 bytes plus a key, comes to a few hundred megabytes. A sliding log storing 100 timestamps of 8 bytes per user would be 10M x 100 x 8 B, about 8 GB.

With many gateway servers, counts must be shared, or a user spreads requests across servers to evade the limit. A fast shared store such as an in-memory key value store holds the counters.

The hazard is a race: two servers read a counter of 99, both allow, and both write 100. The read, decision and write must be one atomic step, using an atomic increment or a small script executed inside the store. Fetching the count and updating it in separate steps is a bug.

Other practical points:

• Latency: a network call per request costs time, so keep the store close, and consider allowing a small local allowance and syncing counts periodically, accepting a slightly loose limit.
• Fail open or closed? If the counter store is down, either allow everything (risk of overload) or block everything (outage). For most public APIs, fail open, but fail closed for sensitive actions like logins.
• Rules as data: load limits from configuration, and change them without redeploying.
• Clear feedback: return remaining quota and reset time in headers.

Find tweets containing given words, newest or most relevant first, within a fraction of a second, including tweets posted moments ago. Assume 100 million new tweets per day, about 1,200 per second. The index for the last week, about 700 million tweets with about ten searchable words each, needs roughly 700M x 10 x 8 bytes, around 56 GB of postings. That is small enough to hold the recent index in memory across a handful of machines.

Scanning every tweet for a word is hopeless. An inverted index flips the relationship: for each word, store the list of documents containing it, called a posting list.

• "coffee": tweets 105, 230, 987
• "tokyo": tweets 230, 411, 987

Before indexing, text is cleaned: split into words (tokenization), lowercased, optionally reduced to a root form (stemming), and common words may be dropped. A query for "coffee tokyo" finds the posting list of each word and intersects them. If lists are sorted by id, intersection is a single linear merge, and tweets 230 and 987 match. Sorting posting lists by time means the newest matches come first, and the search can stop once it has enough results.

One machine cannot hold or serve everything, so split the index.

• By document: each shard indexes a subset of tweets, with all words for those tweets. A query is sent to every shard, each returns its best matches, and a coordinator merges them (scatter-gather). Load is even and a shard failure loses only part of the results.
• By term: each shard holds the posting lists for certain words. A query touches only the shards for its words, but popular words create hot spots and long lists must be moved across the network to intersect.

Document partitioning is the usual choice. Replicate each shard for throughput and availability.

New tweets must be searchable within seconds. Keep recent tweets in a fast in-memory segment of the index that accepts writes, and periodically flush it into immutable on-disk segments that are merged in the background. Queries consult the memory segment and the segments on disk. Rank results by a blend of recency, the author's reputation and engagement such as likes, then re-rank the top few hundred with a richer model.

Cache results for popular queries for a few seconds, since trending searches repeat constantly, and handle deleted tweets by filtering them at read time.

Both designs add a thin, fast layer in front of heavier machinery, keep their hot data in memory, and rely on atomic operations or sorted structures to stay both fast and correct. Both also trade exactness for speed in places users never notice.