“PN Counter 的状态是一对G Counter”
形式陈述 ​
设当前复制成员的持久 actor ID 集合为
缺失键视为零。副本
并保持其余分量不变;merge 与 query 分别为
逐分量序使
ID 和本地分量必须跨崩溃持久化。若副本重启后仍用 ID
数学定义使用无界自然数。固定宽度机器整数若回绕,
直觉
计数总和不能直接在网络中反复相加,因为状态可能重复到达。G-Counter 改为记录“每位作者一共写了多少次”,同一作者的后继数概括全部前缀;接收端取最大即可消除重复。不同作者的贡献位于不同槽,最后只在 query 时求和。
向量既是数值,也是去重摘要。看到
不能只交换 scalar query。状态
只增是用户 API 的真实限制。用较小数字直接覆盖某分量不是 decrement,而是破坏历史;需要下降读值时,应增加一个独立负分量,进入 PN-Counter。
例子与边界
两个副本 A、B 初始均保存
再收到
重复收到两个快照中的任意一个都不改变状态。A 收到 B 的
若 merge 错用逐分量加法,B 第一次收到
成员移除后也不能立即重用其 ID。新节点若继承 A 的名字但不知道旧前缀二,从零开始的更新会被旧最大值吞掉。安全做法是使用永不重用的 incarnation ID,或在受协调 epoch 中迁移并重置全体状态。
推论与应用
G-Counter 适合曝光量、已完成任务数和单调指标,支持全状态 gossip、delta-state 或按 actor 范围同步。Delta 可只携带更新后的单分量绝对值,而不能携带数值一后仍用 max 合并。本地 query 无需协调,但可能暂时漏掉尚未传播的远端分量。
空间复杂度随历史 actor 数增长。已退役分量的回收需要知道该 actor 不会以旧身份重返,并把其贡献转移到一个仍单调、不会与迟到状态重复相加的摘要;简单删键会让 value 下降并可能在旧状态到达时反复跳变。分片聚合若让多个 writer 共享一个 max 槽,也会重新引入丢增量问题。
参考资料
- Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski, “A Comprehensive Study of Convergent and Commutative Replicated Data Types,” INRIA RR-7506, 2011, Specification 6.
- Paulo Sérgio Almeida, Ali Shoker, and Carlos Baquero, “Delta State Replicated Data Types,” Journal of Parallel and Distributed Computing 111, 2018, Sec. 4.1.
- Paulo Sérgio Almeida, “Approaches to Conflict-Free Replicated Data Types,” ACM Computing Surveys 56(3), Article 76, 2024, Sec. 3.2.