Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Large scale graph processing with apache giraph
Search
André Kelpe
May 23, 2012
Programming
2
5.4k
Large scale graph processing with apache giraph
André Kelpe
May 23, 2012
Tweet
Share
More Decks by André Kelpe
See All by André Kelpe
Cascading 3 and beyond
fs111
0
160
The Cascading (big) data application framework
fs111
1
230
SELECT ALL THE THINGS - Cascading Lingual, ANSI SQL for Apache Hadoop
fs111
0
190
A whirlwind tour through Lingual: ANSI SQL for Apache Hadoop
fs111
1
180
Tor for everyone!
fs111
0
170
Other Decks in Programming
See All in Programming
Vertical Architectures for Scalable Angular Applications
manfredsteyer
PRO
0
180
実践サーバーレスパフォーマンスチューニング ~その実力に迫る~ / Practical Serverless Performance Tuning ~A Close Look at its Power~
seike460
PRO
2
230
文化が生産性を作る
jimpei
3
620
C#および.NETに対する誤解をひも解く
ymd65536
0
330
レイトレ合宿10 レンダラー紹介 / Renderer Introduction, Ray Tracing Camp 10
shocker_0x15
0
630
Modern Functional Fluent CFML REST by Luis Majano
ortus24
0
160
watsonx.ai Dojo #3 プロンプトエンジニアリング入門
oniak3ibm
PRO
0
340
2024-10-01 dev2next - Observability for Modern JVM Applications
jonatan_ivanov
1
140
画像でわかる北島直樹
naoki0917
0
110
今日で分かる!カスタムコップの作り方
krpk1900
2
210
ActiveRecordの力でDBのメタデータを迅速に解析する
lnit
5
1.9k
Vue SFCのtemplateでTypeScriptの型を活用しよう
tsukkee
3
270
Featured
See All Featured
Statistics for Hackers
jakevdp
796
220k
10 Git Anti Patterns You Should be Aware of
lemiorhan
653
59k
Reflections from 52 weeks, 52 projects
jeffersonlam
346
20k
Rebuilding a faster, lazier Slack
samanthasiow
79
8.6k
Build The Right Thing And Hit Your Dates
maggiecrowley
32
2.3k
Building a Scalable Design System with Sketch
lauravandoore
459
33k
StorybookのUI Testing Handbookを読んだ
zakiyama
26
5.2k
Embracing the Ebb and Flow
colly
84
4.4k
Cheating the UX When There Is Nothing More to Optimize - PixelPioneers
stephaniewalter
280
13k
Optimizing for Happiness
mojombo
375
69k
Done Done
chrislema
181
16k
Refactoring Trust on Your Teams (GOTO; Chicago 2020)
rmw
31
2.6k
Transcript
Large scale graph processing with apache giraph André Kelpe @fs111
http://kel.pe
graphs 101
vertices and edges
v2 v5 v4 v7 v3 v8 v6 v1 v9 v8
v10 simple graph
graphs are everywhere road network, the www, social graphs etc.
graphs can be huge
google knows!
Pregel
Pregel by google Describes graph processing approach based on BSP
(Bulk Synchronous Parallel)
pro-tip: search for „pregel_paper.pdf“ on github ;-)
Properties of Pregel batch-oriented, scalable, fault tolerant processing of graphs
It is not a graph database It is a processing
framework
BSP vertex centric processing in so called supersteps
BSP vertices send messages to each other
BSP synchronization points between supersteps
execution of superstep S Each vertex processes messages generated in
S-1 and send messages to be processed in S+1 and determines to halt.
None
apache giraph
giraph Loose implementation of Pregel ideas on top of Hadoop
M/R coming from yahoo
apache giraph http://incubator.apache.org/giraph/
giraph avoid overhead of classic M/R process but reuse existing
infrastructure
giraph simple map jobs in master worker setup. coordination via
zookeeper. messaging via own RPC protocol. in memory processing. custom input and output formats.
current status version 0.1 released compatible with a multitude of
hadoop versions (we use CDH3 at work) still lots of things to do, join the fun!
the APIs the APIs
Vertex-API /** *@param <I> vertex id * @param <V> vertex
data * @param <E> edge data * @param <M> message data */ class BasicVertex<I extends WritableComparable, V extends Writable, E extends Writable, M extends Writable> void compute(Iterator<M> msgIterator); void sendMsg(I id, M msg); void voteToHalt();
Shortest path example https://cwiki.apache.org/confl uence/display/GIRAPH/Shorte st+Paths+Example
v2 v5 v4 v7 v3 v8 v6 v1 v9 v8
v10 simple graph
private boolean isSource() { return (getVertexId().get() == getContext().getConfiguration().getLong(SOURCE_ID, SOURCE_ID_DEFAULT)); }
@Override public void compute(Iterator<DoubleWritable> msgIterator) { if (getSuperstep() == 0) { setVertexValue(new DoubleWritable(Double.MAX_VALUE)); } double minDist = isSource() ? 0d : Double.MAX_VALUE; while (msgIterator.hasNext()) { minDist = Math.min(minDist, msgIterator.next().get()); } if (minDist < getVertexValue().get()) { setVertexValue(new DoubleWritable(minDist)); for (Edge<LongWritable, FloatWritable> edge : getOutEdgeMap().values()) { sendMsg(edge.getDestVertexId(), new DoubleWritable(minDist + edge.getEdgeValue().get())); } } voteToHalt(); }
GiraphJob job = new GiraphJob(getConf(), getClass().getName()); job.setVertexClass(SimpleShortestPathVertex.class); job.setVertexInputFormatClass(SimpleShortestPathsVertexInputFormat.class); job.setVertexOutputFormatClass( SimpleShortestPathsVertexOutputFormat.class);
FileInputFormat.addInputPath(job, new Path(„/foo/bar/baz“)); FileOutputFormat.setOutputPath(job, new Path(„/foo/bar/quux“)); job.getConfiguration().setLong(SimpleShortestPathsVertex.SOURCE_ID, Long.parseLong(argArray[2])); job.setWorkerConfiguration(minWorkers, maxWorkers), 100.0f); GiraphJob
see also http://incubator.apache.org/giraph/ https://cwiki.apache.org/confluence/displ ay/GIRAPH/Shortest+Paths+Example http://googleresearch.blogspot.com/2009/ 06/large-scale-graph-computing-at- google.html
Thanks! Questions?