Redis的五种基本数据类型及其底层实现

Redis的五种基本数据类型

Redis自身是一个map结构，所有的数据都才有key-value的形式存储，而其key永远是字符串string类型，所以我们谈到的数据类型讨论的是value范围的数据类型，即redis存储的数据的类型。

string类型

string类型单个数据，是最简单的数据存储类型，也是最常用的数据存储类型，如果其存储的字符串为整数形式，则可以支持一些整数的简单运算。

string类型的基本操作命令

string类型的通用操作：

命令	说明
set key value	添加/修改数据
get key	获取数据
del key	删除数据
mset key1 value1 key2 value2 …	添加/修改多个数据
mget key1 key2 …	获取多个数据
strlen key	获取数据字符个数（字符串长度）
getset key value	修改原来key的对应值，并将旧值返回
getrange key start end	获取子串，若获取整个字符串则start=0,end=-1
append key value	追加信息到原始信息后部
setex key seconds value	设置数据具有指定的生命周期，单位为秒
psetex key milliseconds value	设置数据具有指定的生命周期，单位为毫秒

string作为数字时支持的简单运算：

命令	说明
incr key	在原字段上加1
incrby key increment	在原字段上加上整数increment
increbyfloat key increment	在原字段上加上浮点数increment
decr key	在原字段上减1
decrby key increment	在原字段上减去整数increment

string类型的内部实现——SDS

redis中用一种名为简单动态字符串（simple dynamic string）的抽象类型作为默认字符串表示，如在上面的测试命令set name sher中，在redis数据中创建了新的键值对name-sher，而在地城就是存储了保存着name的SDS和sher的SDS，除了保存redis数据库中的字符串值外，SDS还用作缓冲区（AOF持久化中的AOF缓冲区、客户端中的输入缓冲区都是由SDS实现），SDS底层是这样的数据结构：

struct sdshdr {
    
    // buf 中已占用空间的长度 等于SDS所保存的字符串长度
    int len;

    // buf 中剩余可用空间的长度
    int free;

    // 数据空间
    char buf[];
};

也就是说与传统的字符串相比，SDS由于在len属性中记录了其存储的字符串长度，所以获取字符串长度时不需要遍历整个字符串，而是直接获取其len属性即可，所以获取SDS存储的字符串的长度时间复杂度为O(1)（而获取C字符串的长度时间复杂度为O(n)），而在SDD中也是由\0作为字符串的结束：

在SDS中，存储数据的buf数组不一定是字符的数量加一（加一为\0），而是还包括未使用的字节，这些字节的长度由free属性记录。

C字符中出现的问题：

由于C字符串中不记录自己的长度，所以会出现内存溢出和内存泄漏：

• 如果将C字符串后面进行拼接操作，如果没有提前分配好内存，很可能就会将原字符串地址后存储的数据进行覆盖，造成内存溢出；
• 如果将C字符串进行缩短操作，原字符串后面不再使用的空间如果没有进行释放，就会造成内存泄漏。

SDS中的解决方案：

• 空间预分配：该策略用于优化字符串的增长操作，其策略用伪代码表示为：

  if (len < 0.5MB) 
  	buf.length = buf.length + len
  else 
  	buf.length = buf.length + 1MB
  

  也就是如果对SDS进行修改之后，其长度若小于1MB，则分配给和len属性同样大小的未使用空间，（分配后SDS中len属性的值和free值相同）；如果对SDS进行修改后，其长度将大于1MB，则分配个1MB的空间。也就是在扩展SDS的buf数组前，会先检查未使用空间是否够用，够用的话就不会执行内存分配了，这样就减少了内存分配的次数。

• 惰性空间释放：该策略用于优化字符串的缩短操作，当要缩短SDS字符串时，并不会立即回收缩短后多出来的字节，而是将这些空出来的字节用free属性记录下来，并等待以后使用。

hash类型

Redis中的哈希结构非常类似于Java中的HashMap，hash特别适合存储对象，若内存足够大，一个Redis的hash结构可以存储40多亿的键值对，hash是一个string类型的field和value的映射表（或称为字典、符号表、关联数组），如下一个球员角色有三个字段：编号（id）、球员名（name）、球员号码（num），则其在内存中的存储结构为：

hash类型的基本操作命令

hash类型的通用操作：

命令	说明
hset key field value	在hash中设置单个键值对
hget key field	获取hash中指定的键的值
hgetall key	获取所有hash中的键值对
hdel key field1 [field2 …]	删除hash中的某个（些）字段
hmset key field1 value1 field2 value2 …	在hash中设置多个键值对
hmget key field1 field2 …	获取hash中指定的多个键的值
hlen key	返回hash中键值对的数量
hexists key field	判断hash中是否存在field字段
hkeys key	获取hash中所有的字段名（键）
hvals key	获取hash中所有的字段值（值）

若键值对中的value存储为数字字符串时的操作：

命令	说明
hincrby key field increment	指定字段的数值数据加increment
hincrbyfloat key field increment	指定字段的数值数据加increment

hash底层的实现

字典dict

字典（映射、符号表、关联数组）就是一种保存键值对key-value的抽象数据结构，在Redis中其应用较为广泛，比如Redis中的数据库就是使用字典来作为底层实现的，因为Redis中的每条记录本身就是个键值对；除了用字典表示数据库外，当一个哈希键key包含的键值对field-value较多时，Redis也会使用字典作为hash的底层实现。首先我们看在普通状态下的字典结构如下：

我们发现在字典中存在两个哈希表，通常情况下，我们只会用ht[0]这个哈希表，那么ht[1]是用来做什么的？ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用。而在哈希表中存放了哈希表节点的数组，而哈希表节点的数组存放了每个哈希表节点，在哈希表节点中就是真正的键值对数据，这几个数据结构在Redis底层源码实现如下：

/*
 * 字典
 */
typedef struct dict {
    dictType *type;// 类型特定函数
    void *privdata;//私有数据
    
    dictht ht[2];// 哈希表
    
    int rehashidx; /* 当 rehash 不在进行时，值为 -1 */

} dict;

对于字典，type和privdata属性是为创建多态字典有关的，这里不详细进行介绍，而**dictth ht[2]字段恰恰就是存储了用来存储键值对数据的哈希表和用来rehash的哈希表**，rehashidx字段在注释中已经说明其用途。

/*
 * 哈希表
 * 每个字典都使用两个哈希表，从而实现渐进式 rehash 。
 */
typedef struct dictht {
    
    dictEntry **table;// 哈希表数组
   
    unsigned long size; // 哈希表大小
    
    unsigned long sizemask; // 哈希表大小掩码，用于计算索引值,总是等于 size - 1
    
    unsigned long used;// 该哈希表已有节点的数量

} dictht;

对于哈希表，其sizemask和哈希表节点计算出的哈希值共同决定了一个键应该被放到table数组的哪个索引上。

/*
 * 哈希表节点
 */
typedef struct dictEntry {
  
    void *key;  // 键
 
    union {   // 值
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    struct dictEntry *next; // 指向下个哈希表节点，形成链表

} dictEntry;

阅读其源码可知，在Redis中，键值对的值可以是一个指针，也可以是一个uint64_t整数，也可以是一个int64_t整数，而在哈希表节点中有一个**next指针，只是为了将多个哈希值相同的键值对连接在一起，以此来解决哈希冲突问题**。

压缩列表ziplist

当哈希键只包含少量键值对，并且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，则Redis就会使用压缩列表来做hash的底层实现：

压缩列表的组成部分如下：

其中各个组成部分的含义如下：

属性	长度	说明
zlbytes	4字节	记录整个压缩列表占用的内存大小
zltail	4字节	记录压缩列表尾结点举例压缩列表的起始地址有多少字节
zllen	2字节	记录压缩列表包含的节点数量
entryX	不定	压缩列表节点，即存储的具体内容
zlend	1字节	特殊值0xFF(255)，用于标记压缩列表的末端

在压缩列表中，存储实际的数据是由压缩列表节点，即上图中的entry属性完成的，而每个entry的组成部分如下：

其中各组成部分的含义如下：

属性	说明
previous_entry_length	记录压缩列表中前一个节点的长度，其长度为1或5字节（若前一个节点长度小于254字节，则为1字节，如0x05就表示前一个节点长度为5；若前一个节点长度大于254字节，则为5字节，且第一字节设置为0xFE，然后后4个字节为前一个节点的长度，如0xFE00002766就表示前一个节点长度为10086）
encoding	记录节点的content属性保存的数据类型以及长度
content	保存节点的值（可以是字节数组或者整数）

由于每个节点记录了上一个节点的长度，所以可以通过当前节点的起始地址来计算出前一个节点的起始地址，即前一个节点起始地址 = 当前节点起始地址 - previous_entry_length，这样就可以实现压缩列表从表尾向表头的遍历。

事实上，不仅hash结构在存储少量数据时选择压缩列表作为底层实现，list结构在包含少量列表项时，也是由压缩列表作为底层实现的。

list类型

Redis中的list类型有些类似于Java中的LinkedList结构，它可以保存多个数据且具有插入顺序，其底层是个双向链表，所以在链表的头尾都可以进行插入删除操作。

list类型的基本操作命令

list常用的基本操作：

命令	说明
lpush key value1 [value2] …	把节点加入到链表最左边
rpush key value1 [value2] …	把节点加入到链表最右边
lindex key index	读取下标为index的节点（从0开始算）
llen key	获得链表的长度
lrange key start stop	获取链表key的下标从start到end的节点值，[star, end]，若获取所有节点可以用lrange key 0 -1
lpop key	删除左边第一个节点并返回
rpop key	删除右边第一个节点并返回
lset key index value	设置下标为index的节点的值为value

list还提供了阻塞命令，如下这几个命令是阻塞版本命令，比如阻塞取数据的时候，现在没有不代表以后没有，可以等！比如当前没有值，但是在timeout时间内有其他客户端添加了值，就可以取到了。

命令	说明
blpop key1 [key2] timeout	移除并获取第一个元素，如果列表没有元素会阻塞列表直到超时时间或有元素可以弹出
brpop key1 [key2] timeout	移除并获取最后一个元素，如果列表没有元素会阻塞列表直到超时时间或有元素可以弹出

list底层的实现

链表

首先看下链表底层实现的整体结构：

然后看其源码数据结构定义如下：

/*
 * 双端链表节点
 */
typedef struct listNode {
    
    struct listNode *prev; // 前置节点

    struct listNode *next; // 后置节点
    
    void *value; // 节点的值

} listNode;
/*
 * 双端链表结构
 */
typedef struct list {
   
    listNode *head;// 表头节点
    
    listNode *tail;// 表尾节点
    
    void *(*dup)(void *ptr);// 节点值复制函数
    
    void (*free)(void *ptr);// 节点值释放函数
    
    int (*match)(void *ptr, void *key);// 节点值对比函数
    
    unsigned long len;// 链表所包含的节点数量

} list;

压缩列表ziplist

当链表存储的数据较少时，list底层由压缩列表实现，在hash类型的底层实现时讲过该结构，可以看出压缩列表也实现了双端的特性。

set类型

set类型适用于存储大量的不重复的数据，在查询时可以提供更高的效率，因为其底层由哈希表实现，所以其插入、删除、查询的时间复杂度都为O(1)。

set类型的基本操作

命令	说明
sadd key member1 [member2]	给键为key的集合增添成员
smembers key	返回集合所有成员
srem key member1 [member2]	删除集合中成员
scard key	获取集合中成员个数
sismember key member	判断集合中是否包含指定数据
srandmember key [count]	随机返回集合中一个或多个元素，count为限制返回总数，若count小于0，先对其求绝对值，若count大于集合成员数，则返回所有成员，若无count，默认返回1个
spop key [count]	随机从集合中移除数据并返回，count作用同上
sinter key1 [key2]	求key1和key2的交集，若无key2则返回key1的所有元素
sinterstore des key1 [key2]	求key1和key2的交集并保存到des中
sunion key1 [key2]	求key1和key2的并集，若无key2则返回key1的所有元素
sunionstore des key1 [key2]	求key1和key2的并集并保存到des中
sdiff key1 [key2]	求key1和key2的差集，若无key2则返回key1的所有元素
sdiffstore des key1 [key2]	求key1和key2的差集并保存到des中
smove src des member	将指定成员从原集合移动到目标集合中

set底层的实现

set底层由两种实现方式，其通常情况下和hash底层结构一样由哈希表实现，但是当set中存储的都是数字时，其底层由一种为整数集合（intset）的数据结构实现：

哈希表

当set中存储的数据不都是数字时，其底层就是用和hash底层结构相同的哈希表一样实现的，只不过只存储哈希表中的field字段作为set的值，而原来哈希表中的value字段置为空：

整数集合intset

当一个集合只包含整数值元素，并且这个集合的元素数量不多时，set 就由整数集合这种数据结构实现。下面展示了一个intset的存储结构：

contents数组是整数集合的底层实现，intset存储的每一项数据都是contents数组中的一项，contents数组中的数值按照从大到小排列，且不含重复元素，其存储的数据类型由encoding属性决定，而length属性记录了存储数据的数量，即contents数组的长度，其源码如下：

typedef struct intset {
    
    uint32_t encoding;// 编码方式
    
    uint32_t length;// 集合包含的元素数量
    
    int8_t contents[];// 保存元素的数组

} intset;

sorted_set类型

有序集合和集合类似，只是它是有序的，和无序集合的主要区别是每一个元素除了值之外，还会多一个分数，也就是有序集合在set的存储结构基础上添加可排序字段。

sorted_set类型的基本操作

命令	说明
zadd key score1 member1 [score2 member2]	添加数据
zrange key start stop [WITHSCORES]	按照排序正向获取索引内的数据，可选参数带分数
zrevrange key start stop [WITHSCORES]	按照排序逆向获取索引内的数据，可选参数带分数
zrem key member [member …]	删除数据
zrangebyscore key min max [WITHSCORES] [LIMIT]	按条件获取数据
zrevrangebyscore key min max [WITHSCORES] [LIMIT]	按条件获取数据
zremrangebyrank key start stop	根据排序条件删除数据
zremrangebyscore key min max	根据分数值条件删除数据
zrank key member	获取成员对应的索引（排名）
zrevrank key member	获取成员对应的倒序排名
zscore key member	获取成员的分数
zincrby key increment member	将成员分数加increment
zcard key	获取集合中成员数量
zcount key min max	获取集合中分数满足条件的数量