Paper Info
Title
Chaos: scale-out graph processing from secondary storage
Abstract
Chaos scales graph processing from secondary storage to multiple machines in a cluster. Earlier systems that process graphs from secondary storage are restricted to a single machine, and therefore limited by the bandwidth and capacity of the storage system on a single machine. Chaos is limited only by the aggregate bandwidth and capacity of all storage devices in the entire cluster. Chaos builds on the streaming partitions introduced by X-Stream in order to achieve sequential access to storage, but parallelizes the execution of streaming partitions. Chaos is novel in three ways. First, Chaos partitions for sequential storage access, rather than for locality and load balance, resulting in much lower pre-processing times. Second, Chaos distributes graph data uniformly randomly across the cluster and does not attempt to achieve locality, based on the observation that in a small cluster network bandwidth far outstrips storage bandwidth. Third, Chaos uses work stealing to allow multiple machines to work on a single partition, thereby achieving load balance at runtime. In terms of performance scaling, on 32 machines Chaos takes on average only 1.61 times longer to process a graph 32 times larger than on a single machine. In terms of capacity scaling, Chaos is capable of handling a graph with 1 trillion edges representing 16 TB of input data, a new milestone for graph processing capacity on a small commodity cluster.
Year
DOI
Venue
2015
10.1145/2815400.2815408
SOSP
Field
DocType
Citations 
Locality,Load balancing (computing),Computer science,Computer data storage,Real-time computing,Bandwidth (signal processing),Work stealing,Auxiliary memory,Scalability,Distributed computing,Sequential access
Conference
60
PageRank 
References 
Authors
1.12
26
4
Name
Order
Citations
PageRank
Amitabha Roy162126.20
Laurent Bindschaedler2834.09
Jasmina Malicevic3793.20
Willy Zwaenepoel45651813.97