[大数据]Redis基础

Redis基础

?

Redis 基础数据结构

Redis常见的数据结构？

String、Hash、List、Set、SortedSet。

1.String 字符串类型

是redis中最基本的数据类型，一个key对应一个value。

String类型是二进制安全的，意思是 redis 的 string 可以包含任何数据。如数字，字符串，jpg图片或者序列化的对象。

实战场景：

1. 缓存： 经典使用场景，把常用信息，字符串，图片或者视频等信息放到redis中，redis作为缓存层，mysql做持久化层，降低mysql的读写压力。
2. 计数器：redis是单线程模型，一个命令执行完才会执行下一个，同时数据可以一步落地到其他的数据源。
3. session：常见方案spring session + redis实现session共享

2.Hash （哈希）

是一个Mapmap，指值本身又是一种键值对结构，如 value={{field1,value1},......fieldN,valueN}}

实战场景：

1.缓存： 能直观，相比string更节省空间，的维护缓存信息，如用户信息，视频信息等。

3.链表

List 说白了就是链表（redis 使用双端链表实现的 List），是有序的，value可以重复，可以通过下标取出对应的value值，左右两边都能进行插入和删除数据。

使用列表的技巧

• lpush+lpop=Stack(栈)
• lpush+rpop=Queue（队列）
• lpush+ltrim=Capped Collection（有限集合）
• lpush+brpop=Message Queue（消息队列）

实战场景：1.timeline：例如微博的时间轴，有人发布微博，用lpush加入时间轴，展示新的列表信息。

4.Set 集合

集合类型也是用来保存多个字符串的元素，但和列表不同的是集合中 1. 不允许有重复的元素，2.集合中的元素是无序的，不能通过索引下标获取元素，3.支持集合间的操作，可以取多个集合取交集、并集、差集。

??

实战场景;

1. 标签（tag）,给用户添加标签，或者用户给消息添加标签，这样有同一标签或者类似标签的可以给推荐关注的事或者关注的人。
2. 点赞，或点踩，收藏等，可以放到set中实现

5.zset 有序集合

有序集合和集合有着必然的联系，保留了集合不能有重复成员的特性，区别是，有序集合中的元素是可以排序的，它给每个元素设置一个分数，作为排序的依据。

（有序集合中的元素不可以重复，但是score 分数 可以重复，就和一个班里的同学学号不能重复，但考试成绩可以相同）。

??

实战场景：

1. 排行榜：有序集合经典使用场景。例如小说视频等网站需要对用户上传的小说视频做排行榜，榜单可以按照用户关注数，更新时间，字数等打分，做排行。

Redis中的数据结构

原文地址?Redis中的数据结构

1. 底层数据结构, 与Redis Value Type之间的关系

对于Redis的使用者来说, Redis作为Key-Value型的内存数据库, 其Value有多种类型.

• String
• Hash
• List
• Set
• ZSet

这些Value的类型, 只是"Redis的用户认为的, Value存储数据的方式". 而在具体实现上, 各个Type的Value到底如何存储, 这对于Redis的使用者来说是不公开的.

举个粟子: 使用下面的命令创建一个Key-Value

SET "Hello" "World"

对于Redis的使用者来说,?Hello这个Key, 对应的Value是String类型, 其值为五个ASCII字符组成的二进制数据. 但具体在底层实现上, 这五个字节是如何存储的, 是不对用户公开的. 即, Value的Type, 只是表象, 具体数据在内存中以何种数据结构存放, 这对于用户来说是不必要了解的.

Redis对使用者暴露了五种Value Type, 其底层实现的数据结构有8种, 分别是:

• SDS - simple synamic string - 支持自动动态扩容的字节数组
• list - 平平无奇的链表
• dict - 使用双哈希表实现的, 支持平滑扩容的字典
• zskiplist - 附加了后向指针的跳跃表
• intset - 用于存储整数数值集合的自有结构
• ziplist - 一种实现上类似于TLV, 但比TLV复杂的, 用于存储任意数据的有序序列的数据结构
• quicklist - 一种以ziplist作为结点的双链表结构, 实现的非常苟
• zipmap - 一种用于在小规模场合使用的轻量级字典结构

而衔接"底层数据结构"与"Value Type"的桥梁的, 则是Redis实现的另外一种数据结构:?redisObject. Redis中的Key与Value在表层都是一个redisObject实例, 故该结构有所谓的"类型", 即是ValueType. 对于每一种Value Type类型的redisObject, 其底层至少支持两种不同的底层数据结构来实现. 以应对在不同的应用场景中, Redis的运行效率, 或内存占用.

2. 底层数据结构

2.1 SDS - simple dynamic string

这是一种用于存储二进制数据的一种结构, 具有动态扩容的特点. 其实现位于src/sds.h与src/sds.c中, 其关键定义如下:

typedef char *sds;

/* Note: sdshdr5 is never used, we just access the flags byte directly.

?* However is here to document the layout of type 5 SDS strings. */

struct __attribute__ ((__packed__)) sdshdr5 {

????unsigned char flags; /* 3 lsb of type, and 5 msb of string length */

????char buf[];

};

struct __attribute__ ((__packed__)) sdshdr8 {

????uint8_t len; /* used */

????uint8_t alloc; /* excluding the header and null terminator */

????unsigned char flags; /* 3 lsb of type, 5 unused bits */

????char buf[];

};

struct __attribute__ ((__packed__)) sdshdr16 {

????uint16_t len; /* used */

????uint16_t alloc; /* excluding the header and null terminator */

????unsigned char flags; /* 3 lsb of type, 5 unused bits */

????char buf[];

};

struct __attribute__ ((__packed__)) sdshdr32 {

????uint32_t len; /* used */

????uint32_t alloc; /* excluding the header and null terminator */

????unsigned char flags; /* 3 lsb of type, 5 unused bits */

????char buf[];

};

struct __attribute__ ((__packed__)) sdshdr64 {

????uint64_t len; /* used */

????uint64_t alloc; /* excluding the header and null terminator */

????unsigned char flags; /* 3 lsb of type, 5 unused bits */

????char buf[];

};

SDS的总体概览如下图:

??

其中sdshdr是头部, buf是真实存储用户数据的地方. 另外注意, 从命名上能看出来, 这个数据结构除了能存储二进制数据, 显然是用于设计作为字符串使用的, 所以在buf中, 用户数据后总跟着一个\0. 即图中 "数据" + "\0" 是为所谓的buf

SDS有五种不同的头部. 其中sdshdr5实际并未使用到. 所以实际上有四种不同的头部, 分别如下:

??

• len分别以uint8, uint16, uint32, uint64表示用户数据的长度(不包括末尾的\0)
• alloc分别以uint8, uint16, uint32, uint64表示整个SDS, 除过头部与末尾的\0, 剩余的字节数.
• flag始终为一字节, 以低三位标示着头部的类型, 高5位未使用.

当在程序中持有一个SDS实例时, 直接持有的是数据区的头指针, 这样做的用意是: 通过这个指针, 向前偏一个字节, 就能取到flag, 通过判断flag低三位的值, 能迅速判断: 头部的类型, 已用字节数, 总字节数, 剩余字节数. 这也是为什么sds类型即是char *指针类型别名的原因.

创建一个SDS实例有三个接口, 分别是:

// 创建一个不含数据的sds:

// ?头部 ???3字节 sdshdr8

// ?数据区 ?0字节

// ?末尾 ???\0 占一字节

sds sdsempty(void);

// 带数据创建一个sds:

// ?头部 ???按initlen的值, 选择最小的头部类型

// ?数据区 ?从入参指针init处开始, 拷贝initlen个字节

// ?末尾 ???\0 占一字节

sds sdsnewlen(const void *init, size_t initlen);

// 带数据创建一个sds:

// ?头部 ???按strlen(init)的值, 选择最小的头部类型

// ?数据区 ?入参指向的字符串中的所有字符, 不包括末尾 \0

// ?末尾 ???\0 占一字节

sds sdsnew(const char *init);

• 所有创建sds实例的接口, 都不会额外分配预留内存空间
• sdsnewlen用于带二进制数据创建sds实例, sdsnew用于带字符串创建sds实例. 接口返回的sds可以直接传入libc中的字符串输出函数中进行操作, 由于无论其中存储的是用户的二进制数据, 还是字符串, 其末尾都带一个\0, 所以至少调用libc中的字符串输出函数是安全的.

在对SDS中的数据进行修改时, 若剩余空间不足, 会调用sdsMakeRoomFor函数用于扩容空间, 这是一个很低级的API, 通常情况下不应当由SDS的使用者直接调用. 其实现中核心的几行如下:

sds sdsMakeRoomFor(sds s, size_t addlen) {

????...

????/* Return ASAP if there is enough space left. */

????if (avail >= addlen) return s;

????len = sdslen(s);

????sh = (char*)s-sdsHdrSize(oldtype);

????newlen = (len+addlen);

????if (newlen < SDS_MAX_PREALLOC)

????????newlen *= 2;

????else

????????newlen += SDS_MAX_PREALLOC;

????...

}

可以看到, 在扩充空间时

• 先保证至少有addlen可用
• 然后再进一步扩充, 在总体占用空间不超过阈值SDS_MAC_PREALLOC时, 申请空间再翻一倍. 若总体空间已经超过了阈值, 则步进增长SDS_MAC_PREALLOC. 这个阈值的默认值为?1024 * 1024

SDS也提供了接口用于移除所有未使用的内存空间.?sdsRemoveFreeSpace, 该接口没有间接的被任何SDS其它接口调用, 即默认情况下, SDS不会自动回收预留空间. 在SDS的使用者需要节省内存时, 由使用者自行调用:

sds sdsRemoveFreeSpace(sds s);

总结:

• SDS除了是某些Value Type的底层实现, 也被大量使用在Redis内部, 用于替代C-Style字符串. 所以默认的创建SDS实例接口, 不分配额外的预留空间. 因为多数字符串在程序运行期间是不变的. 而对于变更数据区的API, 其内部则是调用了 sdsMakeRoomFor, 每一次扩充空间, 都会预留大量的空间. 这样做的考量是: 如果一个SDS实例中的数据被变更了, 那么很有可能会在后续发生多次变更.
• SDS的API内部不负责清除未使用的闲置内存空间, 因为内部API无法判断这样做的合适时机. 即便是在操作数据区的时候导致数据区占用内存减少时, 内部API也不会清除闲置内在空间. 清除闲置内存空间责任应当由SDS的使用者自行担当.
• 用SDS替代C-Style字符串时, 由于其头部额外存储了数据区的长度信息, 所以字符串的求长操作时间复杂度为O(1)

2.2 list

这是普通的链表实现, 链表结点不直接持有数据, 而是通过void *指针来间接的指向数据. 其实现位于 src/adlist.h与src/adlist.c中, 关键定义如下:

typedef struct listNode {

????struct listNode *prev;

????struct listNode *next;

????void *value;

} listNode;

typedef struct listIter {

????listNode *next;

????int direction;

} listIter;

typedef struct list {

????listNode *head;

????listNode *tail;

????void *(*dup)(void *ptr);

????void (*free)(void *ptr);

????int (*match)(void *ptr, void *key);

????unsigned long len;

} list;

其内存布局如下图所示:

??

这是一个平平无奇的链表的实现. list在Redis除了作为一些Value Type的底层实现外, 还广泛用于Redis的其它功能实现中, 作为一种数据结构工具使用. 在list的实现中, 除了基本的链表定义外, 还额外增加了:

• 迭代器listIter的定义, 与相关接口的实现.
• 由于list中的链表结点本身并不直接持有数据, 而是通过value字段, 以void *指针的形式间接持有, 所以数据的生命周期并不完全与链表及其结点一致. 这给了list的使用者相当大的灵活性. 比如可以多个结点持有同一份数据的地址. 但与此同时, 在对链表进行销毁, 结点复制以及查找匹配时, 就需要list的使用者将相关的函数指针赋值于list.dup, list.free, list.match字段.

2.3 dict

dict是Redis底层数据结构中实现最为复杂的一个数据结构, 其功能类似于C++标准库中的std::unordered_map, 其实现位于 src/dict.h 与 src/dict.c中, 其关键定义如下:

typedef struct dictEntry {

????void *key;

????union {

????????void *val;

????????uint64_t u64;

????????int64_t s64;

????????double d;

????} v;

????struct dictEntry *next;

} dictEntry;

typedef struct dictType {

????uint64_t (*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;

/* This is our hash table structure. Every dictionary has two of this as we

?* implement incremental rehashing, for the old to the new table. */

typedef struct dictht {

????dictEntry **table;

????unsigned long size;

????unsigned long sizemask;

????unsigned long used;

} dictht;

typedef struct dict {

????dictType *type;

????void *privdata;

????dictht ht[2];

????long rehashidx; /* rehashing not in progress if rehashidx == -1 */

????unsigned long iterators; /* number of iterators currently running */

} dict;

/* If safe is set to 1 this is a safe iterator, that means, you can call

?* dictAdd, dictFind, and other functions against the dictionary even while

?* iterating. Otherwise it is a non safe iterator, and only dictNext()

?* should be called while iterating. */

typedef struct dictIterator {

????dict *d;

????long index;

????int table, safe;

????dictEntry *entry, *nextEntry;

????/* unsafe iterator fingerprint for misuse detection. */

????long long fingerprint;

} dictIterator;

其内存布局如下所示:

??

dict中存储的键值对, 是通过dictEntry这个结构间接持有的, k通过指针间接持有键, v通过指针间接持有值. 注意, 若值是整数值的话, 是直接存储在v字段中的, 而不是间接持有. 同时next指针用于指向, 在bucket索引值冲突时, 以链式方式解决冲突, 指向同索引的下一个dictEntry结构.

传统的哈希表实现, 是一块连续空间的顺序表, 表中元素即是结点. 在dictht.table中, 结点本身是散布在内存中的, 顺序表中存储的是dictEntry的指针

哈希表即是dictht结构, 其通过table字段间接的持有顺序表形式的bucket, bucket的容量存储在size字段中, 为了加速将散列值转化为bucket中的数组索引, 引入了sizemask字段, 计算指定键在哈希表中的索引时, 执行的操作类似于dict->type->hashFunction(键) & dict->ht[x].sizemask. 从这里也可以看出来, bucket的容量适宜于为2的幂次, 这样计算出的索引值能覆盖到所有bucket索引位.

dict即为字典. 其中type字段中存储的是本字典使用到的各种函数指针, 包括散列函数, 键与值的复制函数, 释放函数, 以及键的比较函数. privdata是用于存储用户自定义数据. 这样, 字典的使用者可以最大化的自定义字典的实现, 通过自定义各种函数实现, 以及可以附带私有数据, 保证了字典有很大的调优空间.

字典为了支持平滑扩容, 定义了ht[2]这个数组字段. 其用意是这样的:

• 1. 一般情况下, 字典dict仅持有一个哈希表dictht的实例, 即整个字典由一个bucket实现.
  2. 随着插入操作, bucket中出现冲突的概率会越来越大, 当字典中存储的结点数目, 与bucket数组长度的比值达到一个阈值(1:1)时, 字典为了缓解性能下降, 就需要扩容
  3. 扩容的操作是平滑的, 即在扩容时, 字典会持有两个dictht的实例, ht[0]指向旧哈希表, ht[1]指向扩容后的新哈希表. 平滑扩容的重点在于两个策略:
  4. 后续每一次的插入, 替换, 查找操作, 都插入到ht[1]指向的哈希表中
  5. 每一次插入, 替换, 查找操作执行时, 会将旧表ht[0]中的一个bucket索引位持有的结点链表, 迁移到ht[1]中去. 迁移的进度保存在rehashidx这个字段中.在旧表中由于冲突而被链接在同一索引位上的结点, 迁移到新表后, 可能会散布在多个新表索引中去.
  6. 当迁移完成后, ht[0]指向的旧表会被释放, 之后会将新表的持有权转交给ht[0], 再重置ht[1]指向NULL

这种平滑扩容的优点有两个:

• 1. 平滑扩容过程中, 所有结点的实际数据, 即dict->ht[0]->table[rehashindex]->k与dict->ht[0]->table[rehashindex]->v分别指向的实际数据, 内存地址都不会变化. 没有发生键数据与值数据的拷贝或移动, 扩容整个过程仅是各种指针的操作. 速度非常快
  2. 扩容操作是步进式的, 这保证任何一次插入操作都是顺畅的, dict的使用者是无感知的. 若扩容是一次性的, 当新旧bucket容量特别大时, 迁移所有结点必然会导致耗时陡增.

除了字典本身的实现外, 其中还顺带实现了一个迭代器, 这个迭代器中有字段safe以标示该迭代器是"安全迭代器"还是"非安全迭代器", 所谓的安全与否, 指是的这种场景: 设想在运行迭代器的过程中, 字典正处于平滑扩容的过程中. 在平滑扩容的过程中时, 旧表一个索引位上的, 由冲突而链起来的多个结点, 迁移到新表后, 可能会散布到新表的多个索引位上. 且新的索引位的值可能比旧的索引位要低.

遍历操作的重点是, 保证在迭代器遍历操作开始时, 字典中持有的所有结点, 都会被遍历到. 而若在遍历过程中, 一个未遍历的结点, 从旧表迁移到新表后, 索引值减小了, 那么就可能会导致这个结点在遍历过程中被遗漏.

所以, 所谓的"安全"迭代器, 其在内部实现时: 在迭代过程中, 若字典正处于平滑扩容过程, 则暂停结点迁移, 直至迭代器运行结束. 这样虽然不能保证在迭代过程中插入的结点会被遍历到, 但至少保证在迭代起始时, 字典中持有的所有结点都会被遍历到.

这也是为什么dict结构中有一个iterators字段的原因: 该字段记录了运行于该字典上的安全迭代器的数目. 若该数目不为0, 字典是不会继续进行结点迁移平滑扩容的.

下面是字典的扩容操作中的核心代码, 我们以插入操作引起的扩容为例:

先是插入操作的外部逻辑:

1. 如果插入时, 字典正处于平滑扩容过程中, 那么无论本次插入是否成功, 先迁移一个bucket索引中的结点至新表
2. 在计算新插入结点键的bucket索引值时, 内部会探测哈希表是否需要扩容(若当前不在平滑扩容过程中)

int dictAdd(dict *d, void *key, void *val)

{

????dictEntry *entry = dictAddRaw(d,key,NULL); ?????????// 调用dictAddRaw

????if (!entry) return DICT_ERR;

????dictSetVal(d, entry, val);

????return DICT_OK;

}

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)

{

????long index;

????dictEntry *entry;

????dictht *ht;

????if (dictIsRehashing(d)) _dictRehashStep(d); // 若在平滑扩容过程中, 先步进迁移一个bucket索引

????/* Get the index of the new element, or -1 if

?????* the element already exists. */

????// 在计算键在bucket中的索引值时, 内部会检查是否需要扩容

????if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)

????????return NULL;

????/* Allocate the memory and store the new entry.

?????* Insert the element in top, with the assumption that in a database

?????* system it is more likely that recently added entries are accessed

?????* more frequently. */

????ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];

????entry = zmalloc(sizeof(*entry));

????entry->next = ht->table[index];

????ht->table[index] = entry;

????ht->used++;

????/* Set the hash entry fields. */

????dictSetKey(d, entry, key);

????return entry;

}

下面是计算bucket索引值的函数, 内部会探测该哈希表是否需要扩容, 如果需要扩容(结点数目与bucket数组长度比例达到1:1), 就使字典进入平滑扩容过程:

static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)

{

????unsigned long idx, table;

????dictEntry *he;

????if (existing) *existing = NULL;

????/* Expand the hash table if needed */

????if (_dictExpandIfNeeded(d) == DICT_ERR) // 探测是否需要扩容, 如果需要, 则开始扩容

????????return -1;

????for (table = 0; table <= 1; table++) {

????????idx = hash & d->ht[table].sizemask;

????????/* Search if this slot does not already contain the given key */

????????he = d->ht[table].table[idx];

????????while(he) {

????????????if (key==he->key || dictCompareKeys(d, key, he->key)) {

????????????????if (existing) *existing = he;

????????????????return -1;

????????????}

????????????he = he->next;

????????}

????????if (!dictIsRehashing(d)) break;

????}

????return idx;

}

/* Expand the hash table if needed */

static int _dictExpandIfNeeded(dict *d)

{

????/* Incremental rehashing already in progress. Return. */

????if (dictIsRehashing(d)) return DICT_OK; // 如果正在扩容过程中, 则什么也不做

????/* If the hash table is empty expand it to the initial size. */

????// 若字典中本无元素, 则初始化字典, 初始化时的bucket数组长度为4

????if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

????/* If we reached the 1:1 ratio, and we are allowed to resize the hash

?????* table (global setting) or we should avoid it but the ratio between

?????* elements/buckets is over the "safe" threshold, we resize doubling

?????* the number of buckets. */

????// 若字典中元素的个数与bucket数组长度比值大于1:1时, 则调用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))

????{

????????return dictExpand(d, d->ht[0].used*2);

????}

????return DICT_OK;

}

int dictExpand(dict *d, unsigned long size)

{

????dictht n; /* the new hash table */ ?// 新建一个dictht结构

????unsigned long realsize = _dictNextPower(size); ?

????/* the size is invalid if it is smaller than the number of

?????* elements already inside the hash table */

????if (dictIsRehashing(d) || d->ht[0].used > size)

????????return DICT_ERR;

????/* Rehashing to the same table size is not useful. */

????if (realsize == d->ht[0].size) return DICT_ERR;

????/* Allocate the new hash table and initialize all pointers to NULL */

????n.size = realsize;

????n.sizemask = realsize-1;

????n.table = zcalloc(realsize*sizeof(dictEntry*));// 初始化dictht下的table, 即bucket数组

????n.used = 0;

????/* Is this the first initialization? If so it's not really a rehashing

?????* we just set the first hash table so that it can accept keys. */

????// 若是新字典初始化, 直接把dictht结构挂在ht[0]中

????if (d->ht[0].table == NULL) {

????????d->ht[0] = n;

????????return DICT_OK;

????}

????// 否则, 把新dictht结构挂在ht[1]中, 并开启平滑扩容(置rehashidx为0, 字典处于非扩容状态时, 该字段值为-1)

????/* Prepare a second hash table for incremental rehashing */

????d->ht[1] = n;

????d->rehashidx = 0;

????return DICT_OK;

}

下面是平滑扩容的实现:

static void _dictRehashStep(dict *d) {

????// 若字典上还运行着安全迭代器, 则不迁移结点

????// 否则每次迁移一个旧bucket索引上的所有结点

????if (d->iterators == 0) dictRehash(d,1);

}

int dictRehash(dict *d, int n) {

????int empty_visits = n*10; /* Max number of empty buckets to visit. */

????if (!dictIsRehashing(d)) return 0;

????while(n-- && d->ht[0].used != 0) {

????????dictEntry *de, *nextde;

????????/* Note that rehashidx can't overflow as we are sure there are more

?????????* elements because ht[0].used != 0 */

????????assert(d->ht[0].size > (unsigned long)d->rehashidx);

????????// 在旧bucket中, 找到下一个非空的索引位

????????while(d->ht[0].table[d->rehashidx] == NULL) {

????????????d->rehashidx++;

????????????if (--empty_visits == 0) return 1;

????????}

????????// 取出该索引位上的结点链表

????????de = d->ht[0].table[d->rehashidx];

????????/* Move all the keys in this bucket from the old to the new hash HT */

????????// 把所有结点迁移到新bucket中去

????????while(de) {

????????????uint64_t h;

????????????nextde = de->next;

????????????/* Get the index in the new hash table */

????????????h = dictHashKey(d, de->key) & d->ht[1].sizemask;

????????????de->next = d->ht[1].table[h];

????????????d->ht[1].table[h] = de;

????????????d->ht[0].used--;

????????????d->ht[1].used++;

????????????de = nextde;

????????}

????????d->ht[0].table[d->rehashidx] = NULL;

????????d->rehashidx++;

????}

????/* Check if we already rehashed the whole table... */

????// 检查是否旧表中的所有结点都被迁移到了新表

????// 如果是, 则置先释放原旧bucket数组, 再置ht[1]为ht[0]

????// 最后再置rehashidx=-1, 以示字典不处于平滑扩容状态

????if (d->ht[0].used == 0) {

????????zfree(d->ht[0].table);

????????d->ht[0] = d->ht[1];

????????_dictReset(&d->ht[1]);

????????d->rehashidx = -1;

????????return 0;

????}

????/* More to rehash... */

????return 1;

}

总结:

字典的实现很复杂, 主要是实现了平滑扩容逻辑 用户数据均是以指针形式间接由dictEntry结构持有, 故在平滑扩容过程中, 不涉及用户数据的拷贝 有安全迭代器可用, 安全迭代器保证, 在迭代起始时, 字典中的所有结点, 都会被迭代到, 即使在迭代过程中对字典有插入操作 字典内部使用的默认散列函数其实也非常有讲究, 不过限于篇幅, 这里不展开讲. 并且字典的实现给了使用者非常大的灵活性(dictType结构与dict.privdata字段), 对于一些特定场合使用的键数据, 用户可以自行选择更高效更特定化的散列函数

2.4 zskiplist

zskiplist是Redis实现的一种特殊的跳跃表. 跳跃表是一种基于线性表实现简单的搜索结构, 其最大的特点就是: 实现简单, 性能能逼近各种搜索树结构. 血统纯正的跳跃表的介绍在维基百科中即可查阅. 在Redis中, 在原版跳跃表的基础上, 进行了一些小改动, 即是现在要介绍的zskiplist结构.

其定义在src/server.h中, 如下:

/* ZSETs use a specialized version of Skiplists */

typedef struct zskiplistNode {

????sds ele;

????double score;

????struct zskiplistNode *backward;

????struct zskiplistLevel {

????????struct zskiplistNode *forward;

????????unsigned int span;

????} level[];

} zskiplistNode;

typedef struct zskiplist {

????struct zskiplistNode *header, *tail;

????unsigned long length;

????int level;

} zskiplist;

其内存布局如下图:

??

zskiplist的核心设计要点为:

1. 头结点不持有任何数据, 且其level[]的长度为32
2. 每个结点, 除了持有数据的ele字段, 还有一个字段score, 其标示着结点的得分, 结点之间凭借得分来判断先后顺序, 跳跃表中的结点按结点的得分升序排列.
3. 每个结点持有一个backward指针, 这是原版跳跃表中所没有的. 该指针指向结点的前一个紧邻结点.
4. 每个结点中最多持有32个zskiplistLevel结构. 实际数量在结点创建时, 按幂次定律随机生成(不超过32). 每个zskiplistLevel中有两个字段.
5. forward字段指向比自己得分高的某个结点(不一定是紧邻的), 并且, 若当前zskiplistLevel实例在level[]中的索引为X, 则其forward字段指向的结点, 其level[]字段的容量至少是X+1. 这也是上图中, 为什么forward指针总是画的水平的原因.
6. span字段代表forward字段指向的结点, 距离当前结点的距离. 紧邻的两个结点之间的距离定义为1.
7. zskiplist中持有字段level, 用以记录所有结点(除过头结点外), level[]数组最长的长度.

跳跃表主要用于, 在给定一个分值的情况下, 查找与该分值最接近的结点. 搜索时, 伪代码如下:

int level = zskiplist->level - 1;

zskiplistNode p = zskiplist->head;

while(1 && p)

{

????zskiplistNode q = (p->level)[level]->forward:

????if(q->score > 分值)

????{

????????if(level > 0)

????????{

????????????level--;

????????}

????????else

????????{

????????????return :

????????????????q为整个跳跃表中, 分值大于指定分值的第一个结点

????????????????q->backward为整个跳跃表中, 分值小于或等于指定分值的最后一个结点

????????}

????}

????else

????{

????????p = q;

????}

}

跳跃表的实现比较简单, 最复杂的操作即是插入与删除结点, 需要仔细处理邻近结点的所有level[]中的所有zskiplistLevel结点中的forward与span的值的变更.

另外, 关于新创建的结点, 其level[]数组长度的随机算法, 在接口zslInsert的实现中, 核心代码片断如下:

zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {

????//...

????level = zslRandomLevel(); ??// 随机生成新结点的, level[]数组的长度

????????if (level > zsl->level) { ??

????????// 若生成的新结点的level[]数组的长度比当前表中所有结点的level[]的长度都大

????????// 那么头结点中需要新增几个指向该结点的指针

????????// 并刷新ziplist中的level字段

????????for (i = zsl->level; i < level; i++) {

????????????rank[i] = 0;

????????????update[i] = zsl->header;

????????????update[i]->level[i].span = zsl->length;

????????}

????????zsl->level = level;

????}

????x = zslCreateNode(level,score,ele); // 创建新结点

????//... 执行插入操作

}

// 按幂次定律生成小于32的随机数的函数

// 宏 ZSKIPLIST_MAXLEVEL 的定义为32, 宏 ZSKIPLIST_P 被设定为 0.25

// 即

// ?????level == 1的概率为 75%

// ?????level == 2的概率为 75% * 25%

// ?????level == 3的概率为 75% * 25% * 25%

// ?????...

// ?????level == 31的概率为 0.75 * 0.25^30

// ?????而

// ?????level == 32的概率为 0.75 * sum(i = 31 ~ +INF){ 0.25^i }

int zslRandomLevel(void) {

????int level = 1;

????while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))

????????level += 1;

????return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;

}

2.5 intset

这是一个用于存储在序的整数的数据结构, 也底层数据结构中最简单的一个, 其定义与实现在src/intest.h与src/intset.c中, 关键定义如下:

typedef struct intset {

????uint32_t encoding;

????uint32_t length;

????int8_t contents[];

} intset;

#define INTSET_ENC_INT16 (sizeof(int16_t))

#define INTSET_ENC_INT32 (sizeof(int32_t))

#define INTSET_ENC_INT64 (sizeof(int64_t))

inset结构中的encoding的取值有三个, 分别是宏INTSET_ENC_INT16, INTSET_ENC_INT32, INTSET_ENC_INT64. length代表其中存储的整数的个数, contents指向实际存储数值的连续内存区域. 其内存布局如下图所示:

??

• intset中各字段, 包括contents中存储的数值, 都是以主机序(小端字节序)存储的. 这意味着Redis若运行在PPC这样的大端字节序的机器上时, 存取数据都会有额外的字节序转换开销
• 当encoding == INTSET_ENC_INT16时, contents中以int16_t的形式存储着数值. 类似的, 当encoding == INTSET_ENC_INT32时, contents中以int32_t的形式存储着数值.
• 但凡有一个数值元素的值超过了int32_t的取值范围, 整个intset都要进行升级, 即所有的数值都需要以int64_t的形式存储. 显然升级的开销是很大的.
• intset中的数值是以升序排列存储的, 插入与删除的复杂度均为O(n). 查找使用二分法, 复杂度为O(log_2(n))
• intset的代码实现中, 不预留空间, 即每一次插入操作都会调用zrealloc接口重新分配内存. 每一次删除也会调用zrealloc接口缩减占用的内存. 省是省了, 但内存操作的时间开销上升了.
• intset的编码方式一经升级, 不会再降级.

总之, intset适合于如下数据的存储:

• 所有数据都位于一个稳定的取值范围中. 比如均位于int16_t或int32_t的取值范围中
• 数据稳定, 插入删除操作不频繁. 能接受O(lgn)级别的查找开销

2.6 ziplist

ziplist是Redis底层数据结构中, 最苟的一个结构. 它的设计宗旨就是: 省内存, 从牙缝里省内存. 设计思路和TLV一致, 但为了从牙缝里节省内存, 做了很多额外工作.

ziplist的内存布局与intset一样: 就是一块连续的内存空间. 但区域划分比较复杂, 概览如下图:

??

• 和intset一样, ziplist中的所有值都是以小端序存储的
• zlbytes字段的类型是uint32_t, 这个字段中存储的是整个ziplist所占用的内存的字节数
• zltail字段的类型是uint32_t, 它指的是ziplist中最后一个entry的偏移量. 用于快速定位最后一个entry, 以快速完成pop等操作
• zllen字段的类型是uint16_t, 它指的是整个ziplit中entry的数量. 这个值只占16位, 所以蛋疼的地方就来了: 如果ziplist中entry的数目小于65535, 那么该字段中存储的就是实际entry的值. 若等于或超过65535, 那么该字段的值固定为65535, 但实际数量需要一个个entry的去遍历所有entry才能得到.
• zlend是一个终止字节, 其值为全F, 即0xff. ziplist保证任何情况下, 一个entry的首字节都不会是255

在画图展示entry的内存布局之前, 先讲一下entry中都存储了哪些信息:

• 每个entry中存储了它前一个entry所占用的字节数. 这样支持ziplist反向遍历.
• 每个entry用单独的一块区域, 存储着当前结点的类型: 所谓的类型, 包括当前结点存储的数据是什么(二进制, 还是数值), 如何编码(如果是数值, 数值如何存储, 如果是二进制数据, 二进制数据的长度)
• 最后就是真实的数据了

entry的内存布局如下所示:

??

prevlen即是"前一个entry所占用的字节数", 它本身是一个变长字段, 规约如下:

• 若前一个entry占用的字节数小于 254, 则prevlen字段占一字节
• 若前一个entry占用的字节数等于或大于 254, 则prevlen字段占五字节: 第一个字节值为 254, 即0xfe, 另外四个字节, 以uint32_t存储着值.

encoding字段的规约就复杂了许多

• 若数据是二进制数据, 且二进制数据长度小于64字节(不包括64), 那么encoding占一字节. 在这一字节中, 高两位值固定为0, 低六位值以无符号整数的形式存储着二进制数据的长度. 即 00xxxxxx, 其中低六位bitxxxxxx是用二进制保存的数据长度.
• 若数据是二进制数据, 且二进制数据长度大于或等于64字节, 但小于16384(不包括16384)字节, 那么encoding占用两个字节. 在这两个字节16位中, 第一个字节的高两位固定为01, 剩余的14个位, 以小端序无符号整数的形式存储着二进制数据的长度, 即 01xxxxxx, yyyyyyyy, 其中yyyyyyyy是高八位, xxxxxx是低六位.
• 若数据是二进制数据, 且二进制数据的长度大于或等于16384字节, 但小于2^32-1字节, 则encoding占用五个字节. 第一个字节是固定值10000000, 剩余四个字节, 按小端序uint32_t的形式存储着二进制数据的长度. 这也是ziplist能存储的二进制数据的最大长度, 超过2^32-1字节的二进制数据, ziplist无法存储.
• 若数据是整数值, 则encoding和data的规约如下:
  1. 首先, 所有存储数值的entry, 其encoding都仅占用一个字节. 并且最高两位均是11
  2. 若数值取值范围位于[0, 12]中, 则encoding和data挤在同一个字节中. 即为1111 0001~1111 1101, 高四位是固定值, 低四位的值从0001至1101, 分别代表 0 ~ 12这十五个数值
  3. 若数值取值范围位于[-128, -1] [13, 127]中, 则encoding == 0b 1111 1110. 数值存储在紧邻的下一个字节, 以int8_t形式编码
  4. 若数值取值范围位于[-32768, -129] [128, 32767]中, 则encoding == 0b 1100 0000. 数值存储在紧邻的后两个字节中, 以小端序int16_t形式编码
  5. 若数值取值范围位于[-8388608, -32769] [32768, 8388607]中, 则encoding == 0b 1111 0000. 数值存储在紧邻的后三个字节中, 以小端序存储, 占用三个字节.
  6. 若数值取值范围位于[-2^31, -8388609] [8388608, 2^31 - 1]中, 则encoding == 0b 1101 0000. 数值存储在紧邻的后四个字节中, 以小端序int32_t形式编码
  7. 若数值取值均不在上述范围, 但位于int64_t所能表达的范围内, 则encoding == 0b 1110 0000, 数值存储在紧邻的后八个字节中, 以小端序int64_t形式编码

在大规模数值存储中, ziplist几乎不浪费内存空间, 其苟的程序到达了字节级别, 甚至对于[0, 12]区间的数值, 连data里的那一个字节也要省下来. 显然, ziplist是一种特别节省内存的数据结构, 但它的缺点也十分明显:

• 和intset一样, ziplist也不预留内存空间, 并且在移除结点后, 也是立即缩容, 这代表每次写操作都会进行内存分配操作.
• ziplist最蛋疼的一个问题是: 结点如果扩容, 导致结点占用的内存增长, 并且超过254字节的话, 可能会导致链式反应: 其后一个结点的entry.prevlen需要从一字节扩容至五字节. 最坏情况下, 第一个结点的扩容, 会导致整个ziplist表中的后续所有结点的entry.prevlen字段扩容. 虽然这个内存重分配的操作依然只会发生一次, 但代码中的时间复杂度是o(N)级别, 因为链式扩容只能一步一步的计算. 但这种情况的概率十分的小, 一般情况下链式扩容能连锁反映五六次就很不幸了. 之所以说这是一个蛋疼问题, 是因为, 这样的坏场景下, 其实时间复杂度并不高: 依次计算每个entry新的空间占用, 也就是o(N), 总体占用计算出来后, 只执行一次内存重分配, 与对应的memmove操作, 就可以了. 蛋疼说的是: 代码特别难写, 难读. 下面放一段处理插入结点时处理链式反应的代码片断, 大家自行感受一下:

unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {

????size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen;

????unsigned int prevlensize, prevlen = 0;

????size_t offset;

????int nextdiff = 0;

????unsigned char encoding = 0;

????long long value = 123456789; /* initialized to avoid warning. Using a value

????????????????????????????????????that is easy to see if for some reason

????????????????????????????????????we use it uninitialized. */

????zlentry tail;

????/* Find out prevlen for the entry that is inserted. */

????if (p[0] != ZIP_END) {

????????ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);

????} else {

????????unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);

????????if (ptail[0] != ZIP_END) {

????????????prevlen = zipRawEntryLength(ptail);

????????}

????}

????/* See if the entry can be encoded */

????if (zipTryEncoding(s,slen,&value,&encoding)) {

????????/* 'encoding' is set to the appropriate integer encoding */

????????reqlen = zipIntSize(encoding);

????} else {

????????/* 'encoding' is untouched, however zipStoreEntryEncoding will use the

?????????* string length to figure out how to encode it. */

????????reqlen = slen;

????}

????/* We need space for both the length of the previous entry and

?????* the length of the payload. */

????reqlen += zipStorePrevEntryLength(NULL,prevlen);

????reqlen += zipStoreEntryEncoding(NULL,encoding,slen);

????/* When the insert position is not equal to the tail, we need to

?????* make sure that the next entry can hold this entry's length in

?????* its prevlen field. */

????int forcelarge = 0;

????nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;

????if (nextdiff == -4 && reqlen < 4) {

????????nextdiff = 0;

????????forcelarge = 1;

????}

????/* Store offset because a realloc may change the address of zl. */

????offset = p-zl;

????zl = ziplistResize(zl,curlen+reqlen+nextdiff);

????p = zl+offset;

????/* Apply memory move when necessary and update tail offset. */

????if (p[0] != ZIP_END) {

????????/* Subtract one because of the ZIP_END bytes */

????????memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);

????????/* Encode this entry's raw length in the next entry. */

????????if (forcelarge)

????????????zipStorePrevEntryLengthLarge(p+reqlen,reqlen);

????????else

????????????zipStorePrevEntryLength(p+reqlen,reqlen);

????????/* Update offset for tail */

????????ZIPLIST_TAIL_OFFSET(zl) =

????????????intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);

????????/* When the tail contains more than one entry, we need to take

?????????* "nextdiff" in account as well. Otherwise, a change in the

?????????* size of prevlen doesn't have an effect on the *tail* offset. */

????????zipEntry(p+reqlen, &tail);

????????if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {

????????????ZIPLIST_TAIL_OFFSET(zl) =

????????????????intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);

????????}

????} else {

????????/* This element will be the new tail. */

????????ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);

????}

????/* When nextdiff != 0, the raw length of the next entry has changed, so

?????* we need to cascade the update throughout the ziplist */

????if (nextdiff != 0) {

????????offset = p-zl;

????????zl = __ziplistCascadeUpdate(zl,p+reqlen);

????????p = zl+offset;

????}

????/* Write the entry */

????p += zipStorePrevEntryLength(p,prevlen);

????p += zipStoreEntryEncoding(p,encoding,slen);

????if (ZIP_IS_STR(encoding)) {

????????memcpy(p,s,slen);

????} else {

????????zipSaveInteger(p,value,encoding);

????}

????ZIPLIST_INCR_LENGTH(zl,1);

????return zl;

}

unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {

????size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), rawlen, rawlensize;

????size_t offset, noffset, extra;

????unsigned char *np;

????zlentry cur, next;

????while (p[0] != ZIP_END) {

????????zipEntry(p, &cur);

????????rawlen = cur.headersize + cur.len;

????????rawlensize = zipStorePrevEntryLength(NULL,rawlen);

????????/* Abort if there is no next entry. */

????????if (p[rawlen] == ZIP_END) break;

????????zipEntry(p+rawlen, &next);

????????/* Abort when "prevlen" has not changed. */

????????if (next.prevrawlen == rawlen) break;

????????if (next.prevrawlensize < rawlensize) {

????????????/* The "prevlen" field of "next" needs more bytes to hold

?????????????* the raw length of "cur". */

????????????offset = p-zl;

????????????extra = rawlensize-next.prevrawlensize;

????????????zl = ziplistResize(zl,curlen+extra);

????????????p = zl+offset;

????????????/* Current pointer and offset for next element. */

????????????np = p+rawlen;

????????????noffset = np-zl;

????????????/* Update tail offset when next element is not the tail element. */

????????????if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) {

????????????????ZIPLIST_TAIL_OFFSET(zl) =

????????????????????intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);

????????????}

????????????/* Move the tail to the back. */

????????????memmove(np+rawlensize,

????????????????np+next.prevrawlensize,

????????????????curlen-noffset-next.prevrawlensize-1);

????????????zipStorePrevEntryLength(np,rawlen);

????????????/* Advance the cursor */

????????????p += rawlen;

????????????curlen += extra;

????????} else {

????????????if (next.prevrawlensize > rawlensize) {

????????????????/* This would result in shrinking, which we want to avoid.

?????????????????* So, set "rawlen" in the available bytes. */

????????????????zipStorePrevEntryLengthLarge(p+rawlen,rawlen);

????????????} else {

????????????????zipStorePrevEntryLength(p+rawlen,rawlen);

????????????}

????????????/* Stop here, as the raw length of "next" has not changed. */

????????????break;

????????}

????}

????return zl;

}

这种代码的特点就是: 最好由作者去维护, 最好一次性写对. 因为读起来真的费劲, 改起来也很费劲.

2.7 quicklist

如果说ziplist是整个Redis中为了节省内存, 而写的最苟的数据结构, 那么称quicklist就是在最苟的基础上, 再苟了一层. 这个结构是Redis在3.2版本后新加的, 在3.2版本之前, 我们可以讲, dict是最复杂的底层数据结构, ziplist是最苟的底层数据结构. 在3.2版本之后, 这两个记录被双双刷新了.

这是一种, 以ziplist为结点的, 双端链表结构. 宏观上, quicklist是一个链表, 微观上, 链表中的每个结点都是一个ziplist.

它的定义与实现分别在src/quicklist.h与src/quicklist.c中, 其中关键定义如下:

/* Node, quicklist, and Iterator are the only data structures used currently. */

/* quicklistNode is a 32 byte struct describing a ziplist for a quicklist.

?* We use bit fields keep the quicklistNode at 32 bytes.

?* count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k).

?* encoding: 2 bits, RAW=1, LZF=2.

?* container: 2 bits, NONE=1, ZIPLIST=2.

?* recompress: 1 bit, bool, true if node is temporarry decompressed for usage.

?* attempted_compress: 1 bit, boolean, used for verifying during testing.

?* extra: 12 bits, free for future use; pads out the remainder of 32 bits */

typedef struct quicklistNode {

????struct quicklistNode *prev;

????struct quicklistNode *next;

????unsigned char *zl;

????unsigned int sz; ????????????/* ziplist size in bytes */

????unsigned int count : 16; ????/* count of items in ziplist */

????unsigned int encoding : 2; ??/* RAW==1 or LZF==2 */

????unsigned int container : 2; ?/* NONE==1 or ZIPLIST==2 */

????unsigned int recompress : 1; /* was this node previous compressed? */

????unsigned int attempted_compress : 1; /* node can't compress; too small */

????unsigned int extra : 10; /* more bits to steal for future usage */

} quicklistNode;

/* quicklistLZF is a 4+N byte struct holding 'sz' followed by 'compressed'.

?* 'sz' is byte length of 'compressed' field.

?* 'compressed' is LZF data with total (compressed) length 'sz'

?* NOTE: uncompressed length is stored in quicklistNode->sz.

?* When quicklistNode->zl is compressed, node->zl points to a quicklistLZF */

typedef struct quicklistLZF {

????unsigned int sz; /* LZF size in bytes*/

????char compressed[];

} quicklistLZF;

/* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist.

?* 'count' is the number of total entries.

?* 'len' is the number of quicklist nodes.

?* 'compress' is: -1 if compression disabled, otherwise it's the number

?* ???????????????of quicklistNodes to leave uncompressed at ends of quicklist.

?* 'fill' is the user-requested (or default) fill factor. */

typedef struct quicklist {

????quicklistNode *head;

????quicklistNode *tail;

????unsigned long count; ???????/* total count of all entries in all ziplists */

????unsigned long len; ?????????/* number of quicklistNodes */

????int fill : 16; ?????????????/* fill factor for individual nodes */

????unsigned int compress : 16; /* depth of end nodes not to compress;0=off */

} quicklist;

typedef struct quicklistIter {

????const quicklist *quicklist;

????quicklistNode *current;

????unsigned char *zi;

????long offset; /* offset in current ziplist */

????int direction;

} quicklistIter;

typedef struct quicklistEntry {

????const quicklist *quicklist;

????quicklistNode *node;

????unsigned char *zi;

????unsigned char *value;

????long long longval;

????unsigned int sz;

????int offset;

} quicklistEntry;

这里定义了五个结构体:

• quicklistNode, 宏观上, quicklist是一个链表, 这个结构描述的就是链表中的结点. 它通过zl字段持有底层的ziplist. 简单来讲, 它描述了一个ziplist实例
• quicklistLZF, ziplist是一段连续的内存, 用LZ4算法压缩后, 就可以包装成一个quicklistLZF结构. 是否压缩quicklist中的每个ziplist实例是一个可配置项. 若这个配置项是开启的, 那么quicklistNode.zl字段指向的就不是一个ziplist实例, 而是一个压缩后的quicklistLZF实例
• quicklist. 这就是一个双链表的定义. head, tail分别指向头尾指针. len代表链表中的结点. count指的是整个quicklist中的所有ziplist中的entry的数目. fill字段影响着每个链表结点中ziplist的最大占用空间, compress影响着是否要对每个ziplist以LZ4算法进行进一步压缩以更节省内存空间.
• quicklistIter是一个迭代器
• quicklistEntry是对ziplist中的entry概念的封装. quicklist作为一个封装良好的数据结构, 不希望使用者感知到其内部的实现, 所以需要把ziplist.entry的概念重新包装一下.

quicklist的内存布局图如下所示:

??

下面是有关quicklist的更多额外信息:

quicklist.fill的值影响着每个链表结点中, ziplist的长度.

1. 当数值为负数时, 代表以字节数限制单个ziplist的最大长度. 具体为:
   1. -1 不超过4kb
   2. -2 不超过 8kb
   3. -3 不超过 16kb
   4. -4 不超过 32kb
   5. -5 不超过 64kb
   6. 当数值为正数时, 代表以entry数目限制单个ziplist的长度. 值即为数目. 由于该字段仅占16位, 所以以entry数目限制ziplist的容量时, 最大值为2^15个
2. quicklist.compress的值影响着quicklistNode.zl字段指向的是原生的ziplist, 还是经过压缩包装后的quicklistLZF
   1. 0 表示不压缩, zl字段直接指向ziplist
   2. 1 表示quicklist的链表头尾结点不压缩, 其余结点的zl字段指向的是经过压缩后的quicklistLZF
   3. 2 表示quicklist的链表头两个, 与末两个结点不压缩, 其余结点的zl字段指向的是经过压缩后的quicklistLZF
   4. 以此类推, 最大值为2^16
3. quicklistNode.encoding字段, 以指示本链表结点所持有的ziplist是否经过了压缩. 1代表未压缩, 持有的是原生的ziplist, 2代表压缩过
4. quicklistNode.container字段指示的是每个链表结点所持有的数据类型是什么. 默认的实现是ziplist, 对应的该字段的值是2, 目前Redis没有提供其它实现. 所以实际上, 该字段的值恒为2
5. quicklistNode.recompress字段指示的是当前结点所持有的ziplist是否经过了解压. 如果该字段为1即代表之前被解压过, 且需要在下一次操作时重新压缩.

quicklist的具体实现代码篇幅很长, 这里就不贴代码片断了, 从内存布局上也能看出来, 由于每个结点持有的ziplist是有上限长度的, 所以在与操作时要考虑的分支情况比较多. 想想都蛋疼.

quicklist有自己的优点, 也有缺点, 对于使用者来说, 其使用体验类似于线性数据结构, list作为最传统的双链表, 结点通过指针持有数据, 指针字段会耗费大量内存. ziplist解决了耗费内存这个问题. 但引入了新的问题: 每次写操作整个ziplist的内存都需要重分配. quicklist在两者之间做了一个平衡. 并且使用者可以通过自定义quicklist.fill, 根据实际业务情况, 经验主义调参.

2.8 zipmap

dict作为字典结构, 优点很多, 扩展性强悍, 支持平滑扩容等等, 但对于字典中的键值均为二进制数据, 且长度都很小时, dict的中的一坨指针会浪费不少内存, 因此Redis又实现了一个轻量级的字典, 即为zipmap.

zipmap适合使用的场合是:

• 键值对量不大, 单个键, 单个值长度小
• 键值均是二进制数据, 而不是复合结构或复杂结构. dict支持各种嵌套, 字典本身并不持有数据, 而仅持有数据的指针. 但zipmap是直接持有数据的.

zipmap的定义与实现在src/zipmap.h与src/zipmap.c两个文件中, 其定义与实现均未定义任何struct结构体, 因为zipmap的内存布局就是一块连续的内存空间. 其内存布局如下所示:

??

• zipmap起始的第一个字节存储的是zipmap中键值对的个数. 如果键值对的个数大于254的话, 那么这个字节的值就是固定值254, 真实的键值对个数需要遍历才能获得.
• zipmap的最后一个字节是固定值0xFF
• zipmap中的每一个键值对, 称为一个entry, 其内存占用如上图, 分别六部分:
  1. len_of_key, 一字节或五字节. 存储的是键的二进制长度. 如果长度小于254, 则用1字节存储, 否则用五个字节存储, 第一个字节的值固定为0xFE, 后四个字节以小端序uint32_t类型存储着键的二进制长度.
  2. key_data为键的数据
  3. len_of_val, 一字节或五字节, 存储的是值的二进制长度. 编码方式同len_of_key
  4. len_of_free, 固定值1字节, 存储的是entry中未使用的空间的字节数. 未使用的空间即为图中的free, 它一般是由于键值对中的值被替换发生的. 比如, 键值对hello <-> word被修改为hello <-> w后, 就空了四个字节的闲置空间
  5. val_data, 为值的数据
  6. free, 为闲置空间. 由于len_of_free的值最大只能是254, 所以如果值的变更导致闲置空间大于254的话, zipmap就会回收内存空间.

Redis持久化的原理及优化

Redis为持久化提供了两种方式：

• RDB：在指定的时间间隔能对你的数据进行快照存储。
• AOF：记录每次对服务器写的操作,当服务器重启的时候会重新执行这些命令来恢复原始的数据。

本文将通过下面内容的介绍，希望能够让大家更全面、清晰的认识这两种持久化方式，同时理解这种保存数据的思路，应用于自己的系统设计中。

• 持久化的配置
• RDB与AOF持久化的工作原理
• 如何从持久化中恢复数据
• 关于性能与实践建议

持久化的配置

为了使用持久化的功能，我们需要先知道该如何开启持久化的功能。

RDB的持久化配置

# 时间策略

save 900 1

save 300 10

save 60 10000

# 文件名称

dbfilename dump.rdb

# 文件保存路径

dir /home/work/app/redis/data/

# 如果持久化出错，主进程是否停止写入

stop-writes-on-bgsave-error yes

# 是否压缩

rdbcompression yes

# 导入时是否检查

rdbchecksum yes

配置其实非常简单，这里说一下持久化的时间策略具体是什么意思。

• save 900 1 表示900s内如果有1条是写入命令，就触发产生一次快照，可以理解为就进行一次备份
• save 300 10 表示300s内有10条写入，就产生快照

下面的类似，那么为什么需要配置这么多条规则呢？因为Redis每个时段的读写请求肯定不是均衡的，为了平衡性能与数据安全，我们可以自由定制什么情况下触发备份。所以这里就是根据自身Redis写入情况来进行合理配置。

stop-writes-on-bgsave-error yes?这个配置也是非常重要的一项配置，这是当备份进程出错时，主进程就停止接受新的写入操作，是为了保护持久化的数据一致性问题。如果自己的业务有完善的监控系统，可以禁止此项配置， 否则请开启。

关于压缩的配置?rdbcompression yes?，建议没有必要开启，毕竟Redis本身就属于CPU密集型服务器，再开启压缩会带来更多的CPU消耗，相比硬盘成本，CPU更值钱。

当然如果你想要禁用RDB配置，也是非常容易的，只需要在save的最后一行写上：save ""

AOF的配置

# 是否开启aof

appendonly yes

# 文件名称

appendfilename "appendonly.aof"

# 同步方式

appendfsync everysec

# aof重写期间是否同步

no-appendfsync-on-rewrite no

# 重写触发配置

auto-aof-rewrite-percentage 100

auto-aof-rewrite-min-size 64mb

# 加载aof时如果有错如何处理

aof-load-truncated yes

# 文件重写策略

aof-rewrite-incremental-fsync yes

复制代码还是重点解释一些关键的配置：

appendfsync everysec?它其实有三种模式:

• always：把每个写命令都立即同步到aof，很慢，但是很安全
• everysec：每秒同步一次，是折中方案
• no：redis不处理交给OS来处理，非常快，但是也最不安全

一般情况下都采用?everysec?配置，这样可以兼顾速度与安全，最多损失1s的数据。

aof-load-truncated yes?如果该配置启用，在加载时发现aof尾部不正确是，会向客户端写入一个log，但是会继续执行，如果设置为?no?，发现错误就会停止，必须修复后才能重新加载。

工作原理

关于原理部分，我们主要来看RDB与AOF是如何完成持久化的，他们的过程是如何。

在介绍原理之前先说下Redis内部的定时任务机制，定时任务执行的频率可以在配置文件中通过 hz 10 来设置（这个配置表示1s内执行10次，也就是每100ms触发一次定时任务）。该值最大能够设置为：500，但是不建议超过：100，因为值越大说明执行频率越频繁越高，这会带来CPU的更多消耗，从而影响主进程读写性能。

定时任务使用的是Redis自己实现的 TimeEvent，它会定时去调用一些命令完成定时任务，这些任务可能会阻塞主进程导致Redis性能下降。因此我们在配置Redis时，一定要整体考虑一些会触发定时任务的配置，根据实际情况进行调整。

RDB的原理

在Redis中RDB持久化的触发分为两种：自己手动触发与Redis定时触发。

针对RDB方式的持久化，手动触发可以使用：

• save：会阻塞当前Redis服务器，直到持久化完成，线上应该禁止使用。
• bgsave：该触发方式会fork一个子进程，由子进程负责持久化过程，因此阻塞只会发生在fork子进程的时候。

而自动触发的场景主要是有以下几点：

• 根据我们的?save m n?配置规则自动触发；
• 从节点全量复制时，主节点发送rdb文件给从节点完成复制操作，主节点会触发?bgsave；
• 执行 debug reload 时；
• 执行 shutdown时，如果没有开启aof，也会触发。

由于 save 基本不会被使用到，我们重点看看 bgsave 这个命令是如何完成RDB的持久化的。

?转存失败重新上传取消?

这里注意的是 fork 操作会阻塞，导致Redis读写性能下降。我们可以控制单个Redis实例的最大内存，来尽可能降低Redis在fork时的事件消耗。以及上面提到的自动触发的频率减少fork次数，或者使用手动触发，根据自己的机制来完成持久化。

AOF的原理

AOF的整个流程大体来看可以分为两步，一步是命令的实时写入（如果是?appendfsync everysec?配置，会有1s损耗），第二步是对aof文件的重写。 对于增量追加到文件这一步主要的流程是：命令写入=>追加到aof_buf =>同步到aof磁盘。那么这里为什么要先写入buf在同步到磁盘呢？如果实时写入磁盘会带来非常高的磁盘IO，影响整体性能。 aof重写是为了减少aof文件的大小，可以手动或者自动触发，关于自动触发的规则请看上面配置部分。fork的操作也是发生在重写这一步，也是这里会对主进程产生阻塞。 手动触发：?bgrewriteaof，自动触发 就是根据配置规则来触发，当然自动触发的整体时间还跟Redis的定时任务频率有关系。

下面来看看重写的一个流程图：

?转存失败重新上传取消?

对于上图有四个关键点补充一下：

在重写期间，由于主进程依然在响应命令，为了保证最终备份的完整性；因此它依然会写入旧的AOF file中，如果重写失败，能够保证数据不丢失。 为了把重写期间响应的写入信息也写入到新的文件中，因此也会为子进程保留一个buf，防止新写的file丢失数据。 重写是直接把当前内存的数据生成对应命令，并不需要读取老的AOF文件进行分析、命令合并。 AOF文件直接采用的文本协议，主要是兼容性好、追加方便、可读性高可认为修改修复。

不能是RDB还是AOF都是先写入一个临时文件，然后通过 rename 完成文件的替换工作。

从持久化中恢复数据

数据的备份、持久化做完了，我们如何从这些持久化文件中恢复数据呢？如果一台服务器上有既有RDB文件，又有AOF文件，该加载谁呢？ 其实想要从这些文件中恢复数据，只需要重新启动Redis即可。我们还是通过图来了解这个流程：

?转存失败重新上传取消?

启动时会先检查AOF文件是否存在，如果不存在就尝试加载RDB。那么为什么会优先加载AOF呢？因为AOF保存的数据更完整，通过上面的分析我们知道AOF基本上最多损失1s的数据。

性能与实践

通过上面的分析，我们都知道RDB的快照、AOF的重写都需要fork，这是一个重量级操作，会对Redis造成阻塞。因此为了不影响Redis主进程响应，我们需要尽可能降低阻塞。

• 降低fork的频率，比如可以手动来触发RDB生成快照、与AOF重写；
• 控制Redis最大使用内存，防止fork耗时过长；
• 使用更牛逼的硬件；
• 合理配置Linux的内存分配策略，避免因为物理内存不足导致fork失败。

在线上我们到底该怎么做？我提供一些自己的实践经验。

• 如果Redis中的数据并不是特别敏感或者可以通过其它方式重写生成数据，可以关闭持久化，如果丢失数据可以通过其它途径补回；
• 自己制定策略定期检查Redis的情况，然后可以手动触发备份、重写数据；
• 单机如果部署多个实例，要防止多个机器同时运行持久化、重写操作，防止出现内存、CPU、IO资源竞争，让持久化变为串行；
• 可以加入主从机器，利用一台从机器进行备份处理，其它机器正常响应客户端的命令；
• RDB持久化与AOF持久化可以同时存在，配合使用。

Redis中内存淘汰算法实现

Redis的maxmemory支持的内存淘汰机制使得其成为一种有效的缓存方案，成为memcached的有效替代方案。

当内存达到maxmemory后，Redis会按照maxmemory-policy启动淘汰策略。

Redis 3.0中已有淘汰机制：

• noeviction
• allkeys-lru
• volatile-lru
• allkeys-random
• volatile-random
• volatile-ttl

其中LRU(less recently used)经典淘汰算法在Redis实现中有一定优化设计，来保证内存占用与实际效果的平衡，这也体现了工程应用是空间与时间的平衡性。

PS：值得注意的，在主从复制模式Replication下，从节点达到maxmemory时不会有任何异常日志信息，但现象为增量数据无法同步至从节点。

Redis 3.0中近似LRU算法

Redis中LRU是近似LRU实现，并不能取出理想LRU理论中最佳淘汰Key，而是通过从小部分采样后的样本中淘汰局部LRU键。

Redis 3.0中近似LRU算法通过增加待淘汰元素池的方式进一步优化，最终实现与精确LRU非常接近的表现。

精确LRU会占用较大内存记录历史状态，而近似LRU则用较小内存支出实现近似效果。

以下是理论LRU和近似LRU的效果对比：

?转存失败重新上传取消?

• 按时间顺序接入不同键，此时最早写入也就是最佳淘汰键
• 浅灰色区域：被淘汰的键
• 灰色区域：未被淘汰的键
• 绿色区域：新增写入的键

总结图中展示规律，

• 图1Theoretical LRU符合预期：最早写入键逐步被淘汰
• 图2Approx LRU Redis 3.0 10 samples：Redis 3.0中近似LRU算法(采样值为10)
• 图3Approx LRU Redis 2.8 5 samples：Redis 2.8中近似LRU算法(采样值为5)
• 图4Approx LRU Redis 3.0 5 samples：Redis 3.0中近似LRU算法(采样值为5)

结论：

• 通过图4和图3对比：得出相同采样值下，3.0比2.8的LRU淘汰机制更接近理论LRU
• 通过图4和图2对比：得出增加采样值，在3.0中将进一步改善LRU淘汰效果逼近理论LRU
• 对比图2和图1：在3.0中采样值为10时，效果非常接近理论LRU

采样值设置通过maxmemory-samples指定，可通过CONFIG SET maxmemory-samples 动态设置，也可启动配置中指定maxmemory-samples

源码解析

int freeMemoryIfNeeded(void){

????while (mem_freed < mem_tofree) {

????????if (server.maxmemory_policy == REDIS_MAXMEMORY_NO_EVICTION)

????????return REDIS_ERR; /* We need to free memory, but policy forbids. */

????????if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||

????????????????server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM)

????????????{......}

????????/* volatile-random and allkeys-random policy */

????????if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM ||

????????????????server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_RANDOM)

????????????{......}

????????/* volatile-lru and allkeys-lru policy */

????????else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||

????????????server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)

????????{

????????????// 淘汰池函数

????????????evictionPoolPopulate(dict, db->dict, db->eviction_pool);

????????????while(bestkey == NULL) {

????????????????evictionPoolPopulate(dict, db->dict, db->eviction_pool);

????????????????// 从后向前逐一淘汰

????????????????for (k = REDIS_EVICTION_POOL_SIZE-1; k >= 0; k--) {

????????????????????if (pool[k].key == NULL) continue;

????????????????????de = dictFind(dict,pool[k].key); // 定位目标

????????????????????/* Remove the entry from the pool. */

????????????????????sdsfree(pool[k].key);

????????????????????/* Shift all elements on its right to left. */

????????????????????memmove(pool+k,pool+k+1,

????????????????????????sizeof(pool[0])*(REDIS_EVICTION_POOL_SIZE-k-1));

????????????????????/* Clear the element on the right which is empty

?????????????????????* since we shifted one position to the left. ?*/

????????????????????pool[REDIS_EVICTION_POOL_SIZE-1].key = NULL;

????????????????????pool[REDIS_EVICTION_POOL_SIZE-1].idle = 0;

????????????????????/* If the key exists, is our pick. Otherwise it is

?????????????????????* a ghost and we need to try the next element. */

????????????????????if (de) {

????????????????????????bestkey = dictGetKey(de); // 确定删除键

????????????????????????break;

????????????????????} else {

????????????????????????/* Ghost... */

????????????????????????continue;

????????????????????}

????????????????}

????????????}

????????}

????????/* volatile-ttl */

????????else if (server.maxmemory_policy == EDIS_MAXMEMORY_VOLATILE_TTL) {......}

????????// 最终选定待删除键bestkey

????????if (bestkey) {

????????????long long delta;

????????????robj *keyobj = createStringObject(bestkey,sdslenbestkey)); // 目标对象

????????????propagateExpire(db,keyobj);

????????????latencyStartMonitor(eviction_latency); // 延迟监控开始

????????????dbDelete(db,keyobj); // 从db删除对象

????????????latencyEndMonitor(eviction_latency);// 延迟监控结束

????????????latencyAddSampleIfNeeded("eviction-del",iction_latency); // 延迟采样

????????????latencyRemoveNestedEvent(latency,eviction_latency);

????????????delta -= (long long) zmalloc_used_memory();

????????????mem_freed += delta; // 释放内存计数

????????????server.stat_evictedkeys++; // 淘汰key计数，info中可见

????????????notifyKeyspaceEvent(REDIS_NOTIFY_EVICTED, "evicted", keyobj, db->id); // 事件通知

????????????decrRefCount(keyobj); // 引用计数更新

????????????keys_freed++;

????????????// 避免删除较多键导致的主从延迟，在循环内同步

????????????if (slaves) flushSlavesOutputBuffers();

????????}

????}

}

Redis 4.0中新的LFU算法

从Redis4.0开始，新增LFU淘汰机制，提供更好缓存命中率。LFU(Least Frequently Used)通过记录键使用频率来定位最可能淘汰的键。

对比LRU与LFU的差别：

• 在LRU中，某个键很少被访问，但在刚刚被访问后其被淘汰概率很低，从而出现这类异常持续存在的缓存；相对的，其他可能被访问的键会被淘汰
• 而LFU中，按访问频次淘汰最少被访问的键

Redis 4.0中新增两种LFU淘汰机制：

• volatile-lfu：设置过期时间的键按LFU淘汰
• allkeys-lfu：所有键按LFU淘汰

LFU使用Morris counters计数器占用少量位数来评估每个对象的访问频率，并随时间更新计数器。此机制实现与近似LRU中采样类似。但与LRU不同，LFU提供明确参数来指定计数更新频率。

• lfu-log-factor：0-255之间，饱和因子，值越小代表饱和速度越快
• lfu-decay-time：衰减周期，单位分钟，计数器衰减的分钟数

这两个因子形成一种平衡，通过少量访问 VS 多次访问 的评价标准最终形成对键重要性的评判。

原文：?

Redis主从复制原理

相信很多小伙伴都已经配置过主从复制，但是对于redis主从复制的工作流程和常见问题很多都没有深入的了解。咔咔这次用时俩天时间给大家整理一份redis主从复制的全部知识点。本文实现所需环境 centos7.0 redis4.0

一、什么是Redis主从复制？

主从复制就是现在有俩台redis服务器，把一台redis的数据同步到另一台redis数据库上。前者称之为主节点（master），后者为从节点（slave）。数据是只能master往slave同步单向。

但是在实际过程中是不可能只有俩台redis服务器来做主从复制的，这也就意味这每台redis服务器都有可能会称为主节点（master）

下图案例中，我们的slave3既是master的从节点，也是slave的主节点。

先知道这么个概念，更多详解继续查看下文。

?转存失败重新上传取消?

二、为什么需要Redis主从复制？

假设我们现在就一台redis服务器，也就是单机状态。

在这种情况下会出现的第一个问题就是服务器宕机，直接导致数据丢失。如果项目是跟￥占关系的，那造成的后果就可想而知。

第二个情况就是内存问题了，当只有一台服务器时内存肯定会到达峰值的，不可能对一台服务器进行无限升级的。

?转存失败重新上传取消?

所以针对以上俩个问题，我们就多准备几台服务器，配置主从复制。将数据保存在多个服务器上。并且保证每个服务器的数据是同步的。即使有一个服务器宕机了，也不会影响用户的使用。redis可以继续实现高可用、同时实现数据的冗余备份。

这会应该会有很多疑问，master跟slave怎么连接呢？ 如何同步数据呢？ 假如master服务器宕机了呢？别着急，一点一点解决你的问题。

?转存失败重新上传取消?

三、Redis主从复制的作用

在上边我们说了为什么使用redis的主从复制，那么主从复制的作用就是针对为什么使用它来讲了。

我们继续使用这个图来谈论

• 第一点是数据冗余了，实现了数据的热备份，是持久化之外的另一种方式。
• 第二点是针对单机故障问题。当主节点也就是master出现问题时，可以由从节点来提供服务也就是slave，实现了快速恢复故障，也就是服务冗余。
• 第三点是读写分离，master服务器主要是写，slave主要用来读数据，可以提高服务器的负载能力。同时可以根据需求的变化，添加从节点的数量。
• 第四点是负载均衡，配合读写分离，有主节点提供写服务，从节点提供读服务，分担服务器负载，尤其在写少读多的情况下，通过多个从节点分担读负载，可以大大提高redis服务器的并发量和负载。
• 第五点是高可用的基石，主从复制是哨兵和集群能够实施的基础，因此我们可以说主从复制是高可用的基石。

?转存失败重新上传取消?

四、配置Redis主从复制

说了这么多，我们先简单的配置一个主从复制案例，然后在谈实现的原理。

redis存储路径为：usr/local/redis

日志跟配置文件存储在：usr/local/redis/data

首先我们先配置俩个配置文件，分别为redis6379.conf 和 redis6380.conf

?转存失败重新上传取消?

修改配置文件，主要就是修改端口。为了查看方便在把日志文件和持久化文件的名字都用各自的端口来做标识。

?转存失败重新上传取消?

然后分别开启俩个redis服务，一个端口为6379，一个端口为6380。执行命令redis-server redis6380.conf,然后使用redis-cli -p 6380连接，因为redis的默认端口就是6379所以我们启动另外一台redis服务器直接使用redis-server redis6379.conf 然后直接使用redis-cli直接连接就可以。

?转存失败重新上传取消?

这个时候我们就成功的配置了俩个redis服务，一台为6380，一台为6379，这里只是为了演示。实际工作中是需要配置在俩台不同的服务器的。

?转存失败重新上传取消?

1. 使用客户端命令行启动

我们先得有一个概念，就是在配置主从复制时，所有的操作都是在从节点来操作，也就是slave。

那么我们在从节点执行一个命令为 slaveof 127.0.0.1 6379，执行完就代表我们连接上了。

?转存失败重新上传取消?

我们先测试一下看是否实现主从复制。在master这台服务器上执行俩个set kaka 123 和 set master 127.0.0.1，然后在slave6380端口是可以成功获取到的，也就说明我们的主从复制就已经配置完成了。但是在实现生产环境可不是就这样完事了，后边会在进一步对主从复制进行优化，直到实现高可用。

?转存失败重新上传取消?

2. 使用配置文件启用

在使用配置文件启动主从复制之前呢！先需要把之前使用客户端命令行连接的断开，在从主机执行slaveof no one即可断开主从复制。

?转存失败重新上传取消?

在哪可以查看从节点已经断开了主节点呢！在主节点的客户端输入命令行info查看

这张图是使用从节点使用客户端命令行连接主节点后，在主节点的客户端输入info打印的信息，可以看到有一个slave0的一个信息。

?转存失败重新上传取消?

这个图是在从节点执行完slaveof no one 后，在主节点打印的info，说明从节点已经跟主节点断开连接了。

?转存失败重新上传取消?

在根据配置文件启动redis服务，redis-server redis6380.conf

当在从节点重新启动后就可以在主节点直接查看到从节点的连接信息。

?转存失败重新上传取消?

测试数据，主节点写的东西，从节点还是会自动同步的。

?转存失败重新上传取消?

3. 启动redis服务器时启动

这种方式配置也是很简单，在启动redis服务器时直接就启动主从复制，执行命令：redis-server --slaveof host port 即可。

4. 主从复制启动后的日志信息查看

这个是主节点的日志信息

?转存失败重新上传取消?

这个是从节点的信息，其中有连接主节点信息，还有RDB快照保存。

?转存失败重新上传取消?

五、主从复制工作原理

1. 主从复制的三个阶段

主从复制完整的工作流程分为以下三个阶段。每一段都有自己的内部工作流程，那么我们会对这三个过程进行谈论。

• 建立连接过程：这个过程就是slave跟master连接的过程
• 数据同步过程：是master给slave同步数据的过程
• 命令传播过程：是反复同步数据

?转存失败重新上传取消?

2. 第一阶段：建立连接过程

?转存失败重新上传取消?

上图是一个完整主从复制建立连接工作流程。然后使用简短的话语来描述上边的工作流程。

1. 设置master的地址和端口，保存master的信息
2. 建立socket连接（这个连接做的事情下文会说）
3. 持续发送ping命令
4. 身份验证
5. 发送slave端口信息

在建立连接的过程中，从节点会保存master的地址和端口、主节点master保存从节点slave的端口。

3. 第二阶段：数据同步阶段过程

?转存失败重新上传取消?

这张图是详细描述第一次从节点连接主节点时的数据同步过程。 当从节点第一次连接主节点时，先会执行一次全量复制这次的全量复制是无法避免的。 全量复制执行完成后，主节点就会发送复制积压缓冲区的数据，然后从节点就会执行bgrewriteaof恢复数据，这也就是部分复制。 在这个阶段提到了三个新点，全量复制、部分复制、复制缓冲积压区。会在下文的常见问题里详细说明这几个点。

4. 第三阶段：命令传播阶段

当master数据库被修改后，主从服务器的数据不一致后，此时就会让主从数据同步到一致，这个过程称之为命令传播。 master会将接收到的数据变更命令发送给slave，slave接收命令后执行命令，让主从数据达到一致。 命令传播阶段的部分复制

• 在命令传播阶段出现断网的情况，或者网络抖动时会导致连接断开（connection lost）
• 这个时候主节点master还是会继续往replbackbuffer（复制缓冲积压区）写数据
• 从节点会继续尝试连接主机（connect to master）
• 当从节点把自己的runid和复制偏移量发送给主节点，并且执行pysnc命令同步
• 如果master判断偏移量是在复制缓冲区范围内，就会返回continue命令。并且发送复制缓冲区的数据给从节点。
• 从节点接收数据执行bgrewriteaof，恢复数据

六. 详细介绍主从复制原理（全量复制+部分复制）

?转存失败重新上传取消?

这个过程就是主从复制最齐全的流程讲解。那么下来我们对每一步进程简单的介绍

1. 从节点发送指令psync ? 1 psync runid offset 找对应的runid索取数据。但是这里可以考虑一下，当从节点第一次连接的时候根本就不知道主节点的runid 和 offset 。所以第一次发送的指令是psync ？ 1意思就是主节点的数据我全要。
2. 主节点开始执行bgsave生成RDB文件，记录当前的复制偏移量offset
3. 主节点这个时候会把自己的runid 和 offset 通过 +FULLRESYNC runid offset 指令 通过socket发送RDB文件给从节点。
4. 从节点接收到+FULLRESYNC 保存主节点的runid和offset 然后清空当前所有数据，通过socket接收RDB文件，开始恢复RDB数据。
5. 在全量复制后，从节点已经获取到了主节点的runid和offset，开始发送指令 psync runid offset
6. 主节点接收指令，判断runid是否匹配，判断offset是否在复制缓冲区中。
7. 主节点判断runid和offset有一个不满足，就会在返回到步骤2继续执行全量复制。这里的runid不匹配只有的可能是从节点重启了这个问题后边会解决，offset（偏移量）不匹配就是复制积压缓冲区溢出了。 如果runid或offset校验通过，从节点的offset和主节点的offset相同时则忽略。 如果runid或offset检验通过，从节点的offset与offset不相同，则会发送 +CONTINUE offset(这个offset为主节点的)，通过socket发送复制缓冲区中从节点offset到主节点offset的数据。
8. 从节点收到+CONTINUE 保存master的offset 通过socket接收到信息后，执行bgrewriteaof，恢复数据。

1-4是全量复制 5-8是部分复制

在主节点的第3步下面 主节点在主从复制的期间是一直在接收客户端的数据，主节点的offset是一直变化的。只有有变化就会给每个slave进行发送，这个发送的过程称之为心跳机制

七. 心跳机制

在命令传播阶段是，主节点与从节点之间一直都需要进行信息互换，使用心跳机制进行维护，实现主节点和从节点连接保持在线。

• master心跳
  • 指令：ping
  • 默认10秒进行一次，是由参数repl-ping-slave-period决定的
  • 主要做的事情就是判断从节点是否在线
  • 可以使用info replication 来查看从节点租后一次连接时间的间隔，lag为0或者为1就是正常状态。
• slave心跳任务
  • 指令：replconf ack {offset}
  • 每秒执行一次
  • 主要做的事情是给主节点发送自己的复制偏移量，从主节点获取到最新的数据变更命令，还做一件事情就是判断主节点是否在线。

心跳阶段的注意事项?主节点为保障数据稳定性，当从节点挂掉的数量或者延迟过高时。将会拒绝所有信息同步。

这里有俩个参数可以进行配置调整：

min-slaves-to-write ??2

min-slaves-max-lag 8

这俩个参数表示从节点的数量就剩余2个，或者从节点的延迟大于8秒时，主节点就会强制关闭maste功能，停止数据同步。

那么主节点是如何知道从节点挂掉的数量和延迟时间呢！ 在心跳机制里边slave 会每隔一秒发送perlconf ack 这个指令，这个指令可携带偏移量，也可以携带从节点的延迟时间和从节点的数量。

八、部分复制的三个核心要素

1. 服务器的运行id （run id）

我们先看一下这个run id是什么，执行info命令即可看到。在上文中我们查看启动日志信息也可以看到。

?转存失败重新上传取消?

redis在启动时会自动生成一个随机的id（这里需要注意的是每次启动的id都会不一样），是由40个随机的十六进制字符串组成，用来唯一识别一个redis节点。 在主从复制初次启动时，master会把自己的runid发送给slave，slave会保存master的这个id，我们可以使用info命令查看

?转存失败重新上传取消?

当断线重连时，slave把这个id发送给master，如果slave保存的runid与master现在的runid相同，master会尝试使用部分复制（这块能否复制成功还有一个因素就是偏移量）。如果slave保存的runid与master现在的runid不同，则会直接进行全量复制。

2. 复制积压缓冲区

复制缓冲积压区是一个先进先出的队列，用户存储master收集数据的命令记录。复制缓冲区的默认存储空间是1M。 可以在配置文件修改repl-backlog-size 1mb来控制缓冲区大小，这个比例可以根据自己的服务器内存来修改，咔咔这边是预留出了30%左右。

复制缓冲区到底存储的是什么？

当执行一个命令为set name kaka时，我们可以查看持久化文件查看

?转存失败重新上传取消?

那么复制积压缓冲区就是存储的aof持久化的数据，并且以字节分开，并且每个字节都有自己的偏移量。这个偏移量也就是复制偏移量（offset）

?转存失败重新上传取消?

那为什么会说复制缓冲积压区有可能会导致全量复制呢 在命令传播阶段，主节点会把收集的数据存储到复制缓冲区中，然后在发送给从节点。就是这里出现了问题，当主节点数据量在一瞬间特别大的时候，超出了复制缓冲区的内存，就会有一部分数据会被挤出去，从而导致主节点和从节点的数据不一致。从而进行全量复制。如果这个缓冲区大小设置不合理那么很大可能会造成死循环，从节点就会一直全量复制，清空数据，全量复制。

3. 复制偏移量（offset）

?转存失败重新上传取消?

主节点复制偏移量是给从节点发送一次记录一次，从节点是接收一次记录一次。 用于同步信息，对比主节点和从节点的差异，当slave断联时恢复数据使用。 这个值也就是来自己于复制缓冲积压区里边的那个偏移量。

九. 主从复制常见的问题

1. 主节点重启问题（内部优化）

当主节点重启后，runid的值将发生变化，会导致所有的从节点进行全量复制。

这个问题我们无需考虑，知道系统是怎么优化的即可。

在建立完主从复制后主节点会创建master-replid变量，这个生成的策略跟runid一样，长度是41位，runid长度是40位，然后发送给从节点。

在主节点执行shutdown save命令时，进行了一次RDB持久化会把runid 和 offset保存到RDB文件中。可以使用命令redis-check-rdb查看该信息。

?转存失败重新上传取消?

主节点重启后加载RDB文件，将文件中的repl-id 和repl-offset加载到内存中。纵使让所有从节点认为还是之前的主节点。

2. 从节点网络中断偏移量越界导致全量复制

由于网络环境不佳，从节点网络中断。复制积压缓冲区内存过小导致数据溢出，伴随着从节点偏移量越界，导致全量复制。有可能会导致反复的全量复制。 解决方案：修改复制积压缓冲区的大小：repl-backlog-size 设置建议：测试主节点连接从节点的时间，获取主节点每秒平均产生的命令总量write_size_per_second 复制缓冲区空间设置 = 2 * 主从连接时间 * 主节点每秒产生的数据总量

3. 频繁的网路中断

由于主节点的cpu占用过高，或者从节点频繁连接。出现这种情况造成的结果就是主节点各种资源被严重占用，其中包括但不限于缓冲区，宽带，连接等。 为什么会出现主节点资源被严重占用？ 在心跳机制中，从节点每秒会发送一个指令replconf ack指令到主节点。 从节点执行了慢查询，占用大量的cpu 主节点每秒调用复制定时函数replicationCron，然后从节点长时间没有相应。

解决方案：

• 设置从节点超时释放
• 设置参数：repl-timeout
• 这个参数默认为60秒。超过60秒，释放slave。

4. 数据不一致问题

由于网络因素，多个从节点的数据会不一致。这个因素是没有办法避免的。

关于这个问题给出俩个解决方案：

• 第一个数据需要高度一致配置一台redis服务器，读写都用一台服务器，这种方式仅限于少量数据，并且数据需高度一直。
• 第二个监控主从节点的偏移量，如果从节点的延迟过大，暂时屏蔽客户端对该从节点的访问。设置参数为slave-serve-stale-data yes|no。 这个参数一但设置就只能响应info slaveof等少数命令。

5. 从节点故障

这个问题直接在客户端维护一个可用节点列表，当从节点故障时，切换到其他节点进行工作，这个问题在后边集群会说到。

十. 总结

本文主要讲解了什么是主从复制、主从复制工作的三大阶段以及工作流程、部分复制的三大核心。命令传播阶段的心跳机制。最后说明了主从复制常见问题。

作者：原来是咔咔 链接：掘金?来源：掘金 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。