本篇是对《Redis设计与实现》一书第一部分阅读的记录
Redis的数据结构：简单动态字符串、链表、字典、跳跃表、整数集合、压缩列表
简单动态字符串
简单动态字符串相较于C语言中字符串的优势有如下几点：
(1) 获取字符串长度的时间复杂度为O(1)；
(2) 杜绝缓冲区溢出；
(3) 减少修改字符串时带来的内存重分配次数；当修改SDS会进行空间扩展时，如果SDS长度(len)小于1MB，则程序分配和len属性同样大小的 未使用空间(free)；如果SDS修改后的长度(len)将大于等于1MB，则程序会分配1MB的未使用空间(free)；同时缩短SDS长度时，程序不会立 即进行内存重分配来收回多出来的字节，而是用free属性将字节的数量记录下来；
(4) 二进制安全；
(5) 通过最后空字符结尾与c语言保持一致，来使用c语言的部分函数。
链表
链表数据结构的特点有以下几点：
双端：链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度为O(1)；
无环：表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问以NULL为终点；
带表头指针和表位指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为O(1)；
带链表长度计数器：程序使用list结构的len属性来对list持有的链表节点进行计数，程序获取链表中节点数量的复杂度为O(1)；
多态：链表节点使用void*指针来保存节点，并且通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。
字典
扩展和收缩哈希表的工作可以通过执行rehash(重新散列)操作来完成；当满足以下两个条件中的任意一个时，程序会自动开始对哈希表执行扩展操作：(1) 服务器目前没有在执行BGSAVE命令获取BGREWRITEAOF命令，并且哈希表的负载因子大于等于1；(2) 服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5；负载因子计算公式：load_factor=ht[0].used/ht[0].size；当哈希表的负载因子小于0.1时，程序自动开始对哈希表执行收缩操作。rehash的步骤如下：(1) 为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量（也即是ht[0].used属性的值）：如果执行的是扩展操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的2的n次方幂；如果执行的是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2的n次方幂；(2) 将保存在ht[0]中的所有键值对rehash到ht[1]上面：rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上；(3) 当ht[0]包含的所有键值对都迁移到了ht[1]之后（ht[0]变为空表），释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备。
跳跃表
层：节点中用L1，L2，L3等表示各个层每个层带有两个属性：前进指针和跨度；前进指针用于访问位于表尾方向的其他节点，跨度则记录前进指针所指向节点和当前节点的距离；遍历操作只使用前进指针就可以完成，跨度实际上时用来计算排位(rank)的：在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到结果就是目标节点在跳跃表中的排位；后退指针：它指向位于当前节点的前一个节点；用于从表尾向表头遍历时使用；分值：节点按各自所保存的分值从小到大排列；成员对象：节点所保存的成员对象。
整数集合
整数集合用于保存整数值的集合抽象数据结构，可以保存类型为int16_t、int_32或者int_64的整数值，并且保证集合中不会出现重复元素。整数集合的升级：保存类型从int16_t升级到int_32或者int_64；步骤如下，(1) 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。(2) 将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。(3) 将新元素添加到底层数组里面。
因为引发升级的新元素的长度总是比整数集合现有所有元素的长度都大，所以这个新元素的值要么就大于所有现有元素，要么就小于所有现有元素：在新元素小于所有现有元素的情况下，新元素会被放置在底层数组的最开头(索引0)；在新元素大于所有现有元素的情况下，新元素会被放置在底层数组的最末尾(索引length-1)。
整数集合不支持降级操作。
压缩列表
压缩列表时由一系列特殊编码的连续内存块组成的顺序型数据结构，是Redis为了节约内存而开发的。每个压缩列表节点可以保存一个字节数组或者一个整数值，其中，字节数组可以是以下三种长度的其中一种：长度小于等于63(2的6次幂–1)字节的字节数组；长度小于等于16383(2的14次幂–1)字节的字节数组；长度小于等于4294967295(2的32次幂–1)字节的字节数组；而整数值则可以是以下六种长度的其中一种：4位长，介于0至12之间的无符号整数；1字节长的有符号整数；3字节长的有符号整数；int16_t类型整数; int32_t类型整数；int64_t类型整数。
连锁更新：由于新添加的节点值长度大于后一个节点pervious_entry_length的最大存储长度，而导致需要进行内存重分配并形成的连锁操作。在极端的情况下出现的最坏复杂度为O(n的2次幂)；而在实际中，这种情况并不多见，所以不必担心连锁更新会影响压缩列表的性能。
Redis的对象系统：字符串对象、列表对象、哈希对象、集合对象、有序集合对象。
Redis中的对象
1、Redis中的每个对象都由一个redisObject结构表示，type属性记录了对象的类型，encoding属性记录了对象所使用的编码(同时也是说使用的数据结构作为对象的底层实现)，ptr属性表示指向底层实现数据结构的指针，refcount属性表示对象被程序引用的次数(用来实现内存回收和对象共享机制)，lru属性表示对象最后一次被程序访问的时间(计算对象的空转时长，如果服务器打开了maxmemory选项，当服务器占用的内存数超过了maxmemory选项所设置的上限值时，空转时长较高的那部分键会优先被服务器释放，从而回收内存)；
2、每种对象都用到了至少两种Redis中的数据结构，目的在于可以针对不同的使用场景，为对象设置不同的数据结构实现从而优化对象在不同场景下的使用效率(Redis内部自动转换)；
字符对象的编码方式
3、字符串对象的编码可以是int、embstr或者raw；int编码表示用long类型保存整数值(当对象保存的值不再是整数值时，对象的编码从int变成raw；例如想整数值内容后追加一个字符串值)，embstr编码表示保存字符串值长度小于等于32字节的字符串(专门用于保存短字符串的优化编码方式，与raw编码相比主要优点在于，embstr编码通过调用一次内存分配函数来分配一块连续的空间，释放内存也就只要一次，而raw编码方式是调用两次；另外embstr编码的字符串对象没有相应的修改程序，实际上是只读的，当对embstr编码的字符串执行修改命令时，embstr编码会转换成raw编码)，raw编码表示保存字符串长度大于32字节的字符串；
列表对象的编码方式
4、列表对象的编码可以是ziplist或者linkedlist；ziplist编码需要满足两个条件(这两个的上限值是可以修改的，配置文件中的list-max-ziplist-value和list-max-ziplist-entries；当使用ziplist编码所需的两个条件的任意一个不能被满足时，对象编码会从ziplist变成linkedlist)：(1) 列表对象保存的所有字符串元素的长度都小于64字节；(2) 列表对象保存的元素数量小于512个；当不使用ziplist编码时，使用linkedlist编码。
哈希对象的编码方式
5、哈希对象的编码可以是ziplist或者hashtable；与列表对象内容基本一致，不同的地方在于配置文件的选项是hash-max-ziplist-value和hash-max-ziplist-entries；保存同一键值对的两个节点总是紧挨在一起，保存键的节点在前，保存值得节点在后；不使用ziplist编码时，使用hashtable编码。
集合对象的编码方式
6、集合对象的编码可以是intset或者hashtable；intset编码也需要满足两个条件(元素数量的上限值可以通过set-max-intset-entries选项属性配置；当使用intset编码所需的两个条件的任意一个不能被满足时，对象编码会从intset变成hashtable)：(1) 集合对象保存的所有元素都是整数值；(2) 集合对象保存的元素数量不超过512个；当不使用intset编码时，使用hashtable编码。
有序集合对象的编码方式
7、 有序集合对象的编码可以是ziplist或者skiplist；ziplist编码需要满足两个条件(这两个的上限值是可以修改的，配置文件中的zset-max-ziplist-value和zset-max-ziplist-entries；当使用ziplist编码所需的两个条件的任意一个不能被满足时，对象编码会从ziplist变成skiplist)：(1) 有序集合对象保存的所有元素成员的长度都小于64字节；(2) 有序集合对象保存的元素数量小于128个；当不使用ziplist编码时，使用skiplist编码；skiplist编码同时使用跳跃表和字典来实现有序集合主要是利用字典的查询指定成员分值的时间复杂度为O(1)和跳跃表执行范围型操作的优点来让有序集合的查找和范围型操作都尽可能快的执行。
8、内存回收机制，程序可以通过跟踪对象的引用计数(refcount)信息在适当的时候自动释放对象并进行内存回收；创建一个新对象时，引用计数的值会被初始化为1；被新程序使用时，引用计数赠一；不在被程序使用时，引用计数减一；当对象的引用计数为0时，对象所占用的内存会被释放；
共享机制
9、对象共享机制，目前来说，Redis会在初始化服务器时，创建一万个字符串对象，这些对象包含了从0到9999的所有整数值，当服务器需要用到值为0到9999的字符串对象时，服务器就会使用这些共享对象，而不是新创建对象，从而做到节约内存；创建共享字符串对象的数量可以通过修改redis.h/REDIS_SHARED_INTEGERS常量来修改
分享大数据学习历程，坚持一周一篇原创，欢迎一起关注学习
我相信坚持一定会有收获
网友评论