Skip to content

Positive-Negative Counter CRDT

Positive-Negative Counter · PN-Counter · 可增减计数器 CRDT

以正、负两个只增计数器分别累计增量与减量,并以二者总和之差作为读值。

条目类型
模型

形式陈述

PN-Counter 的状态是一对G-Counter

X=(P,N),P,N:RN.

副本 i 的 increment 只执行 P(i):=P(i)+1,decrement 只执行 N(i):=N(i)+1。合并对两个向量分别逐分量取最大:

(P,N)(P,N)=(PP,NN),

查询为

value(P,N)=rRP(r)rRN(r).

内部状态在乘积偏序中始终膨胀;用户读值却可以增加、减少或不变。这正说明 CRDT 的单调性属于信息状态,而非 query 数值。

每个 actor 对 P(i)N(i) 仍是唯一 writer,ID 与两分量必须持久化且不能被并发重用。数学整数无溢出;实现若对两笔总和分别溢出后再相减,即使最终差值看似可表示,也已破坏 max 所依赖的前缀序。

PN-Counter 没有原生 reset。把两向量清零会向下移动并让旧状态复活;若需要 epoch reset,必须为 epoch 建立可合并的排序和成员协议,或创建新对象身份。读值为负在数学模型中完全合法,查询本身无需截断。

直觉

直接把三减成二会遗忘“三曾经包含哪些 increment”,旧快照三再次出现时无法判断它过期。PN-Counter 不删除正历史,而是新增一条负历史;查询时才把二者抵消。网络层看到的仍是两份只会向上的知识。

这与会计账本相似:收入和支出分别累计,余额是差。两个副本可以并发记录不同方向的变化,merge 不需决定哪一笔“最后发生”。同一快照重复传播也只把各账本前缀取最大。

代价是元数据与语义分离。余额为零可能来自从未更新,也可能来自一百次增、一百次减;内部状态不能据 query 相等而压成零,否则迟到副本会造成重复或丢失。两个状态读值相同也未必可替换,例如 (P,N)=((3,0),(1,0))((2,0),(0,0)) 都读二,却对远端负分量的未来 merge 有不同结果。

例子与边界

设 actor 为 A、B。A 执行三次 increment 和一次 decrement:

PA=(3,0),NA=(1,0).

B 执行一次 increment 和两次 decrement:

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

交换状态后分别取最大,得到

P=(3,1),N=(1,2),

所以读值为 43=1。若 B 先合并 A 的正向量,暂态为 P=(3,1),N=(0,2),读值为二;若先合并 A 的负向量,暂态为 P=(0,1),N=(1,2),读值为负二。两部分最终传播后才回到一,因此 PN-Counter 不提供多分量更新的原子可见性。

若业务规定库存不得小于零,A、B 从一件库存同时各 decrement 一次,合并后读值为 1。CRDT 正确收敛到负数,却违反业务不变量;需要 escrow rights、分区额度或协调,而不是修改 merge 让某次 decrement 消失。

批量 decrement k 应让 N(i) 一次增加非负整数 k。若请求在重试时重新执行批量本地更新而没有 operation ID,源副本会真实记录两笔 k;状态 merge 只能去除网络快照重复,不能替 API 层判断两次调用是否属于同一业务请求。

若实现试图在本地直接执行 P(i):=P(i)1,旧的较大分量会在下次 merge 重新出现。若把正负两向量先相减成单个整数再取最大,并发 decrement 又会被“较大值胜”吞掉。

推论与应用

PN-Counter 可表达投票净值、资源变化量和增减指标,并保留 G-Counter 对乱序、重复状态的宽容。按批次加减 k 可把对应本地分量增加 k,前提是 k0 且算术无溢出。若希望读取两个分量的同一逻辑快照,还需对象级原子存储,避免崩溃只持久化正账或负账的一半。

动态成员和状态压缩仍是主要成本。可以把永久退役 actor 的正负贡献迁移进稳定汇总分量,但迁移必须恰好一次且阻止旧身份重返;否则汇总与迟到原分量会双重计入。

参考资料
  • Marc Shapiro et al., “A Comprehensive Study of Convergent and Commutative Replicated Data Types,” INRIA RR-7506, 2011, Specification 7.
  • Nuno Preguiça, Carlos Baquero, and Marc Shapiro, “Conflict-Free Replicated Data Types,” Encyclopedia of Big Data Technologies, Springer, 2018, counter entries.
  • Paulo Sérgio Almeida, “Approaches to Conflict-Free Replicated Data Types,” ACM Computing Surveys 56(3), Article 76, 2024, Sec. 3.2.
关系图谱1 个相邻概念 · 1 类关系

拖动节点调整位置。

显示关系

显示:依赖

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