Figma 在协同编辑中使用的顺序一致性算法： Fractional indexing

开发运维 2024-03-27 大树 手机阅读

大家好，我是前端西瓜哥。

Figma 支持多人协同，那它是如何做到顺序一致性的呢？

在多人同时操作同层级的多个图形的顺序时，需要保证用户的意图能保留，不会被其他用户的操作覆盖丢弃，且所有用户最终的顺序是一致的。

为解决这个问题，Figma 使用了一种名为 Fractional Indexing 的简单算法。

Fractional indexing 的原理

Fractional Indexing，直译的话，是小数索引。

该算法的原理并不复杂。

图形对象会使用 index 属性表示顺序，记录自己在同级图形中的位置。

index 的值为 0 到 1 之间的 64 位浮点数，不包括 0 和 1。

出于减少体积的考虑，figma 会丢掉前面的 0.，并把剩余的小数部分数字转换成 ASCII 中的可打印字符（共 95个，表达为 95 进制数）。

不能为 0 和 1， 是因为如果给某个图形设置了 0 或 1，这个图形的左侧或右侧添加的图形的 index 就会超出了 0 到 1 的范围。

当往两个图形之间插入新的节点时，我们会取这两个图形 index 的中点。

比如我们要在索引值分别为 0.3 和 0.4 的图形插入图形，这个图形的索引值会取中间值 0.35。

移动图形同理。

但在实现这个算法的时候，你需要注意两个问题。

精度问题

首先是精度问题。

说到取中间值，容易联想到二分查找。

二分查找效率很高，时间复杂度是 O(logn)，是因为不管数据规模多大，它 每一次查找都会直接将数据量减半，给你打骨折。

index 使用的双浮点数，能表示的二进制小数部分位数为 52 位，每次二分就是进行 位右移操作，会用掉一个精度。

假设我们不断地往 0.3 到 0.4 的区间靠近 0.3 的那边插入新图形，我们会看到 index 非常快地接近 0.3，最后因为精度用完，再也无法二分。

const getMid = (a, b) => (a + b) / 2;


const left = 0.3

let right = 0.4


for (let i = 0; i