redis之特殊数据类型

bitmap

bitmap即位图，是一种基于位运算的数据结构，用连续的二进制位描述某些业务，例如用户的签到状态等。redis中的string是二进制安全的，故而使用string来描述这个位图。
相比其他数据结构，位图所占用的存储空间非常小，在上述的业务场景，使用位图更加高效。

Redis提供了SETBIT、GETBIT 、BITCOUNT 、BITOP四个命令，用于处理二进制数组

SETBIT

1	SETBIT key offset value

SETBIT用于将二进制数组在偏移量位置处的二进制值设置为value，当key不存在时，会自动生成一个新的字符串值。字符串会扩展以确保可以在offset位置上设置value值，当字符串扩展时，空白位置以0填充 offset>=0，小于512M
注意对于较大的OFFSET值，命令执行过程中的内存分配可能阻塞redis服务器。

123.122.10.231:6379> setbit bitmap 10086 1
(integer) 0
123.122.10.231:6379> getbit bitmap 10086
(integer) 1

setbit的执行过程

计算保存offset偏移量指定的二进制位至少需要多少个字节：
len=[offset/8] + 1 向下取整。
检查这个位图对应的redisObject.ptr指向的sdshar的len字段
是否小于步骤1中计算的len值，如果小于，则将sds的长度扩展为len字节，并将所有扩展空间的二进制位设置为0。
计算offset偏移量指定的二进制位保存在哪一个字节：
byte=offset/8。
计算offset偏移量指定的二进制位在byte个字节中的第几个二进制位：
bit=offser%8 + 1。
根据计算得出的byte和bit定位到二进制数组中offset的位置，将旧值存储在oldvalue中，并将其值修改为value指定的值。
最后，向客户端返回oldvalue的值。

上述计算过程均可以在常数时间内完成，故而其时间复杂度为O(1)

GETBIT

1	GETBIT key offset

获取二进制数组key指定偏移量offset处的值。当offset比字符串值的长度大或者key不存在时，返回0。

1 2	123.122.10.231:6379> getbit bitmap 10086 (integer) 1

getbit的执行过程

和setbit类似，核心就是计算byte和bit。命令执行过程如下：

计算byte
计算bit
根据byte 和 bit定位到二进制数组中偏移量位置，读取该位置上的值

上述过程的时间复杂度也为O(1)

BITCOUNT

此命令经常被用于统计用户上线次数等业务：模式：使用 bitmap 实现用户上线次数统计

1	BITCOUNT key [start] [end]

计算给定字符串key中，被设置为1的比特位数量；也可以只计算start到stop指定的字节范围的二进制数组。

123.122.10.231:6379> getbit bitmap 10086
(integer) 1
123.122.10.231:6379> bitcount bitmap
(integer) 1
123.122.10.231:6379> setbit bitmap 1 1
(integer) 0
123.122.10.231:6379> setbit bitmap 2 1
(integer) 0
123.122.10.231:6379> bitcount bitmap
(integer) 3

bitcount实现原理

在数学上，统计一个二进制数组中，非0二进制位的数量，被称作计算汉明重量，该算法通过一系列位移和位运算操作，可以在常数时间内计算多个字节的汉明重量，并且不需要使用任何额外的内存。
参见variable-precision swar算法
redis使用查表法+swar实现：
redis中采用的实现源码如下：

/* Count number of bits set in the binary array pointed by 's' and long
 * 'count' bytes. The implementation of this function is required to
 * work with an input string length up to 512 MB or more (server.proto_max_bulk_len) */
long long redisPopcount(void *s, long count) {
    long long bits = 0;
    unsigned char *p = s;
    uint32_t *p4;
    static const unsigned char bitsinbyte[256] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8};

    /* Count initial bytes not aligned to 32 bit. */
    while((unsigned long)p & 3 && count) {
        bits += bitsinbyte[*p++];
        count--;
    }

    /* Count bits 28 bytes at a time */
    p4 = (uint32_t*)p;
    while(count>=28) {
        uint32_t aux1, aux2, aux3, aux4, aux5, aux6, aux7;

        aux1 = *p4++;
        aux2 = *p4++;
        aux3 = *p4++;
        aux4 = *p4++;
        aux5 = *p4++;
        aux6 = *p4++;
        aux7 = *p4++;
        count -= 28;

        aux1 = aux1 - ((aux1 >> 1) & 0x55555555);
        aux1 = (aux1 & 0x33333333) + ((aux1 >> 2) & 0x33333333);
        aux2 = aux2 - ((aux2 >> 1) & 0x55555555);
        aux2 = (aux2 & 0x33333333) + ((aux2 >> 2) & 0x33333333);
        aux3 = aux3 - ((aux3 >> 1) & 0x55555555);
        aux3 = (aux3 & 0x33333333) + ((aux3 >> 2) & 0x33333333);
        aux4 = aux4 - ((aux4 >> 1) & 0x55555555);
        aux4 = (aux4 & 0x33333333) + ((aux4 >> 2) & 0x33333333);
        aux5 = aux5 - ((aux5 >> 1) & 0x55555555);
        aux5 = (aux5 & 0x33333333) + ((aux5 >> 2) & 0x33333333);
        aux6 = aux6 - ((aux6 >> 1) & 0x55555555);
        aux6 = (aux6 & 0x33333333) + ((aux6 >> 2) & 0x33333333);
        aux7 = aux7 - ((aux7 >> 1) & 0x55555555);
        aux7 = (aux7 & 0x33333333) + ((aux7 >> 2) & 0x33333333);
        bits += ((((aux1 + (aux1 >> 4)) & 0x0F0F0F0F) +
                    ((aux2 + (aux2 >> 4)) & 0x0F0F0F0F) +
                    ((aux3 + (aux3 >> 4)) & 0x0F0F0F0F) +
                    ((aux4 + (aux4 >> 4)) & 0x0F0F0F0F) +
                    ((aux5 + (aux5 >> 4)) & 0x0F0F0F0F) +
                    ((aux6 + (aux6 >> 4)) & 0x0F0F0F0F) +
                    ((aux7 + (aux7 >> 4)) & 0x0F0F0F0F))* 0x01010101) >> 24;
    }
    /* Count the remaining bytes. */
    p = (unsigned char*)p4;
    while(count--) bits += bitsinbyte[*p++];
    return bits;
}

BITOP

1	BITOP operation destkey key [key …]

对一个或多个二进制数组key进行元操作，并将结果保存到二进制数组destkey中。其中operation可以是and、or、not、xor中的任意一种，对应与或非、异或操作。

hyperloglog

hyperloglog并非redis特有，它是一种基于统计的算法，用以计算大数据场景下统计基数的算法：
目前用于基数统计的算法包括：

linear counting(LC): 早期的基数估算算法，时间复杂度是O(N)。
LogLog counting(LLC): 相比LC更节省内存，空间复杂度为O(log(log(N)))。
hyperloglog counting(HLLC): 是基于LLC的优化，在相同的空间复杂度下，比LLC的误差要小。

其优点在于，在输入的元素数量或者所占空间非常大时，计算基数的空间开销非常少。每个hyperloglog键只需要花费12KB的内存，就可以计算2^64个不同元素的基数。
另外，它只会根据输入元素计算基数，不会存储元素本身，所以不能返回各个元素。

常用命令

// 将任意数量的元素添加到指定的hyperloglog中
PFADD key element [element …]

// 返回在给定键的hyperloglog的近似基数，key不存在则返回0
PFCOUNT key [key …]

// 将多个hyperloglog 合并为 一个
PFMERGE destkey sourcekey [sourcekey …]

PFADD命令的返回取决于执行命令后，hyperloglog估计的基数发生变化时，则返回1，否则返回0。命令不会一次性分配12K内存。[具体的扩展原则见源码]

如果该key值不存在，则先创建，再执行此命令。
PFCOUNT返回的基数并不是精确值，而是带有一个0.81%标准错误的近似值。
PFMERGE，将多个hyperloglog合并为一个，合并后的htperloglog的基数接近于所有输入的hyperloglog可见集合的并集。
hyperloglog的源码实现主要参考 P. Flajolet, Éric Fusy, O. Gandouet, and F. Meunier. Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm

实际操作如下：

123.122.10.231:6379> PFADD  database  "Redis"  "MongoDB"  "MySQL"
-> Redirected to slot [246] located at 123.122.42.170:6379
(integer) 1
123.122.42.170:6379> PFADD  database  "PostgreSQL"
(integer) 1
123.122.42.170:6379> PFCOUNT  database
(integer) 4
123.122.42.170:6379> PFADD  database  "PostgreSQL"
(integer) 0
123.122.42.170:6379> PFCOUNT  database
(integer) 4



123.122.42.170:6379>  PFADD  nosql  "Redis"  "MongoDB"  "Memcached"
(integer) 1
123.122.42.170:6379> PFADD  RDBMS  "MySQL" "MSSQL" "PostgreSQL"
(integer) 1
123.122.42.170:6379>  PFMERGE  databases  nosql  RDBMS
OK
123.122.42.170:6379>  PFCOUNT  databases
(integer) 6

使用场景

由于不需要保存数据内容+计算基数特别快，所以非常适合计算日活、月活数据

geo

redis 3.2版本开始提供了geo(地理信息定位)功能，支持存储地理位置信息。

常用命令

// 将给定的空间元素加到指定的键中 [longitude latitude member]， 这些元素会以有序集合的形式被存储在键中
GEOADD key longitude latitude member [longitude latitude member …]

// 从key中获取 给定位置元素的位置，返回经纬度
GEOPOS key member [member …]

// 返回两个给定位置之间的距离 
GEODIST key member1 member2 [unit]

//  以给定的经纬度为中心，返回键中与中心点距离不超过最大距离的所有元素位置
GEORADIUS key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [ASC|DESC] [COUNT count]

// 和GEORADIUS类似，不过是以键中元素作为圆心返回与之距离不超过最大距离的所有元素位置
GEORADIUSBYMEMBER key member radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [ASC|DESC] [COUNT count]

// 返回某元素位置的 geohash表示
GEOHASH key member [member …]

GEOADD命令以标准(x,y)的形式接收输入参数，经度在前，纬度在后。另外，它能够记录的坐标是有限的，非常接近两级的区域无法被索引，精确的坐标限制为:

有效的经度介于 -180 度至 180 度之间。
有效的纬度介于 -85.05112878 度至 85.05112878 度之间。
超出上述范围则会返回错误。

GEODIST命令中默认的单位为m，可选参数有：

m，即米。
km，即千米。
mi，即英里。
ft，即英尺。

geohash: 对于精度维度而言，geohash会将其编码为N位的二进制数，实际上就是通过N次分区实现。
对于某一位置元素，分别对其经度和维度进行编码，得到的两个二进制数，偶数位放置经度值，奇数为放置维度，最后使用base32进行编码即得到最后的输出。
这里要注意的是，geohash算法使用的是peano空间填充曲线，这种曲线会产生突变，会导致编码虽然相似，但其距离可能相差很大的问题。在实际应用中，需要先筛选相似geohash编码相似的点，然后计算实际距离。

123.122.228.34:6379> zrange citys 0 -1 withscores 
 1) "zhuhai"
 2) "4046325959374599"
 3) "guangzhou"
 4) "4046533892156333"
 5) "shenzhen"
 6) "4046615882282816"
 7) "shanghai"
 8) "4066919243534770"
 9) "beijing"
10) "4069885649163649"

geo中使用某种编码将经纬度设置为对应 memeber 的 score。
故而，GEOADD citys 116.41667 39.91667 "beijing"命令等价于：
ZADD citys 4069885649163649 beijing。

实际操作：

123.122.10.231:6379> GEOADD citys 116.41667 39.91667 "beijing" 121.43333 34.50000 "shanghai" 113.23333 23.16667 "guangzhou" 114.06667 22.61667 "shenzhen"   113.51667 22.30000 "zhuhai"
-> Redirected to slot [9558] located at 123.122.228.34:6379
(integer) 5
123.122.228.34:6379> geopos citys beijing
1) 1) "116.41667157411575317"
   2) "39.91667095273589183"
123.122.10.231:6379> geodist citys beijing shanghai  km
"748.3469"
123.122.228.34:6379> georadius citys 116 39 500 km
1) "beijing"
123.122.228.34:6379> GEORADIUSBYMEMBER citys shanghai 1000 km
1) "shanghai"
2) "beijing"
123.122.228.34:6379> GEORADIUSBYMEMBER citys shanghai 2000  km
1) "zhuhai"
2) "guangzhou"
3) "shenzhen"
4) "shanghai"
5) "beijing"
123.122.228.34:6379> GEOHASH citys shenzhen
1) "ws10ethzdh0"

123.122.228.34:6379> type citys 
zset
123.122.228.34:6379> OBJECT encoding citys
"ziplist

适用场景

适用于和位置相关的业务，例如附近的人、共享单车等。

引用

1. 详解redis bitmap
2. redis hyperloglog实现
 3. redis geo命令参考
 4. GeoHash核心原理解析