this reminds me of libketama sharding
CRDT: Fractional Indexing
41–48 of 48 posts
Re: CRDT: Fractional Indexing
#42To 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.c…
CRDT is mostly studied in p2p settings while a central server can reduce lots of complexities in resolving conflict.
Re: CRDT: Fractional Indexing
#43Reminds 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-...
Re: CRDT: Fractional Indexing
#44Earlier quoted context omitted.
The first use is a hyperlink to a whole article defining the term, what are you on about?
Also, outside the page title/headings and the reference to the name of said external paper the first use in the document _is_ where they use the expanded name.
five pages down.
Re: CRDT: Fractional Indexing
#45Anyone 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…
Even that link was 5 pages in (on my phone) before it deigned to mention: > It is a Conflict-free Replicated Data Type (CRDT) What happened to the idea of defining all non-universally-recognised acronyms the first time you use the term? With people making up new terms exponentially faster than ever before, it’s now more important than ever.
To be fair it's one of those terms where merely expanding the acronym doesn't help you much understand what it is. Or if you know what a "Conflict-free Replicated Data Type" is, you've probably heard the acronym more than a few times.
Re: CRDT: Fractional Indexing
#46reminds 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 wou…
The algorithm exposed in the article would be better served by a Stern-Brocot than average + jitter.
Re: CRDT: Fractional Indexing
#47Earlier quoted context omitted.
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 locat…
How did you got end to end encryption working with CRDTs?
Re: CRDT: Fractional Indexing
#48Thanks 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.