Cache Refreshing for Online Social News Feeds

Nov 29, 2013

Several social networking applications enable users to view the events generated by other users, typically friends in the social network, in the form of "news feeds''. Friends and events are typically maintained per user and cached in memory to enable efficient generation of news feeds. Caching user friends and events, however, raises concerns about the freshness of news feeds as users may not observe the most recent events when cache content becomes stale. Mechanisms to keep cache content fresh are thus critical for user satisfaction while computing news feeds efficiently through caching. We propose a novel cache scheme called SOCR (Social Online Cache Refreshing) for identifying and refreshing cache entries. SOCR refreshes the cache in an online manner and does not require the backend data store to push updates to the cache. SOCR uses a utility-based strategy to accurately identify cache entries that need to be refreshed. The basic idea is to estimate at the time of each request to generate news feed whether refreshing would lead to different results for a news feed. To make such estimation, we model the rates of changes to social networks and events, and assess the performance of SOCR by analyzing datasets from Facebook and Yahoo News activity. Our experimental evaluation shows that the utility-based strategy ensures fresh news feeds (43% fewer stales) and efficient news feed responses (51% fewer false positives) compared to the TTL-based strategy. SOCR also reduces data transmission between the backend data store and the cache by 27% compared to a hybrid push-pull cache refreshing scheme.

  • Proceedings of the 22nd ACM International Conference on Information and Knowledge Management (CIKM)
  • Conference/Workshop Paper