《redis设计与实现》1-数据结构与对象篇

• 如果前面节点长度小于254字节，preivos_entry_length用1字节表示
• 如果前面节点长度小于254字节，preivos_entry_length用5字节表示，第1个字节为0xFE（254），后面四个字节表示实际长度

• content：保存节点的值

连锁更新

• 连续多个节点大小介于254左右的节点，因扩展导致连续内存分配的情况。不过在时间情况下，这种情况比较少。

对象

概述

• redis并没有直接使用前面的数据结构来实现键值对的数据库，而是基于数据结构创建了一个对象系统，每种对象都用到前面至少一种数据结构
• 每个对象都由一个redisObject结构来表示

//server.h
typedef struct redisObject {
   unsigned type:4; //类型
   unsigned encoding:4; // 编码
   // 对象最后一个被命令程序访问的时间
   unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                           * LFU data (least significant 8 bits frequency
                           * and most significant 16 bits access time). */
   int refcount; // 引用计数
   void *ptr; // 指向底层的数据结构指针
} robj;

使用对象的好处

• 在执行命令之前，根据对象类型判断一个对象是否可以执行给定的命令
• 针对不同厂家，Wie对象设置多种不同的数据结构实现，从而优化效率
• 实现了基于引用计数的内存回收机制，不再使用的对象，内存会自动释放
• 引用计数实现对象共享机制，多个数据库共享同一个对象以节约内存
• 对象带有时间时间积累信息，用于计算空转时间

redis中的对象

• 字符串对象
• 列表对象
• 哈希对象
• 集合对象
• 有序结合对象

对象的类型与编码

对象的类型

对象的编码

• 编码决定了ptr指向的数据类型，表明使用什么数据类型作为底层实现
• 每种类型对象至少使用两种不同的编码
• 通过编码，redis可以根据不同场景设定不同编码，极大提高灵活性和效率

字符串对象

• 字符串对象的编码可以是
  • int

- raw 

- embstr 

• 浮点数在redis中也是作为字符串对象保存，涉及计算时，先转回浮点数。

embstr编码是专门用于保存短字符串的一种优化编码方式。这种编码和raw编码一样，都使用redisObject结构和sdshdr结构来表示对象。区别在于：

• raw编码调用两次内存分配函数来分别创建redisObject和sdrhdr结构
• embstr则调用一次内存分配函数来创建一块连续空间，里面包括redisObject和sdrhdr

编码转换

int编码和embstr编码的对象满足条件时会自动转换为raw编码的字符串对象

• int编码对象，执行命令导致对象不再是整数时，会转换为raw对象
• embstr编码没有相应执行函数，是只读编码。涉及修改时，会转换为raw对象

字符串命令

redis中所有键都是字符串对象，所以所有对于键的命令都是针对字符串键来构建的

• set
• get
• append
• incrbyfloat
• incrby
• decrby
• strlen
• strrange
• getrange

列表对象

• 列表对象的编码可以是
  • ziplist

- linkedlist 

编码转换

使用ziplist编码的两个条件如下，不满足的都用linkedlist编码（这两个条件可以在配置文件中修改）:

• 保存的所有字符串元素的长度都小于64字节
• 列表的元素数量小于512个

列表命令

• lpush
• rpush
• lpop
• rpop
• lindex
• llen
• linsert
• lrem
• ltrim
• lset

哈希对象

哈希对象的编码可以是

• ziplist

• hashtable

编码转换

• 使用ziplist需要满足两个条件，不满足则都使用hashtable（这两个条件可以在配置文件中修改）
  • 所有键值对的键和值的字符串长度都小于64字节
  • 键值对数量小于512个

哈希命令

• hset
• hget
• hexists
• hdel
• hlen
• hgetall

集合对象

集合对象的编码可以是：

• intset：所有元素保存在整数集合里

• hashtale：字典的值为null

编码转换

集合使用intset需要满足两个条件，不满足时使用hashtable（参数可通过配置文件修改）

• 保存的所有元素都是整数值
• 元素数量不超过512个

集合命令

• sadd
• scard
• sismember
• smembers
• srandmember
• spop
• srem

有序结合对象

有序集合的编码可以是

• ziplist：每个元素使用两个紧挨在一起的节点表示，第一个表示成员，第二个表示分值。分值小的靠近表头，分值大的靠近表尾

• skiplist：使用zset作为底层实现，zset结构同时包含了字典和跳跃表，分别用于根据key查找score和分值排序或范围查询

// 两种数据结构通过指针共享元素成员和分值，不会浪费内存
typedef struct zset {
    zskplist *zsl; //跳跃表，方便zrank，zrange
    dict *dict; //字典，方便zscore
}zset;

编码转换

当满足以下两个条件时，使用ziplist编码，否则使用skiplist（可通过配置文件修改）

• 保存的元素数量少于128个
• 成员长度小于64字节

有序集合命令

• zadd
• zcard
• zcount
• zrange
• zrevrange
• zrem
• zscore

类型检查和命令多态

redis的命令可以分为两大类：

• 可以对任意类型的键执行，如
  • del
  • expire
  • rename
  • type
  • object
• 只能对特定类型的键执行，比如前面各种对象的命令。是通过redisObject的type属性实现的

内存回收

redis通过对象的refcount属性记录对象引用计数信息，适当的时候自动释放对象进行内存回收

对象共享

• 包含同样数值的对象，键的值指向同一个对象，以节约内存。
• redis在初始化时，创建一万个字符串对象，包含从0-9999的所有整数值，当需要用到这些值时，服务器会共享这些对象，而不是新建对象
• 数量可通过配置文件修改
• 目前不包含字符串的对象共享，因为要比对字符串是否相同本身就会造成性能问题

对象空转时长

• 空转时长=现在时间-redisObject.lru，lru记录对象最后一次被访问的时间
• 当redis配置了最大内存（maxmemory）时，回收算法判断内存超过该值时，空转时长高的会优先被释放以回收内存

参考命令

# 设置字符串
set msg "hello world"
rpush numbers 1 2 3 4 5
llen numbers
lrange numbers 0 5
# 获取键值使用的底层数据结构
object encoding numbers
# 查看对象的引用计数值
object refcount numbers
# 对象空转时长: value=now-object.lru
object idletime numbers

参考文献

• 《redis设计与实现》