Introduction
In the graph world, supernodes are a common yet devastating problem. In the Cassandra world, wide-partitions can be paralyzing and have a ripple effect across your cluster. Put them together, and you’ve got yourself into a lot of trouble!
Supernodes can impact your cluster in many different ways, but it is not hard to see why it is particularly problematic due to the way it can cause wide-partitions in Cassandra. A supernode is a single node vertex that has a disproportionately high amount of edges (Justin Bieber’s Twitter account is a common example). Accordingly, since edges are generally stored on the same partition as the vertex (more on that later), a supernode can very easily create a wide partition.
Anyone who has used Cassandra before will tell you that the key to avoiding wide-partitions is to have the correct data model, and that applies here as well. DSE Graph is a Tinkerpop implementation that uses Datastax’s implementation of Cassandra as a backend. Accordingly, in order to avoid disaster down the line as you scale up your data, it is crucial to know what’s going on under the hood of DSE Graph so that you can model your data properly.
This issue has been addressed before by the excellent two-part blog-post by Ted Wilmes of Expero, but that was in January 2017, and regarding DSE Graph 5.x. Changes made to DSE Graph since then mean that there are now different considerations involved in addressing this issue.
Accordingly, the goal for this series of blog posts is to bring us up to date for DSE 6.7 and 6.8 in particular. This first part will give an overview of the background information and investigate changes to the partitioning behavior made in DSE 6.0-6.7. The second part will be to apply what we learned from the first part, getting hands-on with DSE Graph 6.7 and showing how to break apart wide partitions caused by supernodes in light of changes made since DSE 5.x. Then finally, since substantial changes were made to DSE Graph 6.8 that calls for a totally different approach than what we do in 6.7, part three will focus on DSE Graph 6.8.
How DSE Graph partitioned vertices and edges in 5.x
Hopefully not many of you are using DSE 5.x still, but in order to understand what is going on in DSE 6.x, it will be helpful to first review the way that DSE Graph partitioned edges and vertices in DSE 5.x. That way we will know how our solution will differ from solutions offered in the past. For that, I will defer to the excellent blog post by Ted Wilmes of Expero.
To quickly summarize, the idea is that in DSE 5.x, there was automatic partitioning available. For automatic partitioning, edges are duplicated and stored in partitions with both vertices. On the other hand, vertices are stored in the same partitions with other vertices that were created in the same transaction and with the same label.
Custom Vertex IDs in DSE 5.x
However, for more control, you could opt out of automatic partitioning and instead use “Custom Vertex Ids”, in which case the vertex’s partition is determined by its id instead (though note that the edge is still duplicated and stored in the same partition as both vertices). This way, you could avoid edge cuts, which is where two connected vertices live in different partitions. As is always true of Cassandra, when possible you want to keep data that is going to be queried together in the same partition. However, if two vertices are stored in different partitions, then traversals between these vertices will necessarily cross partitions, and possibly require a network hop to a different node in your Cassandra cluster.
Custom Vertex IDs would not necessarily solve the supernode issue, however. If you have a few larger nodes (maybe we could call them “semi-supernodes”), then of course maybe you would want to try to make sure that they are not located on the same partition to avoid wide partitions by specifying different custom vertex IDs. But if you have a single supernode that is big enough to be a supernode in itself, it does not matter how many other vertices are co-located with it. For example, if the Justin Bieber supernode has 114 million followers as edges since those 114 million edges are all stored on the same partition as the vertex, just that one node is enough to create a wide partition regardless of whether or not other vertices are in the same partition or not.
Partitioned Vertices in DSE 5.x
Hence Ted Wilmes’ second blog post, on Taming Your Supernodes. He points out that if you cannot avoid creating supernodes in the first place by changing your data model, you can use what is called Partitioned Vertices. This allows you to store the edges of certain vertex labels apart from your vertex. So, for the Justin Bieber node, you could split up his 114 million “follower” edges across several partitions, and thereby avoid wide-partitions for that supernode.
However, all of this changed in DSE 6.0…
How DSE Graph partitions vertices and edges in 6.0-6.7
Two big differences stand out in regard to DSE Graph between 5.x and 6.0 – you guessed it, custom vertex IDs and partitioned vertices.
All Vertex IDs are “Custom IDs”
To quote the release notes:
“Standard vertex IDs are deprecated. Use custom vertex IDs instead. (DSP-13485)”
In other words, using the terminology used in the Expero blog post, now there is no option besides implementing “User-Defined Partitioning” using “DSE Graph Custom Vertex Ids” – there is no longer any “DSE Graph Automatic Partitioning” available.
Partitioned vertex tables are removed
Again, quoting the release notes for DSE 6.0:
Partitioned vertex tables (PVT) are removed. (DSP-13676)
I personally was still unsure about the full implications of this comment, so asked for clarification on Datastax Community and got my answer: the mechanism for partitioning vertices was removed.
Solution: Intermediary Vertices
Instead, the solution to breaking up supernodes is by creating “intermediary vertices”. The best explanation I could find for this is from this StackOverflow post, by a DSE team member. The idea is that a supernode’s edges would be split up into “buckets”. For example, a vertex with 1 million edges could have 1000 such intermediary vertices (AKA 1000 buckets), and the 1 million edges would then be divided up among them. The result that instead of having 1 million edges, the former supernode now has only 1000 edges (one to each intermediary vertex), and each intermediary vertex has 1000 edges each.
There is of course a downside to this approach: if you ever have to traverse from the supernode out to its edges, now there is not only the performance hit caused by “edge cuts”, but now there is an extra hop required (one from Justin Bieber to the intermediate vertex, one from the intermediate vertex to his followers). Additionally, from an application point of view, there is also additional complexity required to navigate through these intermediary vertices.
That said, being able to break up wide partitions means potentially solving all kinds of other (often worse) problems.
Conclusion
It is worth noting briefly that there are other ways to mitigate the effects of supernodes as well besides this, including proper indexing, or general graph data modeling strategies such as moving some information to a property instead of on the edge, or vice versa (depending on your query patterns). Furthermore, in an ideal world, you could avoid creating supernodes in the first place, but if you can’t, then you will want to know how to break it apart when needed.
In part two we will demonstrate how this works in a more hands on format, showing how this works with code examples and the resulting in partition size. In the end we will see that although there is a solution to the wide-partitions issue in 6.7, it is less than ideal in many ways. From there, in part three we will go on to see how a better solution is possible due to changes made in DSE 6.8.
Series
- Partitioning in DSE Graph
- Solving Wide Partitions caused by Supernodes in DSE 6.7
- Solving Wide Partitions caused by Supernodes in DSE 6.8
Cassandra.Link
Cassandra.Link is a knowledge base that we created for all things Apache Cassandra. Our goal with Cassandra.Link was to not only fill the gap of Planet Cassandra but to bring the Cassandra community together. Feel free to reach out if you wish to collaborate with us on this project in any capacity.
We are a technology company that specializes in building business platforms. If you have any questions about the tools discussed in this post or about any of our services, feel free to send us an email!
