Loading presentation...
Prezi is an interactive zooming presentation

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Defense slides

No description
by

Imranul Hoque

on 11 June 2016

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Defense slides

Server 2
Storage and Processing Systems for Power-Law Graphs
Imranul Hoque
Ph.D. Final Exam
Graphs are everywhere
Food web
Protein interaction network
Neural network
Metabolic network
Online social network
Web graph
Financial network
Function call graph
The Internet
Many real-life graphs are power-law
Facebook graph: |V| = 1.1 B, |E| = 150 B
(May 2013)
Degree distribution of power-law graphs:
Many low-degree vertices
Some high-degree vertices
High degree vertices are responsible for most edges
1% vertices are responsible for 58% edges in the Twitter graph
Most real-life power-law graphs are
small world
High clustering coefficient
Small shortest path length
Graph Operations
Analytics
Transactions
Long running batch jobs
Examples:
- Google Search:
PageRank
- LinkedIn:
Shortest path
- Others:
Matching, Triangle counting
Need fast results while using few resources
Online queries
Examples:
- Facebook:
list all friends
- Twitter:
list all who follows 'justinbieber'
- LinkedIn:
list all who work at 'google'
Need low latency in answering queries
Graph Computation Framework
Graph Database
Thesis Statement
LFGraph
Techniques which leverage the
structure of the power-law graph
make
graph computation faster
and
graph storage more efficient
.
Fast, scalable, distributed, in-memory graph computation framework
Leverages
structure and degree distribution
of real power-law graphs
Bondhu
Disk layout manager for graph databases
Leverages
small-world nature
of real power-law graphs
Low latency in answering queries
LFGraph: Fast Distributed Graph Analytics
Distributed Graph Analytics
LFGraph uses
vertex-centric computation
model

A
D
E
B
C
PageRank
PageRank
Server 1
Server 2
PageRank
PageRank
PageRank
PageRank
Graph
Vertex
Program

A
D
E
B
C
Properties of Power-Law Graphs
2010
2012
Pregel
First vertex-centric distributed graph analytics framework from Google
PowerGraph
Partitions
high degree vertices
GraphLab
Uses shared-memory model
2012
Uses message-passing model
Slow due to high communication overhead
A
D
E
B
C
Input Graph
A
D
E
B
C
A
D
E
Server 1
High overhead and memory usage
A
D
E
B
C
Input Graph
Server 2
A
B
C
Server 1
A
D
E
Fastest of all existing graph analytics systems
Related Work
Requirements
1. Low communication and computation overhead
2. Load balanced communication and computation
3. Low pre-processing overhead
4. Low memory footprint
5. Good scalability
Critical for power-law graphs
Intelligent placement consumes up-front runtime
Hard to partition power-law graphs
Existing frameworks transfer too much data
Vertex programs process both incoming and outgoing edges
Existing systems require high memory
Intelligent placement requires location information for vertices
Smaller cluster must be able to process large graphs
Larger cluster = faster results
LFGraph satisfies all of the outlined requirements
Server 2
Server 1
LFGraph: Key Design Features
Reducing Communication Overhead
Publish-subscribe
fetch-once information flow
Cheap
hash-based
partitioning
Single pass
computation
In-neighbor
storage
Reduces communication overhead
Balances communication and computation load
Reduces computation overhead
Reduces memory footprint
Design Features
Benefits
High degree vertices are responsible for most of the out-edges
Server 1
Server 2
A
D
E
B
C
Server 1
Server 2
A
D
E
B
C
Publish List
Server 2: A
Communication Analysis
Communication overhead of a vertex 'v':
# of values 'v' sends over the network in an iteration
Communication overhead of an algorithm:
Average across all vertices
Comparison among:
Pregel, GraphLab, PowerGraph, LFGraph
Twitter graph (2010)
UK web graph (2007)
Amazon book similarity (2008)
41.65 M
1.47 B
105.9 M
3.74 B
0.74 M
5.16 M
Dataset:
|V|
|E|
Graphs
Communication Overhead
Twitter
Amazon
UK Web
LFGraph's improvement over GraphLab is higher for Twitter workload than for other workloads
LFGraph: System Design
JobServer Design
3:
1
4:
3 5
5:
0
0:
2 3
1:
2 4 5
2:
0 4
0:
2 3
JS1:
3
1:
2 4 5
JS0:
2 4
2:
0 4
4:
3 5
JS1:
3 5
3:
1
5:
0
JS0:
2 4 0
JS0:
3 5
JS1:
2 4 0
LFGraph has the lowest overhead
Performance Evaluation
LFGraph implemented in C++, ~5000 LoC
Emulab
32 machine cluster (12 GB RAM, 1 GigE)
Compared against: PowerGraph, Pregel
Random
Increasing complexity
Lower communication overhead
Oblivious
Batch
PowerGraph partitioning:
12 machine cluster (128 GB RAM, 10 GigE)
Twitter graph (|V| = 41M, |E| = 1.4B)
Synthetic graph (|V| = 1B, |E| = 127B)
PageRank (10 iterations)
Single Source Shortest Path
Results are averaged over 6 runs
Time
Communication overhead
Memory footprint
PageRank Runtime
Ignoring partition time
Including partition time
LFGraph is 2x better than the best PowerGraph variant
LFGraph is 5x-380x better than PowerGraph
Communication Overhead
Fetch once reduces communication
# of vertices per server
# of external friends
Memory Footprint
LFGraph stores in-edges and uses hash-based partitioning
Closer Look at Runtime
Compute light
I/O heavy
Full bisection bandwidth ensures scalability, even though total data volume increases
Large Scale Experiment
LFGraph uses 12 machines (96 cores)
vs.
Pregel uses 300 machines (800 cores)
Bondhu: Graph-Aware Disk Manager for Graph Databases
Overview of the Bondhu System
Novel framework for disk layout algorithms
- Based on community detection
Integration into Neo4j - a widely used open source graph database
Experimentation using the Facebook New Orleans network
Works on any power-law small world graph
- We focus on online social network graphs
- 48% improvement in latency compared to default Neo4j
Motivation
Visualization of disk block accesses using Neo4j
400KB blocks/user
List all friends
Use blktrace tool to trace hard disk block access
Disk Block Access Visualization
Scattered disk access
Random access is 100x slower compared to sequential access
Disk Layout Algorithm
Visualization using Bondhu
Scattered
Clustered
Analytics in Wimpy Cluster
Thesis Statement
Techniques which leverage the
structure of the power-law graph
make
graph computation faster
and
graph storage more efficient
.
Efficient utilization of limited memory
SSDs for Graph Storage
Fast random access performance
vs.
limited write cycle
Imprecise Graph Analytics
Partial results within deadline
Leverage Data Structure for NoSQL Databases
Mining structure from unstructured data
Computation and Communication Load Balance
LFGraph uses random hash-based placement
O(1) lookup for friends' location
Low memory footprint
Hypothesis of prior works:
Hash-based partitioning cannot balance loads for power-law graphs
Result: intelligent partitioning schemes
1. Power-law graphs cause load imbalance.
2. Real world graphs are power-law, so they do too.
Computation Load Balance for Power-Law Graphs
Computation overhead # of edges in a server
Simulation with
synthetic power-law graphs:
Place vertices using random hash-based placement
Calculate (average, min, max) # of edges per server
Max loaded worker 35x slower than average worker
Max loaded worker only 7% slower than average worker
Substantial variability across high-degree vertices ensures balanced load with hash-based partitioning
5x-380x improvement in runtime over existing systems
48% improvement over default layout
Placement
[Malewicz 2010]
[Low 2012]
[Gonzalez 2012]
Ghost
Mirror
Error bars denote load imbalance
Computation Load Balance for Real-life Power-law Graphs
PageRank Runtime Comparison
PageRank Runtime Improvement
Intelligent placement schemes do not yield much benefit
Vertex program runs in iterations
Placement
Computation
Communication
Computation
Communication
Iteration 1
Iteration 2
Life of a Vertex Program
Time
Barrier
Barrier
Barrier
Full transcript