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.5k
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
170
The Cascading (big) data application framework
fs111
1
230
SELECT ALL THE THINGS - Cascading Lingual, ANSI SQL for Apache Hadoop
fs111
0
200
A whirlwind tour through Lingual: ANSI SQL for Apache Hadoop
fs111
1
190
Tor for everyone!
fs111
0
190
Other Decks in Programming
See All in Programming
AIレビュアーをスケールさせるには / Scaling AI Reviewers
technuma
2
230
CEDEC2025 長期運営ゲームをあと10年続けるための0から始める自動テスト ~4000項目を50%自動化し、月1→毎日実行にした3年間~
akatsukigames_tech
0
150
一人でAIプロダクトを作るための工夫 〜技術選定・開発プロセス編〜 / I want AI to work harder
rkaga
13
2.8k
令和最新版手のひらコンピュータ
koba789
14
8k
【第4回】関東Kaggler会「Kaggleは執筆に役立つ」
mipypf
0
770
Understanding Ruby Grammar Through Conflicts
yui_knk
1
120
マイコンでもRustのtestがしたい その2/KernelVM Tokyo 18
tnishinaga
2
2.3k
「リーダーは意思決定する人」って本当?~ 学びを現場で活かす、リーダー4ヶ月目の試行錯誤 ~
marina1017
0
240
GUI操作LLMの最新動向: UI-TARSと関連論文紹介
kfujikawa
0
1k
The Past, Present, and Future of Enterprise Java
ivargrimstad
0
170
TDD 実践ミニトーク
contour_gara
0
140
大規模FlutterプロジェクトのCI実行時間を約8割削減した話
teamlab
PRO
0
490
Featured
See All Featured
Designing for Performance
lara
610
69k
A Modern Web Designer's Workflow
chriscoyier
695
190k
Evolution of real-time – Irina Nazarova, EuRuKo, 2024
irinanazarova
8
890
Code Reviewing Like a Champion
maltzj
525
40k
Balancing Empowerment & Direction
lara
2
590
How To Stay Up To Date on Web Technology
chriscoyier
790
250k
Site-Speed That Sticks
csswizardry
10
780
Embracing the Ebb and Flow
colly
87
4.8k
Speed Design
sergeychernyshev
32
1.1k
GraphQLの誤解/rethinking-graphql
sonatard
71
11k
Music & Morning Musume
bryan
46
6.7k
Producing Creativity
orderedlist
PRO
347
40k
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?