Fast Data in the Era of Big Data: Twitter's Real-Time Related Query Suggestion Architecture

1. INTRODUCTION

• The target is useful search assistance within ten minutes of a major news event, as query associations rapidly change.The paper frames responsiveness to newly formed associations as a balance against accumulating enough evidence for relevant suggestions.Source: §1 · p. 1
• The initial Hadoop-based solution missed the latency requirements, prompting a different architecture designed for real-time processing.The paper focuses on processing architecture, discussing the query and spelling-correction algorithms only as needed to explain it.Source: §1 · p. 1
• The case study describes two working systems—the initial Hadoop implementation and the deployed in-memory processing engine—and their lessons for Hadoop-based stacks.The paper presents practical experience rather than novel research contributions.Source: §1 · p. 1
• The authors identify a gap between architectures for big data and fast data, and discuss a future direction for bridging them.The paper’s progression moves from the Hadoop implementation to its deployed replacement and then to the need for a unified platform.Source: §1 · p. 2

2. BACKGROUND

• Related query suggestions offer queries of interest, while spelling correction is a special case that proposes a closely related form of the original query.Earlier work used clickthrough data, query–URL graphs, and successive queries in sessions; the paper adopts session-based statistical associations.Source: §2 · p. 2, §2.1 · p. 2

2.1 Related Work

• The paper situates query suggestion in decades of information-retrieval work, while noting that temporal relevance is not explicit in standard relevance treatments.Prior work also modeled temporal patterns in web queries, including bursts, query profiles, and forecast frequencies.Source: §2.1 · p. 2, §2.2 · p. 2

2.2 Real-Time Related Query Suggestion

• Real-time suggestions must be both timely and temporally relevant, since breaking-news query associations can matter only briefly and query streams mix fast and slow signals.The section describes a narrow window of maximal impact: suggestions made too early may lack evidence, while late suggestions may arrive after users discover related queries elsewhere.Source: §2.2 · pp. 2–3

2.3 Quantifying “Churn”

• 17% of the top 1000 query terms churn hourly, and 13% churn daily; during major events, “steve jobs” reached 15% of the query stream.The study used five-minute windows to balance responsiveness against the need to accumulate enough counts, with a target of relevant suggestions within ten minutes of an event.Source: §2.3 · p. 3

2.4 Algorithm Overview

• The system treats queries seen in the same context as evidence of a relationship, using search sessions and co-occurrence in tweets as contexts.It can use query order to suggest a follow-on query, and query similarity such as edit distance to identify likely spelling corrections; evidence is accumulated across contexts.Source: §2.4 · p. 3
• The design space includes association metrics, temporal decay functions, and methods for combining relevance signals, while the actual algorithm is not described.The paper limits queries to n-grams up to n = 3, but the resulting query-pair event space is still too large to materialize fully in memory; more sophisticated graph methods are future work.Source: §2.4 · pp. 3–4

3. TAKE ONE: HADOOP SOLUTION

• The first system used Pig and custom Java UDFs to aggregate search sessions, compute co-occurrence statistics, rank suggestions, and periodically load results into a lightweight frontend.The workflow ran on Hadoop; the frontend served incoming requests from the loaded output.Source: §3 · p. 4
• Suggestions arrived several hours after data collection, and even an optimistic end-to-end Hadoop path remained at a few tens of minutes.The authors judged this too slow for breaking-news suggestions.Source: §3 · p. 4, §3.2 · p. 6

3.1 Bottleneck One: Log Import

• Log import typically lagged by a couple of hours, sometimes six; incremental importing might cut this to tens of minutes but add complexity and small-file risk.Atomic delivery also made import wait for the slowest task to finish.Source: §3.1 · p. 5

3.2 Bottleneck Two: Hadoop

• The shared Hadoop cluster ran tens of thousands of jobs from dozens of teams, while resource growth lagged usage and FairScheduler did not provide predictable end-to-end completion times.The team needed bounded job completion times more than differentiated resource allocation.Source: §3.2 · p. 5
• A Pig prototype translated into roughly a dozen MapReduce jobs and took 15–20 minutes per hour of log data even without contention.Large-cluster job startup alone could take tens of seconds regardless of data volume.Source: §3.2 · p. 5
• Zipfian vocabulary distributions made hash-partitioned work uneven, so the slowest task in each chained MapReduce cycle could govern the end-to-end critical path.The Pig script chained a dozen or more Hadoop jobs.Source: §3.2 · p. 5

3.3 Revisiting the Decision to Use Hadoop

• An existing mature analytics platform, established Pig workflows, and reusable search-log scripts made Hadoop a quick, natural prototype starting point.The initial system also yielded insight into query-stream churn that pushed the team toward a more real-time solution.Source: §3.3 · p. 6

4.1 Overall Search Architecture

• The Blender routes client queries to search services and exposes the query hose, while the assistance engine separates cached-result serving from backend computation.Backend results are written to HDFS every five minutes, and frontend caches poll for updates every minute.Source: Figure 3 · p. 6, §4.1 · p. 6, §4.2 · pp. 6–7

4. TAKE TWO: DEPLOYED SOLUTION

• The deployed system is a custom in-memory engine focused on search sessions and tweets, with offline processing added for broader coverage.The earlier Hadoop-based architecture could access richer interaction logs, but the authors found the two sources sufficient for an initial implementation; many algorithms and some code carried over.Source: §4 · p. 6

4.2 The Search Assistance Engine

• The decoupled frontend and backend serve different scaling needs: frontend caches scale with query load, while backend instances are replicated for fault tolerance rather than sharded.Persisting results to HDFS lets caches serve the latest written results after a cold restart and supports retrospective analysis.Source: §4.2 · pp. 6–7

4.3 Data Flow

• Backend nodes update query and cooccurrence statistics from search sessions and query-like tweet n-grams, then periodically rank queries and persist suggestions.Weights are decayed and low-scoring entries pruned to control memory; inactive sessions are pruned as well.Source: §4.3 · pp. 7–8

4.4 Scalability

• Each backend must consume both complete streams without partitioning, while memory for query statistics creates a coverage-versus-relevance tradeoff.More aggressive pruning or shorter session histories can reduce memory use, but these choices also affect result coverage or relevance; CPU was not the reported bottleneck.Source: §4.4 · p. 8

4.5 Background Models

• Because real-time statistics lose impact after about a day, periodic models over several months capture slower-moving trends, and a long-span Pig job finds persistent spelling variants.The frontend loads these less-frequent results from HDFS and interpolates them with real-time results.Source: §4.5 · p. 8

5.1 The General Problem

• Search assistance needs evidence at minute-level granularity for breaking events and across days or months for persistent and tail queries.The required computations span query-pair statistics and varying latency requirements.Source: §5.1 · p. 8
• The deployed engine is neither general nor unified, cannot exploit richer click and impression logs without workarounds, and remains a patchwork that duplicates code and increases coordination complexity.Its real-time engine, retrospective processing, and Pig spelling jobs use different processing paradigms.Source: §5.1 · p. 8
• Real-time processing holds data in memory and may require approximation or pruning, while batch Hadoop jobs can materialize intermediate data and cover the long tail.The current system hand-tunes pruning and decay parameters to the data volume, intertwining performance and algorithmic choices.Source: §5.1 · p. 8
• The need for both recent and long-period statistics also appears in clickthrough-rate analytics, where ad placement uses fresh statistics alongside trends over days or weeks.The authors use this parallel to motivate a unified data-processing platform beyond search assistance.Source: §5.1 · p. 9, §5.2 · p. 9

5.2 Pieces of the Solution

• Existing systems leave gaps: Kafka alone lacks processing and long-span persistence, while stream engines raise persistence and large-temporal-span concerns.The paper also describes uncertainty about whether Percolator and MapUpdate cover the broader use cases the authors need.Source: §5.2 · p. 9
• The authors envision one framework combining stream processing for real-time computation with Hadoop-style batch roll-ups and long-timespan analytics.They report experimenting with components of this approach in working prototypes.Source: §5.2 · p. 10

• Different computation models and processing platforms are needed to address volume, velocity, and variety.Source: §6 · p. 10
• The Hadoop-based solution was ill-suited to the problem, leading the authors to implement the search assistance service twice.Source: §6 · p. 10
• The authors identify a desirable future direction: a generic data processing platform that handles both “big data” and “fast data.”Source: §6 · p. 10