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

CRDT: Fractional Indexing

madebyevan.com

Post reply on HN
Print view View original

21–30 of 48 posts

Re: CRDT: Fractional Indexing

#21

Post by newhouseb »

LAC-Tech wrote: post #9

CRDTs are often talked about in the same breath as collaborative editing software, but they're useful for much more than that. They really are a theoretical model of how distributed, convergent, multi-master systems have to work. IE the DT in CRDT could be a whole datastore, not as just an individual document. (Wish I could remember who on HN alerted me to this. I had read the paper but didn't grok the full implicati…

You might be thinking of this [1] paper? The core idea being if your problem space lends itself to monotonicity (see the paper for a more precise definition than I can give), then you can build a globally consistent database (around a CRDT) where the end-user doesn't need to concern themselves with inconsistent states while consistency is reached.

[1] https://arxiv.org/pdf/1901.01930.pdf

Re: CRDT: Fractional Indexing

#22

Post by LAC-Tech »

newhouseb wrote: post #21
LAC-Tech wrote: post #9

CRDTs are often talked about in the same breath as collaborative editing software, but they're useful for much more than that. They really are a theoretical model of how distributed, convergent, multi-master systems have to work. IE the DT in CRDT could be a whole datastore, not as just an individual document. (Wish I could remember who on HN alerted me to this. I had read the paper but didn't grok the full implicati…

You might be thinking of this [1] paper? The core idea being if your problem space lends itself to monotonicity (see the paper for a more precise definition than I can give), then you can build a globally consistent database (around a CRDT) where the end-user doesn't need to concern themselves with inconsistent states while consistency is reached. [1] https://arxiv.org/pdf/1901.01930.pdf

I wasn't clear - by "the paper" I meant the original CRDT paper. I read it, thought I understood it on some level, but had not drawn the dots between the theory and real world problems.

Regardless, thanks very much for linking the paper! Right up my alley.

Re: CRDT: Fractional Indexing

#23

Post by throwaway81523 »

This is kind of interesting but "fractional indexing" doesn't seem to be a computer science topic, and I think it might be clearer to treat these indexes as lists of numbers (or ordinals in ω^ω, if you prefer) rather than fractions. Those are simpler to generate and compare than arbitrary-precision fractions. Or as jitl's post suggests, using trees as indexes (I haven't yet looked at jitl's linked articles). Those would presumably have order type ε₀. It's not clear to me why you'd want that, but it seems doable. In all these schemes you might occasionally want a "stop the world garbage collection" where you reset all the indices to be ordinary integers or maybe pairs of integers. I guess that is also doable without having to pause all the updates, at least if you use pairs.

Re: CRDT: Fractional Indexing

#25

Post by [deleted] »

samwillis wrote: post #8

Anyone unsure of what a CRDT is (I think everyone on HN must know by now), this is the perfect intro: https://www.inkandswitch.com/peritext/ The two most widely used CRDT implementations (combining JSON like general purpose types and rich text editing types) are: - Automerge https://github.com/automerge/automerge - Yjs https://github.com/yjs/yjs Both have JS and Rust implementations, and have bindings to most online…

[deleted]

Re: CRDT: Fractional Indexing

#26

Post by sitkack »

LAC-Tech wrote: post #22
newhouseb wrote: post #21

Earlier quoted context omitted.

You might be thinking of this [1] paper? The core idea being if your problem space lends itself to monotonicity (see the paper for a more precise definition than I can give), then you can build a globally consistent database (around a CRDT) where the end-user doesn't need to concern themselves with inconsistent states while consistency is reached. [1] https://arxiv.org/pdf/1901.01930.pdf

I wasn't clear - by "the paper" I meant the original CRDT paper. I read it, thought I understood it on some level, but had not drawn the dots between the theory and real world problems. Regardless, thanks very much for linking the paper! Right up my alley.

Marc Shapiro and Nuno Preguiça created CRDTs in 2007.

https://pages.lip6.fr/Marc.Shapiro/pubs.html#CRDTs

The original paper would be https://hal.inria.fr/inria-00177693/

Re: CRDT: Fractional Indexing

#27

Post by conaclos »

This is basically the idea behind Logoot [Weis_2009] that was improved by LSeq [Nédelec_2013] and later extended to the first block-wise sequence CRDT: LogootSplit [André_2013]. LogootSplit was recently improved as Dotted LogootSplit [1] [Elvinger_2021].

Disclamer: I'm the author of Dotted LogootSplit.

[Weis_2009] https://hal.inria.fr/inria-00432368

[Nédelec_2013] https://hal.archives-ouvertes.fr/hal-00921633/en

[André_2013] https://hal.archives-ouvertes.fr/hal-01246212

[Elvinger_2021] https://hal.univ-lorraine.fr/tel-03284806

[1] https://github.com/coast-team/dotted-logootsplit

Re: CRDT: Fractional Indexing

#28

Post by zaphar »

throwaway81523 wrote: post #23

This is kind of interesting but "fractional indexing" doesn't seem to be a computer science topic, and I think it might be clearer to treat these indexes as lists of numbers (or ordinals in ω^ω, if you prefer) rather than fractions. Those are simpler to generate and compare than arbitrary-precision fractions. Or as jitl's post suggests, using trees as indexes (I haven't yet looked at jitl's linked articles). Those wo…

In a large distributed system stop the world garbage collection is probably not going to work very well.

Re: CRDT: Fractional Indexing

#29

Post by jdvh »

jitl wrote: post #20
jdvh wrote: post #13

Earlier quoted context omitted.

We're using a single end-to-end encrypted document tree synced with CRDTs for our collaborative task IDE[1]. All data for a team is a single tree (graph really, if you count transclusions) and its kind of magical how simple everything gets when you know all state will sync in a deterministic way between all clients. It doesn't matter whether you drag&drop some object or add a new user, or rename something. It all red…

Are you using Yjs? How are you thinking about scale-up for teams with 100s - 1000s of users?

We've looked at Yjs but ultimately decided to write our own thing from scratch.

Even scale-ups with thousands of users will have people working on different parts of the document tree in practice. The client doesn't need to receive every keystroke for people editing somewhere far away in the document tree. Those updates can be sent in batches every once in a while.

If 10.000 people decide to edit the exact same location in a document then performance will degrade. The client will start to lag behind if it can't keep up with the stream of updates (cpu or internet bottleneck) but eventually it will process everything and all clients will end up with the same state. We have two channels. One for state updates (soft real-time) and one for UI hints ("hard" real-time) and other user actions that aren't CRDT mutations.

Post reply on HN