建站
咨詢
售后
建站咨詢
新聞中心
前言
- 最基礎(chǔ)的文本編輯功能(哦？好像textarea就可以完成，那如果是富文本呢？)我們需要一個(gè)文檔模型來描述文檔；
- 富文本編輯器，提供富文本的編輯和渲染能力；
- 協(xié)同功能，不同的用戶對同一份文檔的編輯需要保持大家看到的都是一樣的；
- 協(xié)同網(wǎng)絡(luò)模型，保證服務(wù)器和客戶端之間的文檔模型一致；
名詞解釋
OT：一種解決協(xié)同問題的算法；
讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對這個(gè)行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長期合作伙伴，公司提供的服務(wù)項(xiàng)目有：域名申請、網(wǎng)絡(luò)空間、營銷軟件、網(wǎng)站建設(shè)、宜都網(wǎng)站維護(hù)、網(wǎng)站推廣。
OP：operation的簡稱，在OT中指的是一次操作；
etherpad: 一個(gè)實(shí)現(xiàn)文檔協(xié)同功能的開源庫；
easysync: etherpad中實(shí)現(xiàn)文檔協(xié)同的核心算法，是OT算法的一種，主要用來處理文本協(xié)同；
ot-json：ot算法的一種，顧名思義，是主要用來處理結(jié)構(gòu)化數(shù)據(jù)；
Changeset: 一種描述文檔更改的數(shù)據(jù)格式，用來表示整個(gè)文檔的一次修改；
ClientVars ： 表示一篇文檔的初始化數(shù)據(jù)，一般由連續(xù)的changeset組合而成；
符號解釋
??|?? ：移動光標(biāo)；
??·??：疊加；
正文
OT算法
什么是OT算法呢？我們先從頭說起，如果要實(shí)現(xiàn)一個(gè)多人共同編輯文檔的功能，我們最簡單暴力的做法是啥？
編輯鎖
顧名思義，假如A在編輯文檔，服務(wù)端直接將這個(gè)文檔加鎖，B如果在這個(gè)時(shí)候也加入了編輯，由于鎖的存在，B的編輯直接被丟棄?？梢钥闯?，這種編輯鎖的實(shí)現(xiàn)方式非常粗暴，體驗(yàn)極其糟糕，當(dāng)然了，在很多公司(比如我們的某死對頭公司)的一些wiki系統(tǒng)就是用這種實(shí)現(xiàn)方式，由于這種實(shí)現(xiàn)方式比較簡單，而且體驗(yàn)很糟糕(內(nèi)容丟失
& 無法實(shí)時(shí))，我們這里就不做討論了。
Linux中的diff-patch
Linux中有兩個(gè)命令：diff和patch；如果我們能在JS中實(shí)現(xiàn)這套算法，那么多人協(xié)同編輯可以這樣做：
- 用戶打開文檔后和服務(wù)端建立長鏈接，保存文檔副本；
- 用戶編輯的時(shí)候如果有停頓(比如3s)，則將現(xiàn)有的文檔和副本進(jìn)行diff對比，將結(jié)果傳給服務(wù)端，更新副本；
- 服務(wù)端更新文檔，將diff結(jié)果通過長鏈接通知到其它用戶，其它用戶使用patch方法更新本地的文檔；
我們來測試下：
# 本地文檔
$ echo '復(fù)仇者聯(lián)盟
鋼鐵俠
美國隊(duì)長' > test-local.txt
# 生成用戶A編輯后的文檔
$ echo '復(fù)仇者聯(lián)盟
鋼鐵俠
綠巨人' > test-userA.txt
# diff兩個(gè)文檔
$ diff test-local.txt test-userA.txt > diff-test.patch
# 查看diff-test.patch內(nèi)容
$ cat diff-test.patch
3c3
< 美國隊(duì)長
---
> 綠巨人
從diff-test.patch內(nèi)容可以看出，已經(jīng)找出了兩個(gè)文檔不同的地方，然后我們再模擬下用戶B的行為：
# 生成用戶B編輯的文檔
$ echo '復(fù)仇者聯(lián)盟
黑寡婦
美國隊(duì)長' > test-userB.txt
# patch方法更新文檔
$ patch test-userB.txt < diff-test.patch
# 查看test-userB.txt內(nèi)容
$ cat test-userB.txt
復(fù)仇者聯(lián)盟
黑寡婦
綠巨人
可以看到，用戶B文檔的第三行已經(jīng)更新為了用戶A修改后的“綠巨人”。但這種實(shí)現(xiàn)方式有個(gè)問題，因?yàn)樗腔谛衼磉M(jìn)行對比的，就會導(dǎo)致很容易出現(xiàn)沖突，比如：
# 生成文件1
$ echo '復(fù)仇者聯(lián)盟' > local.txt
# 生成文件2
$ echo '復(fù)仇者聯(lián)盟鋼鐵俠' > userA.txt
# diff對比
$ diff local.txt userA.txt > diff.patch
查看diff.patch內(nèi)容：
1c1
< 復(fù)仇者聯(lián)盟
---
> 復(fù)仇者聯(lián)盟鋼鐵俠
這就意味著如果兩個(gè)人同時(shí)修改同一行，那必然就會產(chǎn)生沖突，我們測試下:
# 生成文件3
$ echo '復(fù)仇者聯(lián)盟美國隊(duì)長' > userB.txt
# patch
$ patch userB.txt < diff.patch
以上我們發(fā)現(xiàn)，假如原始文檔是“復(fù)仇者聯(lián)盟”，用戶A修改為“復(fù)仇者聯(lián)盟鋼鐵俠”，將diff結(jié)果傳給服務(wù)端，服務(wù)端傳給用戶B，而用戶B只是將文檔改為了“復(fù)仇者聯(lián)盟美國隊(duì)長”，直覺上我們可以看出，這兩處是不沖突的，完全可以合并成“復(fù)仇者聯(lián)盟鋼鐵俠美國隊(duì)長”，但實(shí)際上的patch結(jié)果卻是這樣的：
$ cat userB.txt.rej
***************
*** 1
- 復(fù)仇者聯(lián)盟
--- 1 -----
+ 復(fù)仇者聯(lián)盟鋼鐵俠
因此這種基于行的算法還是比較粗糙，體驗(yàn)上比編輯鎖雖然好了一點(diǎn)，但實(shí)際弊端還是比較大，既然基于行的實(shí)現(xiàn)無法滿足需求，那有木有可能去基于字符進(jìn)行diff呢？
diff-patch算法
diff-match-patch[1]是另一種diff-patch算法的實(shí)現(xiàn)，它是基于字符去進(jìn)行diff的，這里不介紹該算法的細(xì)節(jié)了，它的算法在這：diff-match-patch JS實(shí)現(xiàn)源碼[2]。我們直接測試下它的效果
// 示例1
const localText = '復(fù)仇者聯(lián)盟';
const userAText = '復(fù)仇者聯(lián)盟鋼鐵俠';
const userBText = '復(fù)仇者聯(lián)盟美國隊(duì)長';
// 結(jié)果為：復(fù)仇者聯(lián)盟鋼鐵俠美國隊(duì)長
// 示例2
const localText = '復(fù)仇者聯(lián)盟';
const userAText = '復(fù)仇者聯(lián)盟美國隊(duì)長';
const userBText = '復(fù)仇者聯(lián)盟鋼鐵俠';
// 結(jié)果為：復(fù)仇者聯(lián)盟鋼鐵俠美國隊(duì)長
// 示例3
const localText = '復(fù)仇者聯(lián)盟';
const userAText = '復(fù)仇者聯(lián)盟 美國隊(duì)長';
const userBText = '復(fù)仇者聯(lián)盟 鋼鐵俠';
// 結(jié)果為：復(fù)仇者聯(lián)盟 美國隊(duì)長 鋼鐵俠
如上示例已經(jīng)解決了Linux的diff-patch基于行diff的弊端，但仍然存在問題，如上的示例1和示例2如果沒有符號分割，那么結(jié)果是一樣的。
const localText = '復(fù)仇者 Iron Man';
const userAText = 'Iron Man 鋼鐵俠';
const userBText = '復(fù)仇者 Caption';
// 結(jié)果為：Caption
原始文檔為“復(fù)仇者 Iron Man”，用戶A修改為了“Iron Man 鋼鐵俠”，用戶B修改為了“復(fù)仇者 Caption”，直覺上其實(shí)可以合并為“Caption 鋼鐵俠”，但實(shí)際上卻修改為了“Caption ”(注意Caption后面有個(gè)空格，鋼鐵俠沒了)，
也就是說diff-match-patch存在丟字符的情況，這個(gè)富文本格式的文檔中會是致命的問題，比如丟失了某個(gè) > 可能整個(gè)文檔都會亂掉，那么有木有既解決了行匹配沖突問題又解決了丟字符問題的解決方案呢？答案就是本文的重點(diǎn)——OT算法
operation transformation
示例
ot.js[3]是針對純文本的一種JS實(shí)現(xiàn)，我們看下它的實(shí)現(xiàn)效果，針對同樣的示例：
const str = '復(fù)仇者 Iron Man';
const operation0 = new ot.TextOperation().delete('復(fù)仇者 ').retain(8).insert(' 鋼鐵俠');
const operation1 = new ot.TextOperation().retain(4).delete('Iron Man').insert('Captain');
const op = ot.TextOperation.transform(operation0, operation1);
// 結(jié)果：Captain 鋼鐵俠
可以看到這正是符合我們預(yù)期的結(jié)果。
原理
看了很多講OT的文檔，基本每一篇都很長，云山霧罩，但其實(shí)它的核心原理很簡單。在OT中，我們將文檔的操作分為三個(gè)類型，通過組合這三個(gè)原子操作完成對整個(gè)文檔的編輯工作：
- insert(插入字符)；
- delete(刪除字符)
- retain(保持n個(gè)字符，也就是移動光標(biāo))；
注： 實(shí)際上diff-match-patch算法也將操作分為三類：insert，delete，equal(不變的字符)，insert、delete和OT中含義類似，equal是指對比diff過程中那些沒有改變的字符，diff-match-patch會給這些不同類型的字符打標(biāo)，后面patch的時(shí)候再根據(jù)不同類型的字符做對應(yīng)的邏輯處理。
insert
|
復(fù)仇者聯(lián)盟|
如上|代表的是光標(biāo)的位置，從上到下模擬用戶操作的行為，以上操作使用ot.js來描述：
const str = '';
const operation = new ot.TextOperation().insert('復(fù)仇者聯(lián)盟');
const result = operation.apply(str);
console.log(result); // 復(fù)仇者聯(lián)盟
op創(chuàng)建時(shí)會有一個(gè)虛擬光標(biāo)位于字符的開頭，在一個(gè)op結(jié)束時(shí)，光標(biāo)一定要在字符串的末尾，其中insert會自動移動光標(biāo)位置，因此我們這里不需要手動去移動光標(biāo)；
retain
|復(fù)仇者聯(lián)盟
復(fù)仇者聯(lián)盟|
復(fù)仇者聯(lián)盟鋼鐵俠|
如上過程用ot.js來描述：
const str = '復(fù)仇者聯(lián)盟';
const operation = new ot.TextOperation().retain(5).insert('鋼鐵俠');
const result = operation.apply(str);
console.log(result);// 復(fù)仇者聯(lián)盟鋼鐵俠
delete
|復(fù)仇者聯(lián)盟鋼鐵俠
復(fù)仇者聯(lián)盟|鋼鐵俠
復(fù)仇者聯(lián)盟|
如上過程用ot.js描述：
const str = '復(fù)仇者聯(lián)盟鋼鐵俠';
const operation = new ot.TextOperation().retain(5).delete('鋼鐵俠');
const result = operation.apply(str);
console.log(result);// 復(fù)仇者聯(lián)盟
刪除字符時(shí)可以輸入字符，也可以輸入字符數(shù)，實(shí)際上源碼中是直接取的??'鋼鐵俠'.length?? 因此對于delete中字符串而言，只要長度正確就可以達(dá)到目的，上面代碼改成??delete('123')??不會有任何影響。
transform
前面的代碼我們看到過ot.js的這個(gè)方法，正是這個(gè)方法實(shí)現(xiàn)了diff-match-patch的丟失字符的問題，而transform正是OT中的核心方法。我們先不羅列他的源碼，先看幾個(gè)例子：
示例1
原始文檔內(nèi)容(空白文檔)：|
用戶A編輯后的文檔內(nèi)容：鋼鐵俠
用戶B編輯后的文檔內(nèi)容：雷神
對應(yīng)代碼實(shí)現(xiàn)：
const str = ' ';
const operation0 = new ot.TextOperation().insert('鋼鐵俠');
const operation1 = new ot.TextOperation().insert('雷神');
const op = ot.TextOperation.transform(operation0, operation1);
console.log('transform后op操作：', op[0].toString(), ' | ', op[1].toString());
// transform后op操作：insert '鋼鐵俠', retain 2 | retain 3, insert '雷神'
console.log('transform后操作后的字符串：', op[0].apply(operation1.apply(str)), ' | ', op[1].apply(operation0.apply(str)));
// transform后操作后的字符串： 鋼鐵俠雷神 | 鋼鐵俠雷神
最終結(jié)果是“鋼鐵俠雷神”；
transform的操作過程：
|
循環(huán)次數(shù) |
op1 |
op2 |
operation1prime |
operation2prime |
|
1 |
3 |
2 |
insert('鋼鐵俠') |
retain(3) |
|
2 |
undefined |
2 |
retain(2) |
insert('雷神') |
示例2
原始文檔：復(fù)仇者聯(lián)盟
用戶A：復(fù)仇者鋼鐵俠聯(lián)盟
用戶B：復(fù)仇者聯(lián)盟美國隊(duì)長
對應(yīng)代碼實(shí)現(xiàn)：
const str = '復(fù)仇者聯(lián)盟';
const operation0 = new ot.TextOperation().retain(3).insert('鋼鐵俠').retain(2);
const operation1 = new ot.TextOperation().retain(5).insert('美國隊(duì)長');
const op = ot.TextOperation.transform(operation0, operation1);
console.log('transform后op操作：', op[0].toString(), ' | ', op[1].toString());
// transform后op操作：retain 3, insert '鋼鐵俠', retain 6 | retain 8, insert '美國隊(duì)長'
console.log('transform后操作后的字符串：', op[0].apply(operation1.apply(str)), ' | ', op[1].apply(operation0.apply(str)));
// transform后操作后的字符串： 復(fù)仇者鋼鐵俠聯(lián)盟美國隊(duì)長 | 復(fù)仇者鋼鐵俠聯(lián)盟美國隊(duì)長
最終結(jié)果是“復(fù)仇者鋼鐵俠聯(lián)盟美國隊(duì)長”；
transform的操作過程：
|
循環(huán)次數(shù) |
op1 |
op2 |
operation1prime |
operation2prime |
|
1 |
3 |
5 |
retain(3) |
retain(3) |
|
2 |
'鋼鐵俠' |
2 |
insert('鋼鐵俠') |
retain(3) |
|
3 |
2 |
2 |
retain(2) |
retain(2) |
|
4 |
undefined |
'美國隊(duì)長' |
retain(4) |
insert('美國隊(duì)長') |
示例3
原始文檔：復(fù)仇者聯(lián)盟鋼鐵俠美國隊(duì)長
用戶A：復(fù)仇者聯(lián)盟鋼鐵俠
用戶B：復(fù)仇者聯(lián)盟美國隊(duì)長
對應(yīng)代碼實(shí)現(xiàn)：
const str = '復(fù)仇者聯(lián)盟鋼鐵俠美國隊(duì)長';
const operation0 = new ot.TextOperation().retain(5).delete('鋼鐵俠').retain(4);
const operation1 = new ot.TextOperation().retain(8).delete('美國隊(duì)長');
const op = ot.TextOperation.transform(operation0, operation1);
console.log('transform后op操作：', op[0].toString(), ' | ', op[1].toString());
// transform后op操作：retain 5, delete 3 | retain 5, delete 4
console.log('transform后操作后的字符串：', op[0].apply(operation1.apply(str)), ' | ', op[1].apply(operation0.apply(str)));
// transform后操作后的字符串： 復(fù)仇者聯(lián)盟 | 復(fù)仇者聯(lián)盟
最終結(jié)果是“復(fù)仇者聯(lián)盟”；
操作過程：
|
循環(huán)次數(shù) |
op1 |
op2 |
operation1prime |
operation2prime |
|
1 |
5 |
8 |
retain(5) |
retain(5) |
|
2 |
-3 |
3 |
delete(3) |
- |
|
3 |
4 |
-4 |
- |
delete(4) |
最終結(jié)果是“復(fù)仇者聯(lián)盟”；
示例4
原始文檔：復(fù)仇者聯(lián)盟鋼鐵俠美國隊(duì)長'
用戶A：復(fù)仇者聯(lián)盟
用戶B：復(fù)仇者聯(lián)盟美國隊(duì)長
對應(yīng)代碼實(shí)現(xiàn)：
const str = '復(fù)仇者聯(lián)盟鋼鐵俠美國隊(duì)長';
const operation0 = new ot.TextOperation().retain(5).delete('鋼鐵俠美國隊(duì)長');
const operation1 = new ot.TextOperation().retain(5).delete('鋼鐵俠').retain(4);
const op = ot.TextOperation.transform(operation0, operation1);
console.log('transform后op操作：', op[0].toString(), ' | ', op[1].toString());
//transform后op操作：retain 5, delete 4 | retain 5
console.log('transform后操作后的字符串：', op[0].apply(operation1.apply(str)), ' | ', op[1].apply(operation0.apply(str)));
// transform后操作后的字符串： 復(fù)仇者聯(lián)盟 | 復(fù)仇者聯(lián)盟
最終結(jié)果是“復(fù)仇者聯(lián)盟”；
操作過程：
|
循環(huán)次數(shù) |
op1 |
op2 |
operation1prime |
operation2prime |
|
1 |
5 |
5 |
retain(5) |
retain(5) |
|
2 |
-7 |
-3 |
- |
- |
|
3 |
-4 |
4 |
delete(4) |
- |
ot.js中transform的源碼如下：
TextOperation.transform = function (operation1, operation2) {
// ...
var operation1prime = new TextOperation();
var operation2prime = new TextOperation();
var ops1 = operation1.ops, ops2 = operation2.ops;
var i1 = 0, i2 = 0;
var op1 = ops1[i1++], op2 = ops2[i2++];
while (true) {
//...
// 對應(yīng)示例1第一次循環(huán)的操作邏輯
if (isInsert(op1)) {
operation1prime.insert(op1);
operation2prime.retain(op1.length);
op1 = ops1[i1++];
continue;
}
// 對應(yīng)示例1第二次循環(huán)的操作邏輯
if (isInsert(op2)) {
operation1prime.retain(op2.length);
operation2prime.insert(op2);
op2 = ops2[i2++];
continue;
}
// ...
var minl;
// 對應(yīng)示例2循環(huán)
if (isRetain(op1) && isRetain(op2)) {
if (op1 > op2) {
minl = op2;
op1 = op1 - op2;
op2 = ops2[i2++];
// 對應(yīng)示例2第三次循環(huán)的操作邏輯
} else if (op1 === op2) {
minl = op2;
op1 = ops1[i1++];
op2 = ops2[i2++];
// 對應(yīng)示例2的第一次循環(huán)操作邏輯
} else {
minl = op1;
op2 = op2 - op1;
op1 = ops1[i1++];
}
operation1prime.retain(minl);
operation2prime.retain(minl);
// 對應(yīng)示例4的第二次循環(huán)
} else if (isDelete(op1) && isDelete(op2)) {
if (-op1 > -op2) {
op1 = op1 - op2;
op2 = ops2[i2++];
} else if (op1 === op2) {
op1 = ops1[i1++];
op2 = ops2[i2++];
} else {
op2 = op2 - op1;
op1 = ops1[i1++];
}
// 示例3的第二次循環(huán)
} else if (isDelete(op1) && isRetain(op2)) {
if (-op1 > op2) {
minl = op2;
op1 = op1 + op2;
op2 = ops2[i2++];
} else if (-op1 === op2) {
minl = op2;
op1 = ops1[i1++];
op2 = ops2[i2++];
} else {
minl = -op1;
op2 = op2 + op1;
op1 = ops1[i1++];
}
operation1prime['delete'](minl "'delete'");
// 示例3的第三次循環(huán)
} else if (isRetain(op1) && isDelete(op2)) {
if (op1 > -op2) {
minl = -op2;
op1 = op1 + op2;
op2 = ops2[i2++];
} else if (op1 === -op2) {
minl = op1;
op1 = ops1[i1++];
op2 = ops2[i2++];
} else {
minl = op1;
op2 = op2 + op1;
op1 = ops1[i1++];
}
op
分享文章：對前端來說開發(fā)一個(gè)在線文檔需要啥技術(shù)？
當(dāng)前地址：http://www.5511xx.com/article/dhohpig.html
