Skip to content

Grow-only Counter CRDT

Grow-only Counter · G-Counter · 只增计数器 CRDT

以每副本唯一写分量、逐分量最大合并和分量求和查询实现的只增状态型计数器。

条目类型
模型

形式陈述

设当前复制成员的持久 actor ID 集合为 R。Grow-only Counter 的状态是有限映射

X:RN,

缺失键视为零。副本 i 只能执行

inci(X)(i)=X(i)+1

并保持其余分量不变;merge 与 query 分别为

(XY)(r)=max(X(r),Y(r)),value(X)=rRX(r).

逐分量序使 NR 成为 join-semilattice,inc 只提升本副本分量,所以这是状态型 CRDT的一个严格构造。每个分量必须只有一个逻辑 writer:X(i) 表示 actor i 已产生的 increment 前缀长度,最大值合并才能解释为前缀包含。

ID 和本地分量必须跨崩溃持久化。若副本重启后仍用 ID i 却把计数从零开始,旧状态的较大 X(i) 会永久盖住新 increment;若两个活副本共享 ID,则它们并发从 k 写成 k+1,merge 只保留一次。

数学定义使用无界自然数。固定宽度机器整数若回绕,2641 后的零不支配旧值,膨胀性失效;实现需检查溢出、扩宽表示或改变协议。

直觉

计数总和不能直接在网络中反复相加,因为状态可能重复到达。G-Counter 改为记录“每位作者一共写了多少次”,同一作者的后继数概括全部前缀;接收端取最大即可消除重复。不同作者的贡献位于不同槽,最后只在 query 时求和。

向量既是数值,也是去重摘要。看到 A:7 就表示 A 的前七次 increment 均已包含,无需保存七个 operation ID。这个压缩依赖同一 actor 的事件连续且唯一;任意跳号并不会让缺失事件自动存在,除非生成协议保证前缀语义。

不能只交换 scalar query。状态 X=(2,0)Y=(0,2) 都读作二,却包含不同作者前缀;正确 merge 为 (2,2)、读作四。把两者压成数字二后,接收者无法判断两份二是重复摘要还是独立贡献。

只增是用户 API 的真实限制。用较小数字直接覆盖某分量不是 decrement,而是破坏历史;需要下降读值时,应增加一个独立负分量,进入 PN-Counter。

例子与边界

两个副本 A、B 初始均保存 (0,0)。A 离线 increment 两次得到 (2,0),B increment 一次得到 (0,1)。B 先收到 A 的旧快照 (1,0)

(0,1)(1,0)=(1,1),

再收到 (2,0)

(1,1)(2,0)=(2,1).

重复收到两个快照中的任意一个都不改变状态。A 收到 B 的 (0,1) 后也得 (2,1),两边 query 为 2+1=3

若 merge 错用逐分量加法,B 第一次收到 (2,0)(2,1),重传后变 (4,1),一次网络重复凭空制造两次 increment。若 A 与 A' 共用 actor ID 且都从 (2,0) 并发增加成 (3,0),最大合并仍为三,而真实总数应为四;唯一 writer 不是实现建议,而是正确性条件。

成员移除后也不能立即重用其 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.
关系图谱2 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
分类位置

上位 / 更一般

下位 / 直接特例

暂未标注直接特例。