对于一个已经上线的系统，常常需要统计一些数据用于支撑运营团队的决策。

对于于不同的数据量，作为开发人员，我们应该如何选择合适的数据结构去完成需求。

开发人员考虑的层面，一是数据量，就是存储这些数据需要暂用内存块的大小；二是这种数据结构的插入、删除、修改、统计的时间复杂度的问题。

统计用户UV，从业务上我们常常会想到使用集合（Set），集合存储的数据不能重复，所以将用户IP直接存储到 Set 可以很完美地解决问题。

下面我们通过Set、HyperLogLogs 两个例子来体会一下。

数据量100W，存储1-100w的值。

有序列表Set

将100w的数据量写入Set结构。

代码

<?php
//连接本地的 Redis 服务
$redis = new Redis();
$redis->connect('redis', 6379);

// 因为写入数据量较大，所以我们采用 pipeline 来优化写入性能 
$pipline = $redis->multi(Redis::PIPELINE);
for($i = 0; $i < 1000000; $i++){
    $pipline->sAdd('num' , $i); 
}
$pipline->exec();

这里同时插入100W条数据，写入压力较大，所以使用 pipeline 作了优化。

命令行执行

php ceshi.php

结果截图

截图里面最重要的信息是 set 占用了 4934341 B的内存空间，也就是 4M 的内存空间。

set在存储大数据量的时候使用的底层数据结构是 字典（dict），插入的时间复杂度为O(1)，

统计的时间复杂度为O(1）。

HyperLogLogs

将100w的数据量写入 HyperLogLogs结构。

代码

<?php
//连接本地的 Redis 服务
$redis = new Redis();
$redis->connect('redis', 6379);

// 因为写入数据量较大，所以我们采用 pipeline 来优化写入性能 
$pipline = $redis->multi(Redis::PIPELINE);
for($i = 0; $i < 1000000; $i++){
    $redis->rawCommand('pfadd','numpf', $i);
}
$pipline->exec();

命令行执行

php ceshi.php

结果截图

这里我们程序插入的数据数量为 100w条， 这里却是 1009972 条。内存占用为 10587B，大约10KB。

hyperLogLogs是基于 概率统计 的，统计的结果数量误差在 1% 以内。这个数据结构是为了使用小的内存空间统计大量的元素。

hyperLogLogs使用的底层数据结构为 bit，该结构使用 2^14 个桶，2^6 表示一个桶，统计2^64 的数据，数据量较大时，单个key固定占用的内存为12K。

hyperLogLogs的插入时间复杂度为O(1)，统计的 平均复杂度 为O(1)。

Set\HyperLogLogs对比

• 两者在插入时的性能是一样的。
• 统计时Set的性能会比HyperLogLogs高。因为 dict 结构体有一个字段 used 可以直接返回。HyperLogLogs 统计时会根据缓存是否过期（每次新增数据时会设置过期）来判断是否重新计算数量，如果过期重新计算，如果没有过期则直接返回 card 结构体字段。
• 内存占用方面，同样100w数据，Set 占用 4M 空间， HyperLogLogs 占用 10K空间。
• dict 结构在数据逐渐增大的时候，会 rehash 扩容，对性能的损耗是比较大的。

综合对比之下，在统计系统UV的场景中，HyperLogLogs 结构更加合适。