Paper Details

Reference:

Alon Shalita, Brian Karrer, Igor Kabiljo, Arun Sharma, Alessandro Presta, Aaron Adcock, Herald Kllapi, and Michael Stumm,
"Social Hash: An assignment framework for optimizing distributed systems operations on social networks",
In Proceedings 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI'16), Santa Clara, CA, USA, Usenix Association, March, 2016, pp. 455–468.

Download:

PDF ; Talk Slides ; Talk

Abstract:

How objects are assigned to components in a distributed system can have a significant impact on performance and resource usage. Social Hash is a framework for producing, serving, and maintaining assignments of objects to components so as to optimize the operations of large social networks, such as Facebook's Social Graph. The framework uses a two-level scheme to decouple compute-intensive optimization from relatively low-overhead dynamic adaptation. The optimization at the first level occurs on a slow timescale, and in our applications is based on graph partitioning in order to leverage the structure of the social network. The dynamic adaptation at the second level takes place frequently to adapt to changes in access patterns and infrastructure, with the goal of balancing component loads.

We demonstrate the effectiveness of Social Hash with two real applications. The first assigns HTTP requests to individual compute clusters with the goal of minimizing the (memory-based) cache miss rate; Social Hash decreased the cache miss rate of production workloads by 25%. The second application assigns data records to storage subsystems with the goal of minimizing the number of storage subsystems that need to be accessed on multiget fetch requests; Social Hash cut the average response time in half on production workloads for one of the storage systems at Facebook.

Keywords:

distributed systems, social graph, performance optimization, social network

BibTeX:

@inproceedings(Shalita-NSDI,
    author = {Alon Shalita and Brian Karrer and Igor Kabiljo and Arun Sharma and Alessandro Presta and Aaron Adcock and Herald Kllapi and Michael Stumm},
    title = {Social {H}ash: {A}n assignment framework for optimizing distributed systems operations on social networks},
    booktitle = {Proceedings 13th USENIX Symposium on Networked Systems Design and Implementation (\textbf{NSDI'16})},
    location = {Santa Clara, CA, USA},
    publisher = {Usenix Association},
    month = {March},
    year = {2016},
    pages = {455-468},
    keywords = {distributed systems, social graph, performance optimization, social network}
)