Yjs解析

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

本文引用自 摸鱼wiki

1. YATA算法解析

YATA算法是Yjs库的核心冲突解决算法这里主要讲解下这个算法成立的三个规则

规则1禁止发生冲突的插入操作之间的origin连线红线发生交叉。

如上图所示图中展示了两个冲突的插入操作基状态 O 1 O_{1} O1​ O 2 O_{2} O2​以及他们对应的插入内容 O 1 ′ O'_{1} O1′​ O 2 ′ O'_{2} O2′​插入后的最终状态只能出现两种情况 O 1 O 1 ′ O 2 O 2 ′ O_{1}O'_{1}O_{2}O'_{2} O1​O1′​O2​O2′​或者 O 1 O 2 O 2 ′ O 1 ′ O_{1}O_{2}O'_{2}O'_{1} O1​O2​O2′​O1′​绝对不能出现 O 1 O 2 O 1 ′ O 2 ′ O_{1}O_{2}O'_{1}O'_{2} O1​O2​O1′​O2′​ 这种交叉的情况否则算法的正确性不能保证。即满足

o 1 < r u l e s 1 o 2 ⇔ o 1 < o r i g i n 2 ∨ o r i g i n 2 ≤ o r i g i n 1 o_{1} <_{rules1}o_{2} \Leftrightarrow o_{1} < origin_{2} \lor origin_{2} \leq origin_{1} o1​<rules1​o2​⇔o1​<origin2​∨origin2​≤origin1​

规则2指定 < c <_{c} <c​ 上的传递性。 o 1 < c o 2 o_{1} <_{c} o_{2} o1​<c​o2​确保没有大于 o 2 o_{2} o2​但小于 o 1 o_{1} o1​的操作 o o o

o 1 < r u l e s 2 o 2 ⇔ ∀ o : o 2 < c o → o 1 ≤ o ⇔ ∄ o : o 2 < c o < o 1 o_{1} <_{rules2} o_{2} \Leftrightarrow \forall o : o_{2} <_{c} o \rightarrow o_{1} \leq o \Leftrightarrow \nexists o : o_{2} <_{c} o < o_{1} o1​<rules2​o2​⇔∀o:o2​<c​o→o1​≤o⇔∄o:o2​<c​o<o1​

规则3当两个冲突操作具有相同的原点时创建者id较小的操作位于左侧

o 1 < r u l e s 3 o 2 ⇔ o r i g i n 1 ≡ o r i g i n 2 → c r e a t o r 1 < c r e a t o r 2 o_{1} <_{rules3} o2 \Leftrightarrow origin_{1} \equiv origin_{2} \rightarrow creator_{1} < creator_{2} o1​<rules3​o2⇔origin1​≡origin2​→creator1​<creator2​

2. 操作序列号生成

Yjs会给每个操作生成一个操作id该id由一个(clientId, clockId)元组构成。clientId表示房间内客户端的标识符全局唯一clockId采用名为 Lamport timestamp 的逻辑时间戳可以理解为是个从零开始的单调递增计数器具体的更新逻辑为

收到本地事件时localClock += 1

收到远端事件时localClock = max(remoteClock, localClock) + 1

3. 存储结构

  • StructStore依据逻辑时序创建的结构化数据。其为房间内每个客户端分配一个扁平的数组数组内存储该客户端的操作列表。该数据类型方便进行二分查找对应某一客户端的某一操作。

  • 双向链表依据文档结构顺序创建的结构化数据。文档的每个操作都会插入到此链表中可以理解为这个链表维护整个文档的最新状态。

4. 删除机制

采用双缓冲队列机制。删除的节点先放到一个临时队列A中一段时间后再放到可删除队列B最后清空B队列即完成删除。

5. 撤销机制

Yjs每次更新都会生成一次Transaction转换主要有以下两个流程

  • 记录本次更新新增的item

  • 往DeleteSet中添加本次更新导致被删除的item

基于上述的数据结构撤销一次Transaction可以简化为下面两个操作

  • 将该次Transaction新增的item标记为删除

  • 重新插入该次Transaction删除的item

6. 同步机制

各客户端维护一个StateVector。Yjs 通过 StateVector 的概念来定位逻辑时间轴这种数据结构实际上就是一组记录了某时刻全部客户端 (clientId, clockId) 的元组。

同步文档状态时Yjs划分了两个阶段

  • 阶段1待同步用户向房间内所有其他用户发送自身的StateVector

  • 阶段2其他用户收到该用户的StateVector后用各自的本地数据计算出最小所需Update数据然后发回给待同步用户。

7. 参考文献

[1] https://zhuanlan.zhihu.com/p/452980520

[2] https://juejin.cn/post/7027487213525041166

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
返回列表

上一篇：选择排序算法的实现和优化

下一篇：Moonbeam生态说｜多链钱包项目Talisman

“Yjs解析” 的相关文章

Dynamsoft Barcode Reader 9.6.1 for NET Crack1年前 (2023-02-02)
Android8.1 系统设置默认值大全1年前 (2023-02-02)
SpringBoot+vue 实现监控视频rtsp播放(java+Nginx+ffmpeg+flv.js)1年前 (2023-02-02)
一文读懂 HTTP/1 HTTP/2 HTTP/31年前 (2023-02-02)
用Java写一个分布式缓存——缓存淘汰算法1年前 (2023-02-02)
模板-线段树1年前 (2023-02-02)
Loj 507 接竹竿 题解1年前 (2023-02-02)
截至到2022年12月12日，知网最新改进 YOLO 核心论文合集 | 22篇创新点速览1年前 (2023-02-02)
数据库系统课程设计（高校成绩管理数据库系统的设计与实现）_数据库学生成绩管理系统课程设计1年前 (2023-02-02)
Python Tkinter Gui 运行不卡顿，多线程解决界面卡死问题_python在运行时窗口卡住1年前 (2023-02-02)

阿里云国际版