distchen / distchen.github.io Goto Github PK

在数学上，基数是集合论中刻画任意集合大小的一个概念。

除了Redis的五种常见数据类型外(#1 )，Redis提供了HyperLogLog结构。这个结构可以非常省内存的去统计各种计数，比如注册ip数、每日访问IP数、页面实时UV、在线用户数等。

这里看到所有的用处都是xxx数，所以这个数据结构的特点就是，可以比较准确的估算出你要统计的数量，但是却无法知道统计的详细内容。比如统计每日访问IP数，可以获取当时访问过的IP总数量，但是没法知道这些IP都是什么。

有得必有失，当然你要统计上面提到的那些内容，可以用集合来处理，这样可以知道数量，也能获得所有的详细列表。但是一个大型的网站，每天IP比如有100万个呢，我们粗算一个IP消耗15字节，那么100万个IP就是15M，如果1千万，就是150M。

再来看看HyperLogLog，在Redis中每个键占用的内容都是12K，理论存储近似接近2^64个值，不管存储的内容是什么。12K，知道这个数据结构的作用了吧。这也是为什么他不能知道里面的详细内容了。这是一个基于基数估算的算法，只能比较准确的估算出基数，可以使用少量固定的内存去存储并识别集合中的唯一元素。而且这个估算的基数并不一定准确，是一个带有 0.81% 标准错误（standard error）的近似值。

HyperLogLog结构，在范围允许的情况下无论多少值，都只会占用12K内存。

这样比如我们把每日IP记录下来，假设每天有一亿个IP访问，如果使用集合的话，一天的内存使用就是1.5G，假设我们存储一个月的记录，就需要45G容量。但是使用HyperLogLog的话，一天12K，一个月360K。如果我们不需要知道IP具体信息的话，完全可以把这些记录留在内存一年、或者不删都行。如果需要，我们也会把所有的IP访问记录通过其他途径存储起来。把每天的信息存储起来，我们可以计算每月IP总数（MERGE），一年的IP总数等（去重）。

下面介绍一下HyperLogLog的命令，其实他和集合的命令比较像，只是命令少，不能获取列表而已。另外这个数据结构需要2.8.9及以上的版本才能使用。

pfadd

• 格式：pfadd key element [element ...]
• 说明：将所有元素参数添加到 HyperLogLog 数据结构中

在执行这个命令之后，HyperLogLog内部的结构会被更新，如果执行完之后HyperLogLog内部的基数估算发生了变化，那么就会返回1，否则（认为已经存在）就返回0。

这个命令还可以只有键，没有值，这样就只是创建空的键，不放值。如果这个键存在，不做任何事情，返回0；不存在的话就创建，并返回1。

redis> pfadd  ip:20160929  "1.1.1.1"  "2.2.2.2"  "3.3.3.3"
(integer) 1
redis> pfadd  ip:20160929 "2.2.2.2"  "4.4.4.4"  "5.5.5.5"  # 存在就只加新的
(integer) 1
redis> pfcount  ip:20160929  #元素估计数量没有变化
(integer) 5
redis> pfadd  ip:20160929 "2.2.2.2"  # 存在就不会增加
(integer) 0

pfcount

• 格式：pfcount key [key ...]
• 说明：返回给定 HyperLogLog 的基数估算值

当命令作用于单个键的时候，返回这个键的基数估算值。如果键不存在，则返回0。
当作用于多个键的时候，返回这些键的并集估算值。类似于把这些键都合并了之后，在调用这个命令输出。

这个命令在作用于单个值的时候，时间复杂度为O(1)，并且具有非常低的平均常数时间；在作用于N个值的时候，时间复杂度为O(N)，这个命令的常数复杂度会比较低些。

redis> pfadd  ip:20160929  "1.1.1.1"  "2.2.2.2"  "3.3.3.3"
(integer) 1
redis> pfcount  ip:20160929
(integer) 3
redis> pfadd  ip:20160928  "1.1.1.1"  "4.4.4.4"  "5.5.5.5"
(integer) 1
redis> pfcount  ip:20160928  ip:20160929
(integer) 5

pfmerge

• 格式：pfmerge destkey sourcekey [sourcekey ...]
• 说明：将多个HyperLogLog合并为一个HyperLogLog，合并后的HyperLogLog的基数估算值是通过对所有给定HyperLogLog进行并集计算得出的

这个命令的时间复杂度为O(N)，其中N为要合并的HyperLogLog的个数。不过这个命令的常数时间复杂度比较高。

redis> pfadd  ip:20160929  "1.1.1.1"  "2.2.2.2"  "3.3.3.3"
(integer) 1
redis> pfadd  ip:20160928  "1.1.1.1"  "4.4.4.4"  "5.5.5.5"
(integer) 1
redis> pfmerge ip:201609   ip:20160928   ip:20160929
OK
redis> pfcount  ip:201609
(integer) 5

关于HLL算法

数据量一大，统计基数也成了一个麻烦事。进行基数统计时，使用Hyperloglog算法，占用内存小，误差小，实乃不错的方法。

算法的论文是《HyperLogLog the analysis of a near-optimal cardinality estimation algorithm》，可以在谷歌学术上下载下来看看，简述下其**核心。

在理想状态下，将一堆数据hash至[0,1]，每两点距离相等，1/间距 即可得出这堆数据的基数。然而实际情况往往不能如愿，只能通过一些修正不断的逼近这个实际的基数。实际采用的方式一是分桶，二是取kmax。分桶将数据分为m组，每组取第k个位置的值，所有组中得到最大的kmax，(k-1)/kmax得到估计的基数。

HLL算法的另一个主观上的理解可以用抛硬币的方式来理解。以当硬币抛出反面为一次过程，当你抛n次硬币全为正面的概率为1/2^n。当你经历过k(k很大时)次这样的过程，硬币不出现反面的概率基本为0。假设反面为1，正面为0，每抛一次记录1或者0，当记录上显示为0000000...001时，这种可以归结为小概率事件，基本不会发生。转换到基数的想法就是，可以通过第一个1出现前0的个数n来统计基数，基数大致为2^(n+1)时。硬币当中可以统计为(1/21+1/42+1/8*3...)，大致可以这么去想。

hll算法java实现参考。

https://blog.csdn.net/x1066988452/article/details/55051809

BitMap是什么？

BitMap就是通过一个bit位来表示某个元素对应的值或者状态，其中key就是对应元素本身。在某些特定的应用场景下，使用BitMap非常适合，如：

• 用户签到：统计今天有多少人签到，某人今天是否签到等；
• 用户在线状态：有多少人在线，某人是否在线；
• 活跃用户统计：一个月来登录次数超过10次的为活跃用户；
• ......

还有很多其它应用场景，使用BitMap的场景大多在于需要记录对象状态（登录、签到、打开、关闭等），这里的对象可以是用户，也可以是其它。总的来说，只要需要记录状态与否，BitMap可能就有用武之地。

Redis 中的 BitMap

Redis从2.2.0开始新增了如下三个与bitmap相关的命令：

• setbit
• getbit
• bitcount

在介绍这三个命令之前，先看一个神奇的示例：

127.0.0.1:6379> set demo B
OK
127.0.0.1:6379> get demo
"B"
127.0.0.1:6379> setbit demo 7 1
(integer) 0
127.0.0.1:6379> get demo
"C"

可以看到，使用了一条setbit demo 7 1命令之后，demo 的值就从B 就变成了 C，这是怎么发生的？

setbit

• 格式：setbit key offset value
• 说明：针对string类型(#1 )，设置或者清空key的value在offset处的bit值(只能只0或者1)：
  • 当 key 不存在时，自动生成一个新的字符串值。
  • 字符串会进行伸展(grown)以确保它可以将value保存在指定的偏移量上。当字符串值进行伸展时，空白位置以 0 填充。
  • offset 参数必须大于或等于0，小于 2^32 (bit 映射被限制在 512 MB 之内)

结合上面的示例，我们来对此命令进行解释。首先我们应该知道：

再看指令说明，设置value指定offset处的bit值，那么setbit demo 7 1 就是将字符B的第7位设置为1，也就是将01000010的最后一个0设为1。因此值变成了01000011，也就是字符C，这就是字符变化的原因。

如何将C变回去，很简单，将第7位变成0即可：

127.0.0.1:6379> set demo C
OK
127.0.0.1:6379> setbit demo 7 0
(integer) 1
127.0.0.1:6379> get demo
"B"

事实上，bit的取值也只能是0或1。

getbit

• 格式：getbit key offset
• 说明：对key所储存的字符串值，获取指定偏移量上的位(bit)：
  • 当 offset 比字符串值的长度大，或者key不存在时，返回 0 。

弄明白了setbit，getbit就很好理解了：取出字符串指定偏移上的bit：

127.0.0.1:6379> set demo B
OK
127.0.0.1:6379> getbit demo 6
(integer) 1
127.0.0.1:6379> getbit demo 7
(integer) 0

字符B的二进制是01000010。

bitcount

• 格式：bitcount key [start end]
• 说明：计算给定字符串中，被设置为1的比特位的数量：
  • 一般情况下，给定的整个字符串都会被进行计数，通过指定额外的start或end参数，可以让计数只在特定的位上进行。
  • start和end参数的设置和GETRANGE命令类似，都可以使用负数值：比如-1表示最后一个字节，-2表示倒数第二个字节，以此类推。
  • 不存在的key被当成是空字符串来处理，因此对一个不存在的key进行bitcount操作，结果为0。

127.0.0.1:6379> set demo B
OK
127.0.0.1:6379> bitcount demo
(integer) 2

补充

bit的取值只能是0或者1，如果每一位代表一个对象，那么一个key就可以记录2^32个对象的状态，占用空间 2^32bit = 512Mb。

除此外，数据库中位图索引的实现(#6 )也与此类似。

Redis 3.2版本之后，新增了对GEO(地理位置)的支持(#1 )，地理位置大概提供了6个命令，分别为：

• GEOADD
• GEODIST
• GEOHASH
• GEOPOS
• GEORADIUS
• GEORADIUSBYMEMBER

http://www.cnblogs.com/LBSer/p/3322630.html