January 22, 2014

The Essence of Reynolds

ACM Symposium on Principles of Programming Languages (POPL)

John Reynolds (1935-2013) was a pioneer of programming languages research. In this paper we pay tribute to the man, his ideas, and his influence.

Stephen Brookes, Peter O'Hearn, Uday S. Reddy
November 4, 2013

An Analysis of Facebook Photo Caching

ACM Symposium on Operating Systems Principles (SOSP)

This paper examines the workload of Facebook’s photo-serving stack and the effectiveness of the many layers of caching it employs. Facebook’s image-management infrastructure is complex and geographically distributed. It includes browser caches on end-user systems, Edge Caches at ~20 PoPs, an Origin Cache, and for some kinds of images, additional caching via Akamai. The underlying image storage layer is widely distributed, and includes multiple data centers.

Qi Huang, Ken Birman, Robbert van Renesse, Wyatt Lloyd, Sanjeev Kumar, Harry Li
October 1, 2013

Virtual Network Diagnosis as a Service

ACM Symposium on Cloud Computing (SoCC)

Today’s cloud network platforms allow tenants to construct sophisticated virtual network topologies among their VMs on a shared physical network infrastructure. However, these platforms provide little…

Wenfei Wu, Guohui Wang, Aditya Akella, Anees Shaikh
August 27, 2013

Scuba: Diving into Data at Facebook

International Conference on Very Large Data Bases (VLDB)

Facebook takes performance monitoring seriously. Performance issues can impact over one billion users so we track thousands of servers, hundreds of PB of daily network traffic, hundreds of daily code…

Lior Abraham, John Allen, Oleksandr Barykin, Vinayak Borkar, Bhuwan Chopra, Ciprian Gerea, Dan Merl, Josh Metzler, David Reiss, Subbu Subramanian, Janet Wiener, Okay Zed
August 26, 2013

Unicorn: A System for Searching the Social Graph

International Conference on Very Large Data Bases (VLDB)

Unicorn is an online, in-memory social graph-aware indexing system designed to search trillions of edges between tens of billions of users and entities on thousands of commodity servers. Unicorn is based on standard concepts in information retrieval, but it includes features to promote results with good social proximity. It also supports queries that require multiple round-trips to leaves in order to retrieve objects that are more than one edge away from source nodes.

Mike Curtiss, Iain Becker, Tudor Bosman, Sergey Doroshenko, Lucian Adrian Grijincu, Tom Jackson, Soren Lassen, Philip Pronin, Guanghao Shen, Gintaras Woss, Chao Yang, Ning Zhang, Sriram Sankar
August 26, 2013

XORing Elephants: Novel Erasure Codes for Big Data

International Conference on Very Large Data Bases (VLDB)

Distributed storage systems for large clusters typically use replication to provide reliability. Recently, erasure codes have been used to reduce the large storage overhead of three-replicated systems. Reed-Solomon codes are the standard design choice and their high repair cost is often considered an unavoidable price to pay for high storage efficiency and high reliability.

Maheshwaran Sathiamoorthy, Megasthenis Asteris, Dimitris Papailiopoulos, Alexandros G. Dimakis, Ramkumar Vadali, Scott Chen, Dhruba Borthakur
July 23, 2013

Semantic Hashing using Tags and Topic Modeling

ACM Special Interest Group on Information Retrieval Conference (SIGIR)

It is an important research problem to design efficient and effective solutions for large scale similarity search. One popular strategy is to represent data examples as compact binary codes through semantic hashing, which has produced promising results with fast search speed and low storage cost. Many existing semantic hashing methods generate binary codes for documents by modeling document relationships based on similarity in a keyword feature space. Two major limitations in existing methods are: (1) Tag information is often associated with documents in many real world applications, but has not been fully exploited yet; (2) The similarity in keyword feature space does not fully reflect semantic relationships that go beyond keyword matching.

Qifan Wang, Dan Zhang, Luo Si
July 14, 2013

TAO: Facebook’s Distributed Data Store for the Social Graph

USENIX Annual Technical Conference 2013

We introduce a simple data model and API tailored for serving the social graph, and TAO, an implementation of this model.

Peter Dimov Hui Ding, George Cabrera, Zach Amsden, Venkat Venkataramani, Lovro Puzar, Harry Li, Anthony Giardullo, Jack Ferris, Sachin Kulkarni, Prasad Chakka, Yee Jiun Song, Nathan Bronson, Mark Marchukov Dmitri Petrov
July 1, 2013

Development and Deployment at Facebook

IEEE Internet Computing 17(4)

More than one billion users log in to Facebook at least once a month to connect and share content with each other. Among other activities, these users upload over 2.5 billion content items every day.

Dror Feitelson, Eitan Frachtenberg, Kent Beck
June 26, 2013

TAO: Facebook’s Distributed Data Store for the Social Graph

USENIX Annual Technical Conference (ATC)

We introduce a simple data model and API tailored for serving the social graph, and TAO, an implementation of this model. TAO is a geographically distributed data store that provides efficient and timely access to the social graph for Facebook’s demanding workload using a fixed set of queries. It is deployed at Facebook, replacing memcache for many data types that fit its model.

Nathan Bronson, Zachary Amsden, George Cabrera III, Prasad Chakka, Peter Dimov, Hui Ding, Jack Ferris, Anthony Giardullo, Sachin Kulkarni, Harry Li, Mark Marchukov, Dmitri Petrov, Lovro Puzar, Yee Jiun Song, Venkat Venkataramani
June 26, 2013

A Solution to the Network Challenges of Data Recovery in Erasure-coded Distributed Storage Systems: A Study on the Facebook Warehouse Cluster

USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage

Erasure codes, such as Reed-Solomon (RS) codes, are being increasingly employed in data centers to combat the cost of reliably storing large amounts of data. Although these codes provide optimal stora…

K.V. Rashmi, Nihar B. Shah, Dikang Gu, Hairong Kuang, Dhruba Borthakur, Kannan Ramchandran
June 23, 2013

Thin Servers with Smart Pipes: Designing SoC Accelerators for Memcached

ACM/IEEE International Symposium on Computer Architecture (ISCA)

Distributed in-memory key-value stores, such as memcached, are central to the scalability of modern internet services. Current deployments use commodity servers with high-end processors. However, give…

Kevin Lim, David Meisner, Ali Saidi, Parthasarathy Ranganathan, Thomas Wenisch
June 22, 2013

LinkBench: a Database Benchmark based on the Facebook Social Graph

ACM Special Interest Group on Management of Data (SIGMOD/PODS)

Database benchmarks are an important tool for database researchers and practitioners that ease the process of making informed comparisons between different database hardware, software and configuratio…

Tim Armstrong, Nagavamsi Ponnekanti, Dhruba Borthakur, Mark Callaghan
June 5, 2013

Speeding up Large-Scale Learning with a Social Prior

ACM Conference on Knowledge Discovery and Data Mining (KDD

Slow convergence and poor initial accuracy are two problems that plague efforts to use very large feature sets in online learning. This is especially true when only a few features are ‘active’ in any…

Deepayan Chakrabarti, Ralf Herbrich
May 7, 2013

Facebook’s Data Center Network Architecture

IEEE Optical Interconnects Conference (OI)

We review Facebook’s current data center network architecture and explore some alternative architectures.

Nathan Farrington, Alexey Andreyev
May 1, 2013

Hash Bit Selection: a Unified Solution for Selection Problems in Hashing

Conference on Computer Vision and Pattern Recognition (CVPR)

Hashing based methods recently have been shown promising for large-scale nearest neighbor search. However, good designs involve difficult decisions of many unknowns – data features, hashing algorithms, parameter settings, kernels, etc.

Xianglong Liu, Junfeng He, Bo Lang, Shih-Fu Chang
April 26, 2013

Storage and Performance Optimization of Long Tail Key Access in a Social Network

International Workshop on Cloud Data and Platforms (Cloud DP)

In a social network, it is natural to have hot objects such as a celebrity’s Facebook page. Duplicating hot object data in each cluster provides quick cache access and avoids stressing a single server’s network or CPU resources. But duplicating cold data in each cache cluster consumes significant RAM. A more storage efficient way is to separate hot data from cold data and duplicate only hot data in each cache cluster within a data center. The cold data, or the long tail data, which is accessed much less frequently, has only one copy at a regional cache cluster.

John Liang, Yang 'James' Luo, Mark Drayton, Rajesh Nishtala, Richard Liu, Nick Hammer, Jason Taylor, Bill Jia
April 3, 2013

Scaling Memcache at Facebook

USENIX Symposium on Networked Systems Design and Implementation (NSDI)

Memcached is a well known, simple, in memory caching solution. This paper describes how Facebook leverages memcached as a building block to construct and scale a distributed key-value store that supports the world’s largest social network.

Rajesh Nishtala, Hans Fugal, Steven Grimm, Marc Kwiatkowski, Herman Lee, Harry Li, Ryan McElroy, Michael Paleczny, Daniel Peek, Paul Saab, David Stafford, Tony Tung, Venkat Venkataramani
February 6, 2013

Characterizing and Curating Conversation Threads: Expansion, Focus, Volume, Re-entry

ACM International Conference on Web Search and Data Mining (WSDM)

Discussion threads form a central part of the experience on many Web sites, including social networking sites such as Facebook and Google Plus and knowledge creation sites such as Wikipedia.

Lars Backstrom, Jon Kleinberg, Lillian Lee, Cristian Danescu-Niculescu-Mizil
October 24, 2012

The HipHop Compiler for PHP

ACM International Conference on Object Oriented Programming Systems, Languages, and Applications (OOPSLA)

Scripting languages are widely used to quickly accomplish a variety of tasks because of the high productivity they enable. Among other reasons, this increased productivity results from a combination o…

Haiping Zhao, Minghui Yang, Xin Qi, Mark Williams, Charlie Gao, Guilherme Ottoni, Drew Paroski, Scott MacVicar, Jason Evans, Stephen Tu