3 ms·

> If you ask me, this is a mistake. The algorithm is simpler if you primarily think of it as inserts into a list. (Thanks Kevin Jahns for this insight!) Can yo

> If you ask me, this is a mistake. The algorithm is simpler if you primarily think of it as inserts into a list. (Thanks Kevin Jahns for this insight!) Can you elaborate? This sounds a little tautological, so I must be missing something.

josephg 1y ago
The way RGA and Fugue are usually described, all the inserted items form a tree. In RGA, each item has {parent: ID, seq: number}. The item is inserted as a child of its specified parent. Fugue is a little more complex because items specify 2 parent IDs. You can store this as a tree where every item has left children and right children. But if you actually implement your CRDT like this, you'll find the tree is incredibly unbalanced. You'll end up with runs of thousands of items where you have (x)->(y)->(z)->(q) and so on. It resembles a linked list more than anything. Performance is abysmal as a result. This is one of the causes for the terrible performance of early versions of automerge. Here's the trick: Flatten the tree. Store all items in a list instead, in the order all the items show up in the document. But this presents a new problem: how do you correctly handle inserts? We need to insert new items in the list in the correct location, as if we inserted into a tree then flattened it afterwards. But it turns out that this translation is quite simple in practice. Its like ~10-20 lines of code. Interestingly, the fugue paper first describes fugue (as a tree). Then it identifies & fixes a problem in the algorithm to produce fuguemax. If you do the list insertion order translation on both fugue and fuguemax, fugue ends up with an extra if() statement that causes this problem. If you remove that if statement, you get the (better) fuguemax algorithm. This transformation results in much better performance, and much lower memory usage. Counter-intuitively, you get another order of magnitude improved performance if you then store this flattened list once more in a b-tree. If you're curious, here's the equivalent insertion code for fuguemax, rga and yjs. These are all fuzz tested against their upstream reference implementations to verify equivalence. Fugue is also somewhere in this file, if you want to compare. Here's FugueMax[1]: https://github.com/josephg/reference-crdts/blob/c539474087701c778c52b2974019f07c5bce8e23/crdts.ts#L299-L354 https://github.com/josephg/reference-crdts/blob/c53947408770... RGA: https://github.com/josephg/reference-crdts/blob/c539474087701c778c52b2974019f07c5bce8e23/crdts.ts#L457-L522 https://github.com/josephg/reference-crdts/blob/c53947408770... And Yjs: https://github.com/josephg/reference-crdts/blob/c539474087701c778c52b2974019f07c5bce8e23/crdts.ts#L405-L454 https://github.com/josephg/reference-crdts/blob/c53947408770... As I said, I didn't come up with this idea. Kevin Jahns figured out this trick for Yjs. I adapted it to the other algorithms. [1] Fuguemax is called "yjsmod" in this repository because this code predates the fugue paper. It turns out our algorithms are equivalent.

josephg 1y ago

The way RGA and Fugue are usually described, all the inserted items form a tree. In RGA, each item has {parent: ID, seq: number}. The item is inserted as a child of its specified parent. Fugue is a little more complex because items specify 2 parent IDs. You can store this as a tree where every item has left children and right children. But if you actually implement your CRDT like this, you'll find the tree is incredibly unbalanced. You'll end up with runs of thousands of items where you have (x)->(y)->(z)->(q) and so on. It resembles a linked list more than anything. Performance is abysmal as a result. This is one of the causes for the terrible performance of early versions of automerge. Here's the trick: Flatten the tree. Store all items in a list instead, in the order all the items show up in the document. But this presents a new problem: how do you correctly handle inserts? We need to insert new items in the list in the correct location, as if we inserted into a tree then flattened it afterwards. But it turns out that this translation is quite simple in practice. Its like ~10-20 lines of code. Interestingly, the fugue paper first describes fugue (as a tree). Then it identifies & fixes a problem in the algorithm to produce fuguemax. If you do the list insertion order translation on both fugue and fuguemax, fugue ends up with an extra if() statement that causes this problem. If you remove that if statement, you get the (better) fuguemax algorithm. This transformation results in much better performance, and much lower memory usage. Counter-intuitively, you get another order of magnitude improved performance if you then store this flattened list once more in a b-tree. If you're curious, here's the equivalent insertion code for fuguemax, rga and yjs. These are all fuzz tested against their upstream reference implementations to verify equivalence. Fugue is also somewhere in this file, if you want to compare. Here's FugueMax[1]: https://github.com/josephg/reference-crdts/blob/c539474087701c778c52b2974019f07c5bce8e23/crdts.ts#L299-L354 https://github.com/josephg/reference-crdts/blob/c53947408770... RGA: https://github.com/josephg/reference-crdts/blob/c539474087701c778c52b2974019f07c5bce8e23/crdts.ts#L457-L522 https://github.com/josephg/reference-crdts/blob/c53947408770... And Yjs: https://github.com/josephg/reference-crdts/blob/c539474087701c778c52b2974019f07c5bce8e23/crdts.ts#L405-L454 https://github.com/josephg/reference-crdts/blob/c53947408770... As I said, I didn't come up with this idea. Kevin Jahns figured out this trick for Yjs. I adapted it to the other algorithms. [1] Fuguemax is called "yjsmod" in this repository because this code predates the fugue paper. It turns out our algorithms are equivalent.