Redis数据结构与对象

参考《Redis设计与实现》

系列文章目录和关于我

一丶简单动态字符串

当redis需要的不仅仅是一个字符串字面量，而是一个可以被修改的字符串值时，就会使用SDS（simple dynamic string）来表示字符串值。比如set msg "hello world"将创建一个新键值对，键值对的键是一个字符串对象（存储着msg），值也是一个字符串对象（存储者hello world）

1.SDS的结构

• free属性记录buf数组剩余未使用的字节数量
• len属性记录当前buf数据已经使用的字符数量
• buf属性是char类型的数组，最后一个字节保存空字符

2.SDS的优点

2.1 常数时间复杂度获取字符串长度

传统C语言的字符串，需要遍历整个字符串遇到字符串结尾的结束计数，但是SDS的len属性便记录了字符串的长度，可以常数时间获取字符串长度

2.2杜绝缓冲区溢出

传统C语言修改字符串可能导致缓冲区溢出（多个字符串相邻的时候，修改到了相邻位置的其他字符串）但是SDS进行修改的时候，会先检查SDS空间是否满足修改需要的要求，如果不满足九自动扩容到需要的大小，然后才执行修改操作

2.3减少修改字符串带来的内存重分配次数

SDS实现了空间预分配和惰性空间释放

• 空间预分配

  如果对SDS修改后，SDS的长度小于1mb（len属性）那么程序分配和len相同大小的未使用空间。如果SDS修改后长度大于1mb那么程序分配1mb大小的未使用空间。空间预分配减少连续执行字符串操作需要的内存分配次数。

• 惰性空间释放

  当SDS进行字符串缩操作的时候，并不会立即将不需要的空间进行内存重分配，而是修改free属性进行记录。

二丶链表

链表在redis中始于广泛，当前列表键包含了较多元素，又或者包含的元素都是较长的字符串的时候，redis将始于链表作为列表键（xx键表示键对应的值是xx类型）的实现。

发布订阅，慢查询等功能就是基于链表实现的

1.链表结构

2.链表的优点

• 双端，获取某个节点的前置后置都是常数时间复杂度
• 无环
• 带表头指针和，表尾指针
• 带链表长度计数器
• 多态，链表节点使用void*指针保存节点值

三丶字典

字典是一种用于保存键值对的数据结构，一个key可以和一个value进行关联。

字典在redis中使用广泛，redis数据库就是使用字典作为底层实现的，对数据库的增删改查都是构建在字典这种数据结构之上，字典还是哈希键的底层实现，当哈希键包含的键值对比较多，又或者键值对中的元素都是较长的字符串是，redis使用字典作为哈希键的底层实现。

1.字典的结构

可以看到redis的字典使用拉链法解决哈希冲突，一个字典存在两个dictht，一个用于存储数据，一个用于渐进式rehash

2.哈希算法

redis使用MurmurHash2算法计算key的hash值，然后将hash值于sizemask进行且操作，相当于一次对数组大小的取模，可以得到当前key应该落在哈希表数组的那个下标位置

3.解决hash冲突

redis使用拉链发来解决hash冲突，每一个哈希节点具备一个next节点，多个哈希节点使用next指针串联成单向链表，从而解决hash冲突的问题

4.渐进式rehash

随着操作不断进行，哈希表可能存储很多数据，为了让哈希表的负载因子维持在一个合理的范围，当哈希表保存的键值太多的时候，程序需要对哈希表的大小进行相应的扩展或者收缩。

4.1渐进式rehash的步骤

• 为ht[1]分配空间
• 字典中维护一个索引计数器rehashidx，设置为0，表示渐进式rehash正式开始
• 在rehash的期间，对字典进行的增删改查，除了完成迁移哈希数组中的内容到ht[1]之外，还会将顺带将rehashidx索引上的所有键值对rehash到ht[1],然后将rehashidx自增1
• 随着字典操作的不断进行，最终会完全rehash完ht[0]中的所有元素，rehashidx置为-1，表示结束

4.2渐进式rehash期间哈希表的使用

由于渐进式rehash的期间，字典具备两个哈希表，字典的增删改查都需要在两个哈希表中进行，如果ht[0]不存在数据，还需要去ht[1]中寻找，

4.3哈希表扩容或者收缩的前提

当下列条件中满足任意一个的时候，程序会自动进行哈希表的扩容

• 服务器没有执行BGSAVE(RDB持久化)，或者BGREWRITEAOF（AOF持久化）并且哈希表负载因子大于等于1
• 服务器正在执行BGSAVE(RDB持久化)，或者BGREWRITEAOF（AOF持久化）但是哈希表负载因子大于等于5

负载因子 = 哈希表存储的节点数量 / 哈希表大小

BGSAVE，或者BGREWRITEAOF进行的途中，进来不进行rehash的原因是，这两个命令进行的过程中，redis需要创建服务器子进程，采用写时复制的技术优化子进程的使用效率，避免子进程运行的途中进行rehash可以节约内存

当负载因子小于0.1的时候，redis会对哈希表进行收缩

四丶跳跃表

跳跃表是一种有序的数据结构，支持O(log N)时间复杂度进行节点查找。

redis使用跳跃表作为有序集合键的底层实现之一，如果有序集合包含的元素，或者有序集合中元素的成员都是较长的字符串的时候，redis使用跳跃表作为有序集合键的底层实现。此外集群节点中也了使用跳表。

1.跳跃表的结构

2.跳跃表中的分值和成员

跳跃表是有序的结构，其中的分值便是排序的依据，多个节点可以包含相同的分值，分值相同的时候根据节点保存对象的大小进行排序，每个节点保存的对象必须唯一

五丶整数集合

整数集合是集合键的底层实现之一，当一个集合只有整数元素，且集合元素不多的适合，redis使用整数集合作为集合键底层实现

1.整数集合的结构

2.整数集合encoding编码方式

属性值表示contents数组中，整数的类型是int8_t，int16_t，int32_t，还是int64_t。

3.升级

当一个新元素添加到整数集合中，并且新元素的类型比整数集合中其他元素的类型都要长时，整数集合会进行升级，然后把新元素添加到集合中。升级的步骤：

• 根据新元素的类型，扩展整数集合底层数组的空间大小，并且为新元素分配空间
• 底层contents元素的类型转换到新元素相同类型，并放到争取的位置上，有序性不变
• 新元素添加到contents数组中

升级的好处：

1. 提升灵活性

   整数集合可以通过升级保存不同类型的新元素

2. 节约内存

   在需要的适合才会升级，才需要更大的内存空间，可以减少内存的占用

整数集合，不会进行降级。

六丶压缩列表

压缩列表ziplist是列表建和哈希键的底层实现之一。

当一个列表只包含少量列表项的，并且每一个列表项是小整数或者长度段的字符串，redis使用压缩列表作为列表键的底层实现（相比于链表，少前继后继指针更加节约内存）

当一个哈希键只包含少量键值对的适合，并且每个键值对的键和值都是小整数，或者段字符串的适合，redis使用压缩列表作为哈希键的底层实现

1.压缩列表的结构

2.连锁更新

每一个节点的previous_entry_length记录了前一个节点的长度，如果前一个节点的长度小于254字节，那么此属性使用一个字节进行记录，如果大于254字节那么使用五字节进行记录，所有如果新的节点的插入，也许这个节点的长度大于1字节，那么其后面的节点需要更新previous_entry_length为5字节大小，可能导致后续的节点也需要更新previous_entry_length，引发连锁更新

七丶对象

前面我们学习了简单动态字符串，链表，字典，跳跃表，整数集合，压缩列表的数据结构，但是redis并没有使用整个数据结构直接实现键值对数据库，而是基于这些数据结构实现了对象系统，包含：字符串对象，列表对象，哈希对象，集合对象，有序集合对象，这样做的好处是，可以针对不同的使用场景使用不同的数据结构，优化效率。

redis还实现引用计数器的内存回收机制，并且会让多个数据库键共享一个对来节约内存。

redis中的对象还带有访问时记录信息，在服务器其余maxmemory功能的时候，根据此信息会删除长时间没有被访问的对象

1.对象的结构

• 类型

  redis数据库中，键固定式字符串对象，但是键可能是字符串，列表，哈希，集合，有序集合对象等。type字段就记录了到底是什么对象（redis客户端使用Type 键名 将返回对象类型）

• 编码

  encoding字段记录了，底层实现使用了什么编码，每种类型的对象至少使用了两种不同类型的编码。

  使用object encoding 键名可以获取对象的编码

  使用编码，可以让redis在不同的情况下，使用不同的底层数据结构，优化效率

  比如在列表元素比较少的时候，redis使用压缩列表，也不是使用链表，就是因为压缩列表相比链表，少了前继，后继指针，使用连续的内存存储，压缩列表更加节约内存。随着元素越来越多，redis将转化使用双端链表进行保存

• 底层实现

  redis使用一个指针，指向底层实现的数据结构

2.字符串对象String

2.1字符串对象的结构

字符串对象的编码可以使用int,raw,embstr

• 当字符串对象保存一个字符串值，并且长度大于39字节的时候，字符串对象将使用简单动态字符串来保存，并且指定编码为raw

  

• 当保存的内容是一个字符串值，但是字符串长度小于等于39字节的时候，redis使用embstr来保存

  

  使用SDS的raw编码，会使用两次内存分配函数，分别创建redisObject，和SDS，但是embStr编码则只需要一次内存分配获取一块连续的空间，一次存储redisObject和字符串内容

• 当字符串对象保存的是一个整数值，并且整数值可以使用long来表示，这是redis会使用int类型编码

  

2.2字符串对象命令

• set

  redis根据情况使用不同的编码保存字符串对象

• get

  返回值

• append

  在尾部追加，对于int编码或者embstr编码会将对象编码转化为raw，然后进行拼接

• incrbyFloat

  redis会尝试将字符串转化为long double类型的数字，然后进行加法运算

• incrby

  只有int编码可以进行此操作，进行整数加法运算

• decrby

  只有int编码可以进行此操作，进行整数减法运算

• strlen

  返回字符串长度

• setrange

  设置特定索引上的值，int 和 embstr编码都会先转换为raw然后进行操作

• getrange

  返回特定索引下的值

3.列表对象list

3.1列表对象的结构

列表对象的编码可以是ziplist，或者linkedlist

• 当列表中的字符串元素都小于64字节的时候，且数量小于521的时候使用ziplist进行保存

• 当列表中的字符串元素存在大于64字节的元素时候，或者数量大于等于521的时候使用linkedlist进行保存

  

3.2列表命令

• lpush

  将新元素压入列表头部

• rpush

  将新元素压入列表尾部

• lpop

  返回表头元素，并删除表头元素

• rpop

  返回表尾元素，并删除表尾元素

• LIndex

  定位列表指定节点，并返回节点保存的元素

• LLen

  返回列表长度

• LInsert

  插入新节点到指定位置

• LREM

  删除给定元素的节点

• LTRIM

  删除不在索引范围内的节点

• LSET

  设置指定索引位置的值

4.哈希对象hash

4.1哈希对象的结构

哈希对象的编码可以是ziplist，也可以是hashtable

• ziplist编码底层使用压缩链表，当新元素加入的时候，现在压缩链表中存储key然后存储value

  当键值字符串长度都小于64字节，且数量小于512的时候，使用此种编码

  

• hashtable编码底层使用字典，每一个键都是字符串对象，每一个值也是字符串对象

  当键值字符串长度存在大于等于64字节的，或者数量大于512的时候，使用此种编码

  

4.2哈希对象的命令

• hset

  设置哈希对象 key和对应的值

• hget

  获取哈希对象key对应的值

• hexists

  判断哈希对象是否存在key

• hdel

  删除哈希对象 key和对应的值

• hlen

  返回哈希对象具备的key数量

• hgetall

  返回哈希对象索引的键和队友的值

5.集合对象set

5.1集合对象的结构

集合对象编码可以是intset，或者hashtable

• intset编码底层使用整数集合

  当集合保存的全是整数，并且数量不超过512个的时候使用此种编码

  

• hashtable底层使用字典，但是value全为null

  当集合保存的不全是整数，或者数量超过512个的时候使用此种编码

  

5.2集合对象的命令

• SCARD

  返回集合元素的数量

• SISMEMBER

  判断元素是否存在于集合

• SMENBERS

  返回所有集合元素

• SRANDMEMBER

  从集合中随机返回一个

• SPOP

  随机删除一个元素，并返回

• SREM

  删除给定元素

6.有序集合对象ZSET

6.1有序集合对象的结构

有序集合的编码有ziplist或者skiplist

• ziplist底层使用压缩列表，每一个集合元素使用两个紧挨在一起的压缩列表节点表示，一个保存集合成员，一个保存分值

  当有序集合元素少于128个，且元素长度都小于64字节的时候使用此种编码

  

• skiplist编码，使用zset结构作为底层实现，一个zset包含一个字典，和一个跳跃表

  当有序集合元素不少于128个，或者元素长度存在大于等于64字节的时候使用此种编码

  跳跃表按照分值从小到大保存了所有集合元素，字典为有序集合创建了成员到分值的映射

  二者的结合保证，范围查找和获取成员的分值都有较高的速度，范围型操作比如ZRANK，ZRANGE基于跳表进行，获取成员分值这种操作基于字典进行

  二者保存的对象是共享的，不会使用两份空间进行保存

  

6.2有序集合对象的命令

• ZADD

  向有序集合存入元素和对应的分值

• ZCARD

  返回有序集合元素数量

• ZCOUNT

  返回有序集合指定分值范围元素的个数

• ZRANGE

  返回指定分值范围内的元素

• ZRANK

  返回元素和对应的排名

• ZREM

  删除元素

• ZSCORE

  返回给定元素的分值