程序员人生 网站导航

《Redis设计与实现》[第一部分]数据结构与对象-C源码阅读(二)

栏目:php教程时间:2016-06-24 08:41:52

4、跳跃表

关键字:层高随机

跳跃表支持平均O(logN)、最坏O(N)复杂度的结点查找,还可以通过顺序性操作来批量处理结点。

在大部份情况下,跳跃表的效力可以和平衡树相媲美,由于跳跃表的实现比平衡树来得更加简单,所以很多程序都使用跳跃表代替平衡树。

Redis使用跳跃表作为有序集合键的底层实现之1,如果有1个有序集合包括的元素数量比较多,或有序集合中元素的成员是比较长的字符串时,Redis就会使用跳跃表作为有序集合键的底层实现。

Redis只在两个地方用到了跳跃表,1个是实现有序集合键,另外一个是在集群结点中用作内部数据结构

数据结构源码

Redis的跳跃表由redis.h/zskiplistNode和redis.h/zskiplist两个结构定义:

/* * 跳跃表节点 */ typedef struct zskiplistNode { // 成员对象 robj *obj; // 分值 double score; // 后退指针 struct zskiplistNode *backward; // 层 struct zskiplistLevel { // 前进指针 struct zskiplistNode *forward; // 跨度 unsigned int span; } level[]; } zskiplistNode;

zskiplistNode结构包括以下属性:

  • 层(level)数组可以包括多个元素:每一个层带有两个属性:前进指针和跨度。前进指针用于访问位于表尾方向的其他结点,而跨度则记录了前进指针所指向结点和当前节点的距离。当程序从表头向表尾进行遍用时,访问会沿着层的前进指针进行。层的数量越多,访问其他结点的速度就越快。

    • 每次创建1个新跳跃表结点,程序都根据幂次定律(power law,越大的数出现的几率越小)随机生成1个介于1和32之间的值作为level数组的大小,即层的高度。
    • 前进指针为NULL的层跨度为0
  • 后退(backward)指针:结点中用BW字样标记结点的后退指针,它指向位于当前节点的前1个结点。后退指针在程序从表尾向表头遍用时使用。与可以1次跳过量个结点的前进指针不同,每一个结点只有1个后退指针,所以每次只能后退至前1个结点

  • 分值(score):1个double类型的浮点数,跳跃表中,结点按各自所保存的分值从小到大排列

  • 成员对象(obj):1个指针,指向保存着1个SDS值的字符串对象
  • 在同1个跳跃表中,各个节点保存的成员对象必须是唯1的,但是多个结点保存的分值可以相同:分值相同的结点依照成员对象在字典序中的大小排序,较小的排在前面(靠近表头)
/* * 跳跃表 */ typedef struct zskiplist { // 表头节点和表尾节点 struct zskiplistNode *header, *tail; // 表中节点的数量 unsigned long length; // 表中层数最大的节点的层数 int level; } zskiplist;

zskiplist结构用于保存跳跃表结点的相干信息,如结点数量,指向表头结点和表尾结点的指针等:

  • header:指向跳跃表的表头结点
  • tail:指向跳跃表的表尾结点
  • level:记录目前跳跃表内,层数最大的那个结点的层数(表头结点的层数不计算在内)
  • length:记录跳跃表的长度,即,跳跃表目前包括结点的数量(表头结点不计算在内)

表头结点和其他结点的构造是1样的:表头结点也有后退指针、分值和成员对象,不过表头结点的这些属性都不会被用到。

5、整数集合

关键字:升级规则

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

数据结构源码

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

整数集合(intset)是Redis用于保存整数值的集合抽象数据结构,可以保存类型为int16_t、int32_t或int64_t的整数值,并且保证集合中不会出现重复元素。

  • contents数组是 整数集合的底层实现:整数集合的每一个元素都是contents数组的1个数组项,各个项在数组中按值的大小从小到大有序排列,并且数组中不包括任何重复项

  • length属性记录了整数集合包括的元素数量,即contents数组的长度

  • encoding属性:虽然intset结构将contents属性声明为int8_t类型的数组,但实际上contents数组其实不保存任何int8_t类型的值,contents数组的真正类型取决于encoding属性的值

    • 若encoding属性的值为INTSET_ENC_INT16,那末contents就是1个int16_t类型的数组,数组里的每一个项都是1个int16_t类型的整数值(最小为⑶2768,最大为32767)
    • 如果encoding属性的值为INTSET_ENC_INT32,那末contents是1个int32_t类型的数组,每一个项都是1个int32_t类型的整数值(最小⑵147483648,最大2147483647)
    • 如果encoding属性的值为INTSET_ENC_INT64,那末contents是1个int64_t类型的数组,数组每一个项是1个int64_t类型的整数值(最小为⑼223372036854775808,最大为9223372036854775807)

整数集合的升级策略

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

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

  1. 根据新元素的类型,扩大整数集合底层数组的空间大小,并为新元素分配空间
  2. 将底层数组现有的所有元素都转换成与新元素相同的类型,并将类型转换后的元素放置到正确的位置上,而且在放置元素的进程中,需要继续保持底层数组的有序性质不变
  3. 讲新元素添加到底层数组里面

由于每次向整数集合添加新元素都可能会引发升级,而每次升级都需要对底层数组中已有的所有元素进行类型转换,所以向整数集合添加新元素的时间复杂度为O(N)

引发升级的新元素长度总是比整数集合现有所有元素的长度都大,所以这个新元素的值要末大于所有现有元素,要末小于所有现有元素:

  • 新元素小于所有现有元素,新元素会被放置在底层数组的最开头(索引0)
  • 新元素大于所有现有元素,新元素放置在底层数组的最末尾(索引length⑴)

整数集合的升级策略有两个好处:

  • 提升整数集合的灵活性,可以随便将int16_t、int32_t或int64_t类型的整数添加到集合中,没必要担心出现类型毛病

  • 节俭内存,这样做可让集合能同时保存3种不同类型的值,又可以确保升级操作只会在有需要的时候进行

整数集合不支持降级操作,1旦对数组升级,编码就会1直保持升级后的状态。

6、紧缩列表

关键字:连锁更新

紧缩列表(ziplist)是列表键和哈希键的底层实现之1。当1个列表键只包括少许列表项,且每一个列表项要末是小整数值,要末是长度比较短的字符串,那末Redis就会是1紧缩列表来做列表键的底层实现

紧缩列表是Redis为了节俭内存开发的,是由1系列特殊编码的连续内存块组成的顺序型(sequential)数据结构。1个紧缩列表可以包括任意多个结点(Entry),每一个结点保存1个字节数组或1个整数值。

数据结构源码

http://blog.csdn.net/ymrfzr/article/details/ziplist.png

/* 空白 ziplist 示例图 area |<---- ziplist header ---->|<-- end -->| size 4 bytes 4 bytes 2 bytes 1 byte +---------+--------+-------+-----------+ component | zlbytes | zltail | zllen | zlend | | | | | | value | 1011 | 1010 | 0 | 1111 1111 | +---------+--------+-------+-----------+ ^ | ZIPLIST_ENTRY_HEAD & address ZIPLIST_ENTRY_TAIL & ZIPLIST_ENTRY_END 非空 ziplist 示例图 area |<---- ziplist header ---->|<----------- entries ------------->|<-end->| size 4 bytes 4 bytes 2 bytes ? ? ? ? 1 byte +---------+--------+-------+--------+--------+--------+--------+-------+ component | zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend | +---------+--------+-------+--------+--------+--------+--------+-------+ ^ ^ ^ address | | | ZIPLIST_ENTRY_HEAD | ZIPLIST_ENTRY_END | ZIPLIST_ENTRY_TAIL */
  • zlbytes属性:uint32_t类型,4个字节,记录全部紧缩列表占用的内存字节数:在对紧缩列表进行内存重分配,或计算zlend的位置时使用
  • zltail属性:uint32_t类型,4个字节,记录紧缩列表表尾结点距离紧缩列表的起始地址有多少字节:通过这个偏移量,不必遍历全部紧缩列表就能够肯定表尾结点的地址
  • zllen属性:uint16_t类型,2个字节,记录了紧缩列表包括的结点数量:当这个值小于uint16_max(65535)时,这个值是紧缩列表包括结点的数量;当这个值等于uint16_max时,结点的真实数量需要遍历全部紧缩列表才能计算出
  • extryX属性:列表结点,字节数不定,紧缩列表包括的各个节点,结点的长度由节点保存的内容决定
  • zlend属性:uint8_t类型,1个字节,特殊值0xFF(10进制255),用于标记紧缩列表的末端
/* * 保存 ziplist 节点信息的结构 */ typedef struct zlentry { // prevrawlen :前置节点的长度 // prevrawlensize :编码 prevrawlen 所需的字节大小 unsigned int prevrawlensize, prevrawlen; // len :当前节点值的长度 // lensize :编码 len 所需的字节大小 unsigned int lensize, len; // 当前节点 header 的大小 // 等于 prevrawlensize + lensize unsigned int headersize; // 当前节点值所使用的编码类型 unsigned char encoding; // 指向当前节点的指针 unsigned char *p; } zlentry;

每一个紧缩列表结点可以保存1个字节数组或1个整数值,其中,字节数组可以是以下3种长度的其中1种:

  • 长度小于等于63(2^6⑴)字节的字节数组
  • 长度小于等于16383(2^14⑴)字节的字节数组
  • 长度小于等于4294967295(2^32⑴)字节的字节数组

整数值则可以是以下中的1种:

  • 4位长,介于0到12之间的无符号整数
  • 1字节长的有符号整数
  • 3字节长的有符号整数
  • int16_t类型整数
  • int32_t类型整数
  • int64_t类型整数

每一个紧缩列表结点都由previous_entry_length、encoding、content3个部份:

  • 结点的previous_entry_length属性以字节为单位,记录了紧缩列表中前1个结点的长度。previous_entry_length属性的长度可以是1字节或5字节

    • 若前1结点的长度小于254字节,那末previous_entry_length的长度为1字节:前1结点的长度就保存在这1个字节里面

    • 如果前1结点长度大于等于254字节,那末previous_entry_length属性的长度为5字节:其中属性的第1字节会被设置为0xFE(10进制254),而以后的4个字节则用于保存前1结点的长度

    • 由于结点的previous_entry_length属性记录了前1个结点的长度,所以程序可以通过指针运算,根据当前节点的起始地址计算出前1个结点的起始地址

    • 紧缩列表的从表尾向表头遍历操作就是使用这1原理实现的,只要具有1个指向某个结点起始地址的指针,那末通过这个指针和这个结点的previous_entry_length属性,就能够1直向前1个结点回溯,终究到达紧缩列表的表头结点。

  • encoding属性记录了结点的content属性所保存数据的类型和长度:

    • 1字节、两字节或5字节长,值的最高位为00、01或10的是字节数组编码:这类编码表示节点的content属性保存着字节数组,数组的长度由编码除去最高两位以后的其他位记录
    • 1字节长,值的最高位以11开头的是整数编码:这类编码表示节点的content属性保存着整数值,整数值的类型和长度由编码最高两位以后的其他位记录
  • content属性保存结点的值,结点值可以是1个字节数组或整数,值的类型和长度由节点的encoding属性决定

连锁更新

紧缩列表的添加新节点操作和删除结点操作都可能会引发连锁更新:

连锁更新在最坏情况下需要对紧缩列表履行N次空间重分配操作,而每次空间重分配的最坏复杂度为O(N),所以连锁更新的最坏复杂度为O(N^2)

虽然连锁更新的复杂度较高,但它真正造成性能问题的可能性不大:

  • 紧缩列表要恰好有多个连续、长度介于250字节到253字节之间的结点,连锁更新才可能被引发
  • 其次,即便出现连锁更新,但只要被更新的结点数量不多,就不会对性能造成影响

7、对象

关键字:编码转换,多态命令,内存回收与同享,LRU

Redis基于以上数据结构创建了1个对象系统,这个系统包括字符串对象、列表对象、哈希对象、集合对象和有序集合对象这5种类型的对象,每种对象都用到了最少1种以上数据结构。

使用对象的好处:

  • Redis履行命令前,根据对象的类型判断1个对象是不是可以履行给定命令
  • 可以针对不同的使用处景,为对象设置多种不同的数据结构实现,从而优化对象在不同场景下的使用效力
  • Redis的对象系统实现了基于援用计数技术的内存回收机制,当程序不再使用某个对象的时候,这个对象所占用的内存就会被自动释放
  • Redis还通过援用计数技术实现了对象同享机制,通过让多个数据库键同享同1个对象来节俭内存
  • Redis的对象带有访问时间记录信息,该信息可以用于计算数据库键的空转时长,在服务器启用maxmemory功能的情况下,空转时长大的那些键可能会被优先删除

数据结构源码

Redis使用对象来表示数据库中的键和值,数据库中新创建1个键值对时,最少会创建两个对象:键对象,用作键值对的键,值对象,用作键值对的值

typedef struct redisObject { // 类型 unsigned type:4; // 编码 unsigned encoding:4; // 对象最后1次被访问的时间,用于计算对象的空转时长 // 当服务器占用的内存数超过了maxmemory选项设置的上限时,空转时长高的那部份键会优先被服务器释放,从而回收内存 unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */ // 援用计数 int refcount; // 指向实际值的指针 void *ptr; } robj;

Redis中的每一个对象都由1个redisObject结构表示,该结构中的type属性、encoding属性和ptr属性与保存数据相关:

  • type属性记录对象的类型,是常量,可选值有REDIS_STRING字符串对象,REDIS_LIST列表对象,REDIS_HASH哈希对象,REDIS_SET集合对象,REDIS_ZSET有序集合对象
  • 对Redis数据库保存的键值对来讲,键总是1个字符串对象,而值则可以是字符串对象、列表对象、哈希对象、集合对象或有序集合对象的1种

  • type命令的实现方式也类似,对1个数据库键履行type命令时,命令返回的结果为数据库键对应的值对象的类型。

  • encoding属性记录了对象所使用的编码,即对象使用了甚么数据结构作为对象的底层实现

通过encoding设定对象所使用的编码,使得Redis可以根据不同的使用处景为1个对象设置不同的编码,从而优化对象在某1场景下的效力

字符串对象的编码转换

字符串对象的编码可以是int、raw或embstr。

如果1个字符串对象保存的是long类型的整数值,那末字符串对象会将整数值保存在字符串对象结构的ptr属性里(将void*转换成long),并将字符串对象的编码设置为int。

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

可以用long double类型表示的浮点数在Redis中也是作为字符串值保存的。

对int编码的字符串对象,如果我们向对象履行了1些命令,使对象保存的不再是整数,而是1个字符串值,那末字符串对象的编码将从int变成raw。

embstr编码的字符串对象实际上是只读的。对embstr编码的字符串对象履行任何修改命令时,程序会先将对象的编码从embstr转换成raw,然后再履行修改命令。所以,embstr编码的字符串对象在履行修改命令后,总会变成1个raw编码的字符串对象

列表对象的编码转换

列表对象的编码可以是ziplist或Linkedlist。

ziplist编码的列表对象使用紧缩列表作为底层实现,每一个紧缩列表结点(Entry)保存了1个列表元素。

Linkedlist编码的列表对象使用双端链表作为底层实现,每一个双端链表结点(Node)保存1个字符串对象,而每一个字符串对象保存1个列表元素。

当列表对象同时满足以下两个条件时,列表对象使用ziplist编码:

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

否则使用linkedlist编码。

哈希对象的编码转换

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

ziplist编码的哈希对象使用紧缩列表作为底层实现,每当有新的键值对要加入到哈希对象时,程序会先将保存键的紧缩列表结点推入到紧缩列表表尾,然后再将保存值的紧缩列表结点推入到紧缩列表表尾:

  • 保存了统1键值对的两个结点总是紧挨在1起,保存键的结点在前,保存值的结点在后
  • 先添加到哈希对象中的键值对会被放在紧缩列表的表头方向,而后来添加到哈希对象的键值对在紧缩列表的表尾方向

hashtable编码的哈希对象使用字典作为底层实现,哈希对象中的每一个键值对都使用1个字典键值对来保存:

  • 字典的每一个键都是1个字符串对象,对象中保存了键值对的键
  • 字典的每一个值都是1个字符串对象,对象中保存了键值对的值

当哈希对象同时满足以下两个条件时,哈希对象使用ziplist编码:

  • 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节
  • 哈希对象保存的键值对数量小于512个

否则需要使用hashtable编码。

集合对象的编码转换

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

intset编码的集合对象使用整数集合作为底层实现,集合对象包括的所有元素都被保存在整数集合里。

hashtable编码的集合对象使用字典作为底层实现,字典的每一个键都是1个字符串对象,每一个字符串对象包括1个集合元素,而字典的值则全部被设置为null.

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

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

否则使用hashtable编码。

有序集合对象的编码转换

有序集合的编码可以是ziplist或skiplist。

ziplist编码的有序集合对象使用紧缩列表作为底层实现,每一个集合元素使用两个紧挨在1起的紧缩列表结点保存,第1个结点保存元素的成员(member),第2个元素则保存元素的分值(score)。

紧缩列表内的集合元素按分值从小到大进行排序,分值较小的元素靠近表头的方向,分值较大靠近表尾。

skiplist编码的有序集合对象使用zset结构作为底层实现,1个zset结构同时包括1个字典和1个跳跃表:

/* * 有序集合 */ typedef struct zset { // 字典,键为成员,值为分值 // 用于支持 O(1) 复杂度的按成员取分值操作 dict *dict; // 跳跃表,按分值排序成员 // 用于支持平均复杂度为 O(log N) 的按分值定位成员操作 // 和范围操作 zskiplist *zsl; } zset;

有序集合每一个元素的成员都是1个字符串对象,而每一个元素的分值都是1个double类型的浮点数。

虽然zset结构同时使用跳跃表和字典来保存有序集合元素,但这两种数据结构都会通过指针来同享相同元素的成员和分值,所以同时使用跳跃表和字典保存集合元素,不会产生重复成员和分值,不会因此浪费额外内存。

满足以下两个条件时,对象使用ziplist编码:

  • 有序集合保存的元素数量小于128个
  • 有序集合保存的所有元素成员的长度都小于64字节

否则有序集合对象使用skiplist编码。

类型检查与命令多态

Redis中用于操作键的命令可分为两种类型:

  • 1种可以对任何类型的键履行,比如del命令、expire命令、rename命令、type命令、Object命令
  • 1种智能对特定类型的键履行的命令

在履行1个类型特定的命令之前,Redis会先检查输入键的类型是不是正确,然后再决定是不是履行给定的命令。

类型特定命令的类型检查是通过redisObject结构的type属性来实现的:

  • 在履行1个类型特定命令之前,服务器会先检查输入数据库键的值对象是不是为履行命令所需的类型,若是,履行命令;
  • 否则服务器谢绝履行命令,并向客户端返回1个类型毛病。

Redis还会根据对象的编码方式,选择正确的命令实现代码来履行命令。

内存回收与对象同享

Redis通过援用计数技术实现内存回收机制。

对象的援用计数信息会随着对象的使用状态而不断变化:

  • 在创建1个新对象时,援用计数的值会被初始化为1
  • 当对象被1个新程序使用时,它的援用计数加1
  • 当对象不再被1个程序使用时,它的援用计数减1
  • 当对象的援用计数值变成0时,对象所占用的内存会被释放

基于援用计数的对象同享机制使Redis更节俭内存。

Redis的同享对象包括字符串键,和那些在数据结构中嵌套了字符串对象的对象(linkedlist编码的列表对象、hashtable编码的哈希对象、hashtable编码的集合对象,zset编码的有序集合对象)也能够使用这些同享对象。

Redis只对包括整数值的字符串对象进行同享。

------分隔线----------------------------
------分隔线----------------------------

最新技术推荐