背景

在一个分布式系统中，有一个集合（Set），每个节点都能随意往里面添加、删除元素。

请设计一个CRDT（Conflict-free Replicated Data Type）来实现一套满足最终一致性的分布式系统

为了减少要理解的概念，下文描述的CRDT同时有两层意思

无冲突的数据类型，即类型一个CRDT实例，即实例思维链

flowchart TD
      A["1. CRDT可以在不同的节点中使用"]
      A --> B["2. CRDT可以表达所有节点最终往Set中添加的元素集合"]
      B --> C["3. CRDT可以让任意节点往Set中添加和删除元素"]
      C --> D["4. 可合并多个节点的CRDT，且其结果与合并顺序无关，\n即 Merge(A.CRDT, B.CRDT, C.CRDT) = Merge(B.CRDT, C.CRDT, A.CRDT) = a new CRDT"]
      D --> E["5. 多次合并同一个节点的CRDT，其结果等同于合并一次，\n即 Merge(A.CRDT, B.CRDT, B.CRDT) = Merge(A.CRDT, B.CRDT) = a new CRDT"]
      E --> F["6. 参照PNCounter的理念，我们设立两个GSet，\n一个代表往Set里添加的元素的集合，一个代表在Set里删除的元素的集合"]
      F --> G["7. CRDT的值为两个集合的差集"]

特别说明：第二点的最终往Set中添加的元素集合，指的是应用了所有节点对Set的增加、删除操作后的结果

实现

这个CRDT如下，我们暂时给它起名PNSet（稍后解释其为什么叫PNSet）

const PNSet:[GSet, GSet] = [new GSet(), new GSet()] 

因为是分布式系统，且支持弱网环境，所以这个PNSet在不同节点里，都不一样。比如

// 节点A的数据副本
A.PNSet = [["element1", "element2", "element3"], ["element2"]]
// 节点B的数据副本
B.PNSet = [["element1", "element2", "element4"], ["element2","element3"]]
// 节点C的数据副本
C.PNSet = [["element1", "element2", "element3", "element5"], ["element2","element3"]]

各自节点往PNSet中添加元素,比如A节点往PNSet中添加元素，通过A.PNSet[0].add(element)即可

各自节点往PNSet中删除元素,比如A节点删除PNSet中的元素，通过A.PNSet[1].add(element)即可

各自节点的PNSet的值，比如A节点的PNSet的值 = 删除A.PNSet[0]中与A.PNSet[1]重合的元素后的集合

合并不同节点的PNSet，比如Merge(A.PNSet, B.PNSet) = GSet.Merge(A.PNSet[0], B.PNSet[0])和GSet.Merge(A.PNSet[1], B.PNSet[1])

// 节点A的数据副本
A.PNSet = [["element1", "element2", "element3"], ["element2"]]
// 节点B的数据副本
B.PNSet = [["element1", "element2", "element4"], ["element2","element3"]]

// 任意节点都能往PNSet[0]中添加元素，代表往PNSet中添加元素
const add = (node, value: T) => {
    node.PNSet[0].add(value)
}
// 任意节点都能往PNSet[1]中添加元素，代表删除PNSet中的元素
const remove = (node, value: T) => {
    node.PNSet[1].add(value)
}
// 获取某个节点的PNSet的值
const value = (node) => {
    const set = new Set([...node.PNSet[0]].filter(item => !node.PNSet[1].has(item)))
    return new GSet(set)
}
// 合并两个PNSet
const merge = (PNSetA: PNSet, PNSetB: PNSet) => {
    const newPNSet: PNSet = [new GSet([...PNSetA[0], ...PNSetB[0]]), new GSet([...PNSetA[1], ...PNSetB[1]])]
    return newPNSet
}
const newPNSet = merge(A.PNSet, B.PNSet)

你按随意的顺序合并A.PNSet，B.PNSet，C.PNSet，其结果都一致，即最终一致性。

QA

问：如果A节点里的PNSet如下

A.PNSet = [["element1", "element3"], ["element2"]]

然后A.PNSet添加了一个元素element2，即

A.PNSet = [["element1", "element2"，"element3"], ["element2"]]

但是在获取A.PNSet的值的逻辑里，element2并不会在最终的结果中，因为A.PNSet[1]中有element2，这明显不合理呀！（即便被别的节点删过element2，或者A节点昨天删过element2，但是今天A节点添加了element2，那最终的的值应该要有element2）

答：是的，你提了一个很好的问题，PNSet无法完全实现我们的需求。我会在下一篇文章会介绍一个新的CRDT来解决这个问题，从而完全实现这个需求

总结

因为这个CRDT可以在集合中增加、删除元素，所以叫PNSet（全称：Positive-Negative Set），它有一个更标准的名字是2P-Set