Redis学习笔记一：数据结构与对象

时间：2022-03-12 08:47:37

1. String(SDS)

Redis使用自定义的一种字符串结构SDS来作为字符串的表示。

127.0.0.1:6379> set name liushijie

OK

在如上操作中，name(key)和liushijie(key)就存储在SDS中。

SDS数据结构如下：

struct sdshdr {

    // 所保存字符串的长度

    int len;

    // 未使用字节长度

    int free;

    // 字节数组，保存字符串

    char buf[];

};

SDS遵循C字符串以'\0'空字符串结尾的惯例，所以buf的内部值为

'l' 'i' 'u' 's' 'h' 'i' 'j' 'i' 'e' '\0'，但是空字符串不算在len中，即在上面的例子中字符串的长度为9，而不是10，所以这个空字符对SDS使用者是完全透明的。这么写的好处是SDS可以直接重用一部分C字符串函数库的函数。

SDS与C字符串的区别

  1. SDS获取字符串长度时间复杂度为O(1)，C字符串为O(N)
  2. 杜绝缓冲区溢出

    SDS在执行字符串赋值时会检查剩余空间是否足够，不够的话会先扩展SDS的空间，然后才执行赋值操作。

    C不会检查，有造成溢出的风险。
  3. 减少修改字符串

    通过未使用空间SDS提供了空间预分配和惰性空间释放两种优化策略

    空间预分配策略：

额外分配的未使用空间数量由以下公式：

  • 如果修改后的SDS的len小于1MB，那么程序分配和len属性同样大小的未使用空间，这时len = free
  • 如果修改后的SDS的len大于1MB，那么程序会分配1MB的未使用使用空间

在扩展SDSk空间之前，如果足够的话，API就会直接使用未使用空间，而无须执行内存重分配。

惰性空间释放：

惰性空间释放用于优化SDS的字符串缩短操作：当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用回收要缩短的字节，而是使用free属性的将这些字节的数量记录起来。

4. 二进制安全

因为Redis SDS结构不会截断'\0'空字符，所以SDS结构不仅可以保存文本数据，也可以保存二进制数据。

2. 链表

链表的简单使用：

127.0.0.1:6379> rpush footmark jiamusi harbin dalian shenzhen beijing shenyang

(integer) 6

127.0.0.1:6379> llen footmark

(integer) 6

127.0.0.1:6379> lrange footmark 0 5

  1. "jiamusi"
  2. "harbin"
  3. "dalian"
  4. "shenzhen"
  5. "beijing"
  6. "shenyang"

使用链表的相关实现：

  • 列表键
  • 发布与订阅
  • 慢查询
  • 监视器
  • ...

链表的数据结构：

// 链表节点

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;

Redis链表的特性：

  • 双向
  • 无环
  • 带表头、表尾指针
  • 带链表长度计数器
  • 多态

3. 字典

字典，又称符号表、关联数组或映射（map），是一种保存键值对的抽象数据结构。

每个键都是独一无二的，程序可以在字典中根据键查找与之关联的值，或者通过键来更新值，又或者根据键来删除整个键值对，等等。

  1. 字典的实现

    Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。（注：结构算法其实相当于一个hashmap）
// 哈希表

typedef struct dictht {

    dictEntry **table;

    unsigned long size;

    unsigned long sizemask;

    unsigned long used;

} dictht;

// 哈希表节点

typedef struct dictEntry {

	// 键

    void *key;

    // 值

    union {

        void *val;

        uint64_t u64;

        int64_t s64;

        double d;

    } v;

    // 指向下个哈希表节点，形成单向链表

    struct dictEntry *next;

} dictEntry;

// 字典

typedef struct dict {

    dictType *type;

    void *privdata;

    dictht ht[2];

    long rehashidx; /* rehashing not in progress if rehashidx == -1 */

    int iterators; /* number of iterators currently running */

} dict;

typedef struct dictType {

    unsigned int (*hashFunction)(const void *key);

    void *(*keyDup)(void *privdata, const void *key);

    void *(*valDup)(void *privdata, const void *obj);

    int (*keyCompare)(void *privdata, const void *key1, const void *key2);

    void (*keyDestructor)(void *privdata, void *key);

    void (*valDestructor)(void *privdata, void *obj);

} dictType;

  1. 哈希算法

    当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis使用MurmurHash2算法来计算键的哈希值。（注：算法相关 http://code.google.com/p/smhasher/）

  2. 解决键冲突

    使用链地址法来解决键冲突。如果发生冲突，程序将新节点加在链表的表头位置。可以参考hashmap的实现。

  3. rehash

    rehash用来扩展和收缩哈希表。

rehash触发条件如下：

+ 服务器目前没有在执行BGSAVE命令或者BGREWRITERAOF命令，并且哈希表的负载因子大于等于1；

+ 服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负责因子大于等于5。

rehash步骤如下：

  1. 为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量：

    • 扩展操作：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[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备。

  4. 渐进式rehash

    rehash动作不是一次性、集中式地完成的，而是分多次、渐进式地完成的。详细步骤：

  1. 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。
  2. 在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始。
  3. 在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的索引键值对rehash到int[1]，当rehash工作完成后，程序将rehashidx变量的值增一。
  4. 随着字典操作的不断执行，最终在某个时间点，ht[0]的所有键值对都会被rehash至ht[1]，这时设置rehashidx变量的值设置为-1，表示rehash操作完成。

渐进式rehash执行期间的哈希表操作：

在进行渐进式rehash的过程中，字典会同时使用ht[0]和ht[1]两个哈希表，所以在渐进式rehash进行期间，字典的删除、查找、更新等操作会在两个哈希表上进行。

在渐进式rehash执行期间，新添加到字典的键值对一律会被保存到ht[1]里面，而ht[0]则不再进行任何添加操作，这一措施保证了ht[0]包含的键值对数量会只减不增，并随着rehash操作的执行而最终变成空表。

4. 跳跃表

跳跃表(skiplist)是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

在Redis中有两个地方用到了跳跃表：实现有序集合键和用作内部数据结构的集群节点。

跳跃表的实现

// 跳跃表节点

typedef struct zskiplistNode {

    // 成员对象

    robj *obj;

    // 分值：节点按各自保存的分值从小到大排列

    double score;

    // 后退指针

    struct zskiplistNode *backward;

    // 层

    struct zskiplistLevel {

    	// 前进指针：用来访问表尾的其他节点

        struct zskiplistNode *forward;

        // 跨度：记录了前进指针所指向节点和当前节点的距离

        unsigned int span;

    } level[];

} zskiplistNode;

// 保存跳跃表节点的相关信息

typedef struct zskiplist {

	// header：指向跳跃表的表头节点，tail：执行跳跃表的表尾节点

    struct zskiplistNode *header, *tail;

    // 跳跃表的长度

    unsigned long length;

    // 层数最大的那个节点的层数

    int level;

} zskiplist;

5. 整数集合

整数集合(intset)是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。

  1. 整数集合的实现
typedef struct intset {

   // 编码方式：用来决定contents属性的数值类型

    uint32_t encoding;

    // contents数组的长度

    uint32_t length;

    // 保存元素的数组，各个项在数组中按值的大小从小到大有序排列，并且数组不包含任何重复项

    // 虽然intset结构将contents属性声明为int8_t类型的数组，但是实际上contents并不保存任何类型int8_t类型的值，content数组的真正类型取决于encoding的值

    int8_t contents[];

} intset;
  1. 升级

    将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级，然后才能将新元素添加到整数集合里。

升级的好处：

  1. 提升灵活性
  2. 节约内存

升级整数集合并并添加新元素共分为三步进行：

  1. 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。

  2. 将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放在正确的位上，而且在放置元素过程中，维持底层数组有序性质不变。

  3. 将新元素添加到底层数组里。

  4. 降级

    不支持降级。

6. 压缩列表

压缩列表(ziplist)是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做列表键的底层实现。

例如：

127.0.0.1:6379> rpush lst 1 2 4 "a" "b"

(integer) 5

127.0.0.1:6379> object encoding lst

"ziplist"

127.0.0.1:6379> hmset profile a 1 b 2

OK

127.0.0.1:6379> object encoding lst

"ziplist"
  1. 压缩列表的构成

    压缩列表是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表尅包含任意多个几点，每个节点可以保存一个字节数组或者一个整数值。
 
压缩列表的各个组成部分
  • zlbytes : 记录整个压缩列表占用的内存字节数
  • zltail：记录压缩列表表尾节点距离压缩列表的起始地址有多少字节
  • zllen：记录了压缩列表包含的节点数量
  • entryN：压缩列表包含的各个节点，节点的长度由节点保存的内容决定
  • zlend：特殊值，用于标记压缩列表的末端
  1. 压缩列表节点的构成

     |

    ------------------- | --

    压缩列表节点的各个组成部分| previous_entry_length | encoding | content
  • previous_entry_length：记录前一个节点的长度
  • encoding：记录了节点的content属性所保存数据的类型以及长度
  • content：保存节点的值。值可以是字节数组或者整数，值的类型和长度由encoding决定
  1. 连锁更新

    添加或删除节点可能会引起连锁更新。

7. 对象

Redis并没有直接使用之前介绍的基本数据结构（SDS/LIST/MAP等）来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象。

对象的好处

  • 通过这五种不同类型的对象，Redis可以在执行命令前，根据对象的类型来判断一个对象是否可以执行给定的命令。多种不同的数据结构实现，从而优化。
  1. 对象的类型与编码

    Redis中的每个对象都由一个redisObject结构表示，和保存数据有关的三个属性分别是type encoding ptr，具体的数据结构如下：
typedef struct redisObject {

    unsigned type:4;

    unsigned encoding:4;

    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */

    int refcount;

    void *ptr;

} robj;

type（常量）：记录了对象的类型，使用命令type key可以查看对象类型：

127.0.0.1:6379> set msg "hellow world"

OK

127.0.0.1:6379> type msg

string

ptr：指向对象的底层实现数据结构，这些结构由对象的encoding决定。

encoding（常量）：记录了对象所使用的编码，即是用了什么数据结构作为对象的底层实现。使用命令object encoding key可以查看一个数据库键的值对象的编码：

127.0.0.1:6379> set msg "liushijie"

OK

127.0.0.1:6379> object encoding msg

"raw"
  1. 字符串对象

    字符串对象可以保存字符串数据，也可以保存整数值类型和long double类型的浮点数，并能提供数值运算。字符串的编码可以是int、raw或embstr。

    常用命令：
set get append incrbyfloat incrby decrby strlen setrange getragne
  1. 列表对象

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

    常用命令：
lpush rpush lpop rpop  lindex llen linsert lerm ltrim lset
  1. 哈希对象

    哈希对象的编码可以是ziplist或者hashtable

    常用命令：
hset hget hexists hdel hlen hgetall
  1. 集合对象

    集合对象的编码可以是inset或者hashtable

    常用命令：
sadd scard sismember smembers srandmember spop srem
  1. 有序集合对象

    有序集合的编码尅是zipist或者skiplist

    常用命令：
zadd zcard zcount zrange zrevrange zrank zrevrank zrem zscore

  1. 类型检查与命令多态

    Redis用于操作键的命令基本可以分为两种类型：

    可以对任何类型的键执行，比如del、expire、rename、type、object等

    只能对特定类型的键执行，比如：set、get、append、strlen等命令只能对字符串键执行；

    类型检查： 在执行一个类型特定的命令之前，Redis会先检查输入键的类型是否正确，然后再决定是否执行给定的命令。类型特定命令所进行的类型检查是通过redisObject结构的type属性来实现的。成功则执行，失败则返回类型错误。

    多态命令 无论输入的键是什么类型，命令都可以正确的执行。一个命令可以同时用于处理多种不同的编码。

  2. 内存回收

    Redis在自己的对象系统中构建了一个引用计数技术实现的内存回收机制，程序可以通过跟踪对象的引用计数信息，在适当的时候自动释放对象并进行内存回收。

    每个对象的引用技术信息由redisObject结构的refcount属性记录。

  3. 对象共享

    对象共享是将数据库的键的值指针指向一个现有的值对象，被共享的值对象的引用计数增一。

    对象共享可以节省内存。

  4. 对象的空转时长

    redisObject结构中包含的最后一个属性为lru属性，该属性记录了对象的最后一次被命令程序访问的时间。object idletime命令可以打印给定的键的空转时长，空转时长是通过将当前时间减去键的值对象的lru时间计算出来的。

127.0.0.1:6379> set msg liushijie

OK

127.0.0.1:6379> object idletime msg

(integer) 11

object idletime不会修改lru属性。

空转时长的其他作用：

如果服务器打开了maxmemory选项，并且服务器用于回收内存的算法为volatile-lru或者allkeys-lru，那么服务器占用的内存数超过了maxmemory选项设置的上线时，服务器会优先释放空转时长较高的那部分键。

Redis命令速查

Redis学习笔记之ABC的开头部分。

相关文章