Shared Editing: OT / CRDT

[magicdawn]

CRDT / OT

CRDT = Conflict-free replicated data types OT = operational transformation

• OT involves index, requires a backend holds a center source of truth

[magicdawn]

OT

• http://www.alloyteam.com/2019/07/13659/

[magicdawn]

CRDT

YATA / yjs

资料

• https://docs.yjs.dev/api/internals
• 论文
• 教程/文章/翻译 https://juejin.cn/collection/7384399933066166324

YATA 论文理解

We define < as the natural predecessor relation on S.

核心规则: origin 线不想交

如果 o2 在 o1 后面, (o1 < o2), 那么

• o2.origin <= o1.origin: o2.orign-o2 连线包含 o1.origin-o1 连线
• 或者 o1 < o2.origin: o2 整体都在 o1 后面, o1 < o2.origin < o2

至于 o1 = o2.origin, 不知这种情况如何处理

---

// Insert ’i’ in a list of
// conflicting operations ’ops ’.
insert(i, ops){
  i.position = ops[0].position
  for o in ops do
    // Rule 2:
    // Search for the last operation
    // that is to the left of i.
    if (o < i.origin OR i.origin <= o.origin)
      AND (o.origin != i.origin OR o.creator < i.creator) do
      // rule 1 and 3:
      // If this formula is fulfilled , 
      // i is a successor of o.
      i.position = o.position + 1
    else do
      if i.origin > o.origin do
      // Breaking condition ,
      // Rule 1 is no longer satisfied 
      // since otherwise origin connections would cross
      break
}