Notion 以及 Google Docs 背後的秘密 - Operational Transformation (OT) 多用戶實時協作系統

Operational Transformation (OT) 是一種用於多用戶實時協作系統的算法。它允許多個用戶同時修改一個共享的數據對象,並能夠解決因此產生的任何衝突。OT 最初是為分散式版本控制系統(如 Git)和實時協作編輯器(如 Google Docs)所設計的。

OT 和 Git 的關鍵區別在於他們如何處理衝突。在 Git 中,當兩個用戶對同一個文件做出不同的變更時,Git 會產生一個衝突,需要手動解決。換句話說,Git 不會嘗試自動地合併這些變更。

相比之下,OT 設計的目的就是能夠自動解決這種衝突。當兩個操作同時修改同一個對象時,OT 可以將這兩個操作變換(transform)成新的操作,這些新的操作可以在任何順序下應用,並且能夠產生一致的結果。這意味著 OT 可以自動合併同時發生的變更,而不需要用戶手動解決衝突。

具體來說,OT 算法的實現通常包括以下三個要素:

  1. 操作(Operations):這些是可以對數據對象進行修改的動作。例如,在文本文檔中,一個操作可能是在某個位置插入或刪除一個字符。

  2. 變換函數(Transformation Functions):當兩個操作同時發生時,變換函數可以將這兩個操作變換成新的操作。

  3. 一致性條件(Consistency Conditions):這些是算法需要滿足的一致性條件。例如,如果兩個操作在時間上是獨立的(也就是說,它們並不知道對方的存在),那麼無論這兩個操作的應用順序如何,結果都應該是一致的。

需要注意的是,雖然 OT 可以自動解決衝突,但它並不能確保每一次的解決都符合用戶的意圖。在某些情況下,OT 的自動合併可能並不是用戶想要的結果。因此,實時協作工具通常會提

因此,實時協作工具通常會提供某種形式的手動衝突解決機制。例如,當兩位用戶在同一時間編輯同一個部分,系統可能會發出警告,讓用戶自行決定哪個版本是他們想要保留的。在一些情況下,這樣的解決方式可能比自動合併更適合,因為它讓用戶可以直接控制最終的結果。

換句話說,Operational Transformation (OT) 是一種非常強大的工具,它可以讓多個用戶同時編輯同一個對象,並且能夠自動解決大部分的衝突。然而,正如任何其他工具一樣,它並非完美無缺。在某些情況下,OT 的自動合併可能不符合用戶的意圖,並需要透過手動介入來解決衝突。不過,儘管如此,OT 依然是實時協作工具中不可或缺的一部分。

變換函數深入說明

變換函數在 Operational Transformation (OT) 中是很重要的部分。它是一種能對衝突操作進行轉化的算法,讓其能在任何順序下達到一致的結果。設計變換函數需要考慮多種因素,如操作的類型、操作的順序、操作的目標等等。因此,實際上的變換函數可能會相當複雜。

讓我們通過一個簡單的文本編輯器來說明這個概念。在這個編輯器中,我們只有兩種操作:插入字符(Insert(position, character))和刪除字符(Delete(position))。我們的變換函數 Transform(op1, op2) 需要根據 op1op2 的類型來選擇不同的處理方式:

  1. 如果 op1op2 都是插入操作,我們可以比較他們的位置來確定如何變換。如果 op1op2 之前(或者在相同的位置),那麼我們可以保持 op1 不變,並將 op2 的位置加一。否則,我們可以保持 op2 不變,並將 op1 的位置加一。

  2. 如果 op1 是插入操作,op2 是刪除操作,我們可以比較他們的位置來確定如何變換。如果 op1op2 之前,那麼我們可以保持 op1 不變,並將 op2 的位置加一。否則,我們可以保持 op2 不變,並將 op1 的位置減一。

  3. 如果 op1op2 都是刪除操作,我們可以比較他們的位置來確定如何變換。如果 op1op2 之前,那麼我們可以保持 op1 不變,並將 op2 的位置減一。否則,我們可以保持 op2 不變,並將 op1 的位置減一。

這只是一種基本的變換函數設計,實際的 OT 系統可能需要處理更複雜的情況,如多個字符的插入或刪除,或者其他類型的操作。

OT 的著名範例 - Google Docs

當多個用戶同時編輯一個 Google Docs 文件時,每個用戶的每次編輯都會被轉化為一個或多個操作。當這些操作在服務器上被收集並排序後,Google Docs 會使用一種變換函數來解決任何可能的衝突。

舉例來說,假設兩個用戶同時對同一個文件進行編輯:

  1. 用戶A在文本的第五個位置插入字母 "A"(操作為 Insert(5, 'A')
  2. 同時,用戶B在文本的第五個位置插入字母 "B"(操作為 Insert(5, 'B')

如果沒有使用變換函數,那麼根據操作的順序,結果可能是 "A...B" 或者 "B...A",這會產生不一致。但如果使用了上述的變換函數,那麼無論操作的順序如何,結果都會是 "AB..."。這樣就確保了所有用戶看到的文件都是一致的。

實際上,Google Docs 的 OT 系統比這更複雜。他們需要處理的操作不只包括插入和刪除字符,還包括格式化文本、插入圖片等等。此外,他們的變換函數也需要考慮更多的因素,如網路延遲、服務器負載等等。但基本的原理是一樣的:透過變換函數將衝突的操作變換為一致的操作。

推薦閱讀

怎麼避免品牌的郵件、Marketing Email 進入垃圾郵件夾?
怎麼避免品牌的郵件、Marketing Email 進入垃圾郵件夾?
掌握技巧,才有機會做出成果   一直以來,電子郵件營銷是很多企業或者個人推廣業務的重要手段,而隨著各電子郵箱服務商和服務器提供商對垃圾郵件的過濾機制越來越嚴格,營銷人員的工作也越來越具有挑戰性。 為了避免我們的郵件進入垃圾箱,...
繼續閱讀
Shopify 讓商家可以接受比特幣支付,這能為品牌商帶來什麼好處?
Shopify 讓商家可以接受比特幣支付,這能為品牌商帶來什麼好處?
比特幣是什麼? 比特幣(Bitcoin)是最早推出的虛擬貨幣(也稱加密貨幣),也是目前市值排名第一的虛擬貨幣。 這種虛擬貨幣不由中央銀行、政府機構所發行,只能使用電子(網路)方式進行交易、轉移、儲存,它只是一串代碼,並沒有實體,比特幣...
繼續閱讀
2023 年用 Shopify 建立一間網路商店/官網要多少錢?隱藏成本?開店費用總整理
2023 年用 Shopify 建立一間網路商店/官網要多少錢?隱藏成本?開店費用總整理
今年很多台灣電商品牌想以 Shopify 建站,Shopify 眾所周知的特色就是在設計及開發上有高度的自由、擴展性強,有成千上萬應用程式和佈景主題可以一鍵安裝到商店。但就像堆積木一樣,安裝越多功能就需要越高的費用,那 Shopify...
繼續閱讀

發表留言

請注意,留言須先通過審核才會發佈