Feed following: the big data challenge in social applications

Adam Silberstein, Ashwin Machanavajjhala, Raghu RamakrishnanDBSocial 2011 · DOI

TL;DR

This paper tackles the massive data management challenge of "feed following" in social applications like Facebook and Twitter, where users receive personalized streams of updates from those they follow. The authors highlight novel data management problems arising from the scale, recency bias, and variable user behavior, proposing that existing approaches like pub/sub, caching, and materialized views fall short. They introduce new research challenges in view selection, scheduling, and placement to optimize these systems.

What Problem Does This Paper Address?

Social media platforms like Facebook and Twitter allow users to "follow" other users or entities, creating personalized "feeds" of events (e.g., status updates, news articles). This "feed following" feature, while seemingly simple, presents a significant data management challenge at scale. The core problem is efficiently delivering a highly personalized, recency-biased stream of events to millions of users who generate and consume events at vastly different rates. Traditional database and distributed systems techniques struggle because:

  • Massive Scale: Billions of minutes spent online, hundreds of millions of users, and billions of connections.
  • Variable Fan-out: Users follow many others, and some users/entities are followed by millions.
  • Recency Bias: Users primarily care about recent events, making older events less valuable.
  • High Throughput: High rates of event production and feed queries.
  • Diurnal Behavior: Users are not constantly active, leading to periods of high and low activity.

The paper aims to stimulate research into novel data management solutions that can effectively handle these unique characteristics.

Methods

The authors analyze existing approaches and identify their shortcomings for feed following:

  • Publish/Subscribe (Pub/Sub): While good for event dissemination, traditional pub/sub systems assume continuous consumption and immediate delivery, which doesn't align with the intermittent nature of feed following and the tolerance for some staleness. They also don't inherently handle the "most recent" bias well.
  • Caching: Caching per-consumer query results can speed up frequent queries. However, a key limitation is that in feed following, each consumer poses the same query repeatedly, leading to inequity if their query isn't globally popular. Cache invalidation strategies also struggle with incremental updates to events.
  • Materialized Views: Materializing views (e.g., consumer-pivoted or producer-pivoted) can pre-compute results. The main issue is that these approaches are often static and assume a stable workload. For feed following, views for individual consumers might be useless for most of the day, leading to wasted memory and maintenance costs. The authors suggest that dynamic swapping of views in and out of memory, similar to caching, is needed but not part of traditional view literature.

The paper then frames new research challenges:

  • View Selection: Deciding which types of views (consumer-pivoted, producer-pivoted, or others) to materialize to optimize for cost, latency, or memory.
  • View Scheduling: Determining when to build, incrementally maintain, and expire views to balance freshness SLAs with resource usage. This involves predicting user activity.
  • View Placement: Strategically distributing materialized views across a distributed system to minimize communication costs and response times, potentially leveraging community structures in social networks.

Datasets

The paper uses a combination of real-world data and hypothetical examples:

  • Facebook and Twitter Statistics: Used to illustrate the scale of users and connections.
  • Yahoo! Social Platform Data: A 20-day trace of consumer feed requests from 1 million users was used to analyze query patterns and user activity.
  • Twitter Connection Graph: A graph with 400,000 consumers and 79,842 producers was used to evaluate view selection strategies for minimizing memory footprint.

No new benchmarks were introduced; instead, existing datasets were analyzed to understand feed following workloads.

Key Insights and Ideas

  • Feed Following is Fundamentally Different: The combination of recency bias, variable user activity, and the "same query, different time" pattern for each user makes it distinct from traditional pub/sub, caching, or materialized view problems.
  • Dynamic Management is Crucial: Static solutions are insufficient. Systems need to dynamically manage views (build, maintain, expire) based on predicted user behavior to optimize resource usage.
  • User Behavior Predictability: Users exhibit diurnal patterns and stable usage habits, which can be leveraged for predictive scheduling of view updates.
  • Trade-offs are Inherent: Optimizing for one aspect (e.g., memory footprint) might conflict with others (e.g., latency or freshness). Clever strategies are needed to balance these.
  • Community Structure Matters for Placement: Organizing views based on social network communities can reduce communication overhead, but high-fanout producers (like celebrities) require different strategies.

Key Results

  • User Activity Patterns: Analysis of Yahoo! data showed that a significant portion of users have long gaps between accesses (over 75% have gaps greater than 1 day), highlighting the inefficiency of maintaining views for them constantly.
  • View Selection for Memory: Using a Twitter graph, the authors demonstrated that a minimal set of cached feeds could reduce memory footprint by up to 5.6x compared to caching all consumer feeds.
  • Predictive Scheduling Effectiveness: A consumer-driven refreshing strategy achieved a hit rate of about 54%. By incorporating signature-driven background refreshes based on user activity patterns, the hit rate improved to 73%. The paper notes that further improvements are possible with more sophisticated data mining.

Limitations and Future Work

  • Formalizing Tolerance: The paper acknowledges that the tolerance for missing events or producers in feeds needs a more formal definition and principled way to leverage it.
  • Access Level Changes: Handling changes in access control (e.g., an event becoming private) efficiently is an open problem.
  • Multi-level Connection Graphs: Integrating multi-level connection graphs (e.g., user-generated pages) into view selection and placement strategies is an open challenge.
  • View Scheduling Optimization: The paper suggests future work on optimizing background refreshes to limit read/write rates to event stores and view sets, incorporating incremental maintenance, and improving prediction accuracy using data mining.
  • View Placement Complexity: The trade-offs between clustering benefits and the need to handle high-fanout producers require further research.

Summary updated

BibTeX
@inproceedings{silberstein2011feed,
  author = {Adam Silberstein and Ashwin Machanavajjhala and Raghu Ramakrishnan},
  title = {{Feed following: the big data challenge in social applications}},
  booktitle = {DBSocial},
  year = {2011},
  doi = {10.1145/1996413.1996414},
}
Figure