from Hacker News

CRDT: Fractional Indexing

by mblode on 11/27/22, 5:03 PM with 44 comments

  • by jitl on 11/27/22, 7:43 PM

    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.

  • by samwillis on 11/27/22, 6:27 PM

    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 rich text editors.

    CRDTs are addictive one you get into them.

  • by LAC-Tech on 11/27/22, 6:52 PM

    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 implications).

  • by paulgb on 11/27/22, 5:48 PM

    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/

  • by superb-owl on 11/27/22, 6:19 PM

    CRDTs are incredible. I recommend checking out the original link [1] as well as this “awesome” list [2]

    [1] https://madebyevan.com/algos/

    [2] https://github.com/alangibson/awesome-crdt

  • by conaclos on 11/27/22, 9:05 PM

    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

  • by throwaway81523 on 11/27/22, 8:08 PM

    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.

  • by lukeramsden on 11/28/22, 7:26 AM

    Reminds me a little of "Lexorank" used in Jira[0], except by using decimals instead of base-36 strings, which I guess could be more efficient? The "rebalancing" aspect is interesting because on a long enough timescale for a document you will definitely want to do it. Would love to read up more on any algorithms for doing this in a p2p manner - with a central server it's probably quite easy using some tombstoning or something.

    [0] https://stackoverflow.com/questions/40718900/jiras-lexorank-...

  • by fatneckbeardz on 11/28/22, 3:03 AM

    reminds me a lot of Ford Circle / Farey Diagram / Stern Brocot tree

    Basically a tree of fractions where you take two rational points on a number line, a/b and c/d, then the next point in the tree is (a+b) / (c+d). Turns out that every single point you create this way has a unique position and never duplicate each other, and it forms a tree like structure.

    https://en.wikipedia.org/wiki/Ford_circle

    not sure if this would be useful, but basically it could be a fractional index that has a built in tree structure, since it basically means any fraction is a leaf on a Stern-Brocot tree.

  • by newhouseb on 11/27/22, 7:26 PM

    Is this the same as LSeq [1] except rather than using bytes one is basically using digits in a floating point representation (given this is JS where most things are floats)?

    [1] https://bartoszsypytkowski.com/operation-based-crdts-arrays-...

  • by brilee on 11/27/22, 7:46 PM

    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.

  • by lelandfe on 11/27/22, 5:45 PM

    For those unaware: Evan is the cofounder, former CTO, and technical wizard behind Figma; creator of esbuild, etc.

  • by bhl on 11/28/22, 2:05 AM

    Is there a good resource on designing collaborative apps with CRDTS, that is which type of CRDT and conflict resolution to pick for a given application? Something like https://mattweidner.com/2022/02/10/collaborative-data-design... but generalizes.

  • by johnxie on 11/29/22, 6:27 AM

    Thanks for sharing this, we implemented OT in our real-time editor, but CRDT's potential is evident in creating a collaborative experience, in particular fractional indexing and reparenting of mutable tree for our use cases.

    We should end the CRDT vs OT debate once and for all.

  • by est on 11/28/22, 2:25 AM

    Reminds me of TokuDB engine for MySQL. Good times.

  • by parentheses on 11/27/22, 10:00 PM

    Maybe I’m missing the point. Random offsets feels like an inelegant solution in the space of elegant solutions (read: CRDTs).

  • by netik on 11/28/22, 5:36 AM

    this reminds me of libketama sharding

  • by dang on 11/27/22, 5:56 PM

    This looks like great stuff if you follow the pointers, but lists don't make good submissions to HN (which itself is already a list). They tend not to lead to deep discussion because comments are about lowest common denominator of the items on the list, and this is usually pretty generic. What's better is to pick the most interesting item on the list and submit that instead. https://hn.algolia.com/?dateRange=all&page=0&prefix=true&sor...

    Edit: let's do that in this case. I've changed the URL from https://madebyevan.com/algos/ based on https://news.ycombinator.com/item?id=33764875.

  • by jiffyjeff on 11/27/22, 7:14 PM

    Conflict-free replicated data type, or CRDT, is often referred to as simply “CRDT” in trade jargon without any definition. Apparently.