Redis 对象与数据结构

Redis 是由C语言编写的。

Redis 的key总是string类型的;

Redis的Value可以是以下五种类型:string(字符串),hash(哈希),list(列表),set(集合)及zset(sorted set:有序集合)。


such as strings, hashes, lists, sets, sorted sets with range queries, bitmaps, hyperloglogs and geospatial indexes with radius queries.

Redis 对象

Redis 设计与实现第二版

主要数据结构, 比如embstr,简单动态字符串( SDS) 、双端链表、字典dict (hashtable)、压缩列表ziplist、整数集合intset,跳跃表skiplist。

Redis 并没有直接使用这些数据结构来实现键值对数据库, 而是基于这些数据结构创建了一个对象系统, 这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象, 每种对象都用到了至少一种我们前面所介绍的数据结构。

通过这五种不同类型的对象, Redis 可以在执行命令之前, 根据对象的类型来判断一个对象是否可以执行给定的命令。

使用对象的另一个好处是, 我们可以针对不同的使用场景,为对象设置多种不同的数据结构实现, 从而优化对象在不同场景下的使用效率。

除此之外, Redis 的对象系统还实现了基于引用计数技术的内存回收机制, 当程序不再使用某个对象的时候, 这个对象所占用的内存就会被自动释放;

另外, Redis 还通过引用计数技术实现了对象共享机制, 这一机制可以在适当的条件下, 通过让多个数据库键共享同一个对象来节约内存。

最后, Redis 的对象带有访问时间记录信息, 该信息可以用于计算数据库键的空转时长, 在服务器启用了maxmemory功能的情况下, 空转时长较大的那些键可能会优先被服务器删除。

redisObject结构

typeof struct redisObject{

    unsigned type:4;

    unsigned encoding:4;

    void *ptr;

    int refcount;

    unsigned lru:22;
}

type: 表示对象的类型

Redis可以依此判断命令是否可以执行,如HDEL,HSET只能对HASH类型的对象执行。

  • SET 、GET 、APPEND 、STRLEN 等命令只能对字符串键执行;
  • HDEL 、HSET 、HGET 、HLEN 等命令只能对哈希键执行;
  • RPUSH 、LPOP、LINSERT 、LLEN 等命令只能对列表键执行;
  • SADD、SPOP、SINTER、SCARD等命令只能对集合键执行;
  • ZADD 、ZCARD 、ZRANK、ZSCORE等命令只能对有序集合键执行;
类型常量对象名称
REDIS_STRING字符串对象
REDIS_LIST列表对象
REDIS_HASH哈希对象
REDIS_SET集合对象
REDIS_ZSET有序集合对象

encoding: 编码,表示Redis类型采取的数据结构

多态命令的实现:这里的命令指的是对Redis类型不同数据结构的操控。

Redis 除了会根据值对象的类型来判断键是否能够执行指定命令之外, 还会根据值对象的编码方式, 选择正确的命令实现代码来执行命令。

编码常量编码所对应的的底层数据结构
REDIS_ENCODING_INTlong 类型的整数
REDIS_ENCODING_EMBSTRembstr 编码的简单动态字符串
REDIS_ENCODING_RAW简单动态字符串
REDIS_ENCODING_HT字典
REDIS_ENCODING_LINKEDLIST双端链表
REDIS_ENCODING_ZIPLIST压缩列表
REDIS_ENCODING_INTSET整数集合
REDIS_ENCODING_SKIPLIST跳跃表和字典
HT 代表hashtable,字典使用hashtable实现的;
embstr是embed string;
REDIS_ENCODING_INT、REDIS_ENCODING_EMBSTR、REDIS_ENCODING_RAW对应的都是Redis五种对象类型中的String;

* ptr : 指向对象的底层实现数据结构的指针,

数据结构由对象的encoding属性决定。

Redis有五种对象类型,他们实现的数据结构可以为以下几种:

类型编码对象
REDIS_STRINGREDIS_ENCODING_INT使用整数值实现的字符串对象
REDIS_STRINGREDIS_ENCODING_EMBSTR使用编码的简单动态字符串实现的字符串对象
REDIS_STRINGREDIS_ENCODING_RAW使用简单动态字符串实现的字符串对象
REDIS_LISTREDIS_ENCODING_ZIPLIST使用压缩列表实现的列表对象
REDIS_LISTREDIS_ENCODING_LINKEDLIST使用双端链表实现的列表对象
REDIS_HASHREDIS_ENCODING_ZIPLIST使用压缩列表实现的哈希对象
REDIS_HASHREDIS_ENCODING_HT使用字典实现的哈希对象
REDIS_SETREDIS_ENCODING_INTSET使用整数集合实现的集合对象
REDIS_SETREDIS_ENCODING_HT使用字典实现的集合对象
REDIS_ZSETREDIS_ENCODING_ZIPLIST使用压缩列表实现的有序集合对象
REDIS_ZSETREDIS_ENCODING_SKIPLIST使用跳跃表和字典实现的有序集合对象

refcount:保存引用计数,内存回收,对象共享

字符串对象共享,其他数据结构中如果嵌套了字符串类型,可以共享数据结构中的字符串。

对象共享则refcount + 1

lru : Least Recently Used 最后一次使用时间,用以计算对象的空转时长

当前时间减去键的值对象的lru时间 即为空转时长。

OBJECT IDlETIME :这个命令用以查看对象的空转时长,且不会改变对象的最后一次访问时间(lru),idle:闲置的,停顿的

键的空转时长还有另外一项作用,如果服务器打开了maxmemory 选项, 并且服务器用于回收内存的算法为volatile-lru或者allkeys-lru ,那么当服务器占用的内存数超过了maxmemory 选项所设置的上限值时, 空转时长较高的那部分键会优先被服务器释放, 从而回收内存。

配置文件的maxmemory 选项和maxmemory-policy 选项的说明介绍了关于这方面的更多信息。

数据结构

REDIS_ENCODING_INT long 类型的整数
REDIS_ENCODING_EMBSTR embstr 编码的简单动态字符串
REDIS_ENCODING_RAW 简单动态字符串

REDIS_ENCODING_INT,REDIS_ENCODING_EMBSTR,REDIS_ENCODING_RAW这三种数据结构或者说编码都是针对Redis的String类型的。

如果一个字符串对象保存的是整数值, 并且这个整数值可以用long 类型来表示, 那么字符串对象会将整数值保存在字符串对象结构的*ptr属性里面( 将void* 转换成long),并将字符串对象的编码设置为int。

如果字符串对象保存的是一个字符串值, 并且这个字符串值的长度大于32 字节, 那么字符串对象将使用一个简单动态字符串( SDS ) 来保存这个字符串值, 并将对象的编码设置raw。

如果字符串对象保存的是一个字符串值, 并且这个字符串值的长度小于等于32 字节,那么字符串对象将使用embstr 编码的方式来保存这个字符串值。

embstr 编码是专门用于保存短字符串的一种优化编码方式, 这种编码和raw 编码一样, 都使用redis0bject 结构和sdshdr 结构来表示字符串对象, 但raw 编码会调用两次内存分配函数来分别创建redis0bject 结构和sdshdr 结构, 而embstr 编码则通过调用一次内存分配函数来分配一块连续的空间, 空间中依次包含redis0bject 和sdshdr两个结构。

  • embstr 编码将创建字符串对象所需的内存分配次数从raw 编码的两次降低为一次。
  • 释放embstr 编码的字符串对象只需要调用一次内存释放函数, 而释放raw 编码的字符串对象需要调用两次内存释放函数。
  • 因为embstr 编码的字符串对象的所有数据都保存在一块连续的内存里面, 所以这种编码的字符串对象比起raw 编码的字符串对象能够更好地利用缓存带来的优势。(内存分配,不需要寻找第二次分配内存的空间)

REDIS_ENCODING_HT 字典

在HASH和SET 中都可以使用HT,hashtable结构的字典,HASH中存储key-value ,在SET中只利用hash来存key(相当于set的值,value则为NULL)

字典dict, dictionary ,键独一无二。

Redis 的字典使用哈希表作为底层实现, 一个哈希表里面可以有多个哈希表节点, 而每个哈希表节点就保存了字典中的一个键值对。也就是key-value 通过hashtable的方式存储。

字典的底层就是一个hashtable :Redis源码中的dictht结构,

  • 其中 **table代表一个数组,其中存储的是dictEntry的指针,dictEntry是hashtable的节点;
  • size代表hashtable的大小,也就是上面table数组的大小;
  • used代表该哈希表巳有节点(dictEntry)的数量;
  • sizemask 属性的值总是等于size-1 , 这个属性和哈希值一起决定一个键应该被放到table 数组的哪个索引上面。
typede f struct dictht {
    // 哈希表數组
    dictEntry **table;
    // 哈希表大小
    unsigned  long size;
    // 该哈希表巳有节点的数量
    unsigned 10ng used;
    //哈希表大小掩码, 用于计算索引值
    //总是等于size-1
    unsigned iong sizemask;
} dictht;

那么来看一下hashtable的节点dictEntry,也就是存储字典key-value的地方:

next属性是指向另一个hashtable节点的指针,解决冲突,也就是使用单链表来保存多个hash相同的值。

typedef struct dictentry {
    void *key
    union{
        void  *val ;
        uint64_t  u64 ;
        int64_t  s64 ;
    }v;
    //指向下个哈希表节点, 形成链表
    struct dictEntry *next;
} dictEntry;

最后再来看一下字典的结构:

type 属性和privdata 属性是针对不同类型的键值对, 为创建多态字典而设置的。

  • type 属性是一个指向dictType 结构的指针, 每个dictType 结构保存了一簇用于操作特定类型键值对的函数, Redis 会为用途不同的字典设置不同的类型特定函数。
  • 而privdata 属性则保存了需要传给那些类型特定函数的可选参数。

ht[2] 代表两个hashtable,字典数据只存储在ht[0]中,ht[1]和rehashidx是在rehash的时候使用的。

typedef struct dict {
    //类型特定函数
    dictType *type;
    //私有數据
    void *privdata;
    //哈希表
    dictht ht[2];
    //rehash 索引
    //当rehash 不在进行时, 值为-1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

rehash

随着操作的不断执行, 哈希表保存的键值对会逐渐地增多或者减少, 为了让哈希表的负载因子( load factor ) 维持在一个合理的范围之内, 当哈希表保存的键值对数量太多或者太少时, 程序需要对哈希表的大小进行相应的扩展或者收缩。

load factor = used / size

扩展和收缩哈希表的工作可以通过执行rehash ( 重新散列) 操作来完成, Redis 对字典的哈希表执行rehash 的步骤如下:
1 ) 为字典的ht[1]哈希表分配空间, 这个哈希表的空间大小取决于要执行的操作, 以及ht[0] 当前包含的键值对数量(也即是ht[0].used 属性的值):

  • 如果执行的是扩展操作, 那么ht[1] 的大小为2^n,且为第一个大于等于ht[0].used*2^n 。
  • 如果执行的是收缩操作, 那么ht[1] 的大小为2^n,且为第一个大于等于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
做准备。

渐进式rehash

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

渐进式rehash 的好处在于它采取分而治之的方式, 将rehash 键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上, 从而避免了集中式rehash 而带来的庞大计算量

因为在进行渐进式的过程中, 字典会同时使用ht[0]和[1]两个哈希表,所以在渐进式rehash 进行期间, 字典的删除〈delete ) 、查找( find ) 、更新( update ) 等操作会在两个哈希表上进行。例如, 要在字典里面查找一个键的话, 程序会先在ht[0] 里面进行查找, 如果没找到的话, 就会继续到ht[1]里面进行查找, 诸如此类。

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

REDIS_ENCODING_LINKEDLIST 双端链表

双链表,只有在Redis对象类型为List的时候才会使用这个数据结构,List两种数据结构的另一种是压缩列表,也就是ziplist。

看下面

REDIS_ENCODING_ZIPLIST 压缩列表

ziplist这种数据结构一般在键值较短,或者存储的值较小的情况下使用,Redis中在LIST、HASH和ZSET中使用。

ziplist是由一系列特殊编码的连续内存块组成的顺序型(sequential)数据结构,什么叫特殊编码,就是自己定义的存储信息的结构。

ziplist在连续内存块的前面存储了4个字节的zlbytes,4个字节的zltail,2个字节的zllen,在内存块的后面存储了1个字节的zlend作为结束标记。

  • zlbytes记录整个压缩列表占用的内存字节数,在对压缩列表进行内存重新分配时,或者计算zlend位置时使用;
  • zltail 记录距离起始地址的表位节点的偏移量;
  • zllen记录了压缩列表的节点数量,因为其只有两个字节,所以最大记录UINT16_MAX 也就是65535,如果数量超过这个大小,那么只能遍历到结尾才知道存储了多少个节点。

压缩节点的构成

previous_entry_length:这个属性记录了压缩列表中的前一个节点的长度,思考一下,这个就是为了从当前位置减去这个偏移量来获得前一个节点的位置。这个属性占一个字节或5个字节。previous_entry_length记录的前一个节点的长度包括前一个节点的previous_entry_length、encoding和content。

encoding记录了该节点中content锁保存数据的类型及其长度。

再来考虑一下previous_entry_length这个属性为什么会占一个字节5个字节?

压缩列表本来就是针对存储内容较小的节点而设计的。一个节点的长度如果小于254那么只需要1个字节的previous_entry_length就可以保存,何乐而不为。但是大于等于254时一个字节不够存,那么就要扩充previous_entry_length为5个字节(第一个字节存特殊字符0xFE,也就是254,用以标记这个previous_entry_length有5个字节)。

如果一个节点的content变动了,或导致一个问题:content大小变动后下一个节点的previous_entry_length大小从1个字节变为5个字节或者从5个字节变为1个字节。这个时候如果ziplist 中大部分节点的大小在加上4个字节(或减小4个字节)都会导致下一个节点重复变动长度大小(需要重写分配内存空间),那么时间复杂度为O(N^2)。这个问题叫做连锁更新,增加和删除、更改操作都会引发这个问题。当然,几乎不太可能。

REDIS_ENCODING_INTSET 整数集合:升级操作

关于Redis中INTSET的升级是最重要的点,至于为什么?先看INTSET的数据结构。

typedef struct intset {
    //编码方式
    uint32_t encoding;
    //集合包含的元素数量
    uint32_t length :
    //保存元素的数组
    int8_t contents[]
} intset;

虽然intset 结构将contents 属性声明为int8_t类型的数组, 但实际上contents 数
组并不保存任何int8_t类型的值, contents 数组的真正类型取决于encoding 属性的值:
encoding 属性的值为可以为INTSET_ENC_INT16, INTSET_ENC_INT32, INTSET_ENC_INT64。其取决于contents中存储元素中类型最长的那个,也就是说如果此时encoding为int16,进行了一个存大小为int64元素的操作,那么encoding变为INTSET_ENC_INT64,且contents数组将重新分配内存,之前的每一个值都要存储在INTSET_ENC_INT64大小的空间中,这就是升级操作。

这么做是为了提升整数集合的灵活性(int16,32,64都可以存),而是尽可能的节约内存。

在Redis中只有在SET中元素数量不多且只包含整数时,SET才会使用intset数据结构。

REDIS_ENCODING_SKIPLIST 跳跃表和字典

跳跃表skiplist在Redis中用于ZSET 和在集群节点中作内部数据结构。

在ZSET中用字典存储key和对value的映射,用以通过hash查找key为O(1),用skiplist存储排序的value。

skiplist在双链表上添加多层索引以达到类似二分查找的效果,与平衡二叉树相比,二叉树在几次修改操作后需要进行rebalance操作。底层又是双链表,所以查到了,再添加删除修改的话都是O(1)操作。其向上建立索引是随机选取节点,因为节点的删除,修改都是随机的。

String (string,int,float) SDS

redis 的字符串并不是C语言的字符串(以空字符结尾的字符数组),而是一种名为简单动态字符串(simple dynamic string, SDS)的抽象类型,作为Redis字符串的默认表示。

C字符串只会作为字符串字面量用在一些无需对字符串值进行修改的地方。

string类型是二进制安全的。意思是redis的string可以包含任何数据。比如jpg图片或者序列化的对象 。
一个键最大能存储512M。
int格式命令:incr(自增),decrby(自减)

127.0.0.1:6379> set name "yiyehu"
OK
127.0.0.1:6379> get name
"yiyehu"

其中name是SDS ,yiyehu也是SDS

SDS还可以被用作缓冲区:AOF模块中的AOF缓冲区,以及客户端状态中的输入缓冲区。

struct sdshdr {
    // 记录buf 数组中巳使用字节的数量
    // 等于SDS 所保存字符串的长度
    int len;
    // 记录加f 数组中耒使用字节的数量
    int free;
    // 字节数组, 用于保存字符串
    char buf [];
};

为什么使用SDS而不是C字符串呢?

SDS取字符串长度的时间复杂度O(1) ;C字符串为O(n)

防止缓冲区溢出;

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

二进制安全

兼容部分C字符串函数

在一般程序中, 如果修改字符串长度的情况不太常出现, 那么每次修改都执行一次内存重分配是可以接受的。但是Redis 作为数据库, 经常被用于速度要求严苛、数据被频繁修改的场合, 如果每次修改字符串的长度都需要执行一次内存重分配的话, 那么光是执行内存重分配的时间就会占去修改字符串所用时间的一大部分, 如果这种修改频繁地发生的话,可能还会对性能造成影响。

  • 修改后的空间预分配:已使用空间小于1M ,分配与已使用空间同样大小的未使用空间,大于1M,分配1M的未使用空间(free = 1M)
  • 惰性空间释放

List

Redis 列表是简单的 字符串列表 ,按照插入顺序排序

127.0.0.1:6379> lpush yiyehu age=23 name=yiyehu address=notToTellYou
(integer) 3
127.0.0.1:6379> lrange yiyehu 0 4
1) "address=notToTellYou"
2) "name=yiyehu"
3) "age=23"

HASH

存储键值(key-value,field-value)对集合。

Redis hash是一个string类型的field和value的映射表,hash特别适合用于存储对象。

HMSET 设置多个散列值 (hash multi-set ??)

HGET 获取散列值

127.0.0.1:6379> HMSET key field value [field value ...]

127.0.0.1:6379> HGET key field

redis-list 介绍和命令:菜鸟教程

Set

ZSet(sorted set)