日韩成人免费在线_国产成人一二_精品国产免费人成电影在线观..._日本一区二区三区久久久久久久久不

當前位置:首頁 > 科技  > 軟件

Figma 在協同編輯中使用的順序一致性算法: Fractional indexing

來源: 責編: 時間:2024-03-27 09:26:22 169觀看
導讀大家好,我是前端西瓜哥。Figma 支持多人協同,那它是如何做到順序一致性的呢?在多人同時操作同層級的多個圖形的順序時,需要保證用戶的意圖能保留,不會被其他用戶的操作覆蓋丟棄,且所有用戶最終的順序是一致的。為解決這個問

pbt28資訊網——每日最新資訊28at.com

大家好,我是前端西瓜哥。pbt28資訊網——每日最新資訊28at.com

Figma 支持多人協同,那它是如何做到順序一致性的呢?pbt28資訊網——每日最新資訊28at.com

在多人同時操作同層級的多個圖形的順序時,需要保證用戶的意圖能保留,不會被其他用戶的操作覆蓋丟棄,且所有用戶最終的順序是一致的。pbt28資訊網——每日最新資訊28at.com

為解決這個問題,Figma 使用了一種名為 Fractional Indexing 的簡單算法。pbt28資訊網——每日最新資訊28at.com

Fractional indexing 的原理

Fractional Indexing,直譯的話,是小數索引。pbt28資訊網——每日最新資訊28at.com

該算法的原理并不復雜。pbt28資訊網——每日最新資訊28at.com

圖形對象會使用 index 屬性表示順序,記錄自己在同級圖形中的位置。pbt28資訊網——每日最新資訊28at.com

index 的值為 0 到 1 之間的 64 位浮點數,不包括 0 和 1。pbt28資訊網——每日最新資訊28at.com

出于減少體積的考慮,figma 會丟掉前面的 0.,并把剩余的小數部分數字轉換成 ASCII 中的可打印字符(共 95個,表達為 95 進制數)。pbt28資訊網——每日最新資訊28at.com

不能為 0 和 1, 是因為如果給某個圖形設置了 0 或 1,這個圖形的左側或右側添加的圖形的 index 就會超出了 0 到 1 的范圍。pbt28資訊網——每日最新資訊28at.com

pbt28資訊網——每日最新資訊28at.com

當往兩個圖形之間插入新的節點時,我們會取這兩個圖形 index 的中點。pbt28資訊網——每日最新資訊28at.com

比如我們要在索引值分別為 0.3 和 0.4 的圖形插入圖形,這個圖形的索引值會取中間值 0.35。pbt28資訊網——每日最新資訊28at.com

pbt28資訊網——每日最新資訊28at.com

移動圖形同理。pbt28資訊網——每日最新資訊28at.com

但在實現這個算法的時候,你需要注意兩個問題。pbt28資訊網——每日最新資訊28at.com

精度問題

首先是精度問題。pbt28資訊網——每日最新資訊28at.com

說到取中間值,容易聯想到二分查找。pbt28資訊網——每日最新資訊28at.com

二分查找效率很高,時間復雜度是 O(logn),是因為不管數據規模多大,它 每一次查找都會直接將數據量減半,給你打骨折。pbt28資訊網——每日最新資訊28at.com

pbt28資訊網——每日最新資訊28at.com

index 使用的雙浮點數,能表示的二進制小數部分位數為 52 位,每次二分就是進行 位右移操作,會用掉一個精度。pbt28資訊網——每日最新資訊28at.com

假設我們不斷地往 0.3 到 0.4 的區間靠近 0.3 的那邊插入新圖形,我們會看到 index 非常快地接近 0.3,最后因為精度用完,再也無法二分。pbt28資訊網——每日最新資訊28at.com

const getMid = (a, b) => (a + b) / 2;const left = 0.3let right = 0.4for (let i = 0; i <= 50; i++) {  right = getMid(left, right);  console.log(right);}

上面的代碼在 50 次左右就將精度耗盡了。pbt28資訊網——每日最新資訊28at.com

pbt28資訊網——每日最新資訊28at.com

這種是很極端的場景,一般正常的用戶操作不會出現,Figma 并不打算處理這種情況的。pbt28資訊網——每日最新資訊28at.com

字符串表示法

當然精度問題是有辦法解決的,那就是用無限精度的數據類型:字符串。pbt28資訊網——每日最新資訊28at.com

該算法使用 "0" 到 "9" 的字符串表示索引,并通過字典序作為排序依據。pbt28資訊網——每日最新資訊28at.com

空字符表示最小值,null 表示最大值。pbt28資訊網——每日最新資訊28at.com

  • 計算中點會做舍入,盡量不占用更多的位數。

比如 "3" 和 "6" 的中點是 "5",而不是 "45"。但 "3" 和 “4” 因為太靠近,只能得到 "35"。pbt28資訊網——每日最新資訊28at.com

  • 如果是空字符,會等價于 "0",如果是 null,等價于 "10"(會比 "9" 大)。
  • 如果有前綴相同部分,取后面不同部分計算中點,再拼回去。

假如兩個相鄰圖形的 index 分別是  "123" 和 "1234"。pbt28資訊網——每日最新資訊28at.com

我們會取后面不同的部分 ""(表示 0) 和 "4",取中點 "2",然后添加回相同前綴 "123",得到我們需要的新索引 "1232"。pbt28資訊網——每日最新資訊28at.com

另外,對比 "123" 和 "123004" 時,"123" 要補全后綴零為 "12300"。pbt28資訊網——每日最新資訊28at.com

我們來看看效果。pbt28資訊網——每日最新資訊28at.com

使用這種方式,對 "3" 和 "4" 進行 1000 次的二分,因為突破了精度限制,我們會得到非常非常長的字符串。pbt28資訊網——每日最新資訊28at.com

pbt28資訊網——每日最新資訊28at.com

很長,通常通過編碼處理精簡,這里就不過多介紹了。pbt28資訊網——每日最新資訊28at.com

沖突問題

最后是沖突問題。pbt28資訊網——每日最新資訊28at.com

如果耿直地計算中點,那當多個客戶的都同時往兩個節點之間插入圖形,同步后就會出現多個圖形的 index 相同的場景。pbt28資訊網——每日最新資訊28at.com

對此,我們會 在中間值的基礎上,加上一個隨機的偏移值,這樣多個客戶端之間的沖突概率就非常的低。pbt28資訊網——每日最新資訊28at.com

但非常極端的情況下,沖突還是可能發生的,這種情況下就需要作為 中心權威的服務端去做修正 了,進行微小偏移,且和其他索引值不沖突。pbt28資訊網——每日最新資訊28at.com

結尾

Fractional Indexing 的優點是實現簡單,不需要 CRDT 那種墓碑機制,要保留大量無用的元數據。pbt28資訊網——每日最新資訊28at.com

缺點是極端場景 index 的長度很長,有精度不夠導致二分失敗的邊緣場景(可用字符串解決),以及對圖形編輯器并無大礙的交錯問題(兩用戶分別輸入 "123" 和 "ABC",同步后可能會得到 "1A2B3C",而不是 "123ABC")。pbt28資訊網——每日最新資訊28at.com

本文鏈接:http://www.www897cc.com/showinfo-26-79607-0.htmlFigma 在協同編輯中使用的順序一致性算法: Fractional indexing

聲明:本網頁內容旨在傳播知識,若有侵權等問題請及時與本網聯系,我們將在第一時間刪除處理。郵件:2376512515@qq.com

上一篇: 詳解SpringBoot錯誤處理

下一篇: 完美世界控股集團入選新一批國家文化產業示范基地名單

標簽:
  • 熱門焦點
Top 主站蜘蛛池模板: 朝阳区| 南宁市| 鲁甸县| 揭西县| 兴隆县| 宜黄县| 农安县| 周宁县| 西藏| 上犹县| 宣汉县| 万盛区| 榆林市| 德州市| 陆良县| 达拉特旗| 乐清市| 富源县| 那曲县| 本溪| 湘乡市| 廊坊市| 栾城县| 休宁县| 姜堰市| 宁都县| 防城港市| 富平县| 晋中市| 裕民县| 衡水市| 叶城县| 西充县| 张家川| 新巴尔虎右旗| 比如县| 宕昌县| 南皮县| 绥江县| 沾益县| 泉州市|