algorithm - 实时数据一致性检查的好算法

Question

给定多个服务器(不止一个)，每个服务器存储以下信息:

key1 => value1
key2 => value2
key1 => newValue1
key3 => value3
...
key4 => value4
...
key3 => newValue3
...
keyN => valueN

每个服务器接收到的键值对是实时按顺序过来的。我们想设计一个监控程序来自动检查不同服务器之间的数据一致性。

建议 1> 最简单的想法是为服务器上的每个(键值)对构建一个哈希表。然而哈希表的大小非常大，如果我们必须每分钟/秒都比较全表，那将会非常慢。每台服务器接收到的数据序列都有一定的网络延迟，因此我们必须不断地检查跨多台服务器的一致性。

建议 2> 如果我们不关心哪个键值不一致，那么我们可以根据每个(键值)对生成一个唯一的哈希值，并比较计算出的哈希值服务器。但是，这种方法无法帮助识别服务器之间丢失或不匹配的键值对。

问题> 这个问题应该很常见，我们希望有一个预先存在的算法可以帮助我们有效地解决问题。欢迎提出任何建议。

谢谢

Answer 1

可能正在寻找 Merkle Tree .

在默克尔树中，每片叶子都是一个键值对，以及它的哈希值。
每个内部节点都是其子节点值的某种组合(它们的值的散列是常见的做法)。

这允许您(很有可能):

1. 快速(O(1))检查两个服务器是否存储了相同的键值。
2. 找到每个不匹配项(添加/更改的键值对)的对数时间。
3. 每个服务器中每个条目的对数时间插入/删除/修改。