7 ms·

Building a BFT JSON CRDT

205 points by raykyri 4y ago

MWil 4y ago
when you see it...them...
- athorax 4y ago
  we are legion
barbazoo 4y ago
That was a bit creepy while it lasted. (the mouse pointer thing that is)
PointyFluff 4y ago
A little early in the morning for so much alphabet soup.
- MWil 4y ago
  or to give up on an opportunity to learn/enjoy something
EGreg 4y ago
Yessss finally someone is doing it.
adamdusty 4y ago
For people like me: BFT - Byzantine Fault Tolerant [0] CRDT - Conflict-free Replicated Data Type [1] [0] https://en.wikipedia.org/wiki/Byzantine_fault https://en.wikipedia.org/wiki/Byzantine_fault [1] https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...
- deleted 4y ago
  [deleted]
- karmakaze 4y ago
  RGA/CT - Replicated Growable Array/Causal Tree I don't like unexplained acronyms/initialisms.
- hansvm 4y ago
  JSON - JavaScript Object Notation [0] [0] https://en.m.wikipedia.org/wiki/JSON https://en.m.wikipedia.org/wiki/JSON
  - canadiantim 4y ago
    Building - 1: a usually roofed and walled structure built for permanent use (as for a dwelling) 2: the art or business of assembling materials into a structure [0] https://www.merriam-webster.com/dictionary/building https://www.merriam-webster.com/dictionary/building
    - hmcamp 4y ago
      A - 1: used when referring to someone or something for the first time in a text or conversation. "a man came out of the room" 2: used to indicate membership of a class of people or things. "he is a lawyer" [0] https://www.google.com/search?q=define+a https://www.google.com/search?q=define+a
Karrot_Kream 4y ago
Hash graph reconciliation is generally the harder part of this problem as noted in future work, but this is a very exciting direction.
- jchanimal 4y ago
  Check out this implementation of hash-stable trees. The same dataset generates the same Merkle hash, regardless of insertion orders. This makes verifiable sync computationally efficient. https://github.com/mikeal/prolly-trees https://github.com/mikeal/prolly-trees
thruflo 4y ago
From the article, this appears to be an implementation of Making CRDTs Byzantine Fault Tolerant [0] in Rust [1]. [0]: https://martin.kleppmann.com/papers/bft-crdt-papoc22.pdf https://martin.kleppmann.com/papers/bft-crdt-papoc22.pdf [1]: https://github.com/jackyzha0/bft-json-crdt https://github.com/jackyzha0/bft-json-crdt
recuter 4y ago
To somebody who knows Erlang, isn't this reinventing the wheel basically?
- jansommer 4y ago
  Could you elaborate? How do you get CRDT's for free in Erlang?
- thruflo 4y ago
  Erlang is a great language and runtime to build distributed systems in but it doesn’t provide primitives to resolve concurrent overlapping updates. Hence projects like https://www.antidotedb.eu https://www.antidotedb.eu (CRDT database in Erlang)
  - recuter 4y ago
    Yes, sorry I should have been less terse: never heard of antidotedb but I figured there is probably a bunch of these projects mature already. I was asking, not stating.
- NavinF 4y ago
  AFAIK Erlang isn't byzantine fault tolerant, doesn't use CRDTs, and doesn't even have a JSON library in its stdlib. So just from the title you can tell it has nothing to do with the article.
jitl 4y ago
I'm quite surprised by the [benchmarks versus Automerge JS & Rust](https://github.com/jackyzha0/bft-json-crdt#benchmarks https://github.com/jackyzha0/bft-json-crdt#benchmarks) when it comes to memory: > Ours (Basic) 27.6MB > Ours (BFT) 59.5MB > Automerge (Rust) 232.5MB I would expect adding the public key tracking to use more memory; I wonder how Automerge is spending so much more memory. Possibly on a bunch of internal caches or memoization that give the order-of-magnitude improvement in speed? > Ops: 100k > Ours (Basic) 9.321s > Ours (BFT) 38.842s > Automerge (Rust) 0.597s
samwillis 4y ago
It's the Byzantine Fault Tolerant part of this that is particularly innovative and based on Kleppmanns most recent work. I believe it solves the issue of either malicious actors in the networks modifying others transactions, spoofing them, or the messages being modified by third parties ("outside" the network) who have MITM the connection. These are really great problems to solve. However, when I was experimenting with CRDTs a while back, it seemed to me the other big issue is where multiple transactions from different users combine to create an invalid state. Most CRDT toolkits are aiming for a combination of a JSON like type structure, with the addition on specific structures for rich text. The JSON structures for general purpose data, and those for rich text as that is the most common current use case. These sort of general purpose CRDTs don't have a way to handle, say, the maximum length of an array/string, or minimum and maximum values for a number. They leave this to the application using the toolkit. For the Yjs + ProseMirror system, effectively the CRDTs are resolved outside of ProseMirror. Thats useful as they can be combined/resolved on the server without a ProseMirror instance running. However there is a strong possibility that the resulting structure is no longer valid for your ProseMirror Schema, this is currently handled by ProseMirror throwing away the invalid parts of the document when it loads. What I think is needed is a Schema system that is a layer either on top of these toolkits, or as part of them, that provides rules and conflict resolution. So there is a way to specify the maximum length of an array/string, or what the maximum value of a number is. Effectively generic CRDTs that have an understanding of developer supplied rules and bounds. The "maximum length" is an interesting one, as depending on the order of transactions you could end up with a different result.
- sbazerque 4y ago
  I think this is the schema system you're asking for: https://www.hyperhyperspace.org/ https://www.hyperhyperspace.org/ (specifically, the data representation part)
  - jitl 4y ago
    This is a cool idea, but I didn't find any examples of max length constraints or other normalization rules in the source code I reviewed. Maybe there's something in there. Here's some source code for an early, work-in-progress Wiki CRDT: https://github.com/hyperhyperspace/wiki-collab/blob/master/src/model/WikiSpace.ts https://github.com/hyperhyperspace/wiki-collab/blob/master/s... Page in the Wiki. Note that data types have a validate method that returns true or false; maybe if false, they're just dropped from the UI? Not sure how the method is used. https://github.com/hyperhyperspace/wiki-collab/blob/master/src/model/Page.ts#L90 https://github.com/hyperhyperspace/wiki-collab/blob/master/s... I haven't found the underlying text or rich text CRDT implementation yet.
simonw 4y ago
> I write this blog post mostly as a note to my past self, distilling a lot of what I’ve learned since into a blog post I wish I had read before going in The best kind of blog post!
lukeigel 4y ago
Let's go Jackie!!!

205 points by raykyri 4y ago

MWil 4y ago

when you see it...them...

athorax 4y ago
we are legion

barbazoo 4y ago

That was a bit creepy while it lasted. (the mouse pointer thing that is)

PointyFluff 4y ago

A little early in the morning for so much alphabet soup.

MWil 4y ago
or to give up on an opportunity to learn/enjoy something

EGreg 4y ago

Yessss finally someone is doing it.

adamdusty 4y ago

For people like me: BFT - Byzantine Fault Tolerant [0] CRDT - Conflict-free Replicated Data Type [1] [0] https://en.wikipedia.org/wiki/Byzantine_fault https://en.wikipedia.org/wiki/Byzantine_fault [1] https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...

deleted 4y ago
[deleted]
karmakaze 4y ago
RGA/CT - Replicated Growable Array/Causal Tree I don't like unexplained acronyms/initialisms.
hansvm 4y ago
JSON - JavaScript Object Notation [0] [0] https://en.m.wikipedia.org/wiki/JSON https://en.m.wikipedia.org/wiki/JSON
- canadiantim 4y ago
  Building - 1: a usually roofed and walled structure built for permanent use (as for a dwelling) 2: the art or business of assembling materials into a structure [0] https://www.merriam-webster.com/dictionary/building https://www.merriam-webster.com/dictionary/building
  - hmcamp 4y ago
    A - 1: used when referring to someone or something for the first time in a text or conversation. "a man came out of the room" 2: used to indicate membership of a class of people or things. "he is a lawyer" [0] https://www.google.com/search?q=define+a https://www.google.com/search?q=define+a

Karrot_Kream 4y ago

Hash graph reconciliation is generally the harder part of this problem as noted in future work, but this is a very exciting direction.

jchanimal 4y ago
Check out this implementation of hash-stable trees. The same dataset generates the same Merkle hash, regardless of insertion orders. This makes verifiable sync computationally efficient. https://github.com/mikeal/prolly-trees https://github.com/mikeal/prolly-trees

thruflo 4y ago

From the article, this appears to be an implementation of Making CRDTs Byzantine Fault Tolerant [0] in Rust [1]. [0]: https://martin.kleppmann.com/papers/bft-crdt-papoc22.pdf https://martin.kleppmann.com/papers/bft-crdt-papoc22.pdf [1]: https://github.com/jackyzha0/bft-json-crdt https://github.com/jackyzha0/bft-json-crdt

recuter 4y ago

To somebody who knows Erlang, isn't this reinventing the wheel basically?

jansommer 4y ago
Could you elaborate? How do you get CRDT's for free in Erlang?
thruflo 4y ago
Erlang is a great language and runtime to build distributed systems in but it doesn’t provide primitives to resolve concurrent overlapping updates. Hence projects like https://www.antidotedb.eu https://www.antidotedb.eu (CRDT database in Erlang)
- recuter 4y ago
  Yes, sorry I should have been less terse: never heard of antidotedb but I figured there is probably a bunch of these projects mature already. I was asking, not stating.
NavinF 4y ago
AFAIK Erlang isn't byzantine fault tolerant, doesn't use CRDTs, and doesn't even have a JSON library in its stdlib. So just from the title you can tell it has nothing to do with the article.

jitl 4y ago

I'm quite surprised by the [benchmarks versus Automerge JS & Rust](https://github.com/jackyzha0/bft-json-crdt#benchmarks https://github.com/jackyzha0/bft-json-crdt#benchmarks) when it comes to memory: > Ours (Basic) 27.6MB > Ours (BFT) 59.5MB > Automerge (Rust) 232.5MB I would expect adding the public key tracking to use more memory; I wonder how Automerge is spending so much more memory. Possibly on a bunch of internal caches or memoization that give the order-of-magnitude improvement in speed? > Ops: 100k > Ours (Basic) 9.321s > Ours (BFT) 38.842s > Automerge (Rust) 0.597s

samwillis 4y ago

It's the Byzantine Fault Tolerant part of this that is particularly innovative and based on Kleppmanns most recent work. I believe it solves the issue of either malicious actors in the networks modifying others transactions, spoofing them, or the messages being modified by third parties ("outside" the network) who have MITM the connection. These are really great problems to solve. However, when I was experimenting with CRDTs a while back, it seemed to me the other big issue is where multiple transactions from different users combine to create an invalid state. Most CRDT toolkits are aiming for a combination of a JSON like type structure, with the addition on specific structures for rich text. The JSON structures for general purpose data, and those for rich text as that is the most common current use case. These sort of general purpose CRDTs don't have a way to handle, say, the maximum length of an array/string, or minimum and maximum values for a number. They leave this to the application using the toolkit. For the Yjs + ProseMirror system, effectively the CRDTs are resolved outside of ProseMirror. Thats useful as they can be combined/resolved on the server without a ProseMirror instance running. However there is a strong possibility that the resulting structure is no longer valid for your ProseMirror Schema, this is currently handled by ProseMirror throwing away the invalid parts of the document when it loads. What I think is needed is a Schema system that is a layer either on top of these toolkits, or as part of them, that provides rules and conflict resolution. So there is a way to specify the maximum length of an array/string, or what the maximum value of a number is. Effectively generic CRDTs that have an understanding of developer supplied rules and bounds. The "maximum length" is an interesting one, as depending on the order of transactions you could end up with a different result.

sbazerque 4y ago
I think this is the schema system you're asking for: https://www.hyperhyperspace.org/ https://www.hyperhyperspace.org/ (specifically, the data representation part)
- jitl 4y ago
  This is a cool idea, but I didn't find any examples of max length constraints or other normalization rules in the source code I reviewed. Maybe there's something in there. Here's some source code for an early, work-in-progress Wiki CRDT: https://github.com/hyperhyperspace/wiki-collab/blob/master/src/model/WikiSpace.ts https://github.com/hyperhyperspace/wiki-collab/blob/master/s... Page in the Wiki. Note that data types have a validate method that returns true or false; maybe if false, they're just dropped from the UI? Not sure how the method is used. https://github.com/hyperhyperspace/wiki-collab/blob/master/src/model/Page.ts#L90 https://github.com/hyperhyperspace/wiki-collab/blob/master/s... I haven't found the underlying text or rich text CRDT implementation yet.

simonw 4y ago

> I write this blog post mostly as a note to my past self, distilling a lot of what I’ve learned since into a blog post I wish I had read before going in The best kind of blog post!

lukeigel 4y ago

Let's go Jackie!!!