各位观众，各位朋友，欢迎来到今天的Redis茶话会！今天我们要聊的是Redis里一个听起来高大上，但其实挺好玩的数据结构——HyperLogLog，简称HLL。这玩意儿，简单来说，就是用来估算集合里有多少个不同元素的。
你可能会问：“估算？为啥不用集合直接存？精准它不香吗？” 哎，这就是HLL的妙处所在。当你的数据量大到爆炸，比如几百万、几千万甚至上亿的时候，直接存可就爆炸了你的内存。HLL呢，它用极小的内存，就能给你一个相当靠谱的估算结果。就像你猜瓜子数量，不用一颗颗数，看看体积大概就能估个八九不离十。
那HLL是怎么做到的呢？关键就在于它的内部存储结构：稀疏表示和稠密表示。 这就好比你家衣柜，衣服少的时候随便塞，衣服多了就要整理一下才能塞更多。
一、HLL的原理：抛硬币的哲学
在深入了解稀疏和稠密表示之前，我们先来理解HLL的核心思想。这思想，说白了，就是抛硬币。
想象一下，你不停地抛硬币，直到出现正面为止。记录你抛了多少次才出现正面。如果让你估计你总共抛了多少次，你会怎么做？
是不是感觉有点懵？别急，咱们换个角度。如果我告诉你，你抛了100次硬币，最长的一次连续反面的次数是5次，你觉得你总共抛了多少次硬币？
直觉告诉你，应该远远超过100次吧？因为连续出现5次反面的概率比较小。
HLL就是基于这个思想。它把每个元素通过哈希函数映射成一个二进制串，然后观察这个二进制串中从低位开始，连续出现多少个0。这个连续0的个数，就代表了“抛硬币”的结果。
如果所有元素中，最大的连续0的个数是n，那么HLL就估计总共有 2^n 个不同的元素。
这个 2^n 就是对基数的估计值。 当然，实际情况要复杂一些，HLL会使用多个“抛硬币器”（也就是多个寄存器），然后取平均值，来减少误差。
二、稀疏表示：小数据量的精打细算
当你的HLL里数据量比较小的时候，HLL会采用稀疏表示。 稀疏表示就像你刚搬进新家，衣服不多，随便往衣柜里一扔就行。
稀疏表示的核心思想是：只记录非零的寄存器。
具体来说，Redis的HLL的稀疏表示使用两种数据结构：
- ziplist: 当HLL非常小的时候，Redis会使用ziplist来存储。ziplist是一种紧凑的线性数据结构，它会把所有寄存器的索引和值都存储在一起。 ziplist的好处是节省空间，但缺点是插入和查找效率比较低。
- listpack: 当ziplist不够用的时候，Redis会使用listpack来存储。listpack是Redis 7.0引入的一种新的数据结构，它比ziplist更节省空间，并且插入和查找效率更高。
稀疏表示的优势在于：
- 节省内存: 只存储非零的寄存器，大大减少了内存占用。
- 简单高效: 对于小数据量，插入和查找操作都比较快。
稀疏表示的劣势在于：
- 扩展性差: 当数据量增大时，稀疏表示会变得非常低效。
- 合并效率低: 合并多个HLL时，需要遍历所有寄存器，效率较低。
下面我们用伪代码来模拟一下稀疏表示的存储结构：
class SparseHLL:
def __init__(self):
# 使用字典来存储寄存器，key是索引，value是值
self.registers = {}
def set_register(self, index, value):
self.registers[index] = value
def get_register(self, index):
return self.registers.get(index, 0) # 默认值为0
def merge(self, other_hll):
# 合并两个HLL
for index, value in other_hll.registers.items():
current_value = self.get_register(index)
self.set_register(index, max(current_value, value))
# 示例
hll1 = SparseHLL()
hll1.set_register(10, 3)
hll1.set_register(20, 5)
hll2 = SparseHLL()
hll2.set_register(10, 4)
hll2.set_register(30, 2)
hll1.merge(hll2)
print(hll1.registers) # 输出: {10: 4, 20: 5, 30: 2}这个例子展示了稀疏表示的基本操作：设置寄存器、获取寄存器和合并HLL。 注意，这里我们用字典来模拟存储寄存器，实际Redis内部使用的是ziplist或者listpack。
三、稠密表示：大数据量的力挽狂澜
当你的HLL里的数据量增大到一定程度，稀疏表示就扛不住了。这时候，HLL会转换为稠密表示。 稠密表示就像你把衣服整理好，一件件叠起来，充分利用衣柜的每一寸空间。
稠密表示的核心思想是：使用一个固定大小的数组来存储所有寄存器。
在Redis中，HLL的稠密表示使用一个16384个字节的数组。每个字节代表一个寄存器。 为什么要用16384个字节呢？ 这是因为HLL使用了14位的哈希值来选择寄存器，所以总共有 2^14 = 16384 个寄存器。
稠密表示的优势在于：
- 扩展性强: 可以处理大量数据。
- 合并效率高: 合并多个HLL时，只需要遍历数组，效率较高。
稠密表示的劣势在于：
- 内存占用高: 即使数据量很小，也要占用16384个字节。
- 插入和查找效率相对较低: 需要计算哈希值和索引。
下面我们用伪代码来模拟一下稠密表示的存储结构：
class DenseHLL:
def __init__(self):
# 使用数组来存储寄存器
self.registers = [0] * 16384
def set_register(self, index, value):
self.registers[index] = value
def get_register(self, index):
return self.registers[index]
def merge(self, other_hll):
# 合并两个HLL
for i in range(16384):
self.registers[i] = max(self.registers[i], other_hll.registers[i])
# 示例
hll1 = DenseHLL()
hll1.set_register(10, 3)
hll1.set_register(20, 5)
hll2 = DenseHLL()
hll2.set_register(10, 4)
hll2.set_register(30, 2)
hll1.merge(hll2)
print(hll1.registers[9:31]) # 输出: [0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0]这个例子展示了稠密表示的基本操作。 注意，这里我们用Python的列表来模拟数组，实际Redis内部使用的是C语言的数组。
四、稀疏到稠密的转换：华丽的转身
HLL会在什么时候从稀疏表示转换为稠密表示呢？ 这个转换的时机是由一个阈值控制的。 当HLL中非零的寄存器数量超过阈值时，HLL就会自动转换为稠密表示。
这个阈值是可以配置的，默认值是hll_sparse_max_bytes，可以在redis.conf文件中设置。
转换的过程其实也很简单：
- 创建一个16384个字节的数组。
- 遍历稀疏表示中的所有寄存器，将它们的值复制到数组中。
- 释放稀疏表示占用的内存。
转换完成后，HLL就变成了稠密表示，可以处理更多的数据了。
下面我们用伪代码来模拟一下稀疏到稠密的转换过程：
def sparse_to_dense(sparse_hll):
dense_hll = DenseHLL()
for index, value in sparse_hll.registers.items():
dense_hll.set_register(index, value)
# 释放稀疏表示占用的内存（这里省略）
return dense_hll
# 示例
sparse_hll = SparseHLL()
# 假设sparse_hll有很多数据，超过了阈值
for i in range(1000):
sparse_hll.set_register(i, i % 10)
dense_hll = sparse_to_dense(sparse_hll)
print(type(dense_hll)) # 输出: <class '__main__.DenseHLL'>五、HLL的实际应用：流量统计、用户去重
HLL的应用场景非常广泛，只要涉及到统计不同元素个数的场景，都可以考虑使用HLL。
- 流量统计: 统计网站的UV（Unique Visitor），也就是独立访客数。 使用HLL可以大大减少内存占用，即使网站有数百万的UV，也只需要几KB的内存。
- 用户去重: 统计APP的DAU（Daily Active User），也就是日活跃用户数。 HLL可以快速地对用户进行去重，避免重复计算。
- 社交网络: 统计某个话题的独立参与用户数。
- 搜索引擎: 统计某个关键词的独立搜索用户数。
六、HLL的Redis命令：简单易用
Redis提供了以下几个HLL相关的命令：
PFADD key element [element ...]：向HLL中添加元素。PFCOUNT key [key ...]：获取HLL的基数估计值。PFMERGE destkey sourcekey [sourcekey ...]：合并多个HLL。
这些命令都非常简单易用，可以轻松地在Redis中使用HLL。
下面我们来演示一下如何在Redis中使用HLL：
# 添加元素
PFADD myhll a
PFADD myhll b
PFADD myhll c
# 获取基数估计值
PFCOUNT myhll # 输出: (integer) 3
# 添加更多元素
PFADD myhll d
PFADD myhll e
# 再次获取基数估计值
PFCOUNT myhll # 输出: (integer) 5
# 创建另一个HLL
PFADD anotherhll f
PFADD anotherhll g
# 合并两个HLL
PFMERGE combinedhll myhll anotherhll
# 获取合并后的基数估计值
PFCOUNT combinedhll # 输出: (integer) 7七、HLL的误差：鱼和熊掌不可兼得
HLL是一种概率数据结构，它会产生一定的误差。 这个误差是可以控制的，但是误差越小，需要的内存就越多。
Redis的HLL的误差率大概是0.81%。 这意味着，如果你使用HLL来统计1000个不同的元素，那么估计的结果可能会在992到1008之间。
在实际应用中，需要根据业务的需求来权衡误差和内存占用。 如果对精度要求不高，可以使用HLL来节省大量的内存。 如果对精度要求很高，可以考虑使用其他数据结构，比如集合。
八、HLL的总结：小身材，大能量
总而言之，Redis的HLL是一种非常实用的数据结构。 它可以用极小的内存来估算集合的基数，适用于大数据量的场景。 HLL内部使用了稀疏表示和稠密表示两种存储结构，可以根据数据量的大小自动切换。 HLL的误差是可以控制的，可以根据业务的需求来权衡精度和内存占用。
HLL就像一个身材娇小的魔法师，它可以用简单的咒语（算法）来解决复杂的问题（基数估计）。 在你的Redis工具箱里，HLL绝对是一个值得拥有的利器。
九、代码示例：更深入的理解
为了更深入地理解HLL的原理和实现，我们再来编写一些代码示例。
1. 模拟哈希函数和计算连续0的个数
import hashlib
def hash_element(element):
"""
使用SHA256哈希函数将元素转换为二进制串
"""
hash_object = hashlib.sha256(element.encode())
hex_dig = hash_object.hexdigest()
# 将16进制字符串转换为二进制字符串
binary_string = bin(int(hex_dig, 16))[2:].zfill(256) # 保证长度为256位
return binary_string
def count_leading_zeros(binary_string):
"""
计算二进制串中从低位开始连续0的个数
"""
count = 0
for bit in reversed(binary_string):
if bit == '0':
count += 1
else:
break
return count
# 示例
element = "hello world"
binary_string = hash_element(element)
leading_zeros = count_leading_zeros(binary_string)
print(f"Element: {element}")
print(f"Binary String: {binary_string[:20]}...") # 只显示前20位
print(f"Leading Zeros: {leading_zeros}")2. 模拟HLL的简化版实现
import hashlib
import random
class SimpleHLL:
def __init__(self, num_registers=16): # 为了简化，使用较少的寄存器
self.num_registers = num_registers
self.registers = [0] * num_registers
def hash_element(self, element):
"""
使用SHA256哈希函数将元素转换为二进制串
"""
hash_object = hashlib.sha256(element.encode())
hex_dig = hash_object.hexdigest()
# 将16进制字符串转换为二进制字符串
binary_string = bin(int(hex_dig, 16))[2:].zfill(256) # 保证长度为256位
return binary_string
def count_leading_zeros(self, binary_string):
"""
计算二进制串中从低位开始连续0的个数
"""
count = 0
for bit in reversed(binary_string):
if bit == '0':
count += 1
else:
break
return count
def add(self, element):
"""
向HLL中添加元素
"""
binary_string = self.hash_element(element)
leading_zeros = self.count_leading_zeros(binary_string)
# 使用前4位作为寄存器索引 (假设有16个寄存器)
register_index = int(binary_string[:4], 2)
self.registers[register_index] = max(self.registers[register_index], leading_zeros)
def estimate_cardinality(self):
"""
估算基数
"""
alpha = 0.7213 / (1 + 1.079 / self.num_registers) # 根据寄存器数量调整
harmonic_mean = 0.0
for register_value in self.registers:
harmonic_mean += 1.0 / (2 ** register_value)
estimate = alpha * (self.num_registers ** 2) / harmonic_mean
return int(estimate) # 返回整数结果
# 示例
hll = SimpleHLL()
elements = [f"user_{i}" for i in range(100)] # 添加100个不同的元素
for element in elements:
hll.add(element)
estimated_cardinality = hll.estimate_cardinality()
print(f"Estimated Cardinality: {estimated_cardinality}")
print(f"Actual Cardinality: {len(elements)}")这个简化版的HLL实现，使用了较少的寄存器，并且省略了一些优化步骤，但是它可以帮助你理解HLL的基本原理。 实际Redis的HLL实现要复杂得多，它使用了更多的寄存器，并且使用了更复杂的算法来提高精度。
十、Q & A环节：解答你的疑惑
-
问：HLL的误差率可以降低吗？
答：可以。增加寄存器的数量可以降低误差率。但是，增加寄存器的数量也会增加内存占用。
-
问：HLL适用于所有场景吗？
答：不是。HLL只适用于需要估算基数的场景。如果需要精确的基数，或者需要存储元素本身，就不适合使用HLL。
-
问：HLL的性能如何？
答：HLL的性能非常高。添加元素和获取基数估计值的操作都可以在常数时间内完成。
-
问：稀疏表示和稠密表示的切换是自动的吗？
答：是的。Redis会自动根据数据量的大小来切换稀疏表示和稠密表示。
希望今天的茶话会对你有所帮助！ 感谢大家的观看，我们下次再见！