Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Building a BFT JSON CRDT

jzhao.xyz

Post reply on HN
Print view View original

31–38 of 38 posts

Re: Building a BFT JSON CRDT

#31

Post by jitl »

jackyzhao wrote: post #26
jitl wrote: post #23

Earlier quoted context omitted.

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/s... Page in the Wiki. Note that data types have a validate method that returns true or false; maybe if false, they're just…

Hey! Author of the post responding here :) Unfortunately max/min-length is a global invariant and not one that can be reinforced by CRDTs without coordination bloom-lang.net is a really cool project working on trying to figure out what types of program state actually require coordination at compile time

Right - I think what Sam is wondering about is if there’s a better way to maintain some of those invariants when decoding the CRDT data or at least preserve user intent with more fidelity by taking the invariants into account. For example, if a ProseMirror schema says “figure can have one caption child”, then a CRDT library can assist by making Child a LWW register instead of an array; or picking the last item in the array instead of the first when limiting length.

Re: Building a BFT JSON CRDT

#32

Post by jackyzhao »

jitl wrote: post #31
jackyzhao wrote: post #26

Earlier quoted context omitted.

Hey! Author of the post responding here :) Unfortunately max/min-length is a global invariant and not one that can be reinforced by CRDTs without coordination bloom-lang.net is a really cool project working on trying to figure out what types of program state actually require coordination at compile time

Right - I think what Sam is wondering about is if there’s a better way to maintain some of those invariants when decoding the CRDT data or at least preserve user intent with more fidelity by taking the invariants into account. For example, if a ProseMirror schema says “figure can have one caption child”, then a CRDT library can assist by making Child a LWW register instead of an array; or picking the last item in the…

Ah gotcha. This would be a cool area of research! Not sure if I know of many people working on that right now

Re: Building a BFT JSON CRDT

#33

Post by canadiantim »

hansvm wrote: post #14
adamdusty wrote: post #8

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

JSON - JavaScript Object Notation [0] [0] https://en.m.wikipedia.org/wiki/JSON

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

Re: Building a BFT JSON CRDT

#34

Post by hmcamp »

canadiantim wrote: post #33
hansvm wrote: post #14

Earlier quoted context omitted.

JSON - JavaScript Object Notation [0] [0] https://en.m.wikipedia.org/wiki/JSON

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

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

Re: Building a BFT JSON CRDT

#35

Post by jitl »

jackyzhao wrote: post #32
jitl wrote: post #31

Earlier quoted context omitted.

Right - I think what Sam is wondering about is if there’s a better way to maintain some of those invariants when decoding the CRDT data or at least preserve user intent with more fidelity by taking the invariants into account. For example, if a ProseMirror schema says “figure can have one caption child”, then a CRDT library can assist by making Child a LWW register instead of an array; or picking the last item in the…

Ah gotcha. This would be a cool area of research! Not sure if I know of many people working on that right now

To me it seems mostly a composition problem; we need a better way of expressing these kinds of application constraints in a formal schema so we can encode/decode application data structures to CRDTs without requiring invasive intermixing of the two concerns in a way that explodes complexity of both the app and the CRDT details.

Re: Building a BFT JSON CRDT

#36

Post by micahscopes »

jitl wrote: post #23
sbazerque wrote: post #19

Earlier quoted context omitted.

I think this is the schema system you're asking for: https://www.hyperhyperspace.org/ (specifically, the data representation part)

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/s... Page in the Wiki. Note that data types have a validate method that returns true or false; maybe if false, they're just…

Okay wow, it's fun and surreal to see code you're working on pop up in the comment section unexpectedly right in front of your eyes :D

I've been helping Santi on this wiki application and we've actually been dreaming about how nice it'd be to eventually have some kind of schema language for defining Hyper Hyper Space types. In the current version of HHS, data types are fully defined via TypeScript classes, and constraints like that are implemented via the validation method you discovered. If that method returns false, the data won't even be stored or synced, let alone make it to the UI. So for now it's an open ended way of defining constraints, making it easier to explore and experiment. Many of the core HHS data types have constraints built into them too, enforced via the validate method. For example, the CausalSet type can be made to only allow certain elements as members.

Anyway there are a few reasons I can see that it'd be amazing to have something more like JSON Schema. One is that it'd just clarify using these data types outside of TypeScript, and ideally they'd be more succinct to read and write than TypeScript classes.

Another reason I'm especially curious about is the possibility of using it along with some kind of query system, which could potentially make a bunch of stuff easier both both in selecting data for applications and in implementing casual validation logic. Validating multiple interacting causal data types requires looking at chains of events in the DAG. Maybe being able to query for these chains could make this nicer?

All that to say, my guess is that the hardest part of moving to a succinct schema definition format would be how to deal with constraint/validation specification.

> I haven't found the underlying text or rich text CRDT implementation yet.

I think something like this in the works! Right now we're just using last write wins. We did experiment with using Y.js for realtime collaboration, but we ran into some complexity in reliably ensuring that the Y.js state could get persisted to the HHS data types without race conditions, so we took a step back from that idea.

Re: Building a BFT JSON CRDT

#37

Post by jitl »

micahscopes wrote: post #36
jitl wrote: post #23

Earlier quoted context omitted.

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/s... Page in the Wiki. Note that data types have a validate method that returns true or false; maybe if false, they're just…

Okay wow, it's fun and surreal to see code you're working on pop up in the comment section unexpectedly right in front of your eyes :D I've been helping Santi on this wiki application and we've actually been dreaming about how nice it'd be to eventually have some kind of schema language for defining Hyper Hyper Space types. In the current version of HHS, data types are fully defined via TypeScript classes, and constr…

I encourage you to follow up on the schema language plus a code generator. It’s a powerful technique that can make your implementation more agile as you develop new strategies.

Re: Building a BFT JSON CRDT

#38

Post by recuter »

thruflo wrote: post #15
recuter wrote: post #12

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

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 (CRDT database in Erlang)

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.
Post reply on HN