石墨文檔的雲端表格實時壓縮策略

多人實時協作是石墨文檔吸引人的一大特性之一。使用石墨文檔，你可以和同事、朋友同時編寫一篇文檔或表格，每個人的修改都會實時的同步給其他人。你可以看到每個人游標的跳動，每一個鍵入的文字。一篇篇運營文案、一份份產品頭腦風暴，伴著一杯杯茶與咖啡，就這樣在石墨文檔上誕生了。

美好的事物背後總是充滿艱辛。在技術實現上，多人實時編寫會造成許多的衝突，拿表格來說，當用戶 Bob 在 B2 單元格編寫內容的時候，他的朋友 Jeff 在 B 列的前面又插入了一列，如果兩個操作同時發給伺服器就會產生衝突。在石墨文檔，我們維護了一個數據計算集群通過一套演算法計算分析來幫助用戶解決衝突。如上面提的例子，最終 Bob 在 B2 單元格編寫內容的操作經過服務端的計算會被 transform 成在 C2 單元格的操作發給 Jeff。

為了儘可能地降低多人實時編寫的時延，我們付出了非常多的努力來使得這套演算法能夠在符合語義地解決編寫衝突的前提下儘可能地高效。數據統計表明，在石墨文檔有將近 90% 的衝突數據計算可以在幾毫秒的時間內運算完成。成就這瞬息時間的功臣之一，就是我們這套演算法的一個基本原則：運算耗時僅和操作本身相關，與文檔（或表格）原始內容大小無關，換句話來講，就是演算法的時間複雜度不能和原始內容大小正相關。

這個基本原則來源於我們對用戶體驗的直覺感知：隨著用戶在一篇文檔或表格中不斷地編寫，數據同步的速度不應該隨著內容的增多而不斷變慢，否則使用者對寫作體驗的好感會逐漸降低，最終導致用戶慢慢傾向於盡量少地在石墨文檔上編寫內容。

去年 12 月，石墨文檔正式對外發布了表格公測版。在上線了一段時間後，表格的性能問題逐漸引起我們的重視。當在表格選擇一個範圍後，設置表格屬性（如對齊方式、字型大小等）後，程序會為範圍內的每個單元格創建一個數據對象來記錄這些數據。如果選擇的範圍很大，數據對象就會變得非常多，影響了網路傳輸和演算法計算的速度。

為了解決這個問題，我們決定引入 Range 的概念來將這些擁有同樣屬性的鄰近單元格通過一個範圍矩形來表示。如為 B2-C4 單元格設置了文本右對齊格式，之前的表示方法為：

{n B2: { attributes: { align: right } },n B3: { attributes: { align: right } },n B4: { attributes: { align: right } },n C2: { attributes: { align: right } },n C3: { attributes: { align: right } },n C4: { attributes: { align: right } }n}n

而通過 Range 來表示則為：

{n RANGE: {n start: B2,n end: C4,n attributes: { align: right }n }n}n

可見使用 Range 來表示表格內容能夠使數據的存儲更為精簡，這樣既降低了網路帶寬開銷，也相應地提高了計算的性能。

確定目標後，問題就被歸結為「尋找一個矩陣中的最大公共屬性子矩陣」這樣清晰的演算法邏輯了。

由經驗可知，實現尋找最大公共矩陣的目標演算法的最佳時間複雜度應該是 O(M*N)，因為無論漏掉矩陣中的哪一個元素，都無法確保找到的矩陣是最佳方案。另一方面，與這個問題非常接近的經典演算法 Largest Rectangle in Histogram，其時間複雜度為 O(N)。所以我們這裡可以進一步地將演算法歸結成尋找 M 次直方圖中的最大矩形，如下圖所示。

以 A1-D5 為矩陣邊界，我們從 D 列開始開始對每一列計算直方圖的最大矩陣，其中圖中的「upper」為直方圖的上部方向。對於每一列，我們使用一個長度為 N （如果使用 Sentinel 來避免邊界計算的話則為 N+1）的 cache 數組來存儲當前列的直方圖高度，即其右側連續公共屬性矩陣的長度。拿 B 列舉例，其對應的直方圖為：

可以看出，B 列最大的矩陣是由第三行和第四行組成的面積為 4 的方形。實際計算時可以通過維護一個堆棧來存儲遞增的直方柱高度，y遍歷一次找出最大的矩形，具體細節可以參考相關的演算法資料。對每列進行同樣的計算，我們最終可以得出最終的結果。

然而這種演算法雖然能夠在功能上解決我們的需求，但是其卻違背了我們上述提到的演算法的基本原則——每次用戶的修改，即使只更改了一個單元格，因為有可能會把得到的最大矩形破壞掉，所以我們也不得不對整個表格進行重新運算。

為了能夠解決這個問題，我們支持了一個表格存在多個 Range 的結構。在上述演算法的基礎上，我們定義了一個候選矩陣閾值，每當發現一個矩陣得分超過閾值時，就將其加入一個列表中。閾值的大小取值與表格本身的大小（因為表格數據結構本身緩存了自身的大小，所以這裡並不違反「基本原則」）相關，基於我們根據生產環境中的數據計算出的經驗公式呈正相關關係。加入列表的時候，因為當前的矩形可能和列表中已經存在的矩形重合，重合的面積就是當同時保留這兩個矩形時所浪費的面積，我們稱之為冗餘面積。我們同樣給出了一個經驗公式來根據這個冗餘面積對新加入（或已存在）的候選矩形進行取捨，宏觀來講即是當候選矩形面積越大、冗餘面積越小時就更傾向於保留兩個候選矩形，反之則傾向於捨棄一個候選矩形。

接下來，當用戶對表格做了修改時，我們不再對整個表格進行重新計算了，只需要對 Range 列表進行一些更新。根據修改位置和原先存在的 Range 中的每個矩形的關係，分為如下幾種情況：

1. 與原先 Range 中的矩形不相連

2. 與原先 Range 中的矩形相連
3. 在原先 Range 中的矩形內

如下圖所示：

對於第一種情況，則判斷用戶修改的矩形是否達到了候選矩陣閾值，如果達到了則加入 Range 列表中，否則就以單元格的形式存儲。

對於第二種情況，則判斷有沒有新形成一個更大的矩形（根據坐標進行簡單運算即可，是一個 O(1) 操作），如果有則更新原矩形，否則就以單元格形式存儲用戶的修改。

對於第三種情況，用戶的修改會將原來的矩形打散成幾個部分，這時會具體分析打散後的每個矩形是否達到候選矩陣閾值，如果達到則放入 Range 中，否則就將改矩形轉存成單元格的形式。

可想而知，隨著用戶修改的增多，原有 Range 中的矩形會不斷地被打散，導致越來越趨近於候選矩陣閾值；同時多次增加小的矩形即使最終組成了符合閾值的矩形，也因為沒有全局遍歷導致無法識別。以上兩種情況共同導致了 Range 的碎片化。

針對碎片化的問題，我們為每個表格增加了 fragment 參數記錄了當前表格的碎片化程度。每次有針對單元格的操作和行列變換時，就會更新 fragment 的值（實際上，單元格操作和行列變換對 fragment 值的影響並不相同，行列變換時如果命中 Range 中的很多矩形，我們會將 fragment 值進行更大幅度的提升）。當 fragment 達到臨界值時，我們會重新跑一次演算法來對表格數據進行一次全盤壓縮，並重置 fragment。

現在，我們只剩最後一個問題了。那就是儘管我們對表格壓縮演算法做了精細的優化，實際壓縮起來，面對有幾萬個單元格的大表格來說，壓縮一次也要消耗十幾毫秒左右。而且一般來說，越大的表格，其協作頻率越高，即 fragment 越容易達到臨界值，也導致了壓縮的頻率會更高，從而對伺服器的壓力也更大。

當多個人編寫同一份表格時，每個人拿到的表格數據都是完整且最終一致（約幾十毫秒的時延）的。根據這個背景，我們在工程層面對大表格的碎片問題進行了進一步地解決：多個人同時編寫表格時，每一個用戶都會內置一個碎片計數器並以固定的相位差來定時在瀏覽器端計算候選矩陣列表，然後和當前伺服器版本的結果比較，並在下次向伺服器發送本地修改時附帶比較的結果。伺服器端會根據這個結果相應地調整表格的 fragment 值。對於大表格而言，用戶操作的頻率雖然會相對更高，但是因為往往都是在已經規範好格式的表格中進行編寫的，所以導致的碎片程度反而會比較低。使用這種方法使得伺服器只需要在必要的時候才重新計算 Range；並且由於在瀏覽器端使用了 Web Worker 進行計算，用戶實際的表格編寫體驗並不會受到影響，反而降低碎片整理頻率最終能給用戶帶來更好的編寫體驗。

我們正在招聘！

石墨文檔技術部是一個有趣的團隊，我們熱衷於嘗試新技術，思考新方向，探索一切可以為目之可及的世界增添色彩的方法。歡迎加入我們來一起改進身邊人的文檔編寫體驗，經歷人生中的下一場波瀾！

[北京/武漢] 石墨文檔 做最美產品 - 尋找中國最有才華的工程師加入

推薦閱讀：