Redis没有直接使用C语言传统的字符串表示(以空字符结尾的字符数组,以下简称C字符串),而是自己构建了一种名为简单动态字符串(simple dynamic string,SDS)的抽象类型,并将SDS用作Redis的默认字符串表示。
在Redis里面,C字符串只会作为字符串字面量(string literal)用在一些无须对字符串值进行修改的地方,比如打印日志: redisLog(REDIS_WARNING,"Redis is now ready to exit, bye bye..."); 当Redis需要的不仅仅是一个字符串字面量,而是一个可以被修改的字符串值时,Redis就会使用SDS来表示字符串值,比如在Redis的数据库里面,包含字符串值的键值对在底层都是由SDS实现的。
struct sdshdr { // 记录buf 数组中已使用字节的数量 // 等于SDS 所保存字符串的长度 int len; // 记录buf 数组中未使用字节的数量 int free; // 字节数组,用于保存字符串 char buf[]; };
redis中所定义SDS,如上所示。字符串内容由一个char数组定义的buf保存,结构中还保存了字符串的实际长度(不包括最后的‘\0’结束标志)以及buf的可用空间大小。
SDS有如下几个特点:
Redis使用的c语言并没有内置链表这种数据结构,所以Redis构建了自己的链表实现,作为redis列表的底层数据结构
typedef struct listNode { // 前置节点 struct listNode * prev; // 后置节点 struct listNode * next; // 节点的值 void * value; }listNode; typedef struct list { // 表头节点 listNode * head; // 表尾节点 listNode * tail; // 链表所包含的节点数量 unsigned long len; // 节点值复制函数 void *(*dup)(void *ptr); // 节点值释放函数 void (*free)(void *ptr); // 节点值对比函数 int (*match)(void *ptr,void *key); } list;
Redis中定义的链表结构,如上list所示,具有以下特性:
双端:链表节点带有prev和next指针,获取某个节点的前置节- 点和后置节点的复杂度都是O(1)。
字典在Redis中的应用相当广泛,比如Redis的数据库就是使用字典来作为底层实现的,对数据库的增、删、查、改操作也是构建在对字典的操作之上的。
除了用来表示数据库之外,字典还是哈希键的底层实现之一,当一个哈希键包含的键值对比较多,又或者键值对中的元素都是比较长的字符串时,Redis就会使用字典作为哈希键的底层实现。
Redis的字典使用哈希表作为底层实现,一个哈希表里面可以有多个哈希表节点,而每个哈希表节点就保存了字典中的一个键值对。
typedef struct dictht { // 哈希表数组 (表节点指针数组) dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩码,用于计算索引值 // 总是等于size-1 unsigned long sizemask; // 该哈希表已有节点的数量 unsigned long used; } dictht; typedef struct dictEntry { // 键 void *key; // 值 union{ void *val; uint64_t u64; int64_t s64; } v; // 指向下个哈希表节点,形成链表 struct dictEntry *next; } dictEntry;
Redis中字典的底层实现hash表实现如上所示。
hash表如dictht所示,其包含的数据由一个指针数组table关联,table的大小记录在size中,used记录了哈希表目前包含节点的数量。
table中每个元素是一个指向哈希表节点的dicEntry指针。哈希表节点存储了一个键值对 key - v, 以及一个指向另外一个节点的指针next。这个指针可以将多个哈希值相同的键值对连接在一次,以此来解决键冲突(collision)的问题。所以Redis中哈希表是采用链地址法来解决键冲突问题。
typedef struct dict { // 类型特定函数 dictType *type; // 私有数据 void *privdata; // 哈希表 dictht ht[2]; // rehash 索引 // 当rehash不在进行时,值为-1 int rehashidx; } 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;
Redis中基于哈希表的字典完整结构如上所示。
为了hash表的负载因子( ht0.used/ht0.size )维持在一个合理范围之内,当哈希表保存的键值对数量太多或者太少时,程序需要对哈希表的大小进行相应的扩展或者收缩。
扩展和收缩哈希表的工作可以通过执行rehash(重新散列)操作来完成,Redis对字典的哈希表执行rehash的步骤如下:
考虑到hash表中的键值对可能非常多,如果一次性完成rehash操作,rehash操作过程中可能因为庞大的计算量导致服务器不能正常处理请求,所以rehash操作是分多次渐进完成的。
以下是哈希表渐进式rehash的详细步骤:
在渐进式rehash进行期间,字典的删除(delete)、查找(find)、更新(update)等操作会在两个哈希表上进行。新添加到字典的键值对一律会被保存到ht1里面,而ht0则不再进行任何添加操作,这一措施保证了ht0包含的键值对数量会只减不增,并随着rehash操作的执行而最终变成空表。
Redis中常用的有序集合键的底层实现用到了跳跃表,其结构如下所示。
typedef struct zskiplistNode { // 层 struct zskiplistLevel { //前进指针 struct zskiplistNode *forward; // 跨度 unsigned int span; } level[]; // 后退指针 struct zskiplistNode *backward; // 分值 double score; // 成员对象 robj *obj; } zskiplistNode; typedef struct zskiplist { // 表头节点和表尾节点 structz skiplistNode *header, *tail; // 表中节点的数量 unsigned long length; // 表中层数最大的节点的层数 int level; } zskiplist;
上图左边第一个表示了 zskiplist结构,管理整个跳表,右边四个节点描述了4个zskiplistNode结构,代表了跳表中的节点。
zskiplist结构中的header指向的头节点分值score和obj无意义,length字段记录的长度不包含该头节点,level记录了跳表中目前最高层次节点的层数。
zskiplistNode结构中 obj指向节点实际存储的成员对象(o1,o2,o3),score表示节点的分值,跳表中节点按分值从小到大排列,backward指向前驱节点。level(L1、L2、……、LN)记录了该节点的各层信息。
(L1、L2、……、LN)层信息结构为zskiplistLevel结构所定义的层信息,其中包含了指向该层下一节点的指针forward,以及距离本层下一节点的距离span, 相邻节点的距离为1。因此计算从头节点遍历到某个节点所经过的路径的span之和就可以得到该节点的在整个跳表中的排名。
整数集合(intset)是Redis用于保存整数值的集合抽象数据结构,它可以保存类型为int16_t、int32_t或者int64_t的整数值,并且保证集合中不会出现重复元素。整数集合的结构如下。
typedef struct intset { // 编码方式 uint32_t encoding; // 集合包含的元素数量 uint32_t length; // 保存元素的数组 int8_t contents[]; } intset;
实际元素有序的保存在contents中,其中不存在重复元素。contents虽然被定义为int8_t,但其并不保存int8_t的元素。根据实际需要,编码方式encoding会从16位到64位升级,分别对应INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64三种编码类型。encoding为上述三种值时,contents分别为 int16_t、int32_t、int64_t的数组。
说明:在能满足表示集合中元素范围的情况下,redis总时采用最省空间的编码方式,当有超出当前编码方式表示的范围的新元素加入,整数集合会对所有元素升级编码方式、重新申请空间。编码方式一旦被升级,不会再降级。
压缩列表(ziplist)是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来做列表键的底层实现。
压缩列表是Redis为了节约内存而开发的,是由一系列特殊编码的连续内存块组成的顺序型(sequential)数据结构。一个压缩列表可以包含任意多个节点(entry),每个节点可以保存一个字节数组或者一个整数值。
压缩列表结构如上图所示,其节点数据存放在entryX中,每个节点entryX结构如下图所示。
previous_entry_length: 字段代表前一个节点(entry)的长度,有了这个值,就可以通过当前节点的起始地址进行指针偏移运算得到前一个节点的起始地址,从而直接访问前一个节点。
encoding: 记录了节点的content属性所保存数据的类型以及长度。
content: 保存节点的值,可以是一个字节数组或整数,值的类型和长度,根据encoding的值确定。
typedef struct redisObject { // 类型 unsigned type:4; // 编码 unsigned encoding:4; // 指向底层实现数据结构的指针 void *ptr; // ... } robj;
redis对象数据结构的核心定义如上代码片段所示:
不同类型的对象,其采用的底层结构,如下图所示。
原创声明,本文系作者授权云+社区发表,未经许可,不得转载。
如有侵权,请联系 yunjia_community@tencent.com 删除。
我来说两句