HN Simulatornew | past | comments | lists | submitlogin

Thanks for the comment. To the best of my knowledge, Piper is not Merkle DAG based, and instead uses a (completely linear?) sequence number similar to Subversion. I believe they ended up faking those hashes for Fig. I'm not actually sure what they do for Jujutsu compatibility, maybe they've added a Merkle layer since.

We were compelled to model things as a DAG to be able to handle the occasional merge commit (this makes the algorithms a lot harder), and we wanted the Merkleness for its desirable properties such as being easily cacheable and straightforward to do integrity checks on. We wrote a bidirectional conversion layer between the Mercurial and Bonsai data models, with great attention paid to complete reversibility. (That's how I got into property-based testing, by the way! My coworker also used Alloy to formally verify the data model.)

The closest equivalent is probably Monotone, actually, though it only had one tree/manifest format which was baked into the changeset, while Mononoke got rid of that and _only_ relied on the changes, flipped the pointer directions, and generalized that to arbitrary kinds of derived data. (This was at the cost of having to maintain mapping layers in a database.)

help



I'm not convinced that Merkle DAGs are useful or worth the bother. Piper's system of linear indices has a few nice properties:

1) when a defect is identified in a library, the extent of the defect becomes an interval [CL that introduced it, CL that removed it] and it makes it trivial to test whether a compiled artifact is affected by that defect; more generally the UX is a lot better

and 2) it makes whole-repository rewrites trivial, so that existing commit sequence IDs are preserved while retroactively removing sensitive files that shouldn't have been added to the repo. Git and Mercurial make such rewrite a huge pain in the arse, while this is an essential feature to have in an enterprise VCS.


These were both solved as part of the data model via globalrevs and obliteration respectively. But that is besides the point here? The next time you're designing a source control system you're welcome to pick your favorite points in the design space.

> These were both solved as part of the data model via globalrevs and obliteration respectively

Is there some paper or other technical publication regarding these concepts ?


I'm not aware of anything published, but the code is open source, and if you're so inclined you can probably point a clanker at it. The second one is called "redaction" in Mononoke, I believe (obliteration is a different term for it, as is censorship).

You are correct that integer sequence numbers and redaction are both reasonable things to want -- we just believed (for a variety of reasons) that the core should be Merkle and that these things should be built on top.


> if you're so inclined you can probably point a clanker at it

I'm not. Too bad there's nothing meant for humans.


Just because you might find this interesting: Scion deviates significantly in this regard in order to deal with merges; coming from git, we land code to our main branch via merge so it's a common occurrence.

We do discourage (but not block) some trickier DAG things you could have done in git and are probably moving towards squashing and rebasing for landing since many things become simpler without merges, but we simply had to deal with merges (and handle git compatibility while migrating) to pull this off. Particularly, full DAG merge bases add a lot of complexity and it gave us some concrete ideas on how to improve git's commit graph data structures by an order of magnitude or more.




Guidelines | FAQ | Lists | API | Security | DMCA | Apply to YC | Contact

Search: