Part 5 of 8 · 1 min read
Data gathering
Logs, aggregators and workers.
Updating the trie on every search would be too slow, because there are billions of searches a day. And the top suggestions rarely change within a day. So the trie is built in batches. The book assumes a weekly rebuild, and notes that a real-time product would rebuild more often.
The pipeline has five parts.
- Analytics logs: raw, append-only records of each search.
- Aggregators: combine the logs into counts, for example the total frequency of each query in a week.
- Aggregated data: a table of query, week and frequency.
- Workers: servers that run at set times, build the trie from the aggregated data, and save it.
- Trie DB: durable storage for the trie. Two ways to store it. As a snapshot in a document store, serialised whole. Or as a key-value store, where each prefix is a key and the node's data is the value.
- Trie cache: a distributed in-memory copy of the trie for fast reads, refreshed from the database each week.
Sampling. Logging every search is costly. The book suggests logging one of every N searches. Counts stay close to the true shape, and cost falls. A worked example (made up): 100 million searches a day, with 1 of every 50 logged, gives 2 million records a day.
Aggregator
An aggregator is a job that combines many raw records into a smaller set of totals.
Example: a million log lines for "twitter" become one row: twitter, this week, 1,000,000.
Check yourself: 1. Why not update the trie on every search? 2. What do workers do? 3. How does sampling help?