关键词：
多人实时协作是石墨文档吸引人的一大特性之一。使用石墨文档，你可以和同事、朋友同时编写一篇文档或表格，每个人的修改都会实时的同步给其他人。你可以看到每个人光标的跳动，每一个键入的文字。一篇篇运营文案、一份份产品头脑风暴，伴着一杯杯茶与咖啡，就这样在石墨文档上诞生了。
美好的事物背后总是充满艰辛。在技术实现上，多人实时编写会造成许多的冲突，拿表格来说，当用户 Bob 在 B2 单元格编写内容的时候，他的朋友 Jeff 在 B 列的前面又插入了一列，如果两个操作同时发给服务器就会产生冲突。在石墨文档，我们维护了一个数据计算集群通过一套算法计算分析来帮助用户解决冲突。如上面提的例子，最终 Bob 在 B2 单元格编写内容的操作经过服务端的计算会被 transform 成在 C2 单元格的操作发给 Jeff。
为了尽可能地降低多人实时编写的时延，我们付出了非常多的努力来使得这套算法能够在符合语义地解决编写冲突的前提下尽可能地高效。数据统计表明，在石墨文档有将近 90% 的冲突数据计算可以在几毫秒的时间内运算完成。成就这瞬息时间的功臣之一，就是我们这套算法的一个基本原则：运算耗时仅和操作本身相关，与文档（或表格）原始内容大小无关，换句话来讲，就是算法的时间复杂度不能和原始内容大小正相关。
这个基本原则来源于我们对用户体验的直觉感知：随着用户在一篇文档或表格中不断地编写，数据同步的速度不应该随着内容的增多而不断变慢，否则使用者对写作体验的好感会逐渐降低，最终导致用户慢慢倾向于尽量少地在石墨文档上编写内容。
去年 12 月，石墨文档正式对外发布了表格公测版。在上线了一段时间后，表格的性能问题逐渐引起我们的重视。当在表格选择一个范围后，设置表格属性（如对齐方式、字号等）后，程序会为范围内的每个单元格创建一个数据对象来记录这些数据。如果选择的范围很大，数据对象就会变得非常多，影响了网络传输和算法计算的速度。
为了解决这个问题，我们决定引入 Range 的概念来将这些拥有同样属性的邻近单元格通过一个范围矩形来表示。如为 B2-C4 单元格设置了文本右对齐格式，之前的表示方法为：
{
B2: { attributes: { align: ‘right‘ } },
B3: { attributes: { align: ‘right‘ } },
B4: { attributes: { align: ‘right‘ } },
C2: { attributes: { align: ‘right‘ } },
C3: { attributes: { align: ‘right‘ } },
C4: { attributes: { align: ‘right‘ } }}
而通过 Range 来表示则为：
{
RANGE: {
start: ‘B2‘,
end: ‘C4‘,
attributes: { align: ‘right‘ }
}}
可见使用 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 中的每个矩形的关系，分为如下几种情况：
与原先 Range 中的矩形不相连
与原先 Range 中的矩形相连
在原先 Range 中的矩形内
如下图所示：
对于第一种情况，则判断用户修改的矩形是否达到了候选矩阵阈值，如果达到了则加入 Range 列表中，否则就以单元格的形式存储。
对于第二种情况，则判断有没有新形成一个更大的矩形（根据坐标进行简单运算即可，是一个 O(1) 操作），如果有则更新原矩形，否则就以单元格形式存储用户的修改。
对于第三种情况，用户的修改会将原来的矩形打散成几个部分，这时会具体分析打散后的每个矩形是否达到候选矩阵阈值，如果达到则放入 Range 中，否则就将改矩形转存成单元格的形式。
可想而知，随着用户修改的增多，原有 Range 中的矩形会不断地被打散，导致越来越趋近于候选矩阵阈值；同时多次增加小的矩形即使最终组成了符合阈值的矩形，也因为没有全局遍历导致无法识别。以上两种情况共同导致了 Range 的碎片化。
针对碎片化的问题，我们为每个表格增加了 fragment 参数记录了当前表格的碎片化程度。每次有针对单元格的操作和行列变换时，就会更新 fragment 的值（实际上，单元格操作和行列变换对 fragment 值的影响并不相同，行列变换时如果命中 Range 中的很多矩形，我们会将 fragment 值进行更大幅度的提升）。当 fragment 达到临界值时，我们会重新跑一次算法来对表格数据进行一次全盘压缩，并重置 fragment。
现在，我们只剩最后一个问题了。那就是尽管我们对表格压缩算法做了精细的优化，实际压缩起来，面对有几万个单元格的大表格来说，压缩一次也要消耗十几毫秒左右。而且一般来说，越大的表格，其协作频率越高，即 fragment 越容易达到临界值，也导致了压缩的频率会更高，从而对服务器的压力也更大。
当多个人编写同一份表格时，每个人拿到的表格数据都是完整且最终一致（约几十毫秒的时延）的。根据这个背景，我们在工程层面对大表格的碎片问题进行了进一步地解决：多个人同时编写表格时，每一个用户都会内置一个碎片计数器并以固定的相位差来定时在浏览器端计算候选矩阵列表，然后和当前服务器版本的结果比较，并在下次向服务器发送本地修改时附带比较的结果。服务器端会根据这个结果相应地调整表格的 fragment 值。对于大表格而言，用户操作的频率虽然会相对更高，但是因为往往都是在已经规范好格式的表格中进行编写的，所以导致的碎片程度反而会比较低。使用这种方法使得服务器只需要在必要的时候才重新计算 Range；并且由于在浏览器端使用了 Web Worker 进行计算，用户实际的表格编写体验并不会受到影响，反而降低碎片整理频率最终能给用户带来更好的编写体验。
我们正在招聘！
石墨文档技术部是一个有趣的团队，我们热衷于尝试新技术，思考新方向，探索一切可以为目之可及的世界增添色彩的方法。欢迎加入我们来一起改进身边人的文档编写体验，经历人生中的下一场波澜！
[北京/武汉] 石墨文档 做最美产品 - 寻找中国最有才华的工程师加入
本文出自 “12395360” 博客，请务必保留此出处http://12405360.blog.51cto.com/12395360/1882184
石墨文档入选「2021数字经济产业top100榜单」
...直播和评委评议等层层筛选后，决出最终上榜名单。石墨文档入选产业新锐TOP50。石墨文档(https://shimo.im)创立于2014年，是中国首款支持多人实时协同的云端Office办公软件。截止到2021年11月，石墨已服务85万家企业客户&... 查看详情
微服务过时了-serverless了解一下|技术专题第七期征文
一、2020年的服务端革命你知道吗我们天天使用的石墨文档、微博、芒果TV都在全部或部分使用Serverless技术。其实知乎也是用的leancloud。技术的发展使我们有可能不花一分钱、不雇佣一个只强大的后端团队也可以建立一个媲美大... 查看详情
在线word文档编辑都有哪些
1、石墨文档石墨文档是中国一款支持云端实时协作的企业办公服务软件（功能类比于GoogleDocs、Quip），可以实现多人同时在同一文档及表格上进行编辑和实时讨论，同步响应速度达到毫秒级。2、腾讯文档腾讯文档是一款支持随... 查看详情
怎么多人在线编辑excel表格？
...可以节省繁重的表格汇总工作。将设定好的表格模板导入石墨文档，打开后点击分享，就可以直接复制粘贴给需要填写个人信息的师生们，此外也可通过分享二维码把多人协作表格分享给填写人。当对某单元格的内容产生疑问时... 查看详情
自制桌面小工具——石墨文档自动索引
现在线上协作大多需要使用诸如石墨文档或云协作这样的协同工具。进行社群运营工作时，由于文档太多，各人建立文件夹的方式又难以统一，因而产生文件多而乱的问题。为了快速地找到文件，除了使用石墨本身自带的搜索功... 查看详情
我一直在维护的石墨文档开源了
...。这篇文章，让我来介绍一下自己一直在维护的一个石墨文档。 没有错，正如大家看到的一样，我从去年2月23日建立的石墨文档，到现在从外网访问的次数已过万。 这个数量不是很大，... 查看详情
zine和石墨文档竞品分析
...笔记类的工具产品在市场上很多：印象笔记、为知笔记、石墨文档、Zine等等。 这些产品基本上已经覆盖了笔记这一类工具所衍生出来的各种需求 查看详情
腾讯文档表格里为啥没有粘贴功能?
腾讯文档表格里是有粘贴功能的，该功能在“编辑”菜单下，具体使用方法如下：所需材料：任意一款能够打开腾讯文档的浏览器。一、打开腾讯文档内的表格文档，选中需要复制的单元格。二、点击工具栏内的“编辑”菜单，... 查看详情
如何将word文档和excel表格打包成压缩包
...件一般推荐winrar或winzip或者把WORD跟EXCEL一起放进一个PDF的文档：下载安装AdobeAcrobat。打开AdobeAcrobat软件，点击文件---创建PDF---从多个文件。根据提示浏览添加word，excel文件，创建PDF保存即可。4、想压缩就压缩一个文件就好，或... 查看详情
查看wps云端备份文档的方法步骤
参考技术A 我们都知道可以在wps中将文档备份到云端里去，那么，我们如何查看备份到云端中的文档呢?下面就让我告诉你查看wps云端备份文档的方法，希望对大家有所帮助。 查看wps云端备份文档的方法 点击特色功能&... 查看详情
石墨文档是如何通过websocket实现百万长连接的？(代码片段)
标准定义的WebSocket规范。随着石墨文档的发展，现在日连接峰值达到了百万量级，日益增长的用户连接数和停止更新的架构设计导致了内存和CPU使用量急剧增长，因此我们考虑对网关进行重构，以适应发展需求。基于Socket.IO进行... 查看详情
大家都喜欢用啥思维导图工具呢？
...格】在线excel表格超级表格（表格）：超级表格:多人协作云端表格,在线表格,在线表单,在线Excel,在线Office,手机办公班牛（表格）：班牛_移动电商企业协同办公软件OA参考技术A思维导图工具我们用的是 Leangoo，它不但是免费的... 查看详情
在线协作文档综合评测：notionflowuswolai飞书语雀微软office谷歌文档金山文档腾讯文档石墨文档dropboxpaper坚果云文档百度网盘在线文档
...书、语雀、微软Office、谷歌文档、金山文档、腾讯文档、石墨文档、DropboxPaper、坚果云文档、百度网盘在线文档如今，在线协作文档已经成为效率办公的必备产品。然而，面临各种各样的在线文档产品，应该如何选择呢？事实上... 查看详情
如何清理石墨耳语的数据？
】如何清理石墨耳语的数据？【英文标题】：Howtocleanupthegraphitewhisper\'sdata?【发布时间】：2012-03-2403:15:29【问题描述】：我想删除石墨的存储耳语数据，但石墨文档中没有任何内容。我做的一种方法是手动删除/opt/graphite...../whispe... 查看详情
“云”端的语雀：用javascript全栈打造商业级应用
...管理，打造轻松流畅的工作协同，它提供各种格式的在线文档（富文本、表格、设计稿等）编辑能力，支持实时在线多人协同编辑，数据云端保存不丢失。而语雀与其他文档工具最大的不同是，它通过知识库来对文档进行组织，... 查看详情
druid（准）实时分析统计数据库——列存储+高效压缩
...具有较好的稳定性（HighlyAvailable）。其相对比较轻量级，文档非常完善，也比较容易上手。Druidvs其他系统DruidvsImpala/SharkDruid和Impala、Shark的比较基本上可以归结为需要设计什么样的系统Druid被设计用于：一直在线的服务获取实时... 查看详情
解压缩并将内容推送到表格视图中
...2010-12-1708:49:18【问题描述】：我有一个tableView列出了我的文档目录的内容。我有一些zip文件。如果我在tableView中触摸一个文件，则相应的zip文件将解压缩到一个临时目录中。问题是如何导航我在tableView中提取的内容。如果假设，... 查看详情
Django 会话不是使用 JWT 和石墨烯生成的
】Django会话不是使用JWT和石墨烯生成的【英文标题】：DjangosessionisnotgeneratedusingJWTandgraphene【发布时间】：2018-09-2621:36:52【问题描述】：我是使用django学习石墨烯的新手，正如文档所说，我有这个课程：importgraphql_jwtclassMutations(gra... 查看详情