This site has limited support for your browser. We recommend switching to Edge, Chrome, Safari, or Firefox.

Cart 0

No more products available for purchase

Products
Pair with
Subtotal Free
Shipping, taxes, and discount codes are calculated at checkout

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

Leave a comment

Please note, comments must be approved before they are published