本篇文章基于redis 4.0.14

字符串(String)

1、String常用命令

set、mset、get、mget、incr（针对数字递增1）、incrby（递增N） setnx

2、String应用场景

（1）计数器

（2）集群环境下的session共享

（3）分布式锁

3、String内部实现

struct RedisObject { 
    int4 type;       // 4bit 对象类型REDIS_STRING 0,REDIS_LIST 1,REDIS_SET 2,REDIS_ZSET 3,REDIS_HASH 4
    int4 encoding;   // 4bit 对象使用的编码
    int24 lru;       // 24bit  LRU 信息
    int32 refcount;  // 4bytes 引用计数，当为0时，对象销毁，内存回收
    void *ptr;       // 8bytes, 指向对象内容的具体存储位置
} robj;

一个RedisObject对象头需要占据16字节的存储空间。

Redis 的字符串是动态字符串，是可以修改的字符串，内部结构实现上类似于 Java 的 ArrayList，采用预分配冗余空间的方式来减少内存的频繁分配，内部为当前字符串实际分配的空间 capacity 一般要高于实际字符串长度 len。当字符串长度小于 1M 时，扩容都是加倍现有的空间，如果超过 1M，扩容时一次只会多扩 1M 的空间。字符串最大长度为 512M。

Redis的字符串叫SDS，Simple Dynamic String。

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

len表示buf中已占用空间的长度，alloc中表示buf中可剩余空间的长度，buf是数据空间。Redis的字符串有三种存储形式，如果一个字符串对象保存的是整数值，字符串对象的编码设置为INT。在长度比较短时，使用emb形式存储（embedded），当长度超过44字节，使用raw形式存储。

内存分配器 jemalloc/tcmalloc 等分配内存大小的单位都是 2、4、8、16、32、64 等等，为了能容纳一个完整的 embstr 对象，jemalloc 最少会分配 32 字节的空间，如果字符串再稍微长一点，那就是 64 字节的空间。如果总体超出了 64 字节，Redis 认为它是一个大字符串，不再使用 emdstr 形式存储，而该用 raw 形式。64-19-3-1 = 44。

存储的是正数时：

local:0>set demo "12"
"OK"
local:0>debug object demo
"Value at:0x2495228 refcount:2147483647 encoding:int serializedlength:2 lru:4087283 lru_seconds_idle:12"

存储字符串时，长度不大于44字节

local:0>set demo "abcdefghijklmnopqrstuvwxyz012345678912345678"
"OK"
local:0>debug object demo
"Value at:0x2487fe8 refcount:1 encoding:embstr serializedlength:45 lru:4090426 lru_seconds_idle:3"

存储字符创大于44字节时

local:0>set demo "abcdefghijklmnopqrstuvwxyz0123456789123456789"
"OK"
local:0>debug object demo
"Value at:0x2520b88 refcount:1 encoding:raw serializedlength:46 lru:4090636 lru_seconds_idle:2"

4、bitmap

SETBIT key offset value #对 key 所储存的字符串值，设置或清除指定偏移量上的位(bit)

'a' 的ASCII码是 97。转换为二进制是：0110,0001 这里 offset 0 = ‘0’ ，offset 1='1' ,offset2 = '1',offset 6 = '0' ，offset是从左往右计数的，也就是从高位往低位。 通过setbit命令把'a'改为'b' ，'b'的ascii码98 = 0110,0010,也就是把a的offset 6设置为1，offset 7设置为0即可。

bitmap本身offset的限制就是0到2^32，内存限制为512MB，刚刚好是2^32个bit，也就是4294967296，也就是说，offset最大能去到4294967296-1去。有四十二亿。

哈希(Hash)

1、常用命令

hset key field value
hget key field
hgetall key
hmset key field value …
hincrby key field increment 

2、应用场景

 （1）购物车 
 hmset  userId:001 prod:001  1  prod:002  1
 用户id为key，商品id为field，商品数量为 value
 （2）即时通信的未读消息。以用户id为key，好友或者群id为field，未读消息为value

3、内部实现

哈希对象的编码可以是 ziplist(压缩列表) 或者 hashtable (哈希表)

ziplist(压缩列表)

压缩列表不是基础数据结构，而是 Redis 自己设计的一种数据存储结构。有点儿类似数组，通过一片连续的内存空间，来存储数据。不过，它跟数组不同的一点是，它允许存储的数据大小不同。

struct ziplist<T> {    
    int32 zlbytes; // 整个压缩列表占用字节数    
    int32 zltail; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点 
    int16 zllen; // ziplist的节点（entry）个数  
    T[] entries; // 元素内容列表，挨个挨个紧凑存储    
    int8 zlend; // 标志压缩列表的结束，值恒为 0xFF 
}

entry 块随着容纳的元素类型不同，也会有不一样的结构。

struct entry {    
    int<?> prevlen; // 前一个 entry 的字节长度    
    int<?> encoding; // 元素类型编码    
    optional byte[] content; // 元素内容，可以是数字或字符串
}

prevlen 字段表示前一个 entry 的字节长度，当压缩列表倒着遍历时，需要通过这个字段来快速定位到下一个元素的位置。它是一个变长的整数，当字符串长度小于 254(0xFE) 时，使用一个字节表示；如果达到或超出 254(0xFE) 那就使用 5 个字节来表示。

Redis 使用压缩列表来实现字典类型。需要同时满足两个条件：

• 当哈希类型元素个数小于hash-max-ziplist-entries配置（默认512个）
• 所有值都小于hash-max-ziplist-value配置（默认64字节）

hashtable (哈希表)

Redis 的字典相当于 Java 语言里面的 HashMap，它是无序字典。内部实现结构上同 Java 的 HashMap 也是一致的，同样的数组 + 链表二维结构。第一维 hash 的数组位置碰撞时，就会将碰撞的元素使用链表串接起来。

（1）开放寻址法；（2）链表法

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

ht属性是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表， 一般情况下，字典只使用ht[0] 哈希表, ht[1]哈希表只会对ht[0]哈希表进行rehash时使用，渐进式rehash，hash算法使用的是SipHash。

列表(List)

Redis 的列表相当于 Java 语言里面的 LinkedList

1、常用命令

LPUSH key value [value ...] #列表头部插入数据
LRANGE key start stop #返回指定范围内的元素
LINSERT key BEFORE|AFTER pivot value #在 基准值pivot 之前/后  插入value
LPOP key #移除并且返回 key 对应的 list 的第一个元素
BLPOP key [key ...] timeout #阻塞式
LTRIM key start stop #让列表只保留指定区间内的元素

2、应用场景

list可以充当栈和队列的角色。

• lpush+lpop=Stack（栈）
• lpush+rpop=Queue（队列）
• lpush+ltrim=Capped Collection（有限集合）
• lpush+brpop=Message Queue（消息队列）

（1）消息队列

（2）文章、商品列表

a、文章使用哈希结构存储
hmset acticle:1 title xx timestamp 1476536196 content xxxx ... 
hmset acticle:k title yy timestamp 1476512536 content yyyy ...
b、用户文章列表user：{id}：articles作为用户文章列表的键
lpush user:1:acticles article:1 article:k
c、分页查询
articles = lrange user:1:articles 0 9
for article in articles{
    hgetall {article}
}

3、内部实现

在redis3.2版本之前list类型内部编码有2种

• ziplist（压缩列表）：当列表的元素个数小于list-max-ziplist-entries配置（默认512个），同时列表中每个元素的值都小于list-max-ziplist-value配置时（默认64字节），Redis会选用ziplist来作为列表的内部实现来减少内存的使用。
• linkedlist（链表）：当列表类型无法满足ziplist的条件时，Redis会使用linkedlist作为列表的内部实现。

linkedlist

typedef struct listNode {  
    struct listNode *prev;  // 前置节点  
    struct listNode *next;  // 后置节点  
    void *value;  // 节点的值  
} listNode;

typedef struct list{
    //表头节点
    listNode *head;
    //表尾节点
    listNode *tail;
    //链表所包含的节点数量
    unsigned long len;
}list;

quicklist

而在redis3.2版本开始对列表数据结构进行了改造，使用 quicklist 代替了 ziplist 和 linkedlist。quicklist 是 ziplist 和 linkedlist 的混合体，它将 linkedList 按段切分，每一段使用 zipList 来紧凑存储，多个 zipList 之间使用双向指针串接起来。

typedef struct quicklist {    
    quicklistNode *head; // 指向头节点的指针    
    quicklistNode *tail; // 指向尾节点的指针   
    unsigned long count; // 所有ziplists中entries的个数总和
    unsigned long len;   // quicklist 节点个数 
    int fill : QL_FILL_BITS; // 16bit ,ziplist 大小设置，存放list-max-ziplist-size参数的值
    unsigned int compress : QL_COMP_BITS; // 节点压缩深度设置，存放list-compress-depth参数的值    
} quicklist;

typedef struct quicklistNode {
    struct quicklistNode *prev; //上一个node节点
    struct quicklistNode *next; //下一个node
    unsigned char *zl;            //保存的数据 压缩前ziplist 压缩后压缩的数据
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     // ziplist里面包含的数据项个数
    unsigned int encoding : 2;   //表示ziplist是否压缩了 RAW==1 or LZF==2 压缩算法
    unsigned int container : 2;  //预留字段 NONE==1 or ZIPLIST==2
    unsigned int recompress : 1; // 当使用了lindex这样的命令查看了一项本来压缩的数据时，需要把数据暂时解压，设置此字段做标记，之后再重新压缩
    unsigned int attempted_compress : 1; // 自动化测试使用
    unsigned int extra : 10; // 扩展字段
} quicklistNode;

// 被压缩过的ziplist
typedef struct quicklistLZF {
    unsigned int sz; // 表示压缩后的ziplist大小
    char compressed[];// 存放压缩户的ziplist字节数组
} quicklistLZF;

集合(Set)

Redis 的集合相当于 Java 语言里面的 HashSet，它内部的键值对是无序的唯一的。它的内部实现相当于一个特殊的字典，字典中所有的 value 都是一个值NULL。

1、常用命令

SADD key member [member ...] #将一个或多个 member 元素加入到集合 key 当中
SDIFF key [key ...] # 差集
SINTER key [key ...] # 交集
SUNION key [key ...] # 并集
SPOP key # 移除并返回集合中的一个随机元素
SMEMBERS key # 返回集合 key 中的所有成员

2、应用场景

（1）点赞
sadd zan:001 userId:001 # 点赞 
srem zan:001 userId:001 # 取消点赞
smembers zan:001 #点赞列表
scard zan:001 #点赞总数
（2）标签
 a、给用户添加标签
sadd user:1:tags tag1 tag2 tag5
sadd user:2:tags tag2 tag3 tag5
 b、给标签添加用户
sadd tag1:users user:1 user:3
sadd tag2:users user:1 user:2 user:3
 c、计算共同感兴趣的标签
sinter user:1:tags user:2:tags

3、内部实现

• intset(整数集合)：当集合中的元素都是整数且元素个数小于set-maxintset-entries配置（默认512个）时，Redis会选用intset来作为集合的内部实现，从而减少内存的使用。
• hashtable(哈希表)：当集合类型无法满足intset的条件时，Redis会使用hashtable作为集合的内部实现。

//每个intset结构表示一个整数集合 
typedef struct intset{    
    uint32_t encoding;  // 编码方式     
    uint32_t length;    // 集合中包含的元素数量      
    int8_t contents[];  // 保存元素的数组,各个项在数组中按值的大小从小到大有序地排列,并且数组中不包含任何重复项
} intset;

有序集合(Sorted Set)

有序集合类型 (Sorted Set或ZSet) 相比于集合类型多了一个排序属性 score（分值），对于有序集合 ZSet 来说，每个存储元素相当于有两个值组成的，一个是有序结合的元素值，一个是排序值。有序集合保留了集合不能有重复成员的特性(分值可以重复)，但不同的是，有序集合中的元素可以排序。

1、常用命令

ZADD key score member [[score member] ...] # 将一个或多个 member 元素及其 score 值加入到有序集 key 当中
ZRANGE key start stop [WITHSCORES] # 返回指定区间内的成员 按 score 值递增(从小到大)来排序 ZREVRANGE
ZREM key member [member ...] # 移除有序集 key 中的一个或多个成员
ZUNIONSTORE destination numkeys key [key ...] # 给定的一个或多个有序集的并集

2、应用场景

（1）延时队列
zadd key current_timestamp + 15min orderId:0001
（2）排行榜
zincrby topic:0917 1 article:1 # 文章阅读，日期为key 
zrevrange topic:0917 0 3 withscores # 展示今日前3排名
zunionstore topic:2day 2 topic:0917 topic:0916 # 统计近2日点击数据
（3）抽奖
set zset

3、内部实现

有序集合是由 ziplist (压缩列表) 或 skiplist (跳跃表) 组成的。

当数据比较少时，有序集合使用的是 ziplist 存储的，有序集合使用 ziplist 格式存储必须满足以下两个条件：

• 有序集合保存的元素个数要小于 128 个；
• 有序集合保存的所有元素成员的长度都必须小于 64 字节。

如果不能满足以上两个条件中的任意一个，有序集合将会使用 skiplist 结构进行存储。

typedef struct zskiplistNode {
    robj *obj; // 存放的是节点数据
    double score; // 数据对应的分数
    struct zskiplistNode *backward; // 指向链表前一个节点的指针（前向指针）
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[]; // 存放指向各层链表后一个节点的指针（后向指针）。每层对应1个后向指针，用forward字段表示。另外，每个后向指针还对应了一个span值，它表示当前的指针跨越了多少个节点。span用于计算元素排名(rank)
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;// 头指针header和尾指针tail。
    unsigned long length;// 链表包含的节点总数
    int level;// 表示skiplist的总层数
} zskiplist;

HyperLogLog

pfadd key element [element ...] # 增加计数
pfcount key # 获取计数
PFMERGE destkey sourcekey # 合并
统计UV数据

GEO 模块

GeoHash 算法，附近人，redis使用zset结构来存储

GEOADD key longitude latitude member # 添加数据
GEODIST key member1 member2 # 返回两个给定位置之间的距离