Redis数据结构与对象-数据库

参考《Redis设计与实现》

系列文章目录和关于我

一丶简单动态字符串

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

1.SDS的结构

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

2.SDS的优点

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

传统C语言的字符串，需要遍历整个字符串遇到字符串结尾的\0结束计数，但是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数组中

升级的好处：

提升灵活性

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

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

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

六丶压缩列表

压缩列表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基于跳表进行，获取成员分值这种操作基于字典进行

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