Active-Active 数据库中的 HyperLogLog
有关将 hyperloglog 与主动-主动数据库一起使用的信息。
| Redis 企业软件 | Redis 云 |
|---|
HyperLogLog 是一种解决 count-distinct 问题的算法。 为此，它近似于一组中的项数。 根据集合的基数确定集合的确切基数需要内存。 由于 HyperLogLog 算法通过概率估计基数，因此可以在更合理的内存要求下运行。
Redis 中的 HyperLogLog
Redis 社区版实现了 HyperLogLog （HLL） 作为原生数据结构。 它支持将元素 （PFADD 添加到 HLL、对元素进行计数 （PLL 计数）以及合并 （PFMERGE HLL.
下面是一个简单写入情况的示例：
| 时间 | 副本 1 | 副本 2 |
|---|---|---|
| T1 | PFADD hll x | |
| T2 | ---同步--- | |
| T3 | PFADD hll y | |
| T4 | ---同步--- | |
| T5 | PFCOUNT hll --> 2 | PFCOUNT hll --> 2 |
以下是并发 add 案例的示例：
| 时间 | 副本 1 | 副本 2 |
|---|---|---|
| T1 | PFADD hll x | PFADD hll y |
| T2 | PFCOUNT hll --> 1 | PFCOUNT hll --> 1 |
| T3 | ---同步--- | |
| T4 | PFCOUNT hll --> 2 | PFCOUNT hll --> 2 |
DEL-wins 方法
Redis-CRDT 实现中的其他集合使用观察到的 remove 方法来解决冲突。 CRDT-HLL 使用 DEL-wins 方法。 如果同时收到 DEL 请求和 HLL 键上的任何其他请求 （ADD/MERGE/EXPIRE） 副本始终聚合以删除键。 在其他集合（集合、列表、排序集和哈希）使用的 observed remove 方法中， 只有收到 DEL 请求的副本会删除元素，但同时添加到其他副本中的元素存在于一致聚合的集合中。 我们选择对 CRDT-HLL 使用 DEL-wins 方法，以保持 Redis 社区版中 HLL 的原始时间和空间复杂度。
以下是 DEL-wins 案例的示例：
| HLL | | | 设置 | ||||
|---|---|---|---|---|---|---|
| | | ||||||
| 时间 | 副本 1 | 副本 2 | | | 时间 | 副本 1 | 副本 2 |
| | | ||||||
| T1 | PFADD h e1 | | | T1 | SADD s e1 | ||
| T2 | ---同步--- | | | T2 | ---同步--- | ||
| T3 | PFCOUNT h --> 1 | PFCOUNT h --> 1 | | | T3 | SCARD s --> 1 | SCARD s --> 1 |
| T4 | PFADD h e2 | Del h | | | T4 | SADD s e2 | Del S |
| T5 | PFCOUNT h --> 2 | PFCOUNT h --> 0 | | | T5 | SCARD s --> 2 | SCARD s --> 0 |
| T6 | ---同步--- | | | T6 | ---同步--- | ||
| T7 | PFCOUNT h --> 0 | PFCOUNT h --> 0 | | | T7 | SCARD s --> 1 | SCARD s --> 1 |
| T8 | 存在 h --> 0 | 存在 h --> 0 | | | T8 | 存在 s --> 1 | 存在 s --> 1 |
| | | T9 | SMEMBERS s --> {e2} | SMEMBERS s --> {e2} |
主动-主动数据库中的 HLL 与 Redis 社区版中的 HLL
在主动-主动数据库中，我们在 Redis 实现的基础上在 CRDT 中实施了 HLL，但有一些例外：
- Redis 将 HLL 数据结构保存为编码字符串对象 这样，您就可以对包含 HLL 的键运行任何字符串请求 CAN。在 CRDT 中，HLL 仅支持 get 和 set。
- 在 CRDT 中，如果对包含编码为 HLL 的值的键执行 SET，则该值将保持为 HLL。如果该值未编码为 HLL，则它将是一个 register。