Aspen

This repository provides experiments, scripts, and instructions for reproducing the experiments in our paper, Low-Latency Graph Streaming Using Compressed Purely-Functional Trees. Our paper introduces Aspen, a graph-streaming system based on compressed purely-functional trees. Aspen is designed for maintaining a dynamic graph subject to updates by a single writer, while supporting multiple concurrent readers. Due to the fact that the graph is purely-functional, all operations in Aspen are strictly serializable.

In the Getting Started Guide, we include functionality to reproduce the main results presented in our paper.

In the Step-By-Step Instructions, we also include the codes and instructions used for running experiments on very large graphs (hundreds of billions of edges). Due to the size of these graphs, and the memory footprint requirement on the machine, and the time to download, convert, and process these graphs, we expect that most users will not perform these steps, but we include them for completeness, and to ensure that our results for very large graphs are reproducible. We have made all graphs used in our paper publicly-available to ensure that our results are reproducible and can be built upon.

Getting Started Guide

This Getting Started Guide gives an overview of

1. Using Aspen as a Graph-Streaming System

2. Setting up Aspen

• Hardware and software dependencies
• Input formats
• Obtaining datasets

3. Experiment Workflow:

• Memory-footprint improvement due to compression and blocking
• Performance and speedup of parallel graph algorithms
• Microbenchmarks measuring the throughput of batch operations

Using Aspen as a Graph-Streaming System

We give a brief overview of the user-level API provided by Aspen for running graph algorithms, and performing updates.

An initial static graph can be generated using the initialize_graph function, which takes as input several optional arguments and returns a versioned_graph.

/* Creates a versioned graph based on an initial static graph snapshot */
initialize_graph(string fname="", bool mmap=false, bool is_symmetric=true,
                 bool compressed=false, size_t n_parts=1) -> versioned_graph

The versioned_graph type has the following interface. It is a single-writer, multi-reader interface, i.e., it can be read by multiple concurrent readers, which can acquire a version of the graph to perform queries or graph analyses, and a single writer, which can perform updates. The type has the following user-facing interface:

/* Used by readers to atomically acquire a snapshot */
acquire_version() -> snapshot_graph

/* Used by a single writer to insert a batch of edges */
insert_edges_batch(size_t m, tuple<uintV, uintV>* edges, bool sorted=false,
                   bool remove_dups=false, bool run_seq=false) -> void

/* Used by a single writer to delete a batch of edges */
delete_edges_batch(size_t m, tuple<uintV, uintV>* edges, bool sorted=false,
                   bool remove_dups=false, bool run_seq=false) -> void

The graph snapshot type snapshot_graph has the following interface:

/* Returns the number of vertices in the graph */
num_vertices() -> size_t

/* Returns the number of edges in the graph */
num_edges() -> size_t

/* Creates a flat snapshot of the vertices */
create_flat_snapshot() -> flat_snapshot

/* Applies f to each (v, u) edge for v in vs and returns a *
 * vertex_subset containing u such that f(v, u) = true           */
template <class F>
edge_map(vertex_subset& vs, F f, long threshold=-1) -> vertex_subset

The interface for snapshot_graph is similar to the Ligra interface, enabling users to implement and run existing Ligra algorithms with only minor cosmetic modifications. We provide the following examples of using the interface in the algorithms directory:

BC.h      /* single-source betweenness centrality */
BFS.h     /* breadth-first search */
MIS.h     /* maximal independent set */
k-Hop.h   /* local algorithm to find the k-hop neighborhood of a vertex */
Nibble.h  /* local clustering algorithm based on Spielman-Teng */

Setting up Aspen

Hardware Dependencies

Any modern x86-based multicore machine can be used. Aspen uses 128-bit CMPXCHG (requires -mcx16 compiler flag) but does not need hardware transactional memory (TSX). Most (small graph) examples in our artifact can be run using fewer than 100GB of memory, but our tests on larger graph (ClueWeb and larger) require 200GB--1TB of memory. All examples below can run in 100GB of memory by using a small graph input.

Software Dependencies

Aspen requires g++ 5.4.0 or later versions supporting the Cilk Plus extensions. The scripts that we provide in the repository use numactl -i all for better performance. However, all tests can also run directly without numactl.

Input Formats

Aspen currently supports reading two formats: the adjacency graph format used by the Problem Based Benchmark suite and Ligra, and a compressed graph format developed as part of the Graph Based Benchmark Suite.

The adjacency graph format starts with a sequence of offsets one for each vertex, followed by a sequence of directed edges ordered by their source vertex. The offset for a vertex i refers to the location of the start of a contiguous block of out edges for vertex i in the sequence of edges. The block continues until the offset of the next vertex, or the end if i is the last vertex. All vertices and offsets are 0 based and represented in decimal. The specific format is as follows:

AdjacencyGraph
<n>
<m>
<o0>
<o1>
...
<o(n-1)>
<e0>
<e1>
...
<e(m-1)>

This file is represented as plain text.

The compressed format is the bytePDA format, which is similar to the parallelByte format of Ligra+, extended with additional functionality.

Note that for the artifact, we limit Aspen to processing symmetric, unweighted graph datasets. The version that we will ultimately release on Github will support both undirected and directed (weighted) graphs.

Obtaining the Datasets

The small graphs used in our experiments can be obtained from the Stanford SNAP repository. We recommend using the soc-LiveJournal graph, and have provided a python script to download this graph, symmetrize it, and store it in the the format(s) used by Aspen. This can be done using the SNAPToAdj software in the Ligra repository (see ligra/utils/SNAPToAdj.C).

Alternately, we have made all graphs used in our experiments publicly-available on a self-hosted machine. Downloading the graphs from this location is likely the fastest way to get up and running. The files are located at https://metis.feralhosting.com/laxman/graphs, and can be downloaded using wget, as follows:

# listing of  https://metis.feralhosting.com/laxman/graphs/
clueweb_sym.bytepda                                21-Feb-2019 04:45     99G
com-orkut.adj                                      23-Feb-2019 05:37      2G
hyperlink2012_sym.bytepda                          22-Feb-2019 02:00    351G
hyperlink2014_sym.bytepda                          21-Feb-2019 07:58    184G
soc-LiveJournal1_sym.adj                           23-Feb-2019 05:38    640M
twitter_SJ.adj                                     23-Feb-2019 05:58     20G

# Download the soc-LiveJournal graph to the inputs/ directory
$ wget https://metis.feralhosting.com/laxman/graphs/soc-LiveJournal1_sym.adj inputs/

Experiment Workflow

This section assumes that you have downloaded some of the input graphs listed above to the inputs/ folder.

All of the applications below share a common set of flags, which we list below:

-f filename     : provides a location to an input graph file
-s              : indicates that the input graph is symmetric
-c              : indicates that the input graph is compressed
-m              : indicates that the input graph should be mmap'd

Memory Usage in Aspen

The memory usage of our codes can be measured using a tool called memory_footprint, which loads a graph using the C-tree data structure and outputs the number of bytes used by the C-tree representation. In our experiments, we set the probability of a node being selected as a head to p = 1/256, so the expected number of nodes in the edges tree is p*m.

Using

$ make memory_footprint
g++ -O3 -DEDGELONG -mcx16 -march=native -fcilkplus -std=c++14 tools/memory_footprint.cpp -o memory_footprint

will give the executable file memory_footprint.

It can be used as follows to reproduce the results in Table 2 in [1]:

# ./memory_footprint [-f graph_file]
$ ./memory_footprint -s -f inputs/soc-LiveJournal1_sym.adj
Running Aspen using 144 threads.
n = 4847571 m = 85702474

== Aspen Difference Encoded Stats (DE) ==
vertex tree: used nodes = 4847571 size/node = 64 memory used = 0.288938 GB
edge bytes: used nodes = 337050 size/node = 48 memory used = 0.0150673 GB
compressed-lists memory used = 0.26274 GB
Total: 0.566745 GB

== Aspen No Difference Encoding Stats (No DE) ==
vertex tree: used nodes = 4847571 size/node = 64 memory used = 0.288938 GB
edge bytes: used nodes = 337050 size/node = 48 memory used = 0.0150673 GB
compressed-lists (no difference-encoding) memory used = 0.480281 GB
Total: 0.784286 GB

== Aspen No C-Trees Stats (Uncompressed) ==
vertex tree: used nodes = 4847571 size/node = 48 memory used = 0.216703 GB
edge tree: used nodes = 85702474 size/node = 32 memory used = 2.55413 GB
Total: 2.77084 GB

Please note that we standardized the parameters used for the C-Tree experiments with and without difference encoding, and also made a small memory-efficiency improvement after our submission, which makes the size of the Aspen C-tree experiments slightly smaller than the numbers reported in the paper. The n