多人实时协作是GraphiteDocument吸引人的特性之一。使用GraphiteDocument，你可以和同事、朋友同时写一个文档或表格，每个人的修改都会实时同步给其他人。你可以看到每个人的光标都在跳跃，每一个输入的文本。一份运营文案，一份产品头脑风暴，伴着一杯茶和咖啡，在石墨文档上诞生。美好的事物背后总有艰辛。在技??术实现上，多人实时写会产生很多冲突。以表格为例。当用户Bob在B2单元格中写入内容时，他的朋友Jeff在B列前面插入了另一列，如果这两个操作同时发送到服务器会造成冲突。在石墨文档中，我们维护了一个数据计算集群，通过一套算法计算分析来帮助用户解决冲突。如上例，最终Bob在B2单元格的写内容操作，在服务器端计算后，会转化为C2单元格的操作，发送给Jeff。为了尽可能减少多人实时书写的延迟，我们付出了很多努力，使这个算法在语义上解决书写冲突的前提下尽可能高效。统计表明，石墨文档中近90%的冲突数据计算都可以在几毫秒内完成。这个瞬时时间的贡献者之一是我们算法的一个基本原则：计算时间只与操作本身有关，与文档（或表格）原始内容的大小无关。也就是说，算法的时间复杂度大小不能与原始内容大小正相关。这个基本原则来自于我们对用户体验的直觉感知：随着用户不断地在文档或表单中书写，数据同步的速度不应该随着内容的增加而变慢，否则会影响用户的书写体验。好感度会逐渐降低，最终用户会逐渐倾向于在石墨文档上写尽可能少的内容。去年12月，GraphiteDocuments正式发布了表单公测版。上线一段时间后，表的性能问题逐渐引起了我们的注意。在表格中选择了一个区域并设置了表格属性（如对齐方式、字体大小等）后，程序会为该区域中的每个单元格创建一个数据对象来记录这些数据。如果选择范围大，数据对象会很多，影响网络传输和算法计算的速度。为了解决这个问题，我们决定引入Range的概念，通过一个范围矩形来表示这些相邻的具有相同属性的单元格。如果B2-C4单元格设置了右对齐文本格式，则前面的表达方式为：{B2:{attributes:{align:'right'}},B3:{attributes:{align:'right'}},B4：{属性：{对齐：'右'}}，C2：{属性：{对齐：'右'}}，C3：{属性：{对齐：'右'}}，C4：{属性：{对齐：'right'}}}并用Range:{RANGE:{start:'B2',end:'C4',attributes:{align:'right'}}}表示，可以看出用Range来表示内容该表可以使数据的存储更加精简，不仅减少了网络带宽开销，还相应地提高了计算性能。确定目标后，将问题简化为“寻找一个矩阵中最大的公共属性子矩阵”等清晰的算法逻辑。经验可知，寻找最大公共矩阵的目标算法的最优时间复杂度应该是O(M*N)，因为无论矩阵中哪个元素缺失，都不能保证找到的矩阵是最好的解决方案。另一方面，非常接近这个问题的经典算法LargestRectangleinHistogram的时间复杂度为O(N)。所以我们这里可以进一步简化算法，找到M-时间直方图中最大的矩形，如下图所示。以A1-D5为矩阵边界，我们从D列开始计算每一列直方图的最大矩阵，图中“上”为直方图的上方向。对于每一列，我们使用一个长度为N（如果使用Sentinel避免边界计算，则为N+1）的缓存数组来存储当前列的直方图高度，即其右侧的连续公共属性矩阵的长度。以B为例，对应的直方图为：可以看出，B列最大的矩阵是由第三行和第四行组成的面积为4的正方形。实际计算时，可以维护一个栈，存放柱子增加的高度，遍历一次y，找到最大的矩形。具体请参考相关算法资料。对每一列都做同样的计算，最后就可以得到最终的结果。但是，这个算法虽然可以在功能上解决我们的需求，但是却违背了我们上面提到的算法的基本原理——用户每次修改，即使只修改了一个cell，因为有可能得到最大的矩形被破坏，所以我们还必须重新计算整个表。为了解决这个问题，我们支持一张表有多个Range结构。在上述算法的基础上，我们定义了一个候选矩阵阈值，每当发现一个矩阵得分超过阈值，就将其加入到列表中。阈值的大小与表本身的大小有关（因为表数据结构本身缓存了自己的大小，所以不违反“基本原则”），根据我们计算的经验公式是正相关的关于生产环境中的数据。添加到列表时，由于当前矩形可能与列表中已有的矩形重叠，重叠的区域就是同时保留两个矩形时浪费的区域，我们称之为冗余区域。我们还给出了一个经验公式来根据这个冗余区域选择新添加（或现有）的候选矩形。宏观上来说，当候选矩形的面积越大，冗余区域越小，越倾向于保留两个候选矩形，否则倾向于丢弃一个候选矩形。接下来，当用户对表进行更改时，我们不再需要重新计算整个表，而只需要更新Range列表。根据修改后的位置与原Range中各个矩形的关系，可以分为以下几种情况：未与原Range中的矩形相连与原Range中的矩形相连与原Range中的矩形相连，如下图：对于第一种情况，判断用户修改的矩形是否达到候选矩阵的阈值，如果是则加入Range列表，否则以一个细胞。对于第二种情况，判断是否形成了更大的矩形（可以根据坐标进行简单的计算，是一个O(1)的操作），如果是，则更新原矩形，否则，用户以单元格修改的形式存储。对于第三种情况，用户的修改会将原来的矩形打散成几个部分。这个时候会具体分析每个打散的矩形是否达到了候选矩阵的阈值。如果是，则将其放入Range中，否则将Changetheformofrectangledumpedintoacell。可以想象，随着用户修改的增多，原来Range中的矩形会不断被打散，导致越来越接近候选矩阵的阈值；同时，多次添加小矩形最终会形成一个满足阈值的范围。矩形也是无法识别的，因为没有全局遍历。以上两种情况共同导致了Range的碎片化。为了解决碎片问题，我们在每张表中都增加了一个fragment参数，用来记录当前表的碎片程度。每次对cell进行操作和行列变换时，都会更新fragment的值（实际上，cell操作和行列变换对fragment值的影响是不同的，如果在Range中有很多矩形被命中）行-列转换，我们将更显着地增加片段值）。当碎片达到临界值时，我们将再次运行算法以压缩表数据并重置碎片。现在，我们只剩下最后一个问题了。也就是说，虽然我们对表的压缩算法进行了精细的优化，但在实际压缩中，对于一个上万个cell的大表，压缩一次大概需要十毫秒左右。而且一般来说表越大，协同的频率越高，也就是分片越容易达到临界值，这也导致压缩的频率越高，对服务器的压力就越大。当多人写同一个表单时，每个人拿到的表单数据是完整的，最终是一致的（有几十毫秒左右的延迟）。基于这样的背景，我们在工程层面进一步解决了大表的分片问题：多人同时写表时，每个用户都会内置一个分片计数器，在浏览器端计算候选矩阵定期以固定的相位差列表，然后与当前服务器版本的结果进行比较，并将比较的结果附在下次本地修改发送到服务器时。服务器会根据这个结果相应地调整表的分片值。对于大表，虽然用户操作的频率比较高，但是因为往往是用标准化格式写的表，所以碎片化程度会比较低。使用这种方法使得服务器只需要在必要的时候重新计算Range；并且由于在浏览器端使用WebWorker进行计算，用户实际的写表体验不会受到影响，但减少碎片整理的频率最终会给用户带来更好的写表体验。我们正在招聘！石墨文档技术部是一个有趣的团队。我们热衷于尝试新技术，思考新方向，探索各种方式，为我们所见的世界增添色彩。欢迎加入我们，提升身边人的文档写作体验，体验人生的下一波浪潮！[北京/武汉]GraphiteDocuments做最美的产品——寻找中国最有才华的工程师加入
