notexOPENOverview
Notex/Systems/Data gathering service
13.09LESSON 09 OF 13 · 3 MIN READ

Data gathering service

Always free to read
SECTION VIDEOData gathering service

Video coming soon. Start with the reading below.

COMING SOON

In our previous design, whenever a user types a search query, data is updated in real-time. This approach is not practical for the following two reasons:

  • Users may enter billions of queries per day. Updating the trie on every query significantly slows down the query service.
  • Top suggestions may not change much once the trie is built. Thus, it is unnecessary to update the trie frequently. To design a scalable data gathering service, we examine where data comes from and how data is used. Real-time applications like Twitter require up to date autocomplete suggestions. However, autocomplete suggestions for many Google keywords might not change much on a daily basis.

Despite the differences in use cases, the underlying foundation for data gathering service remains the same because data used to build the trie is usually from analytics or logging services.

Figure 13-9 shows the redesigned data gathering service. Each component is examined one by one.

Design a search autocomplete system — original diagram 174

Analytics Logs. It stores raw data about search queries. Logs are append-only and are not indexed. Table 13-3 shows an example of the log file.

Design a search autocomplete system — original diagram 175

Aggregators. The size of analytics logs is usually very large, and data is not in the right format. We need to aggregate data so it can be easily processed by our system.

Depending on the use case, we may aggregate data differently. For real-time applications such as Twitter, we aggregate data in a shorter time interval as real-time results are important. On the other hand, aggregating data less frequently, say once per week, might be good enough for many use cases. During an interview session, verify whether real-time results are important. We assume trie is rebuilt weekly.

Aggregated Data. Table 13-4 shows an example of aggregated weekly data. “time” field represents the start time of a week. “frequency” field is the sum of the occurrences for the corresponding query in that week.

Design a search autocomplete system — original diagram 176

Workers. Workers are a set of servers that perform asynchronous jobs at regular intervals. They build the trie data structure and store it in Trie DB.

Trie Cache. Trie Cache is a distributed cache system that keeps trie in memory for fast read. It takes a weekly snapshot of the DB.

Trie DB. Trie DB is the persistent storage. Two options are available to store the data:

  1. Document store: Since a new trie is built weekly, we can periodically take a snapshot of it, serialize it, and store the serialized data in the database. Document stores like MongoDB [4] are good fits for serialized data.
  1. Key-value store: A trie can be represented in a hash table form [4] by applying the following logic:
  • Every prefix in the trie is mapped to a key in a hash table.
  • Data on each trie node is mapped to a value in a hash table. Figure 13-10 shows the mapping between the trie and hash table.
Design a search autocomplete system — original diagram 177

In Figure 13-10, each trie node on the left is mapped to the <key, value> pair on the right. If you are unclear how key-value stores work, refer to Chapter 6: Design a key-value store.

Progress is saved on this device.
KEEP EXPLORING

One note leads to another.

Back to the library →
⌕
Search across the entire library ⌘ K