Beyond Hashing: Optimizing Social Network Latency through Two-Hop Activity Partitioning
Partitioning Social Networks for Fast Retrieval of Time-Dependent Queries
This paper introduces an activity-aware partitioning strategy for Online Social Networks (OSNs) to optimize time-dependent queries. By leveraging the "two-hop neighborhood" concept and an Activity Prediction Graph (APG), the authors proposed static (KMETIS-based) and dynamic local algorithms that significantly outperform traditional hash-based methods, achieving up to 6.4x better data locality.
TL;DR
Social network "news feeds" are deceptively complex; they don't just pull your friends' posts, but often the interactions between your friends. This paper argues that traditional hashing destroys performance by scattering this "two-hop" data across servers. By predicting user activity and partitioning based on interaction intensity rather than just "friending," the authors achieve over 6x improvement in data locality compared to industry-standard hashing.
The "Multi-Get" Headache
When you open Facebook or X (formerly Twitter), the system must aggregate dozens of small records generated by different users. If User A is friends with User B, and User B posts on User C's wall, User A might see that interaction. This is a two-hop query.
Current systems like Cassandra or Gizzard use hash-based partitioning. While simple, hashing is "activity-blind." It treats a dormant account the same as a viral influencer, and it scatters a user's local social circle across a massive cluster. The result? A single page load triggers a "multi-get" storm, where the frontend waits for responses from dozens of servers, leading to a long-tail latency nightmare.
The Insight: Data Locality is Time-Dependent
The authors observed that social links are not created equal. Only a small fraction (about 12.2% in the New Orleans Facebook dataset) of social links show actual wall-post activity. Furthermore, activity is highly bursty and exhibits strong temporal correlation—if you interact with someone today, you are likely to do so again tomorrow.
Instead of partitioning the static social graph, the authors propose partitioning an Activity Prediction Graph (APG).
The Two-Hop Advantage
Most research stops at the "one-hop" neighborhood (you and your friends). This paper proves that for social feeds, you must optimize for the two-hop neighborhood (the interactions between your friends).
Fig 1: A friendship graph where message nodes (interactions) sit between users. A two-hop neighborhood captures the full visibility of a user's feed.
Methodology: Static vs. Adaptive Partitioning
The researchers developed two distinct strategies:
- Periodic Static Algorithm: Every month, the system rebuilds an APG using past interaction data, applying a decay factor so older interactions carry less weight. It uses KMETIS to find a min-cut that balances server load while keeping active clusters together.
- Adaptive Local Algorithm: This is the "surgical" approach. When a query is forced to go remote (cross-partition), the system calculates a reward function: Is the benefit of moving this data node to a local partition greater than the cost of moving it? This allows the system to drift and adapt to new "hot" friendship clusters in real-time.
Fig 2: The Periodic Algorithm significantly outperforms Hash-based methods in keeping query results within a single partition.
Experimental Results
Using real Facebook traces, the results were staggering:
- Locality Boost: The static algorithm achieved 5.6x better locality than hashing. The dynamic local algorithm pushed this to 6.4x.
- Query Scope: Under the proposed algorithms, almost all queries were satisfied by accessing at most 3 partitions. In contrast, hashing often requires dozens of server hits.
- Minimal Overhead: The dynamic algorithm only required about 40 data movements per day to stay optimized—a negligible cost for a massive gain in speed.
Fig 3: Percentage of queries accessing 3 or fewer partitions. The effectiveness of the two-hop strategy remains stable even as the cluster scales.
Critical Insight: Why This Matters
The "Power-Law" distribution of social networks—where a few users have thousands of friends—has long been the "final boss" of graph partitioning. This paper provides a pragmatic middle ground. By focusing on activity rather than just connectivity, and by targeting two-hop neighborhoods, it offers a roadmap for OSN architectures that can scale without sacrificing the milliseconds that define user experience.
Future Outlook: As we move toward decentralized social networks (like the Fediverse), these partitioning strategies may become the blueprint for how "Instances" or "Pods" should replicate data to prevent the entire network from slowing to a crawl during viral events.