4 ms·
High-Performance Graph Databases
- belter 4y ago"...we harness established practices from the HPC landscape to build a system that outperforms all past GDBs presented in the literature by orders of magnitude, for both OLTP and OLAP workloads. For this, we first identify and crystallize performance-critical building blocks in the GDB design, and abstract them into a portable and programmable API specification, called the Graph Database Interface (GDI), inspired by the best practices of MPI. We then use GDI to design a GDB for distributed-memory RDMA architectures. Our implementation harnesses one-sided RDMA communication and collective operations, and it offers architecture-independent theoretical performance guarantees. The resulting design achieves extreme scales of more than a hundred thousand cores..."
- deleted 4y ago[deleted]
- lasfter 4y agoMaciej Besta, the first author of this paper, is a machine. Aside from coordinating big groups to write tons of papers, he does a bunch of impressive wilderness exploration. I recommend checking out his website, there's some stunning photos: https://people.inf.ethz.ch/bestam/expeditions.html https://people.inf.ethz.ch/bestam/expeditions.html
- mathisfun123 4y agoTorsten is PI of that group not Maciej so you're half right, since being Maciej is first author on this one he probably did most of the technical work (and who cares about "coordination").
- osigurdson 4y agoStating that someone “is a machine” is somewhat ambiguous these days as it is increasingly possible that they literally are one.
- gumby 4y agoI also misinterpreted that sentence!
- hackernewds 4y agoIt's nice ChatGPT hasn't been named something like Alexa. Else we would be anthropomorphizing it even more!
- gumby 4y agoUnfortunately we named our kid ChatGPT 20 years ago…
- EGreg 4y agoWasn’t TJ Holowaychuk confirmed to be an AI, or a group of people like Bourbaki? He never showed up at any events :) https://qr.ae/pyvfKK https://qr.ae/pyvfKK
- z3t4 4y agoI once was obsessed at finding the holy Grail of optimization and scaling, but then came to the conclusion that every system is optimized and scaled differently. Different systems have different bottlenecks.
- slively 4y agoSo true, rarely is anything the “best” or “better”, but instead each thing is a bucket of trade offs we choose from. Maybe frustrating, but also what makes engineering genuinely interesting.
- uptownfunk 4y agoThis sounds similar to the no free lunch theorem in AI
- jjgreen 4y agoHuh? NFL is a theorem on optimisation, not AI
- cubefox 4y agoIt's originally a theorem about supervised learning, which turned out to be the prototypical application (via CNNs) of deep learning. Deep learning is now mostly synonymous with AI. Though I'm not aware of any NFL theorem for reinforcement learning or unsupervised learning.
- mumblemumble 4y agoGiven that the most well-known use case for optimization algorithms is training machine learning models, it seems to me like a perfectly reasonable, if buzzword-oriented, thing to say.
- jandrewrogers 4y agoI am a little confused by the purpose of this paper. The architecture described is roughly how graph databases have always been implemented on HPC systems. The main contribution seems to be that they put a lot of polish on what were admittedly prototype-ish implementations historically? I was hoping for some interesting approaches to some of the fundamental computer science problems that cause scaling issues when graphs become large but this is more of a standard “throw hardware at it” solution (which has significant limitations).
- mathisfun123 4y agoI love this - "it's just engineering" say the people that think the hardest part about building a spaceship is having the big idea to build the spaceship. Note the "I love this" was sarcasm.
- jandrewrogers 4y agoMy point was that the architecture they are using has already been done multiple times for graph databases using things like RDMA (which has existed in HPC for ages), that is a known quantity. It was less "it's just engineering" and more I've seen similar implementations for a long time so what makes this different? I am interested in this space in part because I spent much of my time in HPC working on graph databases.
- eternalban 4y agoYou should quickly skim sections marked with a (comically fat) "!" symbol. These indicate their "key design choices and insights" in the design space.
- lmeyerov 4y agoAgreed. They brush aside the years of high performance computing graph implementations, eg, cuStinger. If you look at systems like neo4j's GDS and how other multipurpose systems are going wrt views/projections for accelerated compute, that has been enabling targeting way more performance without dying under complexity. Benchmarking perf without that kind of comparison is weird, I'm surprised reviewers allowed that. (The work may still be good.. just you can't know without that.)
- shrubble 4y agoWhat would be a use of 100k cores for a graph database?
- henrydark 4y ago100 use cases for 1k cores
- jandrewrogers 4y agoAggregate effective memory bandwidth if you use the CPU cache well. Graph databases are not compute intensive, nor are they particularly large data models, but they are extremely memory I/O intensive. The classic model for graph-oriented HPC was vast numbers of weak cores and barrel processors for this reason, though the utility of specialized hardware architectures has been greatly reduced by better software architecture for this purpose over time.
- ocrow 4y agoA social media service for hundreds of millions of users?
- threeseed 4y agoFraud analytics. You're looking for patterns across large numbers of entities and relationships. And ideally you want this all done in real-time so you can stop transactions before they are approved.
- lasfter 3y agoAny chance you could expand on this? I hear about pattern matching for fraud analytics but I have never seen concrete examples, or even anything in the literature.
- uptownfunk 4y agoWhat are these used for in the “real” world?
- perfect_wave 4y agoA few that I’ve encountered: - Feature generation for machine learning model training (particularly popular with fraud detection at financial institutions) - social networks (think LinkedIn or Facebook) - supply chain analysis and optimization - healthcare patient data analysis (looking at similar patients to recommend treatments or do large scale analysis) - user identification (eg taking lots of data points and tying to a specific user). There’s a more specific name for this I can’t remember off the top of my head.
- studmuffin650 4y agoCybersecurity is also a large industry that makes use of large scale graph databases
- fulafel 4y agoIf you mean graph databases generally: Most DB using applications can be built on a graph database. It's just a different data modeling framework than eg relational. Generally you could say that application logic/queries being more concerned about links or linked entity attributes than direct entity attribute values is a sign that a graph DB may be a good fit. I'd say about 50% of db using apps are like this. You can get an idea by looking at their benchmark workload descriptions. If you mean fully RDMA offloaded huge cluster DB systems, then I don't know the answer but suspect this kind of thing hasn't made it to industry yet: "GDA internally uses a distributed hashtable (DHT) to resolve dif- ferent performance-critical tasks conducted under the hood, such as mapping application vertex IDs to internal GDA IDs. For highest performance and scalability, GDA’s DHT is fully-offloaded, i.e., it only uses one-sided communication, implemented with RDMA puts, gets, atomics, and flushes. Its design is lock-free, it incorporates sharding, and it uses distributed chaining for collision resolution. To the best of our knowledge, this is the first DHT with all its oper- ations being fully offloaded, including deletes. The DHT consists of a table (to store the buckets) and a heap (to store linked lists for chained elements)."
- LukeEF 4y agoI am not sure of the exact statistic, but something like 95% of all production databases are less than 10GB. There seems to be a 'FAANG hacker' fascination with 'extreme-scale' which probably comes from seeing the challenges faced by the handful of organizations working at that level. Much of the time most graph database users want (as in why are they there) a DB that allows you to flexibly model your data and run complex queries. They probably also want some sort of interoperability. If you can do that well for 10GB, that is holy grail enough. We certainly found that developing graph database TerminusDB [1] - most users have smaller production DBs, more lightly use bells and whistles features, and really want things like easy schema evolution. [1] https://github.com/terminusdb/terminusdb https://github.com/terminusdb/terminusdb
- belter 4y agoInteresting that you mention the value 10 GB, as it is the size of a DynamoDB partition or an AWS Aurora cell...
- im_down_w_otp 4y agoI think I kind of agree with this. One of the simpler supported backends for our Modality product (https://auxon.io/products/modality https://auxon.io/products/modality), which results in a data model that’s a special case of a DAG for modeling big piles of casually correlated events from piles and piles of distributed components for “system of systems” use cases, is built using SQLite, and the scaling limiter is almost always how efficiently the traces & telemetry can be exfiltrated from the systems under test/observation before how fast the ingest path can actually record things becomes a problem. That said, I do love me some RDMA action. 10 years ago I was fiddling with getting Erlang clustering working via RDMA on a little 5 node Infiniband cluster. To mixed results.
- threeseed 4y agoThis research paper is talking about performance whilst you're talking about scalability. Those are related but are distinct from each other. And sure about 95% of companies would have their needs met with a simpler system but that does leave a lot of companies who will not. And for those of us in say finance doing customer/fraud analytics I would welcome all the performance I can get.
- mihirmp 4y agoAt what performance threshold should one migrate from a relational database to a graph database? In other words, is there something like OtterTune that can help me figure out the best storage engine (SQL vs NoSQL vs Graph vs Timeseries) for my service based on traffic patterns?
- apavlo 4y agoAndy from OtterTune here. I suppose that it is possible to do something like this. We've explored the idea of synthesizing a workload that behaves like an application's real workload. The idea was to do offline testing with the synthesized workload to find optimal configurations that can then be applied to the production database. Our results were inconclusive (not enough real workloads to verify). But the idea could be extended for what you are proposing. But in terms of relational vs graph, my opinions about the matter are public: https://www.theregister.com/Debates/2023/03/06/great_graph_debate/ https://www.theregister.com/Debates/2023/03/06/great_graph_d...
- samsquire 4y agoHow do you search a graph that is separated onto different machines? I know a matrix multiplication can be a breadth first search if you use a 1 for each column you want to breadth search. How do you shard a graph data structure?
- emmanueloga_ 4y agoFollowing the RDF model, every node and edge of a graph can be represented as: subject -> predicate -> object; Example: `<bob> <isa> <person>` (from this RDF primer [1]). Sharding data that follows this model sounds easy? Any sort of rule and/or hashing over the triples could be used to send triples to arbitrary servers. 1: https://www.w3.org/TR/rdf11-primer/#section-triple https://www.w3.org/TR/rdf11-primer/#section-triple
- motohagiography 3y agoThank you for such a succinct explanation of the RDF model of graphs. I have developed applications with cypher and neo4j, and skipped gremlin and even graphql because I found the RDF schema descriptions too complicated to bother with. Nodes and relationships seemed sufficient, but that everything as an implied digraph here makes it clearer. My note thanking you is a multiple of the length of your explanation, which is a pretty good measure!
- emmanueloga_ 3y agothank you!
- samsquire 3y agoThanks for this. I have worked with RDF and N3 notation. I created a D3 visualiser from Jena Fuseki database https://camo.githubusercontent.com/3064a94d00812c1373c4eb3b2ac85e7f5a68dff08df7e25740ae963a2be34d51/68747470733a2f2f7261772e6769746875622e636f6d2f73616d7371756972652f696e746572666163652d6578706572696d656e74732f6d61737465722f6c6976696e672d646f63756d656e742d656469746f722e706e67 https://camo.githubusercontent.com/3064a94d00812c1373c4eb3b2... It renders RDF/N3 relationships. Unfortunately the code is trapped in an Sqlite jsbin file :-) It never occurred to me that it would be that trivial to shard, you could mapreduce the queries. I just worry about how you would do joins on data that live on independent nodes. If a value is on server A and another on server B and there would be a relationship between them, how would you "join" this data unless you colocated join keys.