基于CRDT集合实现CRDT Map：合并为何不满足结合性？

我基于正确实现的LWWSet（支持merge操作的状态型CRDT集合），用Rust实现了LWWMap：

pub struct LWWMap<K, V>
where
    K: Ord,
    V: Merge,
{
    keys: LWWSet<K>,
    values: BTreeMap<K, V>,
}

对应的merge方法实现如下：

impl<K, V> Merge for LWWMap<K, V>
where
    K: Ord + Clone,
    V: Merge,
{
    fn merge_mut(&mut self, mut other: Self) {
        self.keys.merge_mut(other.keys);

        // retain and merge keys
        let mut new_values = BTreeMap::new();

        for key in self.keys.iter().cloned().collect::<Vec<K>>() {
            match (self.values.remove(&key), other.values.remove(&key)) {
                (Some(mut self_value), Some(other_value)) => {
                    self_value.merge_mut(other_value);
                    new_values.insert(key, self_value);
                }
                (Some(self_value), None) => {
                    new_values.insert(key, self_value);
                }
                (None, Some(other_value)) => {
                    new_values.insert(key, other_value);
                }
                (None, None) => {}
            }
        }

        self.values = new_values
    }
}

这个实现满足幂等性和交换性，但不满足结合性。我用merge逻辑为取最大值的Max类型CRDT构建了三个LWWMap<bool, Max<bool>>实例：

a = LWWMap {
    keys: LWWSet {
        adds: {
            true: 1970-01-01T00:00:00Z_0_00000000-0000-0000-0000-000000000000,
        },
        removes: {
            true: 1970-01-01T00:00:01Z_1_00000000-0000-0000-0000-000000000002,
        },
    },
    values: {},
}

b = LWWMap {
    keys: LWWSet {
        adds: {
            true: 1970-01-01T00:00:01Z_0_00000000-0000-0000-0000-000000000000,
        },
        removes: {},
    },
    values: {
        true: Max(
            true,
        ),
    },
}

c = LWWMap {
    keys: LWWSet {
        adds: {
            true: 1970-01-01T00:00:01Z_2_00000000-0000-0000-0000-000000000000,
        },
        removes: {},
    },
    values: {
        true: Max(
            false,
        ),
    },
}

不同合并顺序得到的结果不一致：

• 执行a.merge(b.merge(c))最终得到{true: true}
• 执行a.merge(b).merge(c)最终得到{true: false}

我知道可以通过永久保留所有键值对解决问题，但相关算法说明称合并时可安全移除未使用值。我是否忽略了什么？需满足哪些条件才能保证结合性？

你的问题核心在于错误地在合并时移除了被标记为删除的key对应的value，这直接破坏了CRDT的结合性，同时误解了“安全移除未使用值”的前提条件。

为什么结合性被破坏？ #

我们拆解两种合并顺序的差异：

1. 顺序1：a.merge(b.merge(c))

   • 先合并b和c：两者的keys合并后，true的add操作（时间戳相同但ID更大的c的add）胜出，key存在。values合并时，Max(true)和Max(false)合并得到Max(true)，因此b.merge(c)的values中保留true: Max(true)。
   • 再合并a和b.merge(c)：合并后的keys中，true的add操作（c的00:01_2）比a的remove操作（00:01_1）优先级更高，key存在。此时a的values中没有true，直接取用b.merge(c)的Max(true)，最终结果为{true: true}。

2. 顺序2：a.merge(b).merge(c)

   • 先合并a和b：合并后的keys中，true的remove操作（a的00:01_1）比b的add操作（00:01_0）优先级更高，key被标记为删除。你的代码会从values中移除true的条目，因此a.merge(b)的values为空。
   • 再合并a.merge(b)和c：合并后的keys中，c的add操作（00:01_2）比a的remove操作优先级更高，key重新存在。但此时a.merge(b)的values中没有true的历史记录，只能取用c的Max(false)，最终结果为{true: false}。

问题的关键是：当key被暂时标记为删除时，你丢弃了其他副本中该key的value历史。一旦后续key被重新添加，你无法再合并之前的value，导致不同合并顺序的结果不一致。

“安全移除未使用值”的前提 #

相关算法中提到的“安全移除未使用值”，仅适用于该key的remove操作是最终的、不可被覆盖的场景——也就是你能确定未来不会有任何add操作的优先级超过这个remove操作（比如所有节点都同意该key被永久删除，且不会再添加）。但在标准LWW CRDT模型中，这一点无法保证：分布式环境下可能存在延迟的add操作，或者后续节点可以再次添加该key。

保证结合性的条件 #

要让你的LWWMap满足结合性，必须确保：

• 保留所有key的value历史，即使当前key被标记为删除。merge操作需要合并所有双方存在的key的value，而不仅仅是当前keys集合中存在的key。
• 查询map的当前状态时，只返回keys集合中存在的key对应的value。

修改后的merge逻辑可以调整为：

impl<K, V> Merge for LWWMap<K, V>
where
    K: Ord + Clone,
    V: Merge,
{
    fn merge_mut(&mut self, mut other: Self) {
        self.keys.merge_mut(other.keys);

        // 合并所有存在于self或other中的key的value
        let all_keys: std::collections::BTreeSet<_> = self.values.keys()
            .chain(other.values.keys())
            .cloned()
            .collect();

        for key in all_keys {
            match (self.values.remove(&key), other.values.remove(&key)) {
                (Some(mut self_val), Some(other_val)) => {
                    self_val.merge_mut(other_val);
                    self.values.insert(key, self_val);
                }
                (Some(val), None) => {
                    self.values.insert(key, val);
                }
                (None, Some(val)) => {
                    self.values.insert(key, val);
                }
                (None, None) => {}
            }
        }

        // 可选：仅在确定key的remove是最终操作时清理，否则不要删除
        // self.values.retain(|k, _| self.keys.contains(k));
    }
}

这样，无论key当前是否存在，所有value的历史都会被合并。查询时再通过keys过滤，就能保证合并的结合性。

内容的提问来源于stack exchange，提问作者Brian Hicks