1 簡介 谷歌文檔是一種協作文檔編輯服務。 協作文檔編輯服務可以通過兩種方式設計: 設計為C/S架構的集中式設施,為所有用戶提供文檔編輯服務 使用點對點技術設計,以便在單個文檔上協作 大多數商業解決方案側重於客戶端服務體繫結構,以實現更精細的控制。因此,我們將關註使用客戶端服務體繫結構設計服務。讓我 ...
1 簡介
谷歌文檔是一種協作文檔編輯服務。
協作文檔編輯服務可以通過兩種方式設計:
- 設計為C/S架構的集中式設施,為所有用戶提供文檔編輯服務
- 使用點對點技術設計,以便在單個文檔上協作
大多數商業解決方案側重於客戶端服務體繫結構,以實現更精細的控制。因此,我們將關註使用客戶端服務體繫結構設計服務。讓我們看看在這一章節中我們將如何進展。
2 需求
2.1 功能性
文檔協作
多用戶應該能夠同時編輯文檔。此外,大量用戶應該能夠查看文檔。
衝突解決
系統應該將一個用戶做的編輯推送給所有其他協作者。如果他們正在編輯文檔的同一部分,系統還應解析用戶之間的衝突。
建議
用戶應該能夠獲得有關在文檔中完成常用單詞、短語和關鍵詞的建議,以及有關修複語法錯誤的建議。
查看計數
文檔的編輯應能夠看到該文檔的查看計數。
歷史
用戶應該能夠查看文檔上的協作歷史。
2.2 非功能性
延遲
不同的用戶可以連接起來協作同一份文檔。為來自不同區域的用戶維護低延遲是具有挑戰性的。
一致性
系統應能夠解析用戶併發編輯文檔時之間的衝突,從而實現文檔的一致視圖。與此同時,不同區域的用戶應看到文檔的更新狀態。對於連接到同一區域和不同區域的用戶來說,保持一致性都是重要的。
可用性
該服務應該一直可用,並展示出對故障的魯棒性。
可擴展性
大量用戶應該能夠同時使用該服務。他們可以查看相同的文檔,也可以創建新文檔。
3 組件
3.1 數據存儲
-
關係資料庫 —— 用於保存用戶信息和文檔相關信息以施加特許可權制
-
NOSQL —— 用於存儲用戶評論以獲得更快的訪問速度
-
時間序列 —— 用於保存文檔的編輯歷史記錄
-
Blob 存儲 —— 用於存儲文檔中的視頻和圖像
-
緩存 —— 分散式緩存,如 Redis 和 CDN,為最終用戶提供良好的性能。使用 Redis存儲不同的數據結構,包括用戶會話、類型預期服務的功能、頻繁訪問的文檔。CDN存儲頻繁訪問的文檔和重量級對象如圖像和視頻。
處理隊列
針對每次微小字元更改使用 HTTP 調用是低效的。因此使用 WebSockets 減少開銷,並通過不同用戶實時觀察文檔的更改。
其他組件
其他組件包括會話伺服器,維護用戶的會話信息。通過會話伺服器管理文檔訪問許可權。本質上,還將有配置、監控、發佈-訂閱和日誌記錄服務來處理監控任務,如在伺服器失敗時監控和選舉領導者,排隊用戶通知等任務,以及記錄調試信息。
圖 1.0: 協作文檔編輯服務的詳細設計:
4 工作流程
4.1 協作編輯和衝突解決
每個請求都會轉發到操作隊列。這是解析同一文檔的不同協作者之間衝突的地方。如果沒有衝突,則通過會話伺服器將數據批量存儲在時間序列資料庫中。像視頻和圖像這樣的數據會被壓縮以優化存儲,而字元會被立即處理。
歷史:藉助時間序列資料庫,可以恢覆文檔的不同版本。可以使用 DIFF 操作來比較版本並標識差異以恢復同一文檔的舊版本。
4.2 非同步操作
通知、電子郵件、查看次數和評論都是可以通過像 Kafka 這樣的發佈-訂閱組件排隊的非同步操作。API 網關生成這些請求並將它們轉發到發佈-訂閱模塊。
4.3 建議
建議以類型提前服務(typeahead service)的形式出現,該服務提供通常使用的單詞和短語的自動完成功能。類型提前服務還可以從文檔中提取屬性和關鍵詞並向用戶提供建議。由於單詞數量可能很高,我們將為此目的使用 NoSQL 資料庫。此外,最常用的單詞和短語將存儲在像 Redis 這樣的緩存系統中。
導入和導出文檔
應用程式伺服器執行許多重要任務,包括導入和導出文檔。應用程式伺服器還將文檔從一種格式轉換為另一種格式。例如,.doc 或 .docx 文檔可以轉換為 .pdf 或反之亦然。應用程式伺服器也負責為類型預期服務提取特征。
5 詳細設計
5.1 文檔編輯器
文檔由以特定順序排列的字元組成。每個字元都有一個值和一個位置索引。字元可以是字母、數字、回車()或空格。索引表示字元在有序字元列表中的位置。
文本或文檔編輯器的作用是在文檔中的字元上執行插入()、刪除()、編輯()等操作。下麵是文檔的描繪以及編輯器將如何執行這些操作。
文檔編輯器如何執行各種操作
5.2 併發性
不同用戶對同一文檔的協作可能導致併發問題。若多個用戶編輯文檔的同一部分,可能出現衝突。由於用戶在本地有文檔的副本,伺服器上的最終文檔狀態可能與用戶在他們端看到的不同。在伺服器推送更新版本後,用戶會發現意外結果。
① 在同一位置索引處添加字元
兩個用戶修改同一字元可能導致併發問題:
② 刪除同一字元
刪除同一字元,可能導致意外更改:
第二個例子表明,不同用戶應用相同的操作不會是冪等的。因此,在多個協作者同時編輯文檔同一部分時,需衝突解決。
協作編輯中併發問題的解決方案應遵循規則:
- 交換律:應用操作的順序不應影響最終結果
- 冪等性:重覆的相似操作只應用一次
6 衝突解決技術
6.1 操作轉換(OT)
廣泛用於協作編輯中的衝突解決的技術,一種【無鎖】、【非阻塞】的衝突解決方法。若協作者之間的操作衝突,OT會解析衝突並將正確的匯聚狀態推給最終用戶。因此,OT為用戶提供一致性。
OT 使用位置索引方法執行操作來解析上面討論的那些衝突。通過保持交換律、冪等性來解決上述問題。
OT示例:
基於 OT 的協作編輯器在滿足以下兩個屬性時一致:
- 因果關係保持:如果操作 a 發生在操作 b 前,那先執行操作 a,然後執行操作 b
- 收斂:不同客戶端上的所有文檔副本最終相同
上述屬性是 CC 一致性模型的一部分,CC 一致性模型是協作編輯中一致性維護的模型。
OT的缺點
對字元的每個操作都可能需要更改位置索引。這意味著操作之間存在順序依賴關係。它的開發和實現具有挑戰性。
OT是一組複雜演算法,其正確實現在實際應用中已被證明有挑戰性。Google Wave 團隊花兩年時間實現OT。
6.2 無衝突複製數據類型 (CRDT)
是為了改進 OT。CRDT 具有:
- 複雜的數據結構
- 但簡化的演算法
CRDT 通過為每個字元分配兩個關鍵屬性來滿足交換律和冪等性:
- 為每個字元賦予全局唯一標識
- 全局訂購每個字元
每個操作現在都有一個更新後的數據結構:CRDT 簡化的數據結構
SiteID 唯一標識請求操作的用戶站點,帶有一個值和一個 PositionalIndex。PositionalIndex值可以是分數:
- 某些操作不會改變其他字元的 PositionalIndex
- 避免不同用戶操作之間的順序依賴性
示例描繪來自站點 ID 123e4567-e89b-12d3 的用戶在 PositionalIndex 為 1.5 的位置插入一個值為 A 的字元。儘管添加了新字元,但使用小數索引保留了現有字元的位置索引。因此,避免了操作之間的順序依賴性。如下所示,在 O 和 T 之間插入()並沒有影響 T 的位置。
防止操作之間的順序依賴性:
CRDT 確保用戶之間的強一致性。即使一些用戶處於離線狀態,當他們重新聯機時,最終用戶處的本地副本也將匯聚。
儘管眾所周知的線上編輯平臺如 Google 文檔、Etherpad 和 Firepad 使用 OT,但 CRDT 使協作文檔編輯中的併發和一致性變得容易。事實上,使用 CRDT,可以實現無伺服器點對點協作文檔編輯服務。
註意
OT 和 CRDT 是協作編輯中衝突解決的良好解決方案,但我們使用 WebSockets 可以突出顯示協作者的游標。其他用戶將預期協作者的下一個操作的位置,並自然避免衝突。
7 評估
一致性
操作轉換(OT)和衝突不定決議數據類型(CRDT)在文檔中實現衝突解決的強一致性。
時間序列資料庫能保留事件的順序。一旦 OT 或 CRDT 解析了任何衝突,最終結果就保存在資料庫。這有助我們在單個操作方面實現一致性。
在IDC內的不同伺服器之間保持文檔狀態的一致性。要在同一IDC內同時複製更新後的文檔狀態,可使用 Gossip 協議這樣的點對點協議。這不僅提高一致性,還會提高可用性。
可用性
我們的設計通過使用副本以及使用監控服務監控主副本伺服器來確保可用性。操作隊列和數據存儲等關鍵組件在內部管理自己的複製。
由於使用 WebSockets,WebSocket 伺服器可將用戶連接到會話維護伺服器,這些伺服器將確定用戶是否正在主動查看或協作文檔。
因此,保留多個 WebSocket 伺服器將增加設計的可用性。最後,採用緩存服務和 CDN 改進可用性。
可擴展性
由於使用微服務,若操作隊列的請求數量超過其容量,可輕鬆單獨擴展每個組件。可使用多個操作隊列。此時,每個操作隊列將負責單個文檔。可將不同用戶請求的與單個文檔相關的操作轉發到特定隊列。生成的隊列數量將等於活動文檔的數量。因此可實現水平擴展性。
參考:
本文由博客一文多發平臺 OpenWrite 發佈!