ElectricSQL 与 Rich-CRDTs：为本地优先应用引入数据库级不变量保障

ElectricSQL 与 Rich-CRDTs为本地优先应用引入数据库级不变量保障【免费下载链接】electricThe agent platform built on sync.项目地址: https://gitcode.com/GitHub_Trending/el/electricRich-CRDTs富 CRDT是在经典 CRDT无冲突复制数据类型基础上扩展出数据库级保障的复制数据类型用于在并发写入下维持约束、引用完整性等不变量。本文以 ElectricSQL构建于同步之上的 agent 平台团队的研究视角系统讲解 Rich-CRDTs 的三大核心技术——组合Composition、补偿Compensations与预留Reservations并给出可直接落地的数据建模思路读完你将对如何在不引入全局协调的前提下保证分布式数据的一致性约束建立清晰、可操作的认识。先复习CRDT 与强最终一致性CRDT 是一类特殊的复制数据类型其核心价值在于提供无冲突的并发conflict-free concurrency。借助 CRDT多人可以同时更新同一份数据所有更新会被无冲突地合并最终所有节点收敛到相同的值——这被称为强最终一致性Strong Eventual Consistency一旦全部更新完成复制所有参与者看到的数据完全一致。CRDT 因此成为现代低延迟地理分布式数据库与多人协作系统共同的底层关键组件。CRDT 将冲突解决策略编码进类型本身当分布式系统中的两个节点试图同时更新同一个 CRDT 时CRDT 调用内置的合并方法来处理并发操作。该合并方法必须满足三条数学性质交换律Commutativity合并顺序不影响结果结合律Associativity分组合并的结果一致幂等性Idempotency同一操作重复应用不改变结果。常见的 CRDT 类型包括Counter计数器合并方法将所有操作的增量值累加Last-Writer-Wins RegisterLWW 寄存器合并方法直接以时间戳最新的操作值覆盖寄存器。CRDT 可以相互组合以构造更复杂的对象。但问题在于把合并策略与一致性语义做对非常困难。某些操作在并发合并时无法不破坏一致性而且大量常见的数据库不变量根本无法由单个数据类型的合并策略来保证。实际构建现代应用时几乎必然遇到这类可组合性与不变量安全问题而解决它们至今仍是 ad hoc特设过程——开发者每用 CRDT 构建一个新应用都要从头重新推理这些问题并做决策。这种缺乏标准化的事实使 CRDT 编程极易出错。Rich-CRDTs 的目标正是为开发者提供内置检查与合理默认值的高级抽象让不变量保障开箱即用。Rich-CRDTs 是什么Rich-CRDTs 在基础 CRDT 之上提供额外的不变量安全与数据库保障手段是以下三类技术组合Composition补偿Compensations预留Reservations其中前两类——组合与补偿——是无冲突的它们不引入任何额外协调机制第三类预留则尽可能避免运行时协调但在必要时以协调兜底以保证必须的不变量。单个 Rich-CRDT 可以同时使用其中一种或多种技术设计时的总体思路是先用无冲突技术保住不变量最后才在必要时审慎使用预留。原文档给出了一张清晰的决策流程用于指导 Rich-CRDT 的建模选择┌────────────────────────┐ │ │ │ Can I use basic CRDTs? ├──► Done │ │ └──┬─────────────────────┘ │ ▼ ┌────────────────────────┐ │ │ │ Can I use composition? ├──► Done │ │ └──┬─────────────────────┘ │ ▼ ┌──────────────────────────┐ │ │ │ Can I use compensations? ├──► Done │ │ └──┬───────────────────────┘ │ ▼ ┌────────────────────────────────┐ │ │ │ Can I use escrow reservations? ├──► Done │ │ └──┬─────────────────────────────┘ │ ▼ Use lock based reservations即优先尝试基础 CRDT → 组合 → 补偿 → 托管预留escrow→ 最后才退到基于锁的预留。这一阶梯式取舍贯穿整篇技术方案的设计哲学。组合Composition嵌套出高阶数据结构组合指的是把多个 CRDT 合并或嵌套起来构造更丰富的高阶无冲突数据结构。最简单的组合示例是正负计数器PN Counter它由两个计数器组合而成一个记录正向变化、一个记录负向变化两者结合得到当前净值。PN Counter 由此突破了单个 Counter 无法表示减少的局限。更复杂的组合示例是JSON CRDT。JSON 本质上是由四种数据类型构成的 mapstring、number、object、array。在 map CRDT 中每个 key 可以持有不同的 CRDT 对象作为其值JSON CRDT 为 JSON 提供的每种可能值类型给出合理的默认 CRDT 策略。例如{ name: Valter, score: 234, attributes: { location: Lisbon }, history: [bought-fish, grilled-fish] }上面这个 JSON CRDT 中每个 key 映射到不同的基础 CRDT 类型且各类型可以选用不同的冲突解决策略例如name用 Last-Writer-Wins 寄存器score用 Counterhistory用数组类型如Replicated Growable Array可复制增长数组。map 层还可以额外提供当并发操作把不同类型值关联到同一 key 时的冲突解决策略。组合的价值在于由已验证正确的基础 CRDT 拼装出的高阶结构其合并语义可以分层推导从而降低自定义合并逻辑出错的风险。补偿Compensations由数据库主动执行的额外操作补偿指的是数据库在用户指定操作之外额外执行的操作其目的是确保某项不变量始终成立。数据库里经常存在多张由键关联的表——关联表中的外键指向父表的主键。引用完整性Referential Integrity就是要保证这些关联在任何时刻都有效例如删除了主表中的第 15 行就不允许任何关联表中还残留值为 15 的外键。引用完整性在并发场景下极具挑战因为一个操作可能在删除某行而另一个并发操作正在向引用它的关联表添加新行。经典例子是某个玩家报名参加锦标赛enrol恰好与锦标赛被删除delete并发发生。图示玩家-锦标赛的引用完整性违反示意。补偿可以提供解法。例如在报名玩家操作中附加一个touch 操作把额外的 touch 写进报名玩家的事务里那么即使它与一个删除锦标赛的并发事务合并只要锦标赛集合遵循add-win 语义添加操作胜过删除操作就能保证锦标赛依然存在从而维持引用完整性。图示玩家-锦标赛的补偿操作通过确保锦标赛存在来维持引用完整性。有两个要点需要特别注意:::note 在没有冲突的情况下这些额外补偿操作对外不可观测不影响用户可见的结果。 ::::::note 该例的可交互演示可见原文档引用的 Introduction - Active-active replication 页面。 :::预留Reservations为并发操作预留资源预留是指为每个客户端预留一定量的资源从而允许对单一数据类型执行并发操作。资源预留有三种方式托管预留Escrow reservations托管预留加算法Escrow reservations plus an algorithm锁Locking / 互斥托管预留Escrow托管预留是一类这样的预留为某个操作获取的资源会在整个分布式集群内被分摊出去使各个节点/集群各自持有一部分执行特定操作的权限。有界计数器Bounded Counter是使用预留技术的 Rich-CRDT 典型例子它把一部分资源预分配给每个节点。假设你是 Stubhub有 1000 张 Justin Bieber 演唱会的票要卖你要避免两个人在两个不同节点上同时买到最后一张票的场景。做法是给 10 个节点每个分配 100 张票的预留额度。当某个节点的配额耗尽时它再与其它 peer 协调获取更多预留。这样绝大多数操作无需每次都协调即可校验。托管预留的关键优化之一是主动分配与再平衡proactive rebalancing让预留由真正需要的节点/集群持有。如果 Justin Bieber 演唱会在旧金山、所有票都在 US-West 集群被买走那么 Rich-CRDT 系统可以注意到或预测到这一点主动把更多预留划给 US-West 集群。在运转良好时主动再平衡可以让绝大多数更新都免于协调。托管预留加算法Escrow plus algorithm这一类预留中为操作获取的资源由算法给出。例如对树形结构的操作必须小心执行以维持树不变量——两个节点可能被并发地移动到彼此之下从而引入环。一种朴素做法是预留整棵树的根来安全执行 move 操作这会阻止树上任何其他并发操作而一个预留算法可以更高效只要并发操作触及树的不同部分就是安全的。move 操作的参数源节点与目标节点可以用来计算需要预留的最近公共父节点从而既保证节点安全移动又允许其他子树上的并发操作继续执行。锁Locking锁是指只有持有锁的节点才能访问某资源的技术锁分共享锁与排他锁。典型例子是全局顺序标识符global sequential identifiers必须一个接一个按序生成即全局已知最后生成的值才能保证顺序属性且无空洞。为此开发者可以使用锁 CRDT当某节点持有锁时它能 1) 看到上一个锁持有者产生的变更从而知道序列中下一个标识符应是什么2) 访问生成全局标识符的那段代码。否则它必须与其它 peer 交换权限——这与上述托管预留机制类似。Next stepsRich-CRDTs 在 ElectricSQL 中的落地Rich-CRDTs 并非纯理论。从仓库证据看它直接构成了 ElectricSQL 同步引擎的一致性与约束设计的理论基础团队背景Rich-CRDTs 与 Just Right Consistency 的研究作者 Valter Balegas 正是本项目的联合创始人兼 CTO见 website/data/team/team.yaml 中short_bio: Rich-CRDTs and Just Right Consistency. ...工程落地在 Introducing ElectricSQL v0.6 一文的路线图说明中明确写道ElectricSQL 的不变量支持目前聚焦于使用补偿机制实现引用完整性invariant support is limited to referential integrity using compensations并计划逐步支持跨复制边界的引用完整性、唯一约束unique constraints与检查约束check constraints——In this were building on research we authored and are implementing as Rich-CRDTs研究脉络项目维护了完整的论文清单见 website/docs/sync/reference/literature.md 与 website/data/literature/papers.yaml其中与本文直接相关的论文包括Extending Eventually Consistent Cloud Databases for Enforcing Numeric Invariants2015Balegas 等人、IPA: invariant-preserving applications for weakly consistent replicated databases2018、Just-Right Consistency: reconciling availability and safety2018、Conflict-free Replicated Data Types (CRDTs)2011Preguiça / Baquero / Shapiro等。如需深入了解底层算法可从该清单按图索骥。因此把本文的决策流程与三类技术应用到本地优先local-first应用上正是 ElectricSQL 让带完整约束的 SQL在弱一致复制环境中仍然成立的关键路径能组合就用组合组合不了就用补偿保住引用完整性最后才在必要时引入预留。这也是从写 CRDT 容易出错走向开箱即用的核心抽象思路。【免费下载链接】electricThe agent platform built on sync.项目地址: https://gitcode.com/GitHub_Trending/el/electric创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考