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

Figma 支持多人協(xié)同，那它是如何做到順序一致性的呢？

在多人同時操作同層級的多個圖形的順序時，需要保證用戶的意圖能保留，不會被其他用戶的操作覆蓋丟棄，且所有用戶最終的順序是一致的。

為解決這個問題，F(xiàn)igma 使用了一種名為 Fractional Indexing 的簡單算法。

算法來自 Figma 前 CTO 的這篇文章：

CRDT: Fractional Indexing

https://madebyevan.com/algos/crdt-fractional-indexing/

Fractional indexing 的原理

Fractional Indexing，直譯的話，是小數(shù)索引。

該算法的原理并不復雜。

圖形對象會使用 index 屬性表示順序，記錄自己在同級圖形中的位置。

index 的值為 0 到 1 之間的 64 位浮點數(shù)，不包括 0 和 1。

出于減少體積的考慮，figma 會丟掉前面的 0.，并把剩余的小數(shù)部分數(shù)字轉換成 ASCII 中的可打印字符（共 95個，表達為 95 進制數(shù)）。

不能為 0 和 1， 是因為如果給某個圖形設置了 0 或 1，這個圖形的左側或右側添加的圖形的 index 就會超出了 0 到 1 的范圍。

當往兩個圖形之間插入新的節(jié)點時，我們會取這兩個圖形 index 的中點。

比如我們要在索引值分別為 0.3 和 0.4 的圖形插入圖形，這個圖形的索引值會取中間值 0.35。

移動圖形同理。

但在實現(xiàn)這個算法的時候，你需要注意兩個問題。

精度問題

首先是精度問題。

說到取中間值，容易聯(lián)想到二分查找。

二分查找效率很高，時間復雜度是 O(logn)，是因為不管數(shù)據(jù)規(guī)模多大，它 每一次查找都會直接將數(shù)據(jù)量減半，給你打骨折。

index 使用的雙浮點數(shù)，能表示的二進制小數(shù)部分位數(shù)為 52 位，每次二分就是進行 位右移操作，會用掉一個精度。

假設我們不斷地往 0.3 到 0.4 的區(qū)間靠近 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 <= 50; i++) {
  right = getMid(left, right);
  console.log(right);
}

上面的代碼在 50 次左右就將精度耗盡了。

這種是很極端的場景，一般正常的用戶操作不會出現(xiàn)，F(xiàn)igma 并不打算處理這種情況的。

字符串表示法

當然精度問題是有辦法解決的，那就是用無限精度的數(shù)據(jù)類型：字符串。

可以看看 David Greenspan 的這篇文章。

https://observablehq.com/@dgreensp/implementing-fractional-indexing

該算法使用 "0" 到 "9" 的字符串表示索引，并通過字典序作為排序依據(jù)。

空字符表示最小值，null 表示最大值。

（1）計算中點會做舍入，盡量不占用更多的位數(shù)。

比如 "3" 和 "6" 的中點是 "5"，而不是 "45"。但 "3" 和 “4” 因為太靠近，只能得到 "35"。

（2）如果是空字符，會等價于 "0"，如果是 null，等價于 "10"（會比 "9" 大）。

（3）如果有前綴相同部分，取后面不同部分計算中點，再拼回去。

假如兩個相鄰圖形的 index 分別是  "123" 和 "1234"。

我們會取后面不同的部分 ""（表示 0） 和 "4"，取中點 "2"，然后添加回相同前綴 "123"，得到我們需要的新索引 "1232"。

另外，對比 "123" 和 "123004" 時，"123" 要補全后綴零為 "12300"。

我們來看看效果。

使用這種方式，對 "3" 和 "4" 進行 1000 次的二分，因為突破了精度限制，我們會得到非常非常長的字符串。

很長，通常通過編碼處理精簡，這里就不過多介紹了。

另外還有人基于 David Greenspan 的文章，實現(xiàn)了一個 NPM 庫，感興趣可以看看。

https://github.com/rocicorp/fractional-indexing。

沖突問題

最后是沖突問題。

如果耿直地計算中點，那當多個客戶的都同時往兩個節(jié)點之間插入圖形，同步后就會出現(xiàn)多個圖形的 index 相同的場景。

對此，我們會 在中間值的基礎上，加上一個隨機的偏移值，這樣多個客戶端之間的沖突概率就非常的低。

但非常極端的情況下，沖突還是可能發(fā)生的，這種情況下就需要作為 中心權威的服務端去做修正 了，進行微小偏移，且和其他索引值不沖突。

結尾

Fractional Indexing 的優(yōu)點是實現(xiàn)簡單，不需要 CRDT 那種墓碑機制，要保留大量無用的元數(shù)據(jù)。

缺點是極端場景 index 的長度很長，有精度不夠導致二分失敗的邊緣場景（可用字符串解決），以及對圖形編輯器并無大礙的交錯問題（兩用戶分別輸入 "123" 和 "ABC"，同步后可能會得到 "1A2B3C"，而不是 "123ABC"）。