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

31–40 of 48 posts

Re: CRDT: Fractional Indexing

#31

Post by taneq »

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…

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.

Re: CRDT: Fractional Indexing

#32

Post by maxmcd »

jitl wrote: post #17

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.c…

If you’re working on CRDT stuff in production (or possibly in production) do you have thoughts on the CRDT vs OT debate? I would expect Notion to use operational transform given the availability of reliable central servers. But I know quite little! Interested in your thoughts.

Re: CRDT: Fractional Indexing

#33

Post by dang »

mblode wrote: post #6
dang wrote: post #4

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…

Thank you dang for updating the title and URL!

The funny thing is that the thread so far has still mostly been generic, yet I swear the comments are higher-quality than they would have been without the change. (Impossible to say for sure, of course)

Re: CRDT: Fractional Indexing

#34

Post by al2o3cr »

taneq wrote: post #31
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…

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.

The first use is a hyperlink to a whole article defining the term, what are you on about?

Re: CRDT: Fractional Indexing

#35

Post by glenngillen »

al2o3cr wrote: post #34
taneq wrote: post #31

Earlier quoted context omitted.

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.

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.

Re: CRDT: Fractional Indexing

#36

Post by lelandfe »

al2o3cr wrote: post #34
taneq wrote: post #31

Earlier quoted context omitted.

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.

The first use is a hyperlink to a whole article defining the term, what are you on about?

TBF, it uses the acronym 8 times across 500 words before giving you the actual term.

Re: CRDT: Fractional Indexing

#39

Post by ChadNauseam »

maxmcd wrote: post #32
jitl wrote: post #17

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.c…

If you’re working on CRDT stuff in production (or possibly in production) do you have thoughts on the CRDT vs OT debate? I would expect Notion to use operational transform given the availability of reliable central servers. But I know quite little! Interested in your thoughts.

I’m not the GP, but OT is pretty annoying to implement. There are so many cases that it’s quite difficult to formally prove an OT correct. On the other hand, a large subset of CRDTs can be implemented in Datalog and if you do that you can’t possibly end up with an invalid CRDT.

From wikipedia:

> Similarly, Joseph Gentle who is a former Google Wave engineer and an author of the Share.JS library wrote, "Unfortunately, implementing OT sucks. There's a million algorithms with different tradeoffs, mostly trapped in academic papers. […] Wave took 2 years to write and if we rewrote it today, it would take almost as long to write a second time." But later he amends his comment with "I no longer believe that wave would take 2 years to implement now - mostly because of advances in web frameworks and web browsers."

Re: CRDT: Fractional Indexing

#40

Post by fatneckbeardz »

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.

Post reply on HN