You are here
Social Hash: An Assignment Framework for Optimizing Distributed Systems Operations on Social Networks
Alon Shalita, Brian Karrer, Igor Kabiljo, Arun Sharma, Alessandro Presta, and Aaron Adcock, Facebook; Herald Kllapi, University of Athens; Michael Stumm, University of Toronto
This paper is part of the Operational Systems Track
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.
Open Access Media
USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.
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 Hash: An Assignment Framework for Optimizing Distributed Systems Operations on Social Networks},
booktitle = {13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16)},
year = {2016},
address = {Santa Clara, CA},
pages = {455-468},
url = {https://www.usenix.org/conference/nsdi16/technical-sessions/presentation/shalita},
publisher = {USENIX Association},
month = mar
}
connect with us