Find N3入網(wǎng)：最高支持16+1TB
OPPO將于近期登場的Find N3折疊屏目前已經(jīng)正式入網(wǎng)，型號為PHN110。本次Find N3在外觀方面相比前兩代有很大的變化，不再是小號的橫向折疊屏，而是跟別的廠商一樣采用了較為常見的
我是前端西瓜哥，今天我們來簡單入門一下 CRDT。
CRDT，全稱為 conflict-free replicated data type（無沖突復(fù)制數(shù)據(jù)類型），它是一種數(shù)據(jù)類型，或者說是方案，確保在網(wǎng)絡(luò)中的不同副本最后數(shù)據(jù)保持一致的，可以用協(xié)同編輯領(lǐng)域。
CRDT 在 2011 年在論文中被正式提出，雖相比 OT 算法（1989年）起步晚了很長的時間，但實現(xiàn)難度低很多，且出現(xiàn)了高性能的 CRDT 庫 Y.js，越來越多產(chǎn)品選擇使用 CRDT 來實現(xiàn)協(xié)同編輯功能。
CRDT 有以下特性：
每個客戶端可獨(dú)自操作副本，即支持并發(fā)，不需要和其他副本協(xié)同溝通。
這是一種樂觀復(fù)制（Optimistic replication）的策略。
各個副本可以獨(dú)立地在本地編輯，不用把更新提交到服務(wù)器，等待服務(wù)端返回最新的狀態(tài)，用這個新狀態(tài)覆蓋掉舊狀態(tài)。即可做到離線編輯，本地更新了狀態(tài)后再同步到服務(wù)端。
算法能夠自動地處理不一致的問題。
一個副本和另一個副本通常是不同的，當(dāng)其他副本同步過來時，有可能會出現(xiàn)沖突（不一致）的地方，比如兩個副本同時刪除和新增一個元素。
這個需要 CRDT 算法使用特定的策略去自動處理，而不是像 git merge 那樣去手動處理沖突。
同一時刻不同副本的狀態(tài)可能不同，但同步后它們能最終收斂（converge），達(dá)到相同的狀態(tài)（最終一致性）。
CRDT 主要分為兩大類型：Operation-based 和 State-based。
Operation-based CRDTs，基于操作的 CRDT。
副本進(jìn)行同步時，只會把 新增的本地操作（operation） 發(fā)送出去。
另一個副本拿到這個 operation 會將其應(yīng)用到自己的狀態(tài)上，operataion 需要滿足交換律（commutative）。
交換律，指的是交換運(yùn)算順序，最后的結(jié)果不變。比如加法就滿足交換律，a+b 和 b+a 的結(jié)果是相等的。
operataion 之所以要滿足交換律，是因為網(wǎng)絡(luò)并不可知。
假設(shè)有兩個副本 a 和 b 要同步過來給其他副本，你不知道到底誰先到達(dá)。對于一些副本可能是先 a 后 b，另一些可能是先 b 后 a，我們需保證在不同順序下，結(jié)果是一致的。
通常我們是通過 Generator 函數(shù)生成新的 opreation，發(fā)送給其他副本，然后這些副本通過 Effector 函數(shù)應(yīng)用這些副本。
因為交換律這個特性，Operation-based CRDTs 還有另一個名字 commutative replicated data types（CmRDTs）。
基于操作的 CRDT 的優(yōu)點是， 傳輸?shù)臄?shù)據(jù)量較少。
State-based CRDTs，基于狀態(tài)的 CRDT。
一個副本進(jìn)行同步時，會將 整個完整的本地狀態(tài)（state） 發(fā)送出去。另一個副本需要支持將其他副本進(jìn)行合并（merge）的操作，這個 merge 方法需要滿足交換律、分配律，以及冪等性。
基于狀態(tài)的 CRDT 的問題是，在文檔很大時，需要傳輸大量的數(shù)據(jù)，會耗費(fèi)大量的帶寬，且花費(fèi)時間長。所有實際生產(chǎn)很少會使用它。
優(yōu)點是實現(xiàn)更簡單，如果數(shù)據(jù)量不大，是可以考慮使用的。
State-based CRDTs 同樣也有另一個名字：Convergent Replicated Data Types（CvRDTs）。Convergent 是收斂的意思。
CRDT 做到數(shù)據(jù)最終一致性，是基于數(shù)學(xué)上的特性來保證的。
我們來看幾個簡單的 CRDT 模型。
AWSet（Add-wins set），一種新增優(yōu)先于刪除的集合數(shù)據(jù)結(jié)構(gòu)。
假如剛開始的時候，副本 A 和 副本 B 的狀態(tài)是一致的，有一個 a 在集合中。
副本 A 刪除了 a，然后再新增 a。
副本 B 刪除了 a。
副本 A 的新增 a 和 副本 B 的刪除 a 同時發(fā)生。
此時我們會選擇新增，忽略刪除，最后兩個副本的狀態(tài)還是 a 在集合中。
為判斷兩個操作是否是 “同時” 的，我們會附加一個和時序相關(guān)的元數(shù)據(jù)，比如時間戳、版本向量。
RWSet（Remove-win set），一種刪除優(yōu)先新增的集合數(shù)據(jù)結(jié)構(gòu)。
AWSet 類似，但對于并發(fā)的操作，會保留刪除，丟棄新增。
LWW（Last-writer-wins），最后寫入者優(yōu)先。
所有的操作會有一個時間戳元數(shù)據(jù)，副本會對比同步操作的時間戳。
如果大于當(dāng)前狀態(tài)時間戳，覆蓋掉原來的狀態(tài)；如果小于當(dāng)前狀態(tài)時間戳，則忽略。
Two-Phase Set。
此模型會維護(hù)兩個集合，一個是新增集合，保存新增的元素，另一個是刪除集合，保存被刪除的元素。
模型的最終狀態(tài)為新增集合和刪除集合的差集。
另外，集合比較特殊，它是只增集合（grow-only set），只能往集合里加元素，不能從集合里移除元素。
這意味著一個元素如果被刪除了，就再也不能添加回來。所以刪除集合也被叫做 tombstone set（墓碑集合），人噶不能復(fù)生。
2P-Set 也算是一種 RW-Set（刪除優(yōu)先），特別的點在于元素被刪除后不能新增回來。
G-Counter，Grow-only Counter，只增計數(shù)器，一個只能增加計數(shù)的計數(shù)器。
此模型使用 n 個節(jié)點的容器（一個整數(shù)數(shù)組），每個副本會分配一個 id，某個副本給計數(shù)器 +1，其實就會給對應(yīng)的數(shù)組元素 +1。
計數(shù)器的值為數(shù)組的求和。
PN-Counter，Positive-Negative Counter，一個支持增減的計數(shù)器。
多個 CRDT 可以組合成一個更復(fù)雜的 CRDT。
類似 G-Counter，但 PN-Counter 使用兩個 G-Counter，一個保存新增數(shù)（新增操作），另一個保存減少數(shù)（減少操作）。
計數(shù)器的值為新增數(shù)組求和減去減少數(shù)組的和。
最后我們看看復(fù)雜點的，簡單介紹一下 Y.js 的 YATA（Yet Another Transformation Approach）模型。
假設(shè)我們有值為 "ABCD" 的字符串。
YATA 模型會將其拆分成一個個字符，加上元數(shù)據(jù)，然后按順序首尾相連組成一個雙鏈表。
// 大概這樣子{ id: '2:0', // 客戶端 ID + clock ID val: 'B', left: a, // 當(dāng)前節(jié)點的左節(jié)點 right: c, // 右節(jié)點 origin: a, // 節(jié)點創(chuàng)建時的左節(jié)點 rightOrigin: c // 節(jié)點創(chuàng)建時的右節(jié)點}操作有 “插入” 和 “刪除”。
假設(shè)本地在 AB 之間插入 E，此時沒有發(fā)送同步，然后收到其他副本傳過來的 F，也是要插入到 AB 之間。
此時 E 和 F 是沖突的，我們會對唯一的 id（某種意義上的時間戳）使用特定的規(guī)則來決定先后順序。
至于刪除操作，因為插入操作需要找到在左右節(jié)點的位置，所以節(jié)點即使被刪除了也是不能從雙鏈表中移出的。
對此，YATA 選擇使用墓碑機(jī)制。YATA 將對應(yīng)節(jié)點標(biāo)記為刪除（item.deleted 設(shè)置為 true），并將節(jié)點記錄到刪除集合 DeleteSet 里。
這里其實可以看到，CRDT 通常是需要加很多元數(shù)據(jù)的，尤其是復(fù)雜數(shù)據(jù)結(jié)構(gòu)且數(shù)據(jù)量較大的場景，所以這也是 CRDT 起初被詬病占用內(nèi)存高的原因。
但 Y.js 通過一系列手段（比如將多個節(jié)點合并為一個大節(jié)點），將性能優(yōu)化到足夠面對大多數(shù)場景，證明了用 CRDT 是做協(xié)同編輯的是不用擔(dān)心性能問題的，如果有，一定是你沒優(yōu)化好。
本文只是簡單介紹一些 CRDT 是什么，并感受了一些簡單的 CRDT 模型，希望對你有所幫助。
本文鏈接：http://www.www897cc.com/showinfo-26-88328-0.html這一次，徹底搞懵 CRDT
聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
上一篇： PlantUML畫時序圖，真香！
下一篇： 什么鎖比讀寫鎖性能更高？
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請聯(lián)系：2376512515@qq.com 津ICP備18001702號
津公網(wǎng)安備 12010102000574號