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

11–20 of 48 posts

Re: CRDT: Fractional Indexing

#11

Post by chrisoverzero »

paulgb wrote: post #3

This stuff is fun to play with. I implemented a Rust version of fractional indexing based on another of Evan’s blog posts. https://docs.rs/fractional_index/latest/fractional_index/

Does a Vec with that calculation listed end up smaller than two integers of (presumably) arbitrary length?

When I read about the problem, I imagined using the mediant to calculate “between”. I think that mediant of $value and 1/1 would work for “after” and mediant of $value and 0/1 would work for “before”.

There must be a requirement I’m missing, though!

mediant: https://en.wikipedia.org/wiki/Mediant_(mathematics)

Re: CRDT: Fractional Indexing

#13

Post by jdvh »

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…

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 reduces to a handful of CRDT operations.

(We have a central server and the app works offline so the algorithm from the linked article doesn't apply in our case.)

[1] https://thymer.com

Re: CRDT: Fractional Indexing

#16

Post by paulgb »

chrisoverzero wrote: post #11
paulgb wrote: post #3

This stuff is fun to play with. I implemented a Rust version of fractional indexing based on another of Evan’s blog posts. https://docs.rs/fractional_index/latest/fractional_index/

Does a Vec with that calculation listed end up smaller than two integers of (presumably) arbitrary length? When I read about the problem, I imagined using the mediant to calculate “between”. I think that mediant of $value and 1/1 would work for “after” and mediant of $value and 0/1 would work for “before”. There must be a requirement I’m missing, though! mediant: https://en.wikipedia.org/wiki/Mediant_(mathematics)

That would be an interesting thing to test! My first instinct is that the comparison operation (when denominators differ) would be more expensive.

In general some approaches should be better than others depending on how inserts are distributed — I think my approach is optimal when inserts are made at random (I haven’t proved this), but in practice it may be common for a bunch of things to be inserted in sequence for some applications. In those cases, there are more space-optimal approaches.

Re: CRDT: Fractional Indexing

#17

Post by jitl »

To me the other algorithms described in the list are more novel and interesting:

https://madebyevan.com/algos/crdt-tree-based-indexing/ - for when precise order is critical, like paragraphs in a document. This algorithm is almost like storing adjacency information like a linked list, but is more convergent. Very interesting for [my use-case](https://www.notion.so/blog/data-model-behind-notion).

https://madebyevan.com/algos/crdt-mutable-tree-hierarchy/ - for tree-shaped data, like blocks in a Notion page that should have exactly one parent, but allow concurrent re-parenting operations

https://madebyevan.com/algos/log-spaced-snapshots/ - log space snapshots, for choosing what fidelity of historical information to store. For context, many CRDTs for rich text or sequences store unbounded history so that any edit made at any time can be merged into the sequence. For long-lived documents, this could be impractical to sync to all clients or keep in "hot" memory. Instead, we can decide to compact historical data and move it to cold storage, imposing a time boundary on what writes the system can accept on the hot path. The log-spaced snapshots algorithm here could be used to decide what should be kept "hot", and how to tune the cold storage.

Re: CRDT: Fractional Indexing

#18

Post by brilee »

Doesn't this end up being effectively a binary heap, with a maximum tree depth of 23 (floating point mantissa precision)? I imagine there must be a rebalancing operation required every so often, possibly more frequently for pathological insertion orders.

Re: CRDT: Fractional Indexing

#19

Post by luto »

brilee wrote: post #18

Doesn't this end up being effectively a binary heap, with a maximum tree depth of 23 (floating point mantissa precision)? I imagine there must be a rebalancing operation required every so often, possibly more frequently for pathological insertion orders.

> Fractional positions should be represented using arbitrary-precision decimals so that they don't run out of precision. Floating-point numbers are insufficient.

Re: CRDT: Fractional Indexing

#20

Post by jitl »

jdvh wrote: post #13
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…

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