Download as PDF, PPTX
Uploaded byParis Carbone
Graph Stream Processing : spinning fast, large scale, complex analytics
The document discusses the need for large-scale, complex, and fast data analysis to answer significant questions quickly, particularly in the context of graph stream processing. It details the evolution of distributed graph processing, the challenges of real-time analytics, and offers insights into solutions like Apache Flink and Gelly Stream. The emphasis is on addressing complex problems through efficient data analysis techniques and frameworks to support real-time decision-making.
Graph Stream Processing : spinning fast, large scale, complex analytics
- 1. Graph Stream Processing spinningfast, large-scale, complex analytics Paris Carbone PhD Candidate @ KTH Committer @ Apache Flink
- 2. We want toanalyse….
- 3. We want toanalyse…. data
- 4. We want toanalyse…. datacomplex
- 5. We want toanalyse…. datacomplexlarge-scale
- 6. We want toanalyse…. data fastcomplexlarge-scale
- 7. But why dowe need large-scale, complex and fast data analysis? >
- 8. But why dowe need large-scale, complex and fast data analysis? to answer big complex questions faster>
- 9.
- 10.
- 11. Get me thebest route to work right now >Hej Siri_ to answer big complex questions faster>
- 12. Get me thebest route to work right now >Hej Siri_ …with the fewest human drivers to answer big complex questions faster>
- 13. Get me thebest route to work right now >Hej Siri_ Lookup a pizza recipe all of my friends like but did not eat yesterday… …with the fewest human drivers to answer big complex questions faster>
- 14. Get me thebest route to work right now >Hej Siri_ Lookup a pizza recipe all of my friends like but did not eat yesterday… or the day before yesterday …with the fewest human drivers to answer big complex questions faster>
- 15. Get me thebest route to work right now >Hej Siri_ Lookup a pizza recipe all of my friends like but did not eat yesterday… or the day before yesterday oh! And no kebab pizza! …with the fewest human drivers to answer big complex questions faster>
- 16. Get me thebest route to work right now >Hej Siri_ Lookup a pizza recipe all of my friends like but did not eat yesterday… Siri, is it possible to re-unite all data scientists in the world? or the day before yesterday oh! And no kebab pizza! …with the fewest human drivers to answer big complex questions faster>
- 17. no matter ifthey use Spark or Flink or just ipython Get me the best route to work right now >Hej Siri_ Lookup a pizza recipe all of my friends like but did not eat yesterday… Siri, is it possible to re-unite all data scientists in the world? or the day before yesterday oh! And no kebab pizza! …with the fewest human drivers to answer big complex questions faster>
- 18. no matter ifthey use Spark or Flink or just ipython Get me the best route to work right now >Hej Siri_ Lookup a pizza recipe all of my friends like but did not eat yesterday… Siri, is it possible to re-unite all data scientists in the world? or the day before yesterday oh! And no kebab pizza! …with the fewest human drivers to answer big complex questions faster>
- 19.
- 20.
- 21.
- 22.
- 23. to answer big complex questions faster> FIRST EARTH WORLDPROBLEM use Spark or Flink or just ipython best route to work right now re-unite all data scientists in the world? oh! And no kebab pizza! …with the fewest human drivers 30000 AD
- 24. Still, fast analytics might save us some day… • We canaccess patient movements and fb, twitter and pretty much all social media interactions • Can we stop a pandemic? • Or can we predict fast where the virus can spread?
- 25. Now how dowe analyse… data fastcomplexlarge-scale ?
- 26. Now how dowe analyse… data graphdistributed streaming
- 27. Now how dowe analyse… data graphdistributed streaming everything is a graph
- 28. Now how dowe analyse… data graphdistributed streaming everything is many everything is a graph
- 29. Now how dowe analyse… data graphdistributed streaming everything is many everything is a graph everything is a stream
- 30. it all started… asa first world problem question
- 31. but then thingsescalated quickly… …and machinery got cheaper and we suddenly realised that we have big data
- 32. Distributed Graph processingwas born Thus,
- 33. Distributed Graph processingwas born Thus, Map Reduce 1. Store Partitioned Data 2. Sent Local computation (map) 3. now shuffle it on disks 4. merge the results (reduce) 5. Store the result back DFS : distributed file system
- 34. Distributed Graph processingwas born Thus, 1. Store Updates to DFS 2. Load graph snapshot (mem) 3. Compute round~superstep 4. Store updates 5. …repeat Distributed Graph ProcessingMap Reduce 1. Store Partitioned Data 2. Sent Local computation (map) 3. now shuffle it on disks 4. merge the results (reduce) 5. Store the result back DFS : distributed file system
- 35. Distributed Graph processingwas born Thus, 1. Store Updates to DFS 2. Load graph snapshot (mem) 3. Compute round~superstep 4. Store updates 5. …repeat Distributed Graph ProcessingMap Reduce 1. Store Partitioned Data 2. Sent Local computation (map) 3. now shuffle it on disks 4. merge the results (reduce) 5. Store the result back DFS : distributed file system
- 36. Distributed Graph processingwas born Thus, 1. Store Updates to DFS 2. Load graph snapshot (mem) 3. Compute round~superstep 4. Store updates 5. …repeat Distributed Graph ProcessingMap Reduce 1. Store Partitioned Data 2. Sent Local computation (map) 3. now shuffle it on disks 4. merge the results (reduce) 5. Store the result back DFS : distributed file system
- 37. Distributed Graph processingwas born Thus, 1. Store Updates to DFS 2. Load graph snapshot (mem) 3. Compute round~superstep 4. Store updates 5. …repeat Distributed Graph ProcessingMap Reduce 1. Store Partitioned Data 2. Sent Local computation (map) 3. now shuffle it on disks 4. merge the results (reduce) 5. Store the result back DFS : distributed file system
- 38. Distributed Graph processingwas born Thus, 1. Store Updates to DFS 2. Load graph snapshot (mem) 3. Compute round~superstep 4. Store updates 5. …repeat Distributed Graph ProcessingMap Reduce 1. Store Partitioned Data 2. Sent Local computation (map) 3. now shuffle it on disks 4. merge the results (reduce) 5. Store the result back DFS : distributed file system
- 39. Distributed Graph processingwas born Thus, 1. Store Updates to DFS 2. Load graph snapshot (mem) 3. Compute round~superstep 4. Store updates 5. …repeat Distributed Graph ProcessingMap Reduce 1. Store Partitioned Data 2. Sent Local computation (map) 3. now shuffle it on disks 4. merge the results (reduce) 5. Store the result back DFS : distributed file system
- 40. • We wantto compute the Connected Components of a distributed graph. • Basic computation element (map): vertex • Updates : messages to other vertices Distributed Graph processing example
- 41. • We wantto compute the Connected Components of a distributed graph. • Basic computation element (map): vertex • Updates : messages to other vertices Distributed Graph processing example 1 2 3
- 42. Distributed Graph processingexample 1 43 2 5 6 7 8 ROUND 0
- 43. Distributed Graph processingexample 1 43 2 5 ROUND 0 6 7 8 3 1 4 4 5 2 4 2 3 5 7 8 6 8 6 7
- 44. Distributed Graph processingexample 1 21 2 2 ROUND 1 6 6 6
- 45. Distributed Graph processingexample 1 2 2 2 2 1 2 6 6 6 6 1 21 2 2 ROUND 1 6 6 6 6 6
- 46. Distributed Graph processingexample 1 11 2 2 ROUND 2 6 6 6
- 47. Distributed Graph processingexample 1 11 2 2 ROUND 2 6 6 6 1 1 1
- 48. Distributed Graph processingexample 1 11 1 1 ROUND 3 6 6 6
- 49. Distributed Graph processingexample 1 11 1 1 ROUND 3 6 6 6 1 1 1 1
- 50. Distributed Graph processingexample 1 11 1 1 ROUND 4 6 6 6 No messages, DONE!
- 51. • Examples ofLoad-Compute-Store systems: Pregel, Graphx (spark), Graphlab, PowerGraph • Same execution strategy - Same problems • It’s slow • Too much re-computation ($€) for nothing. • Real World Updates anyone? Distributed Graph processing systems
- 53. …and streaming came tomess everything make fast and simple
- 54. …and streaming came tomess everything make fast and simple real world
- 55. …and streaming came tomess everything make fast and simple real world event records • local state stays here • local computation too The Dataflow™
- 57. Streaming is soadvanced that… • subsecond latency and high throughput finally coexist • it does fault tolerance without batch writes* • late data** is handled gracefully * https://arxiv.org/abs/1506.08603• ** http://dl.acm.org/citation.cfm?id=2824076
- 58. Streaming is soadvanced that… …but what about complex problems? • subsecond latency and high throughput finally coexist • it does fault tolerance without batch writes* • late data** is handled gracefully * https://arxiv.org/abs/1506.08603• ** http://dl.acm.org/citation.cfm?id=2824076
- 60. can we makeit happen?
- 61. can we makeit happen? • Problem: Can’t keep an infinite graph in- memory and do complex stuff
- 62. can we makeit happen? • Problem: Can’t keep an infinite graph in- memory and do complex stuff ?? universe
- 63. can we makeit happen? • Problem: Can’t keep an infinite graph in- memory and do complex stuff ?? universe >it was never about the graph silly, it was about answering complex questions, remember?
- 64. can we makeit happen? • Problem: Can’t keep an infinite graph in- memory and do complex stuff universe ;) universe summary >it was never about the graph silly, it was about answering complex questions, remember? answers
- 65. Examples of Summaries •Spanners : distance estimation • Sparsifiers : cut estimation • Sketches : homomorphic properties graph summary algorithm algorithm~R1 R2
- 66. Distributed Graph streaming example 54 76 86 42 31 52ConnectedComponents on a stream of edges (additions)
- 67. 31 Distributed Graph streaming example 54 76 86 42 43 31 52 ConnectedComponents on a stream of edges (additions) 1
- 68. 52 Distributed Graph streaming example 54 76 86 42 43 87 52 ConnectedComponents on a stream of edges (additions) 31 1 2
- 69. 52 4 Distributed Graph streaming example 54 76 86 42 43 87 41 ConnectedComponents on a stream of edges (additions) 31 1 2
- 70. 52 4 Distributed Graph streaming example 76 86 42 43 87 41 ConnectedComponents on a stream of edges (additions) 31 1 76 2 6
- 71. 52 4 8 Distributed Graph streaming example 86 42 43 87 41 ConnectedComponents on a stream of edges (additions) 31 1 76 2 6
- 72. 8 52 4 76 Distributed Graph streaming example 42 43 87 41 ConnectedComponents on a stream of edges (additions) 31 1 2 6
- 73. 8 52 4 76 Distributed Graph streaming example 42 43 87 41 ConnectedComponents on a stream of edges (additions) 31 1 2 6
- 74. 8 52 4 76 Distributed Graph streaming example 43 87 41ConnectedComponents on a stream of edges (additions) 31 1 6
- 75. But Is thisEfficient? Sure, we can distribute the edges and summaries
- 76. But Is thisEfficient? Sure, we can distribute the edges and summaries any systems in mind?
- 77. Gelly Stream Graph streamprocessing with Apache Flink
- 78. Gelly Stream Oveview DataStreamDataSet DistributedDataflow Deployment Gelly Gelly- ➤ Static Graphs ➤ Multi-Pass Algorithms ➤ Full Computations ➤ Dynamic Graphs ➤ Single-Pass Algorithms ➤ Approximate Computations DataStream
- 79. Gelly Stream Status ➤Properties and Metrics ➤ Transformations ➤ Aggregations ➤ Discretization ➤ Neighborhood Aggregations ➤ Graph Streaming Algorithms ➤ Connected Components ➤ Bipartiteness Check ➤ Window Triangle Count ➤ Triangle Count Estimation ➤ Continuous Degree Aggregate
- 81. wait, so nowwe can detect connected components right away?
- 82. wait, so nowwe can detect connected components right away?
- 83. wait, so nowwe can detect connected components right away? Solved! But how about our other issues now?
- 84.
- 85.
- 86. Gelly-Stream to therescue graphStream.filterVertices(DataScientists()) .slice(Time.of(10, MINUTE), EdgeDirection.IN) .applyOnNeighbors(FindPairs()) wendy checked_in glaze steve checked_in glaze tom checked_in joe’s_grill sandra checked_in glaze rafa checked_in joe’s_grill wendy steve sandra glaze tom rafa joe’s grill {wendy, steve} {steve, sandra} {wendy, sandra} {tom, rafa}
- 87.
- 88.
- 89. The next step •Iterative model* on streams for deeper analytics • More Summaries • Better Our-Of-Core State Integration • AdHoc Graph Queries Large-scale, Complex, Fast, Deep Analytics * http://dl.acm.org/citation.cfm?id=2983551
- 90. Try out Gelly-Stream* becauseall questions matter @SenorCarbone *https://github.com/vasia/gelly-streaming