4 ms·

The conceit here is the assumption that this has not been built many times by very clever software engineers. It is not a new idea. True git-like version contro

The conceit here is the assumption that this has not been built many times by very clever software engineers. It is not a new idea. True git-like version control systems for managing large volumes of data have been built on MVCC kernels for a decades -- branch and merge, push and pull, fork and clone. There are fundamental computer science and technical issues that make scaling these systems for arbitrary data models extremely difficult. The platforms always had the ambition to be general but the design tradeoffs required to make them scale requires narrowly overfitting for a particular type of data model such that they can only be used for the original use case. And even then, the performance ends up being not good. I've never designed one from scratch but I've worked on a few at large companies. All of them started with the vision you are proposing, all of them failed at achieving that vision because of the technical tradeoffs required to enable something resembling scalability. Unless you are proposing some novel computer science that renders these issues moot, you aren't presenting a credible defense that this hasn't been done before.

zachmu 4y ago
Git-like version control requires a Merkle DAG. Unless you know something I don't, there are no RDBMS products that incorporate a Merkle DAG for storage. Dolt is the first. Table data is stored in a cross between a Merkle DAG and a B Tree (a prolly tree), which is what makes diff / merge performant and scalable. We didn't invent these data structures but we believe we are the first to build a SQL database on them. https://docs.dolthub.com/architecture/storage-engine/prolly-tree https://docs.dolthub.com/architecture/storage-engine/prolly-...
- jandrewrogers 4y ago
  > Git-like version control requires a Merkle DAG. This is false, you are conflating the abstract algorithm with a narrow implementation. That's like saying the only possible sorting algorithm is quicksort. With all due respect, you seem to be only loosely familiar with database architecture, both theory and historical practice. Nothing you've described is actually novel. That you are unfamiliar with why no one builds things this way, despite many attempts, does not lend confidence. I am actually a big fan of people trying unorthodox approaches to databases that have never been tried before, this just isn't such an example. Which doesn't make your approach wrong per se, but it leaves you exposed to learning why other people tried and abandoned it. Tangentially, the "prolly tree" is intrinsically not a scalable data structure. That may satisfy your design requirements but I can't tell.
  - throwaway892238 4y ago
    > you are conflating the abstract algorithm with a narrow implementation They're literally telling you Git uses a Merkle DAG and they wanted to recreate Git so they used a Merkle DAG. That's not conflating, it's copying. > you seem to be only loosely familiar with database architecture Based on what? The only comments GP has made about DBA in this entire HN thread is "this is not MVCC", which is correct. > I am actually a big fan of people trying unorthodox approaches to databases that have never been tried before So stop discouraging the neophyte? Sometimes innovation requires the ignorant to figure things out without knowing better, because that way they won't quit before they've begun. Let them figure it out. And if it's not novel, who cares? It doesn't have to be some perfect architectural masterpiece to solve people's problems. If it works well enough just for WordPress blogs, that's pretty great already.
    - discreteevent 4y ago
      > They're literally telling you Git uses a Merkle DAG They literally told them: "Git-like version control requires a Merkle DAG."
  - aboodman 4y ago
    Sigh. Databases seems to be one of the last bastions of ivorytower-ism in software engineering. Databases aren't magic. They are software. And as you say, there is a deep well of literature, and almost all interesting modern databases are open source. So it's possible for anyone with the interest and motivation to learn how they work, and yes, improve them. > With all due respect, you seem to be only loosely familiar with database architecture, both theory and historical practice. Nothing you've described is actually novel. That you are unfamiliar with why no one builds things this way, despite many attempts, does not lend confidence. You claim that there is all this information out there saying why this won't work, and that it has been tried, but don't point to any of it. > Tangentially, the "prolly tree" is intrinsically not a scalable data structure. First: Dolt publishes industry standard performance benchmarks and they are an average of 4.4x slower than MySQL: https://docs.dolthub.com/sql-reference/benchmarks/latency https://docs.dolthub.com/sql-reference/benchmarks/latency This is using the original storage format from noms which wasn't written for oltp workloads. A new storage format is coming which is and will dramatically improve this: https://www.dolthub.com/blog/2022-05-20-new-format-alpha/ https://www.dolthub.com/blog/2022-05-20-new-format-alpha/ In any case 5x slower already shows, experimentally, that this approach works for database-style problems. === Second: In a purely algorithmic sense, prolly trees are the definition of scalable. They are log(n) (with a large base) for inserts, deletes, and seeks and they have efficient ordered scans. They have basically the same algorithmic complexity as B Trees, B+ Trees, LSM trees, etc -- very similar properties to the data structures used by other databases. The problem with prolly trees is actually the reverse: they are scalable, but have large constant factors due to the overhead of hashing. But a single-digit constant factor slower performance than MySQL but with versioning seems like a great product for many applications. If anyone reading this is interested, the Dolt team did a great job writing up the how prolly trees work and how they compare to classic databases here: https://www.dolthub.com/blog/2020-04-01-how-dolt-stores-table-data/ https://www.dolthub.com/blog/2020-04-01-how-dolt-stores-tabl...

zachmu 4y ago

Git-like version control requires a Merkle DAG. Unless you know something I don't, there are no RDBMS products that incorporate a Merkle DAG for storage. Dolt is the first. Table data is stored in a cross between a Merkle DAG and a B Tree (a prolly tree), which is what makes diff / merge performant and scalable. We didn't invent these data structures but we believe we are the first to build a SQL database on them. https://docs.dolthub.com/architecture/storage-engine/prolly-tree https://docs.dolthub.com/architecture/storage-engine/prolly-...

jandrewrogers 4y ago
> Git-like version control requires a Merkle DAG. This is false, you are conflating the abstract algorithm with a narrow implementation. That's like saying the only possible sorting algorithm is quicksort. With all due respect, you seem to be only loosely familiar with database architecture, both theory and historical practice. Nothing you've described is actually novel. That you are unfamiliar with why no one builds things this way, despite many attempts, does not lend confidence. I am actually a big fan of people trying unorthodox approaches to databases that have never been tried before, this just isn't such an example. Which doesn't make your approach wrong per se, but it leaves you exposed to learning why other people tried and abandoned it. Tangentially, the "prolly tree" is intrinsically not a scalable data structure. That may satisfy your design requirements but I can't tell.
- throwaway892238 4y ago
  > you are conflating the abstract algorithm with a narrow implementation They're literally telling you Git uses a Merkle DAG and they wanted to recreate Git so they used a Merkle DAG. That's not conflating, it's copying. > you seem to be only loosely familiar with database architecture Based on what? The only comments GP has made about DBA in this entire HN thread is "this is not MVCC", which is correct. > I am actually a big fan of people trying unorthodox approaches to databases that have never been tried before So stop discouraging the neophyte? Sometimes innovation requires the ignorant to figure things out without knowing better, because that way they won't quit before they've begun. Let them figure it out. And if it's not novel, who cares? It doesn't have to be some perfect architectural masterpiece to solve people's problems. If it works well enough just for WordPress blogs, that's pretty great already.
  - discreteevent 4y ago
    > They're literally telling you Git uses a Merkle DAG They literally told them: "Git-like version control requires a Merkle DAG."
- aboodman 4y ago
  Sigh. Databases seems to be one of the last bastions of ivorytower-ism in software engineering. Databases aren't magic. They are software. And as you say, there is a deep well of literature, and almost all interesting modern databases are open source. So it's possible for anyone with the interest and motivation to learn how they work, and yes, improve them. > With all due respect, you seem to be only loosely familiar with database architecture, both theory and historical practice. Nothing you've described is actually novel. That you are unfamiliar with why no one builds things this way, despite many attempts, does not lend confidence. You claim that there is all this information out there saying why this won't work, and that it has been tried, but don't point to any of it. > Tangentially, the "prolly tree" is intrinsically not a scalable data structure. First: Dolt publishes industry standard performance benchmarks and they are an average of 4.4x slower than MySQL: https://docs.dolthub.com/sql-reference/benchmarks/latency https://docs.dolthub.com/sql-reference/benchmarks/latency This is using the original storage format from noms which wasn't written for oltp workloads. A new storage format is coming which is and will dramatically improve this: https://www.dolthub.com/blog/2022-05-20-new-format-alpha/ https://www.dolthub.com/blog/2022-05-20-new-format-alpha/ In any case 5x slower already shows, experimentally, that this approach works for database-style problems. === Second: In a purely algorithmic sense, prolly trees are the definition of scalable. They are log(n) (with a large base) for inserts, deletes, and seeks and they have efficient ordered scans. They have basically the same algorithmic complexity as B Trees, B+ Trees, LSM trees, etc -- very similar properties to the data structures used by other databases. The problem with prolly trees is actually the reverse: they are scalable, but have large constant factors due to the overhead of hashing. But a single-digit constant factor slower performance than MySQL but with versioning seems like a great product for many applications. If anyone reading this is interested, the Dolt team did a great job writing up the how prolly trees work and how they compare to classic databases here: https://www.dolthub.com/blog/2020-04-01-how-dolt-stores-table-data/ https://www.dolthub.com/blog/2020-04-01-how-dolt-stores-tabl...