scale.bythebay.io: Russell Alexander Spitzer & Artem Aliev, A Tale of Two Graph Engines on Spark
so hi everybody welcome to our talk a tale of two graph frameworks on spark graph frames and tinkerer pop OLAP I'm Russell Spitzer and this is art MLE if you don't know Artem he is a graph analytics expert he lives on the planet Earth but not on the same side that I do I am a distributed systems enthusiast we both work at data stacks mostly on the integration of Cassandra with a bunch of other Big Data technologies in particular we both work a lot with spark so today we want to tell you about something new that we've both kind of been working on which is both Apache tinker pop and graph frames now these are two libraries and frameworks that you can use with your graph data or with other data and using and you can use graph algorithms on them they both share an underlying component is that they can both use spark as an execution engine but they both take different trade-offs and have different options basically as they're running which shape which of these you should choose for your particular application so just to start off with anyone who hasn't seen graphs before graphs are just a group of things we call vertices and edges usually vertices rely refer to some kind of object so like for example they could be these spaceships and edges refer to or and these sorry these spaceships and they have properties you know first things that are attributes of them and then we can also have these relationships between them which we usually call edges so here we've got a bunch of edges connecting these spaceships which tell you that the first USS Enterprise was succeeded by the second USS Enterprise and then another Enterprise and another one and they all have their own call signs and it's great a cool thing to note is that these edges can also have their own properties in their own identifying information and that means we can get this kind of network of the relationship between all of these different things now our vertices and our edges don't actually have to all be of one particular type this is one of the cool aspects of a graph is that we can actually mix things like ships in our graph with things like crew member so since we can have both of these things in the same graph we can have edges that then relate our crew members to our ship types and with all of these relationships we actually get a pretty complete description of the interactions between crew members ships and other crew members so why is this really exciting obviously this looks like a lot of lines we have a lot of labels there's a lot of mixing of things together but the reason that this is really great is that the questions we can ask of a graph are a little bit different than the questions we can ask of relational data so for example asking the question what captain served after Kirk or what ship was - after the first Starship Enterprise is a lot easier to ask of graph data than it is to ask of relational data in relational world we would probably have to do a lot of joins among our normalized forms of our various types of data to actually get our end result but graphs usually let us express these requests as something that's a little bit simpler so for example with our current little graph right here we may want to ask the question what was the captain after Kirk well to do that we actually can follow these well-documented edges and say well we'll start at the Kirk vertex and then we'll move to the ship that he served on see what ship followed that and then go to the crew of that ship so rather than describing this in a term of joins and matching up IDs we just naturally follow the edges of the graph to answer our question if we want to do a similar question like which was two ships after the first enterprise we just follow the seceded by edge twice so instead of saying we have to join in match ID and then join in match ID we just follow this edge two times so this is kind of an overview of tinker pop so tinker pop is one of the many ways you can actually use to access and Express these kind of traversals through a graph it's made up of a lot of different components it's all open source and one of these components is the gremlin traversal language now the gremlin traversal language is a language for actually expressing that go from one vertice follow its edges go to another vertice and do all these kind of exciting things it also has you'll notice a little purple guy down in the corner there and it represents the fact that the underlying execution engine is independent of the language we can actually use this language to do both really fast OLTP queries or we can actually execute our traversals using something like spark and do a more analytics processing but let's start off by talking a little bit about how to do some of these OLTP queries and for that we're going to do a quick switcheroo which requires two mic swaps okay so we will go to the another universe it will be how you'll use mobile ins example that use a set of have a set of movies and movies are rated by users and users have its own occupation and movie skaters get a set of boot Ondra and here is example of such kind of chart a such a kind of graph so for example we have this Star Trek movies that have sci-fi is this sci-fi or we have terminator movie that is a solo sci-fi and we have users who rate them and we have occupation of that users like Artists Program in Royal College great rent students so let's go for the four examples in this case I will use our data stacks studio and we'll start with LTP vr6 tantric practices queries so that this is a query I used to get this random sub graph I will talk about them it later so let's start from them well as Russell said we need to ask question to our talk to our graph for example what Star Trek movies did a you generate so in this case we will all TP we will start from your own user saying graph get vertices find vertices user that have ID 7 100 and that will traverse to other versus in this case we'll find what followed by the rated ages to the movie vertices without then we will filter out our Star Trek movies and we will get the set of movies that user was was watching so well actually let's see how the timer so whoa whoa look I will get pass and unfold it just to show you some kind of visualization the traversal was very simple we start from the users follow up the rated their juices and go to them doesn't movies well it's really simple one-step traversal we can do it a little bit more complicated so let's see what gender of this one also general this movies in this case we add one more out traversal with a genre ages and get a little bit much a little bit messy picture but still we start from the usual go to the movie and then go to the Jandra in this case is a sci-fi action and adventure but let ask more useful questions for example what is a what was the rating calls that Star Trek movies and we all in this case we will choose a much longer travel or so we will start from the usual go to the movies and in this case I will save the movies the rating of age as our then I will go to the movies then I will find movie that has a Star Trek and then I will select movies and ratings this will select keywords and I will get a table and it will show that user Reich that will show all the all the ratings so for example user like Star Trek 6 but hate Star Trek 5 when so in this place I will switch back to the Russell I will do all these fancy things everyone should just bask in that image while I get ready so this was a good example we had these little queries we started at one vertex we moved out we got a little bit of data and then we stopped but what happens when we have a lot of data what if we want to ask a question that relates to all of our data at once well then we start having to look past basic systems that start with just one vertex and we have to think about processing everything at once so for that we like to look at spark spark has a pretty basic execution model I'm just going to go over a quick overview of the things you need to worry about we start out with a driver which is like your application it's got a bunch of executors that run independent pieces of work the important thing to know about all of this is that they're each working on independent pieces of your data that are all separate and every once in a while whenever you want any piece of your data to relate to any other piece of your data you have to do a shuffle and shuffles are expensive and we generally want to avoid them you've probably heard this a few times so far at this conference there's a serialization penalty lots of stuff in there so shuffles over the network required disk i/o expensive bad we usually don't want to do them unless we have to so given that knowledge and that little basic understanding of SPARC how does tinker pop OLAP work so the tinkerer pops spark OLAP engine works by starting a traversal at every single vertice at once and then moving from all of those vertices to all the next vertices in a shuffle step and we've got a quick little diagram of how that works but before we can even do that we have to describe that distributing our data like this requires some kind of partitioning we need some way of taking all of our data and splitting it up amongst all these machines and the way we end up doing that in tinker pop is we build a pair RTD where one side is the ID for the vertex and then the other side of the pair is going to be all of the information about that vertice and its outgoing edges so this means we end up with this basic adjacency list representation where everything we would need to know about a vertex all of its properties and all the properties of its edges are directly accessible without doing a shuffle but if we want to go from one vertex to another vertex we have to do those shuffles because we have to match up the edge property which will have a another vertex ID on it to the ID column of our pair RTD so basically the way that's going to look is that we end up with this partition data that's sitting like this we start our traverser on every single vertex and then whenever we want to for example move from one vertex to another we perform a shuffle step and move our vertices to the new vertex is that they are going to land on the new vertices that they're landing on now we will probably end up doing this over and over again a lot of graph algorithms basically have this pattern of starting on one verdict vertex and then moving to another and you do that several times before you eventually terminate in return as a result so we'll repeat that with the shuffle every single time and go through and eventually we our traverses halt or the program that we've put into art reversers indicates that they are ready to halt and we return a result back to the user so the cool thing about all of this architecture is that you don't actually have to know any of this is happening when you actually write your traversal you use the same gremlin traversal language but the execution engine will just be this under the hood rather than doing a in-memory lookup that's what happens in the OLTP examples so let's just show a quick few examples of how that works [Music] so back to our example and to our movie universe and now we will do a lab queries first of all I will just cache the graph to run all the query faster and we'll ask another set of questions so now now I will ask a kind of a lot of questions about averages and about counts so the first question is how many movies in the data set for agenda and this is a well pretty simple one-step query we just get all the movies all vertices that have label movie and do our gender and then group count by name and we see that most of the movies drama and not not much sci-fi here but let's check who is watching sci-fi and in this case it will be a really long traversal because we will start from the wheel start from the genre sci-fi and we'll go to the occupation of the user so we will start Chandra go opposite direction to the by the Chandra age so we will go to the movie then we go to the users then we go to the occupation and group count by name and we will see that there are a lot of most of our users our students and they rate most of of scarify films and well programmers are only on the first play fifth place so but what what other programmers watching we will ask and in this case we will go in opposite direction but still it will be the same kind of Trevor so we'll start from the programmer go go by the cup patient to them go to the to the movie by rated go to the Chandra and we'll group I by name and we will see that well actually program you'll see a lot of watching a lot of SCI file much more than other guys so but what let's ask more useful questions what is the average Star Trek rating and that's another traditional all our question and in this case I will use a project project project case ok a new function but we will start from the Star Trek movies project names and ratings so native name will be get it as the value of the other movie properties and rating will be get it from the in age start and we'll do mean on it so we will see that well no one like Star Trek 5 you can see and it get for also writing so on this I wish so that was example of a lot kind of queries that use this bunch of so obviously doing this kind of traversal using tinker pop is going to have a bunch of pros and a bunch of cons so the main pros here is that every time we're doing a message pass using tinker pop we only have to do a single shuffle because we have that pair already D representation we already know the identity of every vertex that we're sending a message to so we don't actually have to look that up from somewhere else the edges and the edge properties are also all directly accessible without actually doing a step so if I need to look up something that's a value of my edge I don't actually have to shuffle to get that value it's very flexible because the language itself allows for a lot of different things to be composed and put together and basically arbitrary code can be written into this this library or into this language and then run and of course it can use basically any Java type anything inside can be inside of a vertex and you can do all kinds of exciting things there but the important comes to know here is that because our pair RDD is this adjacency list we're going to have a problem with extremely high degree verdict for Texas because we have an extremely high degree that means that the spark partition needs to necessarily hold all the information for every single edge that's associated with a vertex so a high degree vertex is going to basically oom our executor on the other hand of the flexibility of the framework well it makes it really possible for us to put all sorts of cool objects inside of our graph makes it a little bit harder for the graph engine itself to actually optimize the request we're doing we've seen a lot of talks about how catalysts works and a lot of talking about you know doing these low-level optimizations and you can't really do that when you have generic types inside of your vertices so that's some of the cons that come with tinker pop but there is another option that has a different set of pros and a different set of cons and that is graph frames graph frames is offered as a third party package it's another project out of the amp lab at Berkley and one of the greatest things about this is that it actually integrates directly in with the data set data frame world in the rest of SPARC so while tinker is kind of its own completely self-sustained self-contained collection of api's and server programs graph frames can be integrated with your data frame application that's written right now so just to do a quick example of how this is setup graph frames are built on a basic relational model unlike tinker pop which can have an underlying graph model the graph frame is built on two relational tables or data frames so those two data frames have only a few requirements the vertex data frame as we see over there has to have an ID column and then every other column is basically treated as a property and the edges data frame where we have a source and destination column and those columns have to directly indicate IDs in our vertex data frame so in this little example I have a tiny graph here where we have Geordi and data and they're linked together by a single edge which has a property of friend so one thing that you can notice here that's going to be different than in tinker pop is that we're only allowed to have spark SQL types here really only catalyst supported types can go in any of these columns we can't just put arbitrary objects in there because catalyst can't optimize that sort of thing so you have to have spark SQL types and the other thing is that there is no built-in concept of the label here so if our vertex data frame has different types of vertices in it then we actually have to manually add a column ourselves to indicate that for example that Geordi is a crew member and not a spaceship if we're gonna have them in the same graph so one of the cool things though that we get with all of this is that everything that we do in our data frames is going to kind of be going through the catalyst engine which means we get all of that great bytecode level optimizations we get all of the great reshuffling and reorganizing of our plan that's going to optimize it to hopefully give us better performance although some of the methods inside of the graph frames library do still fall back to graphics methods which are all RDD based but usually in these cases it's because there's a more efficient way to do this without a message pass and other things like that so let's take a quick look at a basic graph frame algorithm a basic grasp frame motif match so graph frames has a motif matching which is the basis of a lot of its algorithms and it looks a little like this syntax up in the corner where we have a in a curly braces and then an edge e inside of square braces connecting to another vertex B which again is in curly braces so when you pass this kind of string into graph frames and you ask it to find these triplets of a EB what it's gonna actually do is build up a series of joints so it starts by taking our vertex data frame and labeling every row that comes out of it as a because obviously we need our source vertices to be labeled then we join our a vertices on our edge data frame where the source of the edge matches the identity of a so this is going to be our first joint now we have a and we have E but we don't have B we don't have the endpoint of this edge to get that we have to join the endpoint of the edges in E with V vertices again and then we get B so now we've done two different joints and we've successfully completed a single step from one vertex to another and you might be saying that's two joints and before you showed me an example where we only had to do one join this is obviously not as good because joints are bad and shuffles are bad we don't ever want a shuffle so why would I ever want to do this over tinker pop well there's a couple reasons that you might so let's take a quick look at this query plan and look at it from the point of view of catalyst so catalyst is going to take a look at this and it's gonna say oh this query plan is completely malleable we're not going to execute it right away so let's say you asked to I don't know only look at one column out of this if you decide to only look at column a that that predicate is gonna actually get pushed up through this tree and every single place that it applies it can actually get pushed down to the source so you didn't actually have to explain to catalyst that oh don't worry selecting a means I only need the a column out or the ID column out of the vertex table it's gonna automatically do that for you and if possible push it down to the underlying source where it read this data from so you get all of that for free without actually having to plan on it the other cool thing is that all of your joints all the normal optimizations that happen when you run through catalysts are going to keep happening so it can check whether or not based on filters or based on pruning that the size of these other joins could be better served by doing for example a broadcast joint instead of doing a full shuffle joint so it can start making all of these optimizations in a way that you couldn't automatically do when you're running through tinker pop and of course the special magic of catalyst also happens where once this entire plan is put together once all of these predicates have been moved around and our joints have been chosen for their execution types we're going to do that same code gin that's going to happen with all other catalyst operations and we're not actually going to work on our java or serialized objects as we go through this so we end up with a much more optimized version of what we would do versus using plain old java objects the whole time so this is all pretty cool and artim is going to show us a few examples of how to actually use graph frames and we will use absolutely the same data the same universe but from another notebook it will be that line in this case and well actually I used data stacks data base here so I can query the same data with graph frames and with tinker problem in this case I will use our implementation of graph frames that has calm data style blah blah blah and so it's really easy to lower it just saying I need graph movie lines and I cash it for the performance so on as a Russell say it graph frame is just two data frames its vertices and ages data frames that I can count on them so this case I have 1 million ages here I can show them I can show all this ages and vertices and you will see that in this case I have to define ID we add label here because we are compatible with the Tinker apartment so we can see users here for example and we have all other columns in a and here and the same for the ages we have to define SRC DST and label columns just to have the different columns and it will ask the same question to the to our graph but using motif finding in this case we will ask what I'm asking here I'm sorry [Laughter] so it will be a question what program in some way I'm sorry I'm sorry it's but the language is not us so good as a secret program so in this case we have over smarty per se users occupation a checkup Asian users rated the movie movie gender to genre and we will filter out based on labels so that occupation Asia's it's HV skills label label occupation and rated Asia's label rated and general label is native and that will do group by countess will do it for battle friends and so you see that it's a little bit longer and I cannot read it but the result is the same and well actually if you take a look at the joints that that query will generate that kind of join oh not that one because that one is right and for the correct SQL database that have different tables for different objects so for the in our case let me show you the real one so I will just create two tables one is for vertices and one for ages and I will have just two tables for them and I will the judge will look like something like that I will join join ages on wave Syst and we can count them one two three four five six so we have a six join for this simple query and well it's provide absolutely the same results old group by my channel name and count by the way graph frames are much better much more readable than this kind of joint but the most important thing for the graph frame it's really a part of the spark ecosystem so I can really simple join this data with any other data frames I have an a in a spark a consistent with my SQL Cassandra TC any other so let's imagine we have additional data that say that our user seven 100 is Russ and we have a user ID and username here so I can just join this data with our vertices create new graph frame with our new vertices and ask how much movie was rated by Russell and we will find out that he he was watching more than 800 movies the same thing is experts and import is also very simple because it just two tables so safe our graph in this to the disk we just need to get vertices and write them and get the get edges and write them and we can then export them import them back for example we can use as spark SQL just to select ID versus series ID and edges with SRC and est columns so well actually is write a lot of graph algorithms available in the graph frame because all of them are get it from the graphics and use this usage of this algorithm are really simple just in one line and most interesting thing that there is an ADD data stacks we mix both languages and get best thing from the tinker pop and best thing from the graph range and in this case in data frame you can mix all these two languages you can use the traversal language from ticker pop get a data frame and then use a data frame method to save data or two in this case group by group by name and count and you will get absolutely the same results so we just talked a little bit about graph frames and let's talk now about our performance Pro cons here so again we're going to be much faster on basic counts things like that because our counting engine is going to be our optimized byte code versions rather than Java serialized objects having actually accessed numbers and fields whenever we filter and things like that we've got this powerful optimization framework and code gen and it's really simple to add to other sources so when you know when we've been talking about composability a lot today this is a key to being able to take graph algorithms and put them into the middle of a pipeline that's doing a lot of other things doing ml work that comes out with a model that applies to a data frame and then want to use that in the graph it's very easy to do when you're using the graph range library some of the cons are it's not as fast on more complex traversals because the way it's storing the edges and the vertices and different data frames means that we have to do two joins every single time we want to do a single step from one vertex to another and the relational model of course is not as flexible you probably saw when Artem loaded that data he had to actually include empty null fields for all the things that weren't a part of the particular vertex if it didn't match the if that first didn't have those fields so it's got a bit of a different performance thing so when you're choosing between these two you really need to take into account what exactly are you planning to do with graph data so if you're using a more complicated query a traversal that requires a lot of different hops or a lot of extensions then it probably makes sense to choose tinker pop because tanker pops gonna have this more efficient method of actually propagating through the graph to a greater depth but it's not going to be as fast if you're doing a lot of simple counts or aggregations and of course because of its storage method a very high degree vertices is going to lead to executors out of memory exceptions so this is something that's being worked on right now but currently there's no real solution if you have a vertex that perhaps dominates your graph so for example we've seen graphs where perhaps location is one of the vertex types and one of the locations is perhaps China and you have a lot of users that happen to live in China so you end up with a single vertex that has hundreds of millions of edges and obviously that's gonna blow up your graph when it starts trying to shuffle it on the other hand graph frames is going to be able to have a different storage method so it'll be able to fix for a lot of that stuff it's got a lot of great use cases if you're doing average stats or aggregations and things like that connecting to other sources becomes really really easy and of course these short paths are gonna be really easy to do because it's gonna be able to optimize away some joins in cases a tiny jump so whichever you choose we would be remiss if we didn't say check out data stacks enterprise because it allows you to use both of these at the same time on a shared library of data we write it so we're very proud of things that we do and that's about it so thanks for listening to us if you want to learn more about graphs we've got a link here to the free data stacks Academy courses and you can try the stuff we work on in data stacks enterprise and of course there's some links to Apache tinker pop and graph frames if you're more interested in just those libraries all by himself and that's it for us so if anyone has any questions we would be glad to field any [Applause] you see network so our question is that everything we want to retrieve our vertex other than will I be having with the index I offer you an index cardinality of one you cannot guarantee that this only one so there's no uniqueness of no other than their primary ID so the suggestion mental time Ally is not Rwanda or lab correct moongra now what kind of methods we run on preferring perfects because the graph frame is was addition to the that of my data stack so especially for the whelk update and bug delete so it should be draw frames yeah this is one of our tune and say this is something he wrote he wrote some additional bulk update methods into the graph frames library so if you are using data sex Enterprise you can bulk change your data from a graph frame [Music] yeah [Music] so I don't think anyone's done some good math on this yet in general you want to remember that under the hood we're really still just doing a lot of joints so general things that you want to do is with any joins is you want to try to make sure that you're not doing a bunch of gigantic joins try to keep one side low cardinality if you can get that into a broadcast instead of you know otherwise I don't I don't know do you have other well that's the there you go well I I still think that if you have real a lot of different objects so you have this object entity model for your SQL data and if you need to traverse them your so you'll better to use tinker pop and that's why we also with much shorter your two-page SQL that you ran for that kind of travel also and in this case it will be probably even faster than than your SQL database because it will use all the spark things how do you feel that about which what should be late what should be vertices in what should be edges well actually it's really simple if you have entity relationship entities entities of vertices and relationship as ages it's a and it's really natural to do that kind of method anybody else okay well thanks so much for coming out and feel free to talk to any of us later about any of this stuff or Cassandra I guess because we spent a lot of time in that too [Music]