redis数据格式介绍

李宁

Remote Dictionary Server(Redis)是一个基于 key-value 键值对的持久化数据库存储系统。由于其丰富的数据结构和单线程高性能特性,现在在各系统中的使用越来越多,大部分情况下被当做缓存使用,也可用于分布式锁,计数器,排行榜,队列等场景。

Redis中的每个键值对的键和值都是一个RedisObject结构体,这样所有的数据类型就都可以以相同的形式在函数间传递而不用使用特定的类型结构。
定义如下:

typedef struct redisObject {  
    unsigned type; /* 4位,表示对象类型 */
    unsigned encoding; /* 4位,表示对象类型的物理编码方式 */
    unsigned lru; /* lru time 24位  */
    int refcount;  /*指向对象的引用计数器 4字节*/
    void *ptr; /*指向真正的存储结构 8字节*/
} robj;

对象类型

其中type对应了五种数据类型:字符串(String)、列表(List)、哈希(Hash)、集合(Set)、有序集合(ZSet

/* The actual Redis Object */
#define OBJ_STRING 0
#define OBJ_LIST 1 
#define OBJ_SET 2
#define OBJ_ZSET 3
#define OBJ_HASH 4

每种类型的对象至少有两种或以上的encoding方式,不同编码 可以在不同的使用场景上优化对象的使用场景,提高性能。用TYPE命令可查看某个键值对的类型

对象编码

encoding则对应了 Redis 中的十种编码方式

/* Objects encoding. Some kind of objects like Strings and Hashes can be
 * internally represented in multiple ways. The 'encoding' field of the object
 * is set to one of this fields for this object. 
 */
#define OBJ_ENCODING_RAW     /* Raw representation */ 简单动态字符串
#define OBJ_ENCODING_INT      /* Encoded as integer */ 整数
#define OBJ_ENCODING_HT       /* Encoded as hash table */ 字典
#define OBJ_ENCODING_ZIPLIST  /* Encoded as ziplist */ 压缩列表
#define OBJ_ENCODING_INTSET   /* Encoded as intset */ 整数集合
#define OBJ_ENCODING_SKIPLIST   /* Encoded as skiplist */ 跳跃表
#define OBJ_ENCODING_EMBSTR  /* Embedded sds string encoding */ embstr编码的简单动态字符串
#define OBJ_ENCODING_QUICKLIST  /* Encoded as linked list of ziplists */

使用object encoding命令可以查看某个对象的编码

typeencoding的对应关系如下图:

String

字符串对象保存值的整数值,那么编码会设置为INT。当字符串值得长度小于等于39字节使用EMBSTR, 大于39字节使用RAW

EMBSTR编码和RAW编码都是用SDS简单动态字符串结构来表示。RAW编码会调用两次内存分配函数来分别创建redisObjectSDS结构, 而EMBSTR只调用一次内存分配函数来分配一块连续的空间保存数据,比起RAW编码的字符串更能节省内存,以及能提升获取数据的速度。

不过EMBSTR是不可修改的,当对EMBSTR编码的字符串执行任何修改命令,总会先将其转换成RAW编码再进行修改

SDS

Redis没有使用C语言的字符串, C语言的字符串只会用在不需要对字符串修改而只使用其值地方. Redis使用SDS表示字符串, 结构定义 :

typedef char *sds;

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

SDS也是以'\0'表示结束, 这一个字节不会计入已使用的长度. 这样做的好处是可以重用C字符串函数库里面的一部分函数.

SDS的优点:

  • 常数时间获取字符串长度,时间复杂度为O(1)
  • 防止缓冲区溢出。当API需要对SDS进行修改时, API会首先会检查SDS的空间是否满足条件, 如果不满足, API会自动对它动态扩展, 然后再进行修改, 这个过程是完全透明的。
  • 减少修改字符串带来的内存重分配次数。修改后len长度将小于 1 M, 这时分配给free的大小和len一样;如果修改后len长度将大于等于1 M, 这时分配给free的长度为 1 M。
  • 二进制安全。C字符串只有末尾能保存空格, 中间如果有空格会被截取, 认作结束标识. 这样就不能保存图片, 音频视频等二进制数据了,数据中间也不能出现'\0'
List

3.2版本之前的列表对象编码为ziplistlinkedlist
当列表对象保存的字符串对象长度都小于64字节并且元素数量小于512个,使用ziplist编码,可以通过修改配置list-max-ziplist-valuelist-max-ziplist-entries来修改这两个条件的上限值、两个条件任意一个不满足时,ziplist会变为linkedlist。

从3.2开始Redis只使用quicklist作为列表的编码

  • linkedlist在插入节点上复杂度很低,但它的内存开销大,每个节点的地址不连续,容易产生内存碎片。
  • ziplist是存储在一段连续的内存上,存储效率高,但是不利于修改操作,插入和删除数都很麻烦,而且需要频繁的申请释放内存,特别是ziplist中数据较多的情况下,搬移内存数据太费时

quickList是zipList和linkedList 的混合体,它将linkedList按段切分,每一段使用zipList来紧凑存储,多个zipList之间使用双向指针串接起来。在时间和空间上做了一个均衡,能较大程度上提高Redis的效率

为了进一步节约空间,Redis还会对ziplist 进行压缩存储,使用LZF算法压缩,可以选择压缩深度。

Hash

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

同时满足以下两个条件将使用ziplist编码:

1. 所有键和值的字符串长度小于64字节;  
2. 键值对的数量小于512个  

使用ziplist编码时,保存同一键值对的两个节点总是紧挨在一起,键节点在前,值节点在后

不能满足这两个条件的都需要使用hashtable编码。

以上两个上限值可以通过hash-max-ziplist-valuehash-max-ziplist-entries来修改

Set

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

当满足以下两个条件时使用intset编码:

1. 所有元素都是整数值  
2. 元素数量不超过512个  

可以修改set-max-intset-entries设置元素数量的上限。

使用hashtable编码时,字典的每一个键都是字符串对象,字典的值全部设置为null。类似java中HashSet的实现

Sorted Set

有序集合对象的编码可以是ziplist或者skiplist

同时满足以下条件时使用ziplist编码:

1. 元素数量小于128个  
2. 所有成员对象的长度都小于64字节  

ziplist编码的有序集合使用紧挨在一起的压缩列表节点来保存,第一个节点保存member,第二个保存score。ziplist内的集合元素按score从小到大排序,score较小的排在表头位置。

skiplist编码的有序集合底层是一个命名为zset的结构体,而一个zset结构同时包含一个字典和一个跳跃表。跳跃表按score从小到大保存所有集合元素,按score定位member速度快。
而字典则保存着从member到score的映射,这样就可以用O(1)的复杂度来查找member对应的score值。

虽然同时使用两种结构,但会通过指针来共享相同元素的member和score,不会浪费额外的内存。

LRU

每一个Redis对象都会设置相应的lru,即最近访问的时间。每一次访问数据的时候都会更新 Redis 提供 6 种数据淘汰策略

1. volatile-lru:从已设置过期时间的数据集(server.db[i].expires)中挑选最近最少使用 的数据淘汰  
2. volatile-ttl:从已设置过期时间的数据集(server.db[i].expires)中挑选将要过期的数 据淘汰  
3. volatile-random:从已设置过期时间的数据集(server.db[i].expires)中任意选择数据 淘汰  
4. allkeys-lru:从数据集(server.db[i].dict)中挑选最近最少使用的数据淘汰  
5. allkeys-random:从数据集(server.db[i].dict)中任意选择数据淘汰  
6. no-enviction(驱逐):禁止驱逐数据  

在Redis中volatile-lru、allkeys-lru算法是一个近似算法,默认情况下,Redis随机挑选5个键,并且从中选取一个最近最久未使用的key进行淘汰,在配置文件中可以通过maxmemory-samples的值来设置redis需要检查key的个数,但是检查的越多,耗费的时间也就越久,但结果越精确

refcount

refcount记录的是该对象被引用的次数,类型为整型。refcount的作用,主要在于对象的引用计数和内存回收。当创建新对象时,refcount初始化为1;当有新程序使用该对象时,refcount加1;当对象不再被一个新程序使用时,refcount减1;当refcount变为0时,对象占用的内存将被释放。

Redis中被多次使用的对象(refcount>1),称为共享对象。Redis为了节省内存,当有一些对象重复出现时,新的程序不会创建新的对象,而是仍然使用原来的对象。这个被重复使用的对象,就是共享对象。目前共享对象仅支持整数值的字符串对象。

reference