↖  想象力,工程方法以及取舍..


想象力,工程方法以及取舍

2021-06-23 , 2794 , 101 , 120

听音频 🔊 . 看视频 🎦

[编按: 转载于 腾讯微信/ 陈小天 程序人生, 2021-06-21.]


小时候看《少儿科学画报》,深深烙在我脑海中的一个故事是「不可能先生」。史蒂文森在矿山上做了很多年蒸汽机工程师,对马车拉煤的低效深有感触,于是萌生了把蒸汽机运用在交通运输上的想法。

但这个想法遭遇到了无数不可能先生的冷嘲热讽,比如「蒸汽机车不可能比马车更快」,「蒸汽机车不安全」等。他做了很多实验,遭遇了无数次失败。但最终,他通过不懈努力证明了「用火车拉煤」是一件更安全更高效成本更低廉的事情。

我们人类之所以成为世间万物的主宰,极其重要的一个能力是想象力 —— 不满足于现状,憧憬和探索未知世界的想象力。

在我们思考一个问题的时候,我们运用想象力去创造自己希望去实现的某个事物的形象,让其逐渐丰满起来,接着,不断地把注意力集中在这个思想或画面上,赋予其更多的细节,将这些细节一点点组织和实现出来,直到它成为客观的现实。在这个过程中,敢于突破桎梏,大胆假设,是第一步,之后才谈得上小心求证。


史蒂文森先生所处的时代还是民智未开的第一次工业革命早期,所以一个个膀大腰圆的「不可能先生」—— 他们往往是现有运输行业的既得利益者以及工业革命的反对者 —— 站出来冷嘲热讽及旗帜鲜明地反对还有情可原。

但我们现在所处的信息时代,知识已经普惠到大部分的阶层,如果考虑到我的读者群以程序员(这个群体应该够得上高级知识分子了吧)为主,却还有如此之多的「不可能先生」,却让我始料未及。

上一篇文章《客户端软件的轮回》,我算是即兴之作,给大家提供一个新的视角看待事物,却收到了大量未经思考就脱口而出的「不可能」。

大部分语气尚可,小部分可能受了微博和知乎社区氛围的感染,「不可能」得阴阳怪气。对于这些不假思索脱口而出的评论,我没有菜头叔那样好的体力去争辩,所以直接删除了事。

当然,也怪我写文章太糙,仅仅打开了一道门,却没有描绘门后面有啥:


所以这篇文章我就继续挥着想象力的翅膀,看看如何做一个数据放在客户端的,注重离线体验的如 Notion,ClickUp 那样的生产力工具。

Single Source of Truth

上篇文章被喷得最多的是如何保证 single source of truth(以下简称 SST)。我觉得软件开发这个领域,适度的行话方便交流,但不要滥用,并且在使用前确保自己对背后的概念有足够的了解。在谈 SST 之前,我们先要明确我们把什么作为 SST。比如,对 clickUp 而言,SST 是一个个 list 么?是一个个 task 么?还是一篇篇 doc?


都不是。这些都是状态(state)。在分布式系统里,能被正确用作 SST 的只有事件(event,或者 operation)。从整个应用的角度,主流的思想是把广义的数据库(RDBMS,DDBMS,kv store,object store)作为 SST,这无可厚非,但我们不能因此推断出数据库就等同于 SST,或者得出结论没有数据库就没有 SST。

从数据库的角度看,数据库里存储的数据(状态)并不是 SST,数据库的 SST 是一个个的 op —— 你可以理解为增删改的动作 —— 它们就是一个个事件。这是最原始,也最容易在集群中复制的信息,数据库的状态可以通过这些 oplog/WAL 按顺序迭加恢复出来。

在 web app 里,我们在更高的层次实现业务逻辑,因此可以把数据库里的数据(状态)作为 SST。因为我们知道,不管数据库的实现是强一致性,还是弱一致性,它们都能保证最终一致性(当更新停止时,最终所有的数据库节点都能聚合到同样的数据)。

而保证了最终一致性的数据库,就有资格被当做 SST。


当我们把数据下放到每个客户端时,每个客户端其实可以被看做所有客户端维护的数据库系统的一个节点。上图中一个个 list,就是状态。我们的目标是这些状态的最终一致性。而根据数据库的思路,SST 是事件 —— 用户对 list 的各种操作。这些事件主要有:

在 list 里添加一个新的数据项

修改一个已有的数据项

删除一个已有的数据项

移动一个已有的数据项

我们如果能在所有参与的节点中确保所有的事件都被正确扩散,那么,通过迭加这些事件,我们可以得到最终一致的状态。


从事件到状态

我们来解释一下,如何「通过迭加这些事件,得到最终一致的状态」。我相信很多人都有疑问。我们搞软件的,讲究一个工程思维。什么是工程思维,就是把一个介于靠谱和不靠谱之间的想法,将其分解,分解,再分解,直到分解成我们能理解,并且能有效实现的任务清单。而我们从小到大的数学课程,其实就在培养这种工程思维:问题太复杂,没有头绪?那我们先从简单的,基础的部分入手。


如果事件是有序的

将一个个事件叠加出大家一致的状态,「不可能先生」的头几个质疑就是:1. 网络不稳定,事件有可能丢;2. 事件到达不同客户端的顺序可能不一致。

那我们就先假设我们有办法做到不丢事件,并且保持同样的事件顺序。这样,所有的客户端的状态都可以被描述成(S 代表状态,E 代表事件,+ 代表事件叠加):



事实上,如果使用合适的网络协议,不丢事件并不难保证。保持所有客户端都看到一致的事件顺序稍微复杂一些。如果用中心化的解决方法,可以引入一个 message queue(其实变相引入了 raft 这类 CFT 共识算法),你可以参考我之前的文章《胖客户端,瘦服务器?》;

如果去中心化的解决方案,需要引入类似区块链技术使用的共识机制来确保顺序(区块链的区块,实质上是一个全局时钟,它用来提供一致的事件顺序,见:《区块链和数据库:致虚极,守静笃》)。这一块我就不展开了,大家感兴趣可以看我之前的文章。

但如果我们要求所有的客户端都看到顺序一致的事件,离线处理就会比较麻烦。这是因为我们无法保证下面的等式:

-loading- -loading--loading-




如果我们必须保证事件的顺序一致,那我们就需要做相应的处理。一种方法是事件到了服务器之后被排序,客户端需要按照服务器要求的顺序生成状态:比如排序和 a 收到的顺序一致,那么 b 就需要回滚到 Sn-2 ,再按照新的顺序迭加事件。这就意味着我们不仅仅要支持迭加的操作(+),还需要支持回滚(-):



UfqiLong

当然,读到这里,我相信「不可能先生」们会跳出来说,你这根本不 work,一旦离线,那么 a 和 b 的操作有可能冲突,你咋处理。

这是个好问题,我们先把它放在一边,因为根据我们使用 git 的经验,大部分的 Pull Request,产生冲突的场景占总体修改的比例是很小的(但也很可观)。我们知道,源代码的修改可以是非常随性的,不设边界的,但我们要解决的问题是可以约束的。

无边界的问题解决起来困难,那我们先解决有边界的问题 —— 比如对上述的对一个 list 的操作,边界就非常具体明晰,所以我们可以对症下药,解决冲突。不过,我们稍后再谈冲突的解决,毕竟,伟大领袖告诉我们:饭要一口一口的吃,地要一块一块地犁。


如果事件是无序的

以上所有的讨论都基于所有人看到的事件必须是顺序一致的。我们能不能放宽这个限制,让迭加(+)的操作满足交换律?也就是说:


这就有意思了。不过稍微思考一下,「不可能先生」就会得出结论这个想法过于离经叛道,违背因果关系:比如众所周知的「外祖母悖论」 —— 你不可能先修改一个不存在的 list item,然后再创建这个 item。

说的没错。我们不可能让任意的交换律成立,但我们可以让来自同一客户端的事件保持全局的相对顺序,而允许来自不同客户端的事件乱序。举个例子(假设目前 list 里有 5 个 task):

a 的操作:添加 task_a6,修改 task6,删除 task3。

a 看到的顺序:添加 task_a6,移动 task2,修改 task_a6,删除 task3,修改 task3,添加 task_b6

b 的操作:移动 task2 到 task5 之前,修改 task3,添加 task_b6。

b 看到的顺序:移动 task2,修改 task3,添加 task_b6,task_a6,修改 task6,删除 task3

最终,a 和 b 的状态应该都是 list 里有 task1, task4, task2, task5, task_b6, task_a6。如果嫌文字看起来逻辑关系比较绕,请看下图:



如果能够保持同一个客户端发出来的事件的顺序不变,那么整个状态就不会发生违背因果律的情况。事实上,这一点很好保证,只要应用的网络层构建在 TCP(或 QUIC)之上,就可以保证接收方收到的发送方的数据是有序的。

接下来,我们只需要使用一定的算法来确保 A 和 B 看到的消息顺序不一致(也就是满足交换律)的情况下,两者最终计算出来的状态是一致的。这就涉及到冲突的解决。

为了让上面这个例子最终达到一直的状态,我们可以设计出以下的算法(规则):

list 里所有数据都有全局唯一的 id。这里我们用 task1, task2, ...。数据的 id 中包含客户端的 id。

每个数据有一个指针,指向前一个数据,以便于我们定位其相对位置,移动数据的时候,我们需要更新这个指针来保持数据的相对位置。


id 之间是可以比较的,比如上图 A 和 B 都在 task5 之后插入了一个新的 item,我们定义 b6 > a6 的比较关系(这个无所谓,也可以 a6 > b6),这样,task_b6 的前一个数据是 task5,而 task_a6 的前一个数据 task_b6。

通过这样的算法,我们可以保证不同的消息顺序,最终算出的状态是相同的。当然这里面还有很多其它场景,但和这个场景一样,我们把最基本的几种情况定义出来,如果有冲突,那么,选择一种合理的方式让冲突得到解决即可。


冲突解决

当我们把冲突解决作为一个特定的问题来研究的时候,我们总是可以找出一个个典型的冲突场景,然后为其设置合理的解决机制。list 是 primitives 外最通用,也是相对简单的结构,我们可以先分析 list 下的各种情况,然后扩展到 map,最后再到复杂的混合结构(btw,字符串可以被看成 list)。这是把问题逐步攻克的方法。

还是拿大家熟悉的 git 来说事 —— git 采用的冲突解决方式是手工,也就是说我们在 merge 时如果发生冲突,需要靠程序员分析冲突代码,根据上下文的逻辑来解决冲突。这样的方式用于协作具有复杂逻辑的代码是必要的;但是对于像 clickUp 或者 Notion 这样的协作软件来说,就不是特别必要。我们总是可以通过一系列冲突解决的规则,来避免冲突:

插入同一个位置:根据 id 来排序

修改同一个位置的数据:暴力一些,可以采用 LWW(last write win)策略;如果这样不满足需求,那么可以把修改的数据看做一个字符串流或者字节流,也就是一个 list,用处理 list 同样的方式处理。


在这个过程中,我们要避免执行出现环的操作。如下图树结构(比如 Notion 的目录树)下,有些操作会产生环。在这个例子里,客户端 A 把 list5 移动到 list4 下,而客户端 B 把 list4 移动到 list5 下。当 A 和 B 收到对方的事件时,如果直接处理,则一定会产生下图的两种环。所以,解决冲突的算法还需要避免环的产生,使最终结果聚合到 A 或者 B 的情况。我们可以对状态进行回滚,然后对事件调整顺序(因为满足交换律,所以算法可以进行合理的调整),然后重新处理事件,使状态进入到无环的结果。如果对于下图的情况,算法最终聚合到 A 的结果,那么对客户端 B 而言,就是用户做了一个操作之后,这个操作被取消,并变成了 A 的样子。



真实世界的协作算法

幸运的是,目前已经有很多已知的算法来解决在线协作的问题。其中典型的两种算法是 OT(Operational Transformation)[2] 和 CRDT(Conflict-free Replicated Data Types)[3]。

OT

OT 是一个思路简单,但实现复杂的算法,其基本思想是,不同的节点在收到不同顺序的事件(在 OT 下是 operation)时,将后续的 OP 进行 transform,使其能够分别聚合出相同的状态,如下图:

operation-transform.webp


(图片来自 Operational Transformation算法图解 [4])

那么谁来做这个 transformation 呢?服务器。Peer1 和 peer2 在执行了自己的操作 OP1 和 OP2 后,将操作通过服务器发送给对端,服务器根据收到的 OP,可以确定一个唯一的顺序,也就是能够确定一个唯一的最终状态,然后服务器再根据每个客户端的不同情况,对将要转发给客户端的 OP(对于 pper1 是 OP2,对于 peer2 是 OP1)进行相应的 transformation,然后发送之。这样,客户端在接收到修改后的 OP 后,可以生成和服务器一致的状态。


CRDT

如果说 OT 是一个中心化的解决方案,那么 CRDT 则是一个非中心化的解决方案。上文中对于事件满足交换律的情况下的冲突解决,基本上符合 CRDT 的思路。如果你看懂了上文中的处理方法,那么恭喜你,你基本上对 CRDT,或者说 sequence CRDT 有了一个粗浅的了解。如果你想更深入地了解其实现细节和挑战,可以看看 Martin Kleppmann 的演讲 CRDTs: the hard parts [5]。Martin 是业界大名鼎鼎的 DDIA (下图)这本书的作者。而 DDIA 是每个想把分布式系统的理论与实际结合起来的工程师的必读著作(感谢我的同事 00 赠书):


-loading- -loading--loading-


UfqiLong

在 CRDTs: the hard parts 演讲的结尾,Martin 还提到了他的项目:automerge[6]。通过 automerge 你可以很方便地使用 CRDT 构建实时协作软件。这个项目功能已经非常丰富,但目前还处在早期,主要的 API 还有可能变动,比如 frontend/backend 的协议,以及像 applyChanges() 这样的接口就还在发生重大改变,所以暂时不要用在生产环境。


继续放飞想象力

我知道,走到这一步,「不可能先生」不会再纠结理论上有没有可能实现,因为成熟的算法,甚至可用的工具已经摆在那里。接下来他们会质疑这个东西能不能实现出来。原因很简单:既然理论可行,那么为什么目前的主流协作软件还是使用 web 技术栈,客户端的每次操作都要「笨拙」地绕到千里之外的云服务器上获取数据呢?这说明什么?这说明这个技术还不够成熟,没办法应用。

对于这种质疑,光打嘴炮是没有意义的,做出来可用的产品才能有力反击。可程序君毕竟只是周末假装带娃的同时思考思考,码码文字,写写代码,做点 PoC,这自然离可用的产品还差十万八千里。所以我无法反击这种质疑。但是放飞想象力的时间精力我还是有的,所以咱们继续(不靠谱地)让想象力飞一会。

我们还以 Notion 为例。一个 Notion 用户可以有多个 workspace。如果数据全部放在本地,以 CRDT 的形式保存成文件,那么一个 workspace 在本地可以存储在一个目录下。根目录下可以存放这个 workspace 下所有用户的基本信息,用一个 automerge 下的 table(姑且简称 amt),存为 user.amt。这个文件里的用户信息,当前用户只能修改自己那一行;workspace 的 owner / admin 可以增删改。用户信息之外,我们还需要一个 permission.amt,存储每个用户在不同上下文下的角色。这样,我们可以使用 oso[7],通过 RABC 来处理授权。user/permission 相当于 workspace 的 metadata,其它的 metadata(比如配置)我们放下不表。


workspace 承载的是用户的数据。对于目录树,我们可以用一个 workspace.amt 来保存目录树的 CRDT 数据。目录树下有子目录或文件,子目录下有更深的目录或者文件。和文件系统的目录树类似,这里的文件我们放一个引用,然后文件本身有单独的 amt,如 doc4.amt。整个 workspace 的结构如下:


当用户在 UI 上对某个文档做了一个改动后,这个改动的 change 会从前端界面发送到应用的后端(非服务器的后端)。在应用的后端,automerge backend 对改动进行处理后,会生成一个 patch,提交回 frontend 去 apply。同时,这个改动通过网络(可以是服务器中转,也可以是 p2p 网络)传播出去。比如我们可以使用 libp2p 下的 gossipsub,在某个 topic 下传播。topic 可以是某一个 workspace,只有在这个 workspace 下的用户才能加入到这个 topic 下。当客户端 B 收到这个 syncMessage 后,它会提交给 automerge backend,生成 patch,提交给 frontend apply。



如果整个系统中有服务器中转事件,那么服务器可以 tap 出一份 amt 作为备份。一个新加入的客户端可以迅速从服务器拿到整个历史记录,进而参与到 workspace 的协作中。如果整个系统中没有服务器中转事件,使用的是 p2p 网络,那么服务器可以充当 p2p 网络中的一个节点,tap 出 amt 做备份。新加入的客户端节点可以从其任一个邻居那里要完整的数据。


上篇文章我还提到了可信网络和不可信网络的问题,现在想想,似乎没有必要考虑不可信网络,因为  Notion / clickUp 的使用场景,都是公司团队或者亲朋好友这种可信网络。如果事件通过服务器中转,那么一切的认证和处理都可以在服务端完成,这是大家所熟悉的流程,我就不再赘述;但如果采用 p2p 网络,则需要在 login 时添加客户端的 peerId 到受信设备,logout 时移除。流程如下:



取舍(Trade off)

最后我们谈谈取舍。我们做工程,不像数学计算那样,有完美的,确定的解。大部分工程问题都是一个实现问题,从 A 点到 B 点的路很多,走得通,实现得了的就是好路。在这个基础上,如果能够照顾好用户体验,性价比,那么就是优选之路。上一篇文章我只是提了一个问题 —— 为什么 Notion / clickUp 这样的效率软件在如今的强力 CPU 下,表现地如此低效,进而谈了谈我个人对这个问题的 vision,并不是说把数据放在客户端就一定比服务器更好。

本着研究研究的态度,本文我们打开另一道门,走走其它的道路。使用 CRDT 的路子可以走得通,甚至在很多场景下可以走得非常好,但这并不意味它就没有缺点。所以我们还是要对它的优劣进行取舍。

CRDT 的思路的好处是:

local first[8]:数据存储到本地,即时的响应速度,允许离线处理。

可以不依赖服务器而在客户端提供各种各样的数据访问的方式(filter, aggregate, projection, gorupby 等等),甚至,可以提供 API 让本地数据很容易被 pandas 等工具使用。

即便使用服务器中转,其服务器资源的开销相对要小很多,对于一个大型的项目,节省的资金会很可观。


但它的缺点是:

随着时间本地数据会增长得越来越大,由于存储着数据的全集,这个数量可能会很可观(可以有一些优化,比如用户上传的图片,视频这样的静态资源可以放在 S3,本地只放链接,访问时再获取 presigned url),所以,这种方法很可能不适合在浏览器端使用。

整个系统的复杂度比大家熟悉的 web 技术栈要大很多。


技术栈小众,很难找到合适的工程师(当然,这也意味着一旦找到,必然是优秀的工程师)。

市场上缺乏成功的先例(我指专门处理列表和文档这块的 sequence CRDT,其实 CRDT 在很多软件中已经得到了广泛使用,比如 phoenix framework,redis 等)。


参考资料

[1] Eventually consistent - revisited: https://www.allthingsdistributed.com/2008/12/eventually_consistent.html

[2] OT: https://en.wikipedia.org/wiki/Operational_transformation

[3] CRDT: https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type

[4] Operational Transformation 算法图解:https://zhuanlan.zhihu.com/p/30890457

[5] CRDTs: the hard parts: https://www.youtube.com/watch?v=PMVBuMK_pJY

[6] automerge: https://github.com/automerge/automerge

[7] oso: https://github.com/osohq/oso

[8] Local-first software: https://www.inkandswitch.com/local-first.html


+想象力 +工程 +方法 +服务器 +顺序

本页Url

↖回首页 +当前续 +尾续 +修订 +评论✍️


👍6 仁智互见 👎0
  • 还没有评论. → +评论
  • -loading- -loading- -loading-


    🔗 连载目录

    🤖 智能推荐

    Java開發手冊-阿里巴巴-嵩山版-11:前后端规约

    透过 Rust 探索系统的本原-2:并发篇 透过 Rust 探索系统的本原-2:并发篇

    Java開發手冊-阿里巴巴-嵩山版-14:日志规约

    互联网络安全攻防黑产之卖假服务器 互联网络安全攻防黑产之卖假服务器

    Java服务并发开发中的线程池 Java服务并发开发中的线程池

    学习掌握“千万工程”所蕴含的理念和方法 23

    学习掌握“千万工程”所蕴含的理念和方法 22

    学习掌握“千万工程”所蕴含的理念和方法 12

    从党的科学理论中汲取前进力量 3

    农业农村部召开学习推广浙江“千万工程”经验座谈会强调深刻体悟浙江“千万工程”精髓要义和理念方法加快建设宜居宜业和美乡村 2

    -loading- -loading- -loading-


    🔥 相关精选

    学习掌握“千万工程”所蕴含的理念和方法 2

    徐祥临:用好“千万工程”经验的要点与方法 1

    省委理论学习中心组学习会强调 自觉把“千万工程”蕴含的理念方法 转化为推进自由贸易港建设的生动实践 1

    勤哲Excel服务器自动生成建筑企业考勤管理系统 0

    市政工程质量验收方法是什么? 0

    今年车市增长机会在哪里 0

    让科学大师剧成为“大思政课”生动教材 0

    重庆港航支队助力重点民生工程节后复工复产 重庆港航支队助力重点民生工程节后复工复产 0

    聚焦2024年中央一号文件:“千万工程”经验学什么?怎么学? 0

    “千万工程”经验学什么?怎么学?中央农办回应 0

    -loading- -loading- -loading-

     


    + 田福军 田福军
    AddToFav   
    新闻 经典 官宣