K60至尊版剛預(yù)熱 一加Ace2 Pro正面硬剛
Redmi這邊剛?cè)缁鹑巛钡男麄髁薑60 Ultra的各種技術(shù)和硬件配置，作為競(jìng)品的一加也坐不住了。一加中國(guó)區(qū)總裁李杰發(fā)布了兩條微博，表示在自家的一加Ace2上早就已經(jīng)采用了和PixelWo
大家好，我是前端西瓜哥。
Figma 支持多人協(xié)同，那它是如何做到順序一致性的呢？
在多人同時(shí)操作同層級(jí)的多個(gè)圖形的順序時(shí)，需要保證用戶(hù)的意圖能保留，不會(huì)被其他用戶(hù)的操作覆蓋丟棄，且所有用戶(hù)最終的順序是一致的。
為解決這個(gè)問(wèn)題，F(xiàn)igma 使用了一種名為 Fractional Indexing 的簡(jiǎn)單算法。
Fractional Indexing，直譯的話(huà)，是小數(shù)索引。
該算法的原理并不復(fù)雜。
圖形對(duì)象會(huì)使用 index 屬性表示順序，記錄自己在同級(jí)圖形中的位置。
index 的值為 0 到 1 之間的 64 位浮點(diǎn)數(shù)，不包括 0 和 1。
出于減少體積的考慮，figma 會(huì)丟掉前面的 0.，并把剩余的小數(shù)部分?jǐn)?shù)字轉(zhuǎn)換成 ASCII 中的可打印字符（共 95個(gè)，表達(dá)為 95 進(jìn)制數(shù)）。
不能為 0 和 1， 是因?yàn)槿绻o某個(gè)圖形設(shè)置了 0 或 1，這個(gè)圖形的左側(cè)或右側(cè)添加的圖形的 index 就會(huì)超出了 0 到 1 的范圍。
當(dāng)往兩個(gè)圖形之間插入新的節(jié)點(diǎn)時(shí)，我們會(huì)取這兩個(gè)圖形 index 的中點(diǎn)。
比如我們要在索引值分別為 0.3 和 0.4 的圖形插入圖形，這個(gè)圖形的索引值會(huì)取中間值 0.35。
移動(dòng)圖形同理。
但在實(shí)現(xiàn)這個(gè)算法的時(shí)候，你需要注意兩個(gè)問(wèn)題。
首先是精度問(wèn)題。
說(shuō)到取中間值，容易聯(lián)想到二分查找。
二分查找效率很高，時(shí)間復(fù)雜度是 O(logn)，是因?yàn)椴还軘?shù)據(jù)規(guī)模多大，它 每一次查找都會(huì)直接將數(shù)據(jù)量減半，給你打骨折。
index 使用的雙浮點(diǎn)數(shù)，能表示的二進(jìn)制小數(shù)部分位數(shù)為 52 位，每次二分就是進(jìn)行 位右移操作，會(huì)用掉一個(gè)精度。
假設(shè)我們不斷地往 0.3 到 0.4 的區(qū)間靠近 0.3 的那邊插入新圖形，我們會(huì)看到 index 非常快地接近 0.3，最后因?yàn)榫扔猛辏僖矡o(wú)法二分。
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 次左右就將精度耗盡了。
這種是很極端的場(chǎng)景，一般正常的用戶(hù)操作不會(huì)出現(xiàn)，F(xiàn)igma 并不打算處理這種情況的。
當(dāng)然精度問(wèn)題是有辦法解決的，那就是用無(wú)限精度的數(shù)據(jù)類(lèi)型：字符串。
該算法使用 "0" 到 "9" 的字符串表示索引，并通過(guò)字典序作為排序依據(jù)。
空字符表示最小值，null 表示最大值。
比如 "3" 和 "6" 的中點(diǎn)是 "5"，而不是 "45"。但 "3" 和 “4” 因?yàn)樘拷荒艿玫?"35"。
假如兩個(gè)相鄰圖形的 index 分別是 "123" 和 "1234"。
我們會(huì)取后面不同的部分 ""（表示 0） 和 "4"，取中點(diǎn) "2"，然后添加回相同前綴 "123"，得到我們需要的新索引 "1232"。
另外，對(duì)比 "123" 和 "123004" 時(shí)，"123" 要補(bǔ)全后綴零為 "12300"。
我們來(lái)看看效果。
使用這種方式，對(duì) "3" 和 "4" 進(jìn)行 1000 次的二分，因?yàn)橥黄屏司认拗疲覀儠?huì)得到非常非常長(zhǎng)的字符串。
很長(zhǎng)，通常通過(guò)編碼處理精簡(jiǎn)，這里就不過(guò)多介紹了。
最后是沖突問(wèn)題。
如果耿直地計(jì)算中點(diǎn)，那當(dāng)多個(gè)客戶(hù)的都同時(shí)往兩個(gè)節(jié)點(diǎn)之間插入圖形，同步后就會(huì)出現(xiàn)多個(gè)圖形的 index 相同的場(chǎng)景。
對(duì)此，我們會(huì) 在中間值的基礎(chǔ)上，加上一個(gè)隨機(jī)的偏移值，這樣多個(gè)客戶(hù)端之間的沖突概率就非常的低。
但非常極端的情況下，沖突還是可能發(fā)生的，這種情況下就需要作為 中心權(quán)威的服務(wù)端去做修正 了，進(jìn)行微小偏移，且和其他索引值不沖突。
Fractional Indexing 的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，不需要 CRDT 那種墓碑機(jī)制，要保留大量無(wú)用的元數(shù)據(jù)。
缺點(diǎn)是極端場(chǎng)景 index 的長(zhǎng)度很長(zhǎng)，有精度不夠?qū)е露质〉倪吘増?chǎng)景（可用字符串解決），以及對(duì)圖形編輯器并無(wú)大礙的交錯(cuò)問(wèn)題（兩用戶(hù)分別輸入 "123" 和 "ABC"，同步后可能會(huì)得到 "1A2B3C"，而不是 "123ABC"）。
本文鏈接：http://www.www897cc.com/showinfo-26-79607-0.htmlFigma 在協(xié)同編輯中使用的順序一致性算法： Fractional indexing
聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。郵件：2376512515@qq.com
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請(qǐng)聯(lián)系：2376512515@qq.com 津ICP備18001702號(hào)
津公網(wǎng)安備 12010102000574號(hào)