# CRDT 类型词典：变体、代数操作与合并策略指南 > CRDT变体详解：从G-Counter到OR-Set的代数结构、合并策略及冲突自由复制的选择标准与工程参数。 ## 元数据 - 路径: /posts/2025/11/30/crdt-types-field-guide-algebraic-ops-merge-strategies/ - 发布时间: 2025-11-30T00:17:59+08:00 - 分类: [systems-engineering](/categories/systems-engineering/) - 站点: https://blog.hotdry.top ## 正文 CRDT（Conflict-free Replicated Data Types，无冲突复制数据类型）是分布式系统中实现最终一致性的核心工具，通过设计数据结构确保副本间无协调即可合并为相同状态。其数学基础是半格（semilattice）：状态形成偏序，合并操作⊔满足交换律（a ⊔ b = b ⊔ a）、结合律（(a ⊔ b) ⊔ c = a ⊔ (b ⊔ c)）和幂等律（a ⊔ a = a）。更新单调递增，确保任意顺序合并收敛。 状态型CRDT（CvRDT）传输全状态并合并；操作型CRDT（CmRDT）传输操作需因果传递。本文聚焦CvRDT变体，列出核心类型、代数操作、合并策略及选择指南。 ### 计数器类（Counters） **G-Counter（增长计数器）**：每个副本维护自身计数，总值∑各计数。 - 操作：increment(r): counter[r] += 1 - 合并：unionWith max（逐副本取最大） - 适用：仅增场景，如浏览量。空间O(副本数)，无垃圾回收。 **PN-Counter（正负计数器）**：组合两个G-Counter，P记录增量、N记录减量，总值P-N。 - 操作：increment(r): P.increment(r)；decrement(r): N.increment(r) - 合并：分别合并P/N - 适用：库存、点赞退赞。缺点：可负值，无原子重置。 ### 集合类（Sets） **G-Set（增长集合）**：标准集合，仅支持添加。 - 操作：add(x): insert x - 合并：union - 适用：追加日志。无法删除。 **2P-Set（两阶段集合）**：added与removed各一G-Set，成员=added \ removed。 - 操作：add(x): added.insert(x)；remove(x): removed.insert(x) - 合并：分别union - 策略：删除优先，一旦删除不可再加。适用：任务完成追踪。 **LWW-Element-Set（最后写入胜集合）**：addTimes/removeTimes各Map，成员若add时间>remove时间。 - 操作：add/remove带时间戳 - 合并：unionWith max时间戳 - 策略：最后写入胜，需时钟同步。适用：特性标志，可GC旧戳。 **OR-Set（观察移除集合）**：Map>，Tag=(replica, seq)唯一标识添加。成员若Tag非空。 - 操作：add(x): 生成新Tag insert；remove(x): 移除观察到的Tag - 合并：union Tag集 - 策略：添加胜，并发add/remove保留add（未观察Tag）。如Ian Duncan所述，此为最复杂集合CRDT，支持全CRUD无LWW丢失。[1] ### 寄存器类（Registers） **LWW-Register**：(value, timestamp)，合并取最新戳。简单但并发丢失。 **MV-Register**：Set<(value, timestamp)>，保留并发值，应用层解析。 ### 序列/映射类（Sequences/Maps） **RGA（复制增长数组）**：树结构，元素存(value, parent UID)，插入指定后继。删除墓碑。合并调和树。适用：协同文本，O(log n)操。 **OR-Map**：键为OR-Set，值为嵌套CRDT。支持put/removeKey/removeValue。 ### 选择矩阵 | 需求\类型 | 仅增 | 增减不可重加 | 全CRUD | 序列 | 嵌套 | |-----------|------|--------------|--------|------|------| | **推荐** | G-Counter/Set | PN/2P | OR/LWW | RGA | OR-Map | | **合并** | max/union | 组件union | unionWith max/union Tag | 树调和 | 递归 | | **风险** | 空间O(r) | 双空间 | Tag墓碑 | 线性化O(n) | 复杂GC | 选择依据操作语义：仅增用G-；需删优先2P/OR；容忍LWW用其简化；序列用RGA/YATA。 ### 工程参数与落地 **Delta-CRDT**：仅传增量δ-state，减少带宽。参数：track per-replica lastSent，delta=state since lastSent。 **垃圾回收（GC）阈值**： - 时间窗：90天过期Tag（保守，防离线>窗）。 - 界限Tag：每元素≤1000，超取最新（降LWW）。 - 因果：用版本向量，丢弃被主导VV的Tag。监控：oldest_unsynced_ts - 安全裕度=GC线。回滚：checkpoint快照+δ日志，新副本全传。 落地清单：1.选CRDT组合（如购物车OR-Set+PN）；2.δ+GC；3.因果广播（如gossip）；4.性能：读写比高选OR，副本多选Delta。库：Yjs（文本）、Automerge（JSON）。 来源：[1] https://www.iankduncan.com/engineering/2025-11-27-crdt-dictionary （Ian Duncan CRDT词典）；Shapiro et al. CRDT论文。 ## 同分类近期文章 ### [Apache Arrow 10 周年：剖析 mmap 与 SIMD 融合的向量化 I/O 工程流水线](/posts/2026/02/13/apache-arrow-mmap-simd-vectorized-io-pipeline/) - 日期: 2026-02-13T15:01:04+08:00 - 分类: [systems-engineering](/categories/systems-engineering/) - 摘要: 深入分析 Apache Arrow 列式格式如何与操作系统内存映射及 SIMD 指令集协同，构建零拷贝、硬件加速的高性能数据流水线，并给出关键工程参数与监控要点。 ### [Stripe维护系统工程：自动化流程、零停机部署与健康监控体系](/posts/2026/01/21/stripe-maintenance-systems-engineering-automation-zero-downtime/) - 日期: 2026-01-21T08:46:58+08:00 - 分类: [systems-engineering](/categories/systems-engineering/) - 摘要: 深入分析Stripe维护系统工程实践，聚焦自动化维护流程、零停机部署策略与ML驱动的系统健康度监控体系的设计与实现。 ### [基于参数化设计和拓扑优化的3D打印人体工程学工作站定制](/posts/2026/01/20/parametric-ergonomic-3d-printing-design-workflow/) - 日期: 2026-01-20T23:46:42+08:00 - 分类: [systems-engineering](/categories/systems-engineering/) - 摘要: 通过OpenSCAD参数化设计、BOSL2库燕尾榫连接和拓扑优化，实现个性化人体工程学3D打印工作站的轻量化与结构强度平衡。 ### [TSMC产能分配算法解析：构建半导体制造资源调度模型与优先级队列实现](/posts/2026/01/15/tsmc-capacity-allocation-algorithm-resource-scheduling-model-priority-queue-implementation/) - 日期: 2026-01-15T23:16:27+08:00 - 分类: [systems-engineering](/categories/systems-engineering/) - 摘要: 深入分析TSMC产能分配策略，构建基于强化学习的半导体制造资源调度模型，实现多目标优化的优先级队列算法，提供可落地的工程参数与监控要点。 ### [SparkFun供应链重构：BOM自动化与供应商评估框架](/posts/2026/01/15/sparkfun-supply-chain-reconstruction-bom-automation-framework/) - 日期: 2026-01-15T08:17:16+08:00 - 分类: [systems-engineering](/categories/systems-engineering/) - 摘要: 分析SparkFun终止与Adafruit合作后的硬件供应链重构工程挑战，包括BOM自动化管理、替代供应商评估框架、元器件兼容性验证流水线设计