5 ms·

Chronofold: A data structure for versioned text (2020)

207 points by tempodox 5y ago

claytongulick 5y ago
Would appreciate anyone knowledgeable in the field who could provide a "layman's" breakdown of the relative merits of this approach vs OT and CRDTs. I'm afraid it's a bit above my head.
- jitl 5y ago
  This is a CRDT. I think the first page or so of the paper is very approachable, explaining well the history of these kinds of ideas and the advantages of Chronofold, did you try reading it?
  - claytongulick 5y ago
    I read the abstract and was a bit lost, I guess. I took from it that this was a novel "locality" approach that was different than CRDT'S. This is far from my area of expertise, so I guess 'approachable' is relative? Was hoping that (in the fine tradition of HN) someone who knows a lot more about this stuff could chime in. I'd really like to learn some of this for a number of projects I'm working on, and I'm not sure where the best place to direct my focus is. ShareJS is OT based, iirc, and but quill js has some basic support for it too. CRDTs are a bit voodoo to me. This is something else? Sorry if it's a remedial question, would appreciate any advice or insight.
    - cpach 5y ago
      Don’t feel bad for asking questions! IMHO that’s crucial for getting forward and gaining deeper knowledge. If I could answer your question I would but I don’t know this domain well enough (^_^)
  - vicda 5y ago
    You say that like they have heard of the acronym CRDT before. Don't let the curse of knowledge be an excuse to be rude to people.
    - misnome 5y ago
      They used the acronym CRDT and explicitly asked for comparisons to it. Don’t let the curse of not reading be an excuse to be rude to people.
- AnthonBerg 5y ago
  I like this one out of a series of similar papers: https://arxiv.org/abs/1905.01518 https://arxiv.org/abs/1905.01518 Maybe not light reading?, but accessible still.
josh11b 5y ago
I suspect this is a follow-up to this recent article: https://news.ycombinator.com/item?id=28017204 https://news.ycombinator.com/item?id=28017204
- jitl 5y ago
  I submitted it right after reading the paper from gritzko’s post but the story didn’t get any traction :( https://news.ycombinator.com/item?id=28020792 https://news.ycombinator.com/item?id=28020792
mikewarot 5y ago
So, this is essentially cache invalidation, mixed with relativity/causality... the hardest aspects of two different fields, all rolled into one data structure/algorithm. I found it interesting, and something I will have to read a few more times before all the details make sense. The idea of collapsing the structure when individual changes are no longer needed is appealing in terms of space saving. I look forward to seeing this implemented.
- DougBTX 5y ago
  > this is essentially cache invalidation, mixed with relativity/causality In a sense these are quite closely related, the challenge with caches is when they go out of sync with their source data, as then reads/writes against the cache/source could appear to violate causality.
wokwokwok 5y ago
This is from April 2020. You can find a few implementations (1, 2) to play with now if you’re interested… I found the video series [3] in the latter particularly interesting in trying to understand it, if you’re game to sit through a few hours of live stream. [1] - (rust) https://github.com/dkellner/chronofold https://github.com/dkellner/chronofold [2] - (js) https://github.com/jmatsushita/purescript-chronofold https://github.com/jmatsushita/purescript-chronofold [3] - https://m.youtube.com/watch?v=gg5q_V7tBjE&pp=sAQA https://m.youtube.com/watch?v=gg5q_V7tBjE&pp=sAQA
- omgtehlion 5y ago
  unfortunately, [1] has incorrect behavior on some inputs. The hard part of the algo - integration - is implemented incorrectly there :( and for [2] it is still an "open question", as per their Readme.
  - joseluis 5y ago
    then would you mind opening an issue in the first repository so that it can have a chance to be fixed?
    - omgtehlion 5y ago
      The repo seems to be abandoned. Author of chronofold (@gritzko) pointed me to another impl ( https://github.com/decentralized-hse/collab-edit https://github.com/decentralized-hse/collab-edit ) but not checked it, yet... Edit: I’m apparently wrong on the “abandoned” part. The author of this repo wants to maintain it and accepts bugs and issues on github, https://news.ycombinator.com/item?id=28025692 https://news.ycombinator.com/item?id=28025692
      - joseluis 5y ago
        that's wonderful news! I'm hoping to be able to use this data structure in the near future using rust, so this helps a lot. thank you so much
  - 5y ago
jitl 5y ago
Here’s a presentation by Grischenko on Chronofold https://m.youtube.com/watch?v=dKzMZsg5EVA https://m.youtube.com/watch?v=dKzMZsg5EVA
deleted 5y ago
[deleted]
tcldr 5y ago
CRDTs are fascinating data structures to me. One question: how would you handle something like cursor position with a DS like this? In the structure itself or a parallel structure with the site-id, insertion-point and expiration date?
- lewisjoe 5y ago
  Cursor positions are nothing but a counter. And counters are CRDTs by default, which means they are associative, idempotent and transitive. Best way is to have them as a separate structure pointing to an index.

207 points by tempodox 5y ago

Would appreciate anyone knowledgeable in the field who could provide a "layman's" breakdown of the relative merits of this approach vs OT and CRDTs. I'm afraid it's a bit above my head.

jitl 5y ago
This is a CRDT. I think the first page or so of the paper is very approachable, explaining well the history of these kinds of ideas and the advantages of Chronofold, did you try reading it?
- claytongulick 5y ago
  I read the abstract and was a bit lost, I guess. I took from it that this was a novel "locality" approach that was different than CRDT'S. This is far from my area of expertise, so I guess 'approachable' is relative? Was hoping that (in the fine tradition of HN) someone who knows a lot more about this stuff could chime in. I'd really like to learn some of this for a number of projects I'm working on, and I'm not sure where the best place to direct my focus is. ShareJS is OT based, iirc, and but quill js has some basic support for it too. CRDTs are a bit voodoo to me. This is something else? Sorry if it's a remedial question, would appreciate any advice or insight.
  - cpach 5y ago
    Don’t feel bad for asking questions! IMHO that’s crucial for getting forward and gaining deeper knowledge. If I could answer your question I would but I don’t know this domain well enough (^_^)
- vicda 5y ago
  You say that like they have heard of the acronym CRDT before. Don't let the curse of knowledge be an excuse to be rude to people.
  - misnome 5y ago
    They used the acronym CRDT and explicitly asked for comparisons to it. Don’t let the curse of not reading be an excuse to be rude to people.
AnthonBerg 5y ago
I like this one out of a series of similar papers: https://arxiv.org/abs/1905.01518 https://arxiv.org/abs/1905.01518 Maybe not light reading?, but accessible still.

josh11b 5y ago

I suspect this is a follow-up to this recent article: https://news.ycombinator.com/item?id=28017204 https://news.ycombinator.com/item?id=28017204

jitl 5y ago
I submitted it right after reading the paper from gritzko’s post but the story didn’t get any traction :( https://news.ycombinator.com/item?id=28020792 https://news.ycombinator.com/item?id=28020792

mikewarot 5y ago

So, this is essentially cache invalidation, mixed with relativity/causality... the hardest aspects of two different fields, all rolled into one data structure/algorithm. I found it interesting, and something I will have to read a few more times before all the details make sense. The idea of collapsing the structure when individual changes are no longer needed is appealing in terms of space saving. I look forward to seeing this implemented.

DougBTX 5y ago
> this is essentially cache invalidation, mixed with relativity/causality In a sense these are quite closely related, the challenge with caches is when they go out of sync with their source data, as then reads/writes against the cache/source could appear to violate causality.

wokwokwok 5y ago

This is from April 2020. You can find a few implementations (1, 2) to play with now if you’re interested… I found the video series [3] in the latter particularly interesting in trying to understand it, if you’re game to sit through a few hours of live stream. [1] - (rust) https://github.com/dkellner/chronofold https://github.com/dkellner/chronofold [2] - (js) https://github.com/jmatsushita/purescript-chronofold https://github.com/jmatsushita/purescript-chronofold [3] - https://m.youtube.com/watch?v=gg5q_V7tBjE&pp=sAQA https://m.youtube.com/watch?v=gg5q_V7tBjE&pp=sAQA

omgtehlion 5y ago
unfortunately, [1] has incorrect behavior on some inputs. The hard part of the algo - integration - is implemented incorrectly there :( and for [2] it is still an "open question", as per their Readme.
- joseluis 5y ago
  then would you mind opening an issue in the first repository so that it can have a chance to be fixed?
  - omgtehlion 5y ago
    The repo seems to be abandoned. Author of chronofold (@gritzko) pointed me to another impl ( https://github.com/decentralized-hse/collab-edit https://github.com/decentralized-hse/collab-edit ) but not checked it, yet... Edit: I’m apparently wrong on the “abandoned” part. The author of this repo wants to maintain it and accepts bugs and issues on github, https://news.ycombinator.com/item?id=28025692 https://news.ycombinator.com/item?id=28025692
    - joseluis 5y ago
      that's wonderful news! I'm hoping to be able to use this data structure in the near future using rust, so this helps a lot. thank you so much
- 5y ago

jitl 5y ago

Here’s a presentation by Grischenko on Chronofold https://m.youtube.com/watch?v=dKzMZsg5EVA https://m.youtube.com/watch?v=dKzMZsg5EVA

deleted 5y ago

[deleted]

tcldr 5y ago

CRDTs are fascinating data structures to me. One question: how would you handle something like cursor position with a DS like this? In the structure itself or a parallel structure with the site-id, insertion-point and expiration date?

lewisjoe 5y ago
Cursor positions are nothing but a counter. And counters are CRDTs by default, which means they are associative, idempotent and transitive. Best way is to have them as a separate structure pointing to an index.