在线协同技术调研

有严重的性能问编辑轨迹有 260 000 次编辑，最终文档大小约为 100 000 个字符。正如我上面所说，automerge 需要不到 5 分钟的时间来处理此跟踪。 这只是每秒 900 次编辑，这可能没问题。 但是当它完成时，automerge 正在使用 880 MB 的 RAM。 哇！ 这是每次按键 10kb 的内存。 在高峰期，automerge 使用了 2.6 GB 的 RAM！题

Automerge (RGA) 的行为由该算法定义：构建树，将每个Item连接到其父项当一个项目有多个子项时，先按序列号再按 ID 对它们进行排序。结果列表（或文本文档）通过使用深度优先遍历把树打平制作。

Automerge（以及 Yjs 和其他 CRDT）将共享文档视为字符列表。 文档中的每个字符都有一个唯一的 ID，每当您插入到文档中时，您都会为要插入的内容命名。

[翻译] - CRDTs 速度提高 5000x：优化探索

yjs 算法优化，以及性能也优化好了

每一个客户端一个数据结构

Yjs 不需要整篇博文来讨论如何使其更快，因为它已经非常快了，我们很快就会看到。Yjs 只是将所有Item放在一个单一的列表中：

技术理解

定义三种操作（insert、retain、delete），编辑器产生的每一个操作记录都保存了对应的操作数据，然后用一些列的操作表达富文本内容，操作列表即最终的结果

数据结构图

2012 年 Quill -> Delta （github 35K）

但是他们都有一个共同点，就是针对数据的修改都可以由操作对象表达，这个操作对象可以在网络中传输，实现基于操作的内容更新，这个是协同编辑的一个基础。

数据结构

2016 年 Slate -> JSON (github 26.8k)

协同编辑是构建在富文本编辑器之上的技术，它的实现一定程度上依赖于富文本数据模型的设计，这里介绍两个比较有代表性的数据模型：

富文本

藏路径

问题一：脏路径问题

问题二：并发冲突问题

问题三：undos/redos 问题

问题四：工程落地问题

整体介绍

协同主要面对的问题

OT 全称是 Operational Transformation，它的核心思想是操作转换，通过转换数据修改操作解决协同编辑中的各种问题。发展历史OT是最早（1989年）被提出的协同冲突处理算法2006 年被应用到 Google docs2011 年被应用到Office 365至今 OT 仍然是实现协同编辑的最主要的技术选择，Google docs 以及 Office 365 至今仍在采用 OT 的方案，国内近些年来的出现的一些文档类产品，包括石墨、钉钉、腾讯文档等等，他们的协同编辑技术也都是基于 OT 的。

OT

强调：最终一致性

CRDTCRDT (Conflict-free Replicated Data Type)即“无冲突复制数据类型”，它主要被应用在分布式系统中，保证分布式应用的数据一致性，文档协同编辑可以理解为分布式应用的一种，它的本质是数据结构，通过数据结构的设计保证并发操作数据的最终一致性。CRDT 于 2011 年正式被提出。 基于 CRDT 的协同编辑框架 Yjs 大概在2015年开源，Yjs 是专门为在 web 上构建协同应用程序而设计的。

CRDT

解决方案就是数据一致性算法 ，学术界主要有两个方面的研究：OT 算法 和 CRDT。

github  5.7k

子主题

架构图

方案流程图

1.ShareDB 方案

github  11.2k

y-websocket - 提供协同编辑时的消息通讯，包含服务端实现和前端集成的SDKy-protocols - 定义消息通讯协议，包括消息服务初始化、内容更新、鉴权、感知系统等y-redis - 持久化数据到 Redisy-indexeddb - 持久化数据到 IndexedDB

提供了完善的生态

1.数据结构

2.协同编辑的情况

3.同步机制

y-websocket内部也有服务的脚本 /bin/server.js 处理过程很简单，建立连接后 处理收到的消息，再发送出去

y-websocket-server

4. yjs后台websocket需要做什么？

yjs协同编辑的逻辑

2.Yjs 方案

开源技术

在线协同技术调研