Redis学习8 Redis数据结构（1）

Fly to the sky…Fire bird!

Redis数据结构（1）

动态字符串SDS

我们都知道Redis中保存的Key是字符串，Value往往是字符串或者字符串的集合。可见字符串是Redis中最常用的一种数据结构。

不过Redis没有直接使用C语言中的字符串，因为C语言字符串存在很多问题:

获取字符串长度的需要通过运算
非二进制安全
不可修改

Redis构建了一种新的字符串结构，称为简单动态字符串(Simple Dynamic String)，简称SDS。Sunny Day Song

Redis是C语言实现的，其中SDS是一个结构体，源码如下:

struct __attribute__ ((__packed__)) sdshdr8 {uint8t len;  /*buf已保存的字符串字节数，不包含结束标示*/uint8_t alloc;  /*buf申请的总的字节数，不包含结束标示*/unsigned char flags;  /*不同SDs的头类型，用来控制sDs的头大小char buf[];
};

其中len，alloc，flags是描述信息header，buf[]是存储信息body
flags存在五种类型

#define SDS_TYPE_5 0 这种类型基本已弃用
#define SDS_TYPE_8 1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4

例如，一个包含字符串"name"的sds结构如下：

SDS动态扩容

SDS之所以叫做动态字符串，是因为它具备动态扩容的能力，例如一个内容为“hi”的SDS:

假如我们要给SDS追加一段字符串“,Amy”，这里首先会申请新内存空间:

如果新字符串小于1M，则新空间为扩展后字符串长度的两倍+1;
如果新字符串大于1M，则新空间为扩展后字符串长度+1M+1。
这样的策略称为内存预分配。目的是减少内存扩张的次数，提升性能

SDS的优点如下：

①获取字符串长度的时间复杂度为0(1)
②支持动态扩容
③减少内存分配次数
④二进制安全

IntSet

IntSet是Redis中set集合的一种实现方式,基于整数数组来实现,并且具备长度可变、有序等特征。

结构如下:

typedef struct intset {uint32_t encoding; /*编码方式,支持存放16位、32位、64位整数*/uint32_t length; /*元素个数 */int8_t contents[]; /*整数数组,保存集合数据*/
} intset;

其中encoding，length是描述信息header，contents[]是存储信息body

其中的encoding包含三种模式,表示存储的整数大小不同:

/* Note that these encodings are ordered, so:
* INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */
#define INTSET_ENC_INT16(sizeof(int16_t))/* 2字节整数,范围类似java的short*/
#define INTSET_ENC_INT32(sizeof(int32_t))/* 4字节整数,范围类似java的int */
#define INTSET_ENC_INT64(sizeof(int64_t))/*8字节整数,范围类似java的long */

为了方便查找，Redis会将intset中所有的整数按照升序依次保存在contents数组中,结构如图:

由于内部整数有序保存，所以查找时会按照二分查找来查询
数组的寻址公式为：startPtr+(sizeof(int)*index)，其中index从0开始，表示与起始元素的间隔
数组中每个数字都在int16_t的范围内，因此采用的编码方式是INTSET_ENC_INT16
每部分占用的字节大小为:

encoding: 4字节
length: 4字节
contents: 2字节*3=6字节

IntSet动态升级

现在，假设有一个IntSet,元素为(5,10,20)，采用的编码是INTSET_ENC_INT16,则每个整数占2字节:

我们向该其中添加一个数字:50000，这个数字超出了int16_t的范围，IntSet会自动升级编码方式到合适的大小。以当前案例来说流程如下:

①升级编码为INTSET_ENC_INT32，每个整数占4字节，并按照新的编码方式及元素个数扩容数组
②倒序依次将数组中的元素拷贝到扩容后的正确位置，这样做的目的是为了防止元素覆盖
③将待添加的元素放入数组末尾
④最后，将IntSet的encoding属性改为INTSET_ENC_INT32，将length属性改为4

Dict

我们知道Redis是一个键值型(Key-Value Pair)的数据库，我们可以根据键实现快速的增删改查，而键与值的映射关系正是通过Dict来实现的。

Dict由三部分组成，分别是:哈希表(DictHashTable)、哈希节点(DictEntry)、字典(Dict)

typedef struct dict {dictType *type; // dict类型,内置不同的hash函数void *privdata; // 私有数据,在做特殊hash运算时用dictht ht[2]; // 一个Dict包含两个哈希表,其中一个是当前数据,另一个一般是空,rehash时使用long rehashidx; // rehash的进度,-1表示未进行int16_t pauserehash; // rehash是否暂停,1则暂停,0则继续
} dict;typedef struct dictht {// entry数组// 数组中保存的是指向entry的指针dictEntry ** table;// 哈希表大小 一般为2^nunsigned long size;// 哈希表大小的掩码,总等于size-1unsigned long sizemask;// entry个数unsigned long used;
} dictht;typedef struct dictEntry {void *key; // 键union {void *val;uint64_t u64;int64_t s64;double d;}v; //值，其可以是四个类型中的任意一个// 下一个Entry的指针，以此用于维护哈希链表struct dictEntry *next;
} dictEntry;

当我们向Dict添加键值对时,Redis首先根据key计算出hash值(h),然后利用h&sizemask来计算元素应该存储到数组中的哪个索引位置。

Dict扩容

Dict中的HashTable就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低。

Dict在每次新增键值对时都会检查负载因子(LoadFactor=used/size),满足以下两种情况时会触发哈希表扩容:

哈希表的LoadFactor>=1，并且服务器没有执行BGSAVE或者BGREWRITEAOF等后台进程，后者是为了防止影响后台进程;
哈希表的LoadFactor>5;

static int _dictExpandIfNeeded(dict *d){// 如果正在rehash,则返回okif (dictIsRehashing(d)) return DICT_OK;// 初始化操作：如果哈希表为空,则初始化哈希表为默认大小:4if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);// 当负载因子(used/size)达到1以上,并且当前没有进行bgrewrite等子进程操作// 或者负载因子超过5,则进行 dictExpand,也就是扩容if (d->ht[0].used >= d->ht[0].size &&(dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio) {// 扩容大小为used+ 1,底层会对扩容大小做判断,实际上找的是第一个大于等于used+1的2^nreturn dictExpand(d, d->ht[0].used + 1);}return DICT_OK;
}

Dict除了扩容以外，每次删除元素时，也会对负载因子做检查，当LoadFactor<0.1时，会做哈希表收缩

Dict的rehash操作

不管是扩容还是收缩,必定会创建新的哈希表,导致哈希表的size和sizemask变化,而key的查询与sizemask有关。因此必须对哈希表中的每一个key重新计算索引,插入新的哈希表,这个过程称为rehash。过程是这样的:

①计算新hash表的realeSize,值取决于当前要做的是扩容还是收缩:

如果是扩容,则新size为第一个大于等于dict.ht[0].used+1的\(2^n\)
如果是收缩,则新size为第一个大于等于dict.ht[0].used的\(2^n\)(不得小于4)

②按照新的realeSize申请内存空间,创建dictht,并赋值给dict.ht[1]
③设置dict.rehashidx=0,标示开始rehash
④将dict.ht[0]中的每一个dictEntry都rehash到dict.ht[1]
⑤将dict.ht[1]赋值给dict.ht[0],给dict.ht[1]初始化为空哈希表,释放原来的dict.ht[O]的内存

此时修改dict.ht[0].table和dict.ht[1].table的指针指向，然后修改参数，完成rehash

Dict的渐进式rehash

Dict的rehash并不是一次性完成的。试想一下，如果Dict中包含数百万的entry，要在一次rehash完成，极有可能导致主线程阻塞。因此Dict的rehash是分多次、渐进式的完成，因此称为渐进式rehash。流程如下:

①计算新hash表的size，值取决于当前要做的是扩容还是收缩:

如果是扩容，则新size为第一个大于等于dict.ht[0].used+1的\(2^n\)
如果是收缩，则新size为第一个大于等于dict.ht[0].used的\(2^n\)(不得小于4)

②按照新的size申请内存空间，创建dictht，并赋值给dict.ht[1]
③设置dict.rehashidx=0,标示开始rehash
④rehash过程中，每次执行新增、查询、修改、删除操作时，都检查一下dict.rehashidx是否大于-1,如果是则将dict.ht[0].table[rehashidx]的entry链表rehash到dict.ht[1]，并且将rehashidx++。直至dict.ht[0]的所有数据都rehash到dict.ht[1]

查询，修改，删除会同时查询dict.ht[0]和dict.ht[1]，找到需要的数据后进行操作
新增只需要在dict.ht[1]执行即可，从而保证dict.ht[0]只减不增，rehash顺利完成

⑤将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存
⑥最终把dict.rehashidx=-1，标志着rehash完成