3 ms·

There is one caveat I would add. While you can always build just about any kind of database or data model on top of a logical KV store, the scalability and perf

There is one caveat I would add. While you can always build just about any kind of database or data model on top of a logical KV store, the scalability and performance is almost always going to be qualitatively worse for queries than using a storage engine purpose-built for the intended type of database or data model. It is simpler to implement, which is why people do it, but you give up a lot of selectivity and locality on the query side. The target design case for KV stores is when all your queries are essentially trivial. Layering SQL on top of it implies the expected use case is complex queries of the type where a KV store won't perform well. Good for a compatibility interface, but not performant.

skrtskrt 5y ago
though as with things like CAP theorem, there are always clever ways to to place a given implementation at various points along the spectrum, rather than just at one end or the other.
sa46 5y ago
Very curious, what’s an alternative implementation strategy or more appropriate mental model? My mental model (I am not a database engineer) is that every SQL database is fundamentally backed by a key value store. For Postgres, each value is a row of a relation, the key is the relation’s key, and the physical storage is the table file. Postgres builds b-trees on top to make it fast, but the b-tree itself is a relation, a key value store that Postgres works hard to keep sorted.
- travisd 5y ago
  i’m also not a db engineer, but i think this is true-ish. however building and maintaining those index tables is hard and probably prone to issues if you can’t update multiple as part of the same transaction. the other major thing you’d miss is smarter joins. the distributed databases do a lot of work to be able to push down predicates as far down as possible to the physical nodes storing the data. there’s probably more as well.
  - Gaelan 5y ago
    > probably prone to issues if you can’t update multiple as part of the same transaction IIRC one of FoundationDB's features is that it does support such transactions, so you can easily implement indexing on top of it.
- mamcx 5y ago
  Not expert, but as enthusiast I have read some about this (for https://tablam.org https://tablam.org). KV is truly ill-suited for this. Is very easy to see if you put the data layout: --data pk city country 1 miami USA 2 bogota Colombia --As Kv (naive): pk1: 1 pk2: 2 city1: miami city2: bogota --As btree, with "value" being N (as you say): Key Value 1 1 miami USA 2 2 bogota Colombia --As paged btree Page1 Low: 1 High:2 //think this is a block 1 miami USA 2 bogota Colombia --As columnar: pk: 1 2 city: miami bogota --As PAX (hybrid columnar/row) Page1 Low: 1 High:2 //think this is a block pk: 1 2 city: miami bogota
- jandrewrogers 5y ago
  Many data models don't have obvious singular keys. The critical search relationships cannot be reduced to an order relationship on a single column a priori. Much of the most interesting research in storage models is around increasingly efficient ways of indexing complex information theoretic features across multiple columns in a single structure, with an underlying storage implementation to match. At some level, every database contains a key-value store. For performance reasons, the hardware always has to be treated this way. Databases work at the level of blocks/pages, but those abstractions are usually hidden from users with a lot of clever logic in the middle that is more opinionated to enable optimization. That doesn't change. An interesting and important property of search data structures is that, at the limit, a single index that can optimally satisfy all possible queries is equivalent to general AI. It is also completely intractable. Fortunately real-world queries tend to be much more limited in nature. A corollary is that the distinction between indexing, storage, and scheduling in databases is a fiction -- useful for making some things simple but not necessary in any database. In essence, the practice of treating indexing, storage, and scheduling as discrete functions in a database is the opposite extreme. There are a vast number of possible implementations between these two extremes with better properties than either in practical real-world databases. As a general design principle for scalability and performance reasons, you want to organize your data model around a single indexing mechanic. Consequently, it is critical to maximize the expressiveness and efficiency of any particular indexing mechanic. At the limit, with a good algorithm, it is equivalent to having an index for each column, with the ability to efficiently search more features of the data and without the overhead of actually having an index for each column. I think we are entering a new golden age of database technology where the boundaries between elements we treated as discrete are much fuzzier.
  - anonymousDan 5y ago
    Any papers you can recommend that go into this in more detail?
manigandham 5y ago
Yes, agreed, although a lot of storage modalities naturally map to key/value in some way. Ironically FDB uses SQLite for the storage servers. Abstractions all the way down.
ovaistariq 5y ago
I think of FoundationDB as a low level persistence layer that you can use to build a fully functional database on top with more complex querying capability. It provides the core set of semantics such as data replication, globally ordered transactions and horizontal scalability - that are all complex to build in their own right. If you look at CRDB or TiKV design, under the hood they are also KV-stores with SQL layered on top.
tomnipotent 5y ago
>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.

skrtskrt 5y ago

though as with things like CAP theorem, there are always clever ways to to place a given implementation at various points along the spectrum, rather than just at one end or the other.

sa46 5y ago

Very curious, what’s an alternative implementation strategy or more appropriate mental model? My mental model (I am not a database engineer) is that every SQL database is fundamentally backed by a key value store. For Postgres, each value is a row of a relation, the key is the relation’s key, and the physical storage is the table file. Postgres builds b-trees on top to make it fast, but the b-tree itself is a relation, a key value store that Postgres works hard to keep sorted.

travisd 5y ago
i’m also not a db engineer, but i think this is true-ish. however building and maintaining those index tables is hard and probably prone to issues if you can’t update multiple as part of the same transaction. the other major thing you’d miss is smarter joins. the distributed databases do a lot of work to be able to push down predicates as far down as possible to the physical nodes storing the data. there’s probably more as well.
- Gaelan 5y ago
  > probably prone to issues if you can’t update multiple as part of the same transaction IIRC one of FoundationDB's features is that it does support such transactions, so you can easily implement indexing on top of it.
mamcx 5y ago
Not expert, but as enthusiast I have read some about this (for https://tablam.org https://tablam.org). KV is truly ill-suited for this. Is very easy to see if you put the data layout: --data pk city country 1 miami USA 2 bogota Colombia --As Kv (naive): pk1: 1 pk2: 2 city1: miami city2: bogota --As btree, with "value" being N (as you say): Key Value 1 1 miami USA 2 2 bogota Colombia --As paged btree Page1 Low: 1 High:2 //think this is a block 1 miami USA 2 bogota Colombia --As columnar: pk: 1 2 city: miami bogota --As PAX (hybrid columnar/row) Page1 Low: 1 High:2 //think this is a block pk: 1 2 city: miami bogota
jandrewrogers 5y ago
Many data models don't have obvious singular keys. The critical search relationships cannot be reduced to an order relationship on a single column a priori. Much of the most interesting research in storage models is around increasingly efficient ways of indexing complex information theoretic features across multiple columns in a single structure, with an underlying storage implementation to match. At some level, every database contains a key-value store. For performance reasons, the hardware always has to be treated this way. Databases work at the level of blocks/pages, but those abstractions are usually hidden from users with a lot of clever logic in the middle that is more opinionated to enable optimization. That doesn't change. An interesting and important property of search data structures is that, at the limit, a single index that can optimally satisfy all possible queries is equivalent to general AI. It is also completely intractable. Fortunately real-world queries tend to be much more limited in nature. A corollary is that the distinction between indexing, storage, and scheduling in databases is a fiction -- useful for making some things simple but not necessary in any database. In essence, the practice of treating indexing, storage, and scheduling as discrete functions in a database is the opposite extreme. There are a vast number of possible implementations between these two extremes with better properties than either in practical real-world databases. As a general design principle for scalability and performance reasons, you want to organize your data model around a single indexing mechanic. Consequently, it is critical to maximize the expressiveness and efficiency of any particular indexing mechanic. At the limit, with a good algorithm, it is equivalent to having an index for each column, with the ability to efficiently search more features of the data and without the overhead of actually having an index for each column. I think we are entering a new golden age of database technology where the boundaries between elements we treated as discrete are much fuzzier.
- anonymousDan 5y ago
  Any papers you can recommend that go into this in more detail?

manigandham 5y ago

Yes, agreed, although a lot of storage modalities naturally map to key/value in some way. Ironically FDB uses SQLite for the storage servers. Abstractions all the way down.

ovaistariq 5y ago

I think of FoundationDB as a low level persistence layer that you can use to build a fully functional database on top with more complex querying capability. It provides the core set of semantics such as data replication, globally ordered transactions and horizontal scalability - that are all complex to build in their own right. If you look at CRDB or TiKV design, under the hood they are also KV-stores with SQL layered on top.

tomnipotent 5y ago

>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.