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) 需要根據 op1 和 op2 的類型來選擇不同的處理方式：

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

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

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

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

OT 的著名範例 - Google Docs