4 ms·

>a logical KV store I've always considered KV to be an API. Under the hood you're still using data structures managing fixed-size blocks and byte-offsets, such

>a logical KV store I've always considered KV to be an API. Under the hood you're still using data structures managing fixed-size blocks and byte-offsets, such as LSM trees, and using binary searches to minimize disk reads (e.g. index files of very 128th 64k key block). If you're building something more robust on top of a KV store, I'd be under the impression you're not doing so using the logical API but leveraging the underlying data structures with algorithms better suited to the task. An LSM tree is pretty decent at random seek/scan, and implementing something like JOINs is less about KV constraints as it is LSMT constraints. For example, FoundationDB doesn't use SQLite directly but rather its B-tree implementation.

jandrewrogers 5y ago
I intentionally added the word "logical" because I think it is important. All database engines are KV at the physical page/block I/O level but they almost never expose that to the user, and there is no requirement to limit the expression to what the lower level can express. The primary limitation of KV as an API is that it can't directly express complex but elementary relationships between keys e.g. intersections when your keys are constraint types. Or graph traversal relationships, if efficiency on real hardware matters at all. Most complex databases, like SQL, are implicitly searching across relationships like this constantly. Not being able to express these types of relationships as first-class citizens is computationally expensive. Putting a KV store under every database is a recent fad. Databases classically had more expressive but still inadequate storage architectures (e.g. first-class operations on constraint types were terrible there too), so this is a step backward in most ways -- but I understand why expediency incentivizes that approach. Kind of like discarding joins to achieve scale-out -- joins are critical operations for many things but scaling out joins requires very challenging computer science. On the flip side, a lot of the cutting edge research has been focused on jamming as much expressiveness in a singular index-organized store as possible, in as little space as possible. This has proven to be a very effective, albeit more difficult to understand. LSM trees are a good example of an incremental hack to address limitations in more traditional approaches while not solving the underlying fundamental issues with the way the indexing structures are constructed. LSM tree write throughput is okay but not great, empirically. Similarly, the query performance is okay but not great, for reasons that are well-understood from other contexts in database engine design. You can use it to solve a specific problem but it is unclear why it should be the solution to a general problem. KV stores, LSM trees, etc are stuck in a suboptimal local minima.
- native_samples 5y ago
  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 node locality to KV locality you can certainly do that.
  - 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.

jandrewrogers 5y ago

I intentionally added the word "logical" because I think it is important. All database engines are KV at the physical page/block I/O level but they almost never expose that to the user, and there is no requirement to limit the expression to what the lower level can express. The primary limitation of KV as an API is that it can't directly express complex but elementary relationships between keys e.g. intersections when your keys are constraint types. Or graph traversal relationships, if efficiency on real hardware matters at all. Most complex databases, like SQL, are implicitly searching across relationships like this constantly. Not being able to express these types of relationships as first-class citizens is computationally expensive. Putting a KV store under every database is a recent fad. Databases classically had more expressive but still inadequate storage architectures (e.g. first-class operations on constraint types were terrible there too), so this is a step backward in most ways -- but I understand why expediency incentivizes that approach. Kind of like discarding joins to achieve scale-out -- joins are critical operations for many things but scaling out joins requires very challenging computer science. On the flip side, a lot of the cutting edge research has been focused on jamming as much expressiveness in a singular index-organized store as possible, in as little space as possible. This has proven to be a very effective, albeit more difficult to understand. LSM trees are a good example of an incremental hack to address limitations in more traditional approaches while not solving the underlying fundamental issues with the way the indexing structures are constructed. LSM tree write throughput is okay but not great, empirically. Similarly, the query performance is okay but not great, for reasons that are well-understood from other contexts in database engine design. You can use it to solve a specific problem but it is unclear why it should be the solution to a general problem. KV stores, LSM trees, etc are stuck in a suboptimal local minima.

native_samples 5y ago
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 node locality to KV locality you can certainly do that.
- 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.