4 ms·

Could you elaborate on this argument? For something like a graph, I din't quite follow why a KV API is problematic or how you'd do it better. If you want to map

• jandrewrogers 5y ago
  The core design problem for graph databases is data locality during join recursion. If you shard your data model by key, the cross-shard join operation asymptotically converges on a Cartesian product for each join iteration i.e. pathological data locality. This is why most graph databases have such poor scalability in practice. A less intuitive approach is to shard the data model based on edge similarity measures, such that a specific key does not map to a single shard. While this obviously has poorer locality for simple key lookup, cross-shard join operations -- the most expensive operation and what actually matters -- only involve a tightly bounded number of shards and therefore have much better locality. While this was originally developed for to make the problem scale on supercomputers (at IBM Research AFAIK), it is entirely amenable to use in graph databases. At the storage engine level, first-class support for indexing by similarity measures has different design requirements and tradeoffs than simple key lookup or ordered-tree indexing. While you could make it work on a KV store, the impedance mismatch would incur a significant performance drag. This cuts both ways; storage engines optimized for use with similarity measure designs are going to offer poor performance if you try to put b-trees or LSM-trees on top of them.