本文共 12897 字,大约阅读时间需要 42 分钟。
原文地址:
这周开始学习 Redis,看看Redis是怎么实现的。所以会写一系列关于 Redis的文章。这篇文章关于 Redis 的基础数据。阅读这篇文章你可以了解:
三个数据结构 Redis 是怎么实现的。
SDS (Simple Dynamic String)是 Redis 最基础的数据结构。直译过来就是”简单的动态字符串“。Redis 自己实现了一个动态的字符串,而不是直接使用了 C 语言中的字符串。
sds 的数据结构:
1234567891011 | struct sdshdr { // buf 中已占用空间的长度 int len; // buf 中剩余可用空间的长度 int free; // 数据空间 char buf[];}; |
所以一个 SDS 的就如下图:
所以我们看到,sds 包含3个参数。buf 的长度 len,buf 的剩余长度,以及buf。
为什么这么设计呢?
可以直接获取字符串长度。
C 语言中,获取字符串的长度需要用指针遍历字符串,时间复杂度为 O(n),而 SDS 的长度,直接从len 获取复杂度为 O(1)。杜绝缓冲区溢出。
由于C 语言不记录字符串长度,如果增加一个字符传的长度,如果没有注意就可能溢出,覆盖了紧挨着这个字符的数据。对于SDS 而言增加字符串长度需要验证 free的长度,如果free 不够就会扩容整个 buf,防止溢出。减少修改字符串长度时造成的内存再次分配。
redis 作为高性能的内存数据库,需要较高的相应速度。字符串也很大概率的频繁修改。 SDS 通过未使用空间这个参数,将字符串的长度和底层buf的长度之间的额关系解除了。buf的长度也不是字符串的长度。基于这个分设计 SDS 实现了空间的预分配和惰性释放。二进制安全。
C 语言中的字符串是以 ”\0“ 作为字符串的结束标记。而 SDS 是使用 len 的长度来标记字符串的结束。所以SDS 可以存储字符串之外的任意二进制流。因为有可能有的二进制流在流中就包含了”\0“造成字符串提前结束。也就是说 SDS 不依赖 “\0” 作为结束的依据。兼容C语言
SDS 按照惯例使用 ”\0“ 作为结尾的管理。部分普通C 语言的字符串 API 也可以使用。C语言中并没有链表这个数据结构所以 Redis 自己实现了一个。Redis 中的链表是:
12345678910111213 | typedef struct listNode { // 前置节点 struct listNode *prev; // 后置节点 struct listNode *next; // 节点的值 void *value;} listNode; |
非常典型的双向链表的数据结构。
同时为双向链表提供了如下操作的函数:
1234567891011121314151617181920212223242526272829303132333435363738 | /* * 双端链表迭代器 */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; |
链表的结构比较简单,数据结构如下:
总结一下性质:
字典数据结构极其类似 java 中的 Hashmap。
Redis的字典由三个基础的数据结构组成。最底层的单位是哈希表节点。结构如下:
1234567891011121314151617 | typedef struct dictEntry { // 键 void *key; // 值 union { void *val; uint64_t u64; int64_t s64; } v; // 指向下个哈希表节点,形成链表 struct dictEntry *next;} dictEntry; |
实际上哈希表节点就是一个单项列表的节点。保存了一下下一个节点的指针。 key 就是节点的键,v是这个节点的值。这个 v 既可以是一个指针,也可以是一个 uint64_t
或者 int64_t
整数。*next 指向下一个节点。
通过一个哈希表的数组把各个节点链接起来:
12345678910111213141516 | typedef struct dictht { // 哈希表数组 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩码,用于计算索引值 // 总是等于 size - 1 unsigned long sizemask; // 该哈希表已有节点的数量 unsigned long used;} dictht; |
dictht
通过图示我们观察:
实际上,如果对java 的基本数据结构了解的同学就会发现,这个数据结构和 java 中的 HashMap 是很类似的,就是数组加链表的结构。
字典的数据结构:
12345678910111213141516171819 | typedef struct dict { // 类型特定函数 dictType *type; // 私有数据 void *privdata; // 哈希表 dictht ht[2]; // rehash 索引 // 当 rehash 不在进行时,值为 -1 int rehashidx; /* rehashing not in progress if rehashidx == -1 */ // 目前正在运行的安全迭代器的数量 int iterators; /* number of iterators currently running */} dict; |
其中的dictType 是一组方法,代码如下:
123456789101112131415161718192021222324 | /* * 字典类型特定函数 */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; |
字典的数据结构如下图:
这里我们可以看到一个dict 拥有两个 dictht。一般来说只使用 ht[0],当扩容的时候发生了rehash的时候,ht[1]才会被使用。
当我们观察或者研究一个hash结构的时候偶我们首先要考虑的这个 dict 如何插入一个数据?
我们梳理一下插入数据的逻辑。
计算Key 的 hash 值。找到 hash 映射到 table 数组的位置。
如果数据已经有一个 key 存在了。那就意味着发生了 hash 碰撞。新加入的节点,就会作为链表的一个节点接到之前节点的 next 指针上。
如果 key 发生了多次碰撞,造成链表的长度越来越长。会使得字典的查询速度下降。为了维持正常的负载。Redis 会对 字典进行 rehash 操作。来增加 table 数组的长度。所以我们要着重了解一下 Redis 的 rehash。步骤如下:
渐进式的 rehash 。
其实如果字典的 key 数量很大,达到千万级以上,rehash 就会是一个相对较长的时间。所以为了字典能够在 rehash 的时候能够继续提供服务。Redis 提供了一个渐进式的 rehash 实现,rehash的步骤如下:这样保证数据能够平滑的进行 rehash。防止 rehash 时间过久阻塞线程。
原文地址:
上篇文章写了 Redis 基础数据结构的可变字符串、链表、字典。大家可以点击查看。今天我们继续研究 Redis 的基础数据结构。
当一个集合只包含整数,且这个集合的元素不多的时候,Redis 就会使用整数集合 intset 。首先看 intset 的数据结构:
1234567891011 | typedef struct intset { // 编码方式 uint32_t encoding; // 集合包含的元素数量 uint32_t length; // 保存元素的数组 int8_t contents[];} intset; |
其实 intset 的数据结构比较好理解。一个数据保存元素,length 保存元素的数量,也就是contents的大小,encoding 用于保存数据的编码方式。
通过代码我们可以知道,encoding 的编码类型包括了:
123 | #define INTSET_ENC_INT16 (sizeof(int16_t))#define INTSET_ENC_INT32 (sizeof(int32_t))#define INTSET_ENC_INT64 (sizeof(int64_t)) |
实际上我们可以看出来。 Redis encoding的类型,就是指数据的大小。作为一个内存数据库,采用这种设计就是为了节约内存。
既然有从小到大的三个数据结构,在插入数据的时候尽可能使用小的数据结构来节约内存,如果插入的数据大于原有的数据结构,就会触发扩容。
扩容有三个步骤:
整数集合不支持降级操作,一旦升级就不能降级了。
跳跃表是链表的一种,是一种利用空间换时间的数据结构。跳表平均支持 O(logN),最坏O(N)复杂度的查找。
跳表是由一个zskiplist 和 多个 zskiplistNode 组成。我们先看看他们的结构:
1234567891011121314151617181920212223242526272829303132333435363738394041424344 | /* ZSETs use a specialized version of Skiplists *//* * 跳跃表节点 */typedef struct zskiplistNode { // 成员对象 robj *obj; // 分值 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; |
所以根据这个代码我们可以画出如下的结构图:
其实跳表就是一个利用空间换时间的数据结构,利用 level 作为链表的索引。
之前有人问过 Redis 的作者 为什么使用跳跃表,而不是 tree 来构建索引?作者的回答是:
压缩链表 Redis 作者的介绍是,为了尽可能节约内存设计出来的双向链表。
对于一个压缩列表代码里注释给出的数据结构如下:
zlbytes
表示的是整个压缩列表使用的内存字节数
zltail
指定了压缩列表的尾节点的偏移量
zllen
是压缩列表 entry 的数量
entry
就是 ziplist 的节点
zlend
标记压缩列表的末端
这个列表中还有单个指针:
ZIPLIST_ENTRY_HEAD
列表开始节点的头偏移量
ZIPLIST_ENTRY_TAIL
列表结束节点的头偏移量
ZIPLIST_ENTRY_END
列表的尾节点结束的偏移量
再看看一个 entry 的结构:
12345678910111213141516171819202122232425 | /* * 保存 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; |
依次解释一下这几个参数。
prevrawlen
前置节点的长度,这里多了一个 size,其实是记录了 prevrawlen 的尺寸。Redis 为了节约内存并不是直接使用默认的 int 的长度,而是逐渐升级的。
len
记录的是当前节点的长度,lensize
记录的是 len 的长度。headersize
就是前文提到的两个 size 之和。encoding
就是这个节点的数据类型。这里注意一下 encoding 的类型只包括整数和字符串。p
节点的指针,不用过多的解释。 需要注意一点,因为每个节点都保存了前一个节点的长度,如果发生了更新或者删除节点,则这个节点之后的数据也需要修改,有一种最坏的情况就是如果每个节点都处于需要扩容的零界点,就会造成这个节点之后的节点都要修改 size 这个参数,引发连锁反应。这个时候就是 压缩链表最坏的时间复杂度 O(n^2)。不过所有节点都处于临界值,这样的概率可以说比较小。
至此Redis的基本数据结构就介绍完了。我们可以看到 Redis 对内存的使用真是“斤斤计较”,对于内存是使用特别节约。同时 Redis 作为一个单线程应用,不用考虑并发的问题,将很多类似 size 或者 length 的参数暴露出来,将很多 O(n) 的操作降低为 O(1)。大大提升效率。下一讲,将会介绍 Redis 是怎么通过这些数据结构向外提供服务。
Redis 的代码真是写的太棒了,简洁高效。值得大家学习。原文地址:
前两篇文章介绍了 Redis 的基本数据结构动态字符串,链表,字典,跳跃表,压缩链表,整数集合,但是使用过 Redis 的同学会发现,平时根本没有使用过这些数据结构。 平时使用的数据结构,包括字符串,列表,哈希,集合,还有有序集合。 其实 Redis 的实现是将底层的一种或者几种数据结构进行结合成我们使用的数据结构。
所以今天这篇文章就是要解释 Redis 是怎么实现符串,列表,哈希,集合,还有有序集合的。
对于 Redis 来说使用了 redisObject 来对所有的对象进行了封装:
12345678910111213141516171819 | typedef struct redisObject { // 对象类型 unsigned type:4; // 编码 unsigned encoding:4; // 对象最后一次被访问的时间 unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */ // 引用计数 int refcount; // 指向实际值的指针 void *ptr;} robj; |
我们先关注两个参数
type
和 encoding
:
12345678910111213141516171819202122 | /* Object types */// 对象类型#define REDIS_STRING 0#define REDIS_LIST 1#define REDIS_SET 2#define REDIS_ZSET 3#define REDIS_HASH 4/* 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 REDIS_ENCODING_RAW 0 /* Raw representation */#define REDIS_ENCODING_INT 1 /* Encoded as integer */#define REDIS_ENCODING_HT 2 /* Encoded as hash table */#define REDIS_ENCODING_ZIPMAP 3 /* Encoded as zipmap */#define REDIS_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */#define REDIS_ENCODING_ZIPLIST 5 /* Encoded as ziplist */#define REDIS_ENCODING_INTSET 6 /* E dncoded as intset */#define REDIS_ENCODING_SKIPLIST 7 /* Encoded as skiplist */#define REDIS_ENCODING_EMBSTR 8 /* Embedded sds string encoding */ |
所以通过这段代码我们可以知道 Redis 支持的数据类型如下:
type | 类型 |
---|---|
REDIS_STRING | 字符串 |
REDIS_LIST | 列表 |
REDIS_SET | 集合 |
REDIS_ZSET | 有序集合 |
REDIS_HASH | 哈希表 |
Redis 的 Object 通过 ptr
指向具体的底层数据。Redis 的底层数据:
编码 | 类型 |
---|---|
REDIS_ENCODING_RAW | SDS 实现的动态字符串对象 |
REDIS_ENCODING_INT | 整数实现的动态字符串对象 |
REDIS_ENCODING_HT | 字典实现的 hash 对象 |
REDIS_ENCODING_ZIPMAP | 压缩map实现对对象,(3.0)版本未使用 |
REDIS_ENCODING_LINKEDLIST | 双向链表实现的对象 |
REDIS_ENCODING_ZIPLIST | 压缩列表实现的对象 |
REDIS_ENCODING_INTSET | 整数集合实现的对象 |
REDIS_ENCODING_SKIPLIST | 跳跃表实现的对象 |
REDIS_ENCODING_EMBSTR | 使用 embstr 实现的动态字符串的对象 |
PS:下文会解释 RAW 和 EMBSTR 的区别。
我就按照类型的顺序看看 Redis 是怎么利用底层的数据结构实现不同的对象类型的。
Redis 的字符串 String,主要由 int、raw 和 emstr 底层数据实现的。 Redis 遵循以下的原则来决定使用底层数据结构的使用。
问题来了:
len
、free
还有 buf
,在3.2之前 len 和 free 的数据类型都是 unsigned int。 这个就是为什么上面的公式 sds header 是 8个字节了。新版本的 sdshdr 变成了 sdshdr8, sdshdr16 和 sdshdr32还有 sdshdr64。优化的地方就在于如果 buf 小,使用更小位数的数据类型来描述 len 和 free 减少他们占用的内存,同时增加了一个char flags
。emstr使用了最小的 sdshdr8。 这个时候 sds header 就变成了(len(1b) + free(1b) + flags(1b)) 3个字节, 比之前的实现少了5个字节。 所以新版本的 emstr 的最大字节变成了 44。 还是那句话 Redis 对内存真是 “斤斤计较”Reids 的列表,底层是一个 ziplist 或者 linkedlist。
两个条件都满足使用ziplist编码,两个条件任意一个不满足时,ziplist会变为linkedlist。
3.2 以后使用 quicklist 保存。这个数据结构之前没有讲解过。
实际上 quicklist 是 ziplist 和双向链表结合的产物。我们这样理解,每个双向链表的节点上是一个ziplist。之所以这么设计,应该是空间和时间之间的取舍或者一个折中的方案。 具体的实现我会在以后的文章里面具体分析。
Redis 的集合底层是一个 intset 或者 一个字典(hashtable)。
这个比较容易理解:
使用字典的时候,字典的每一个 key 就是集合的一个元素,对应的 value 就是一个 null。
Redis 的有序集合使用 ziplist 或者 skiplist 实现的。
同时满足以上条件使用ziplist,否则使用skiplist。
对于 ziplist 的实现,redis 使用相邻的两个 entity 分别保存对象以及对象的排序因子。这样对于插入和查询的复杂度都是 O(n) 的。直接看图:
元素开发工程师,排序的因子就是月薪。(好吧php是世界上最好的语言)。
对于skiplist 的实现:
12345678 | typedef struct zset{ zskiplist *zsl; dict *dict}zset; |
skiplist 的有序链表的实现不只是只有一个 skiplist ,还有一个字典存储对象的key 和 排序因子的映射,这个是为了保证按照key 查询的时候时间负责度为 O(1)。同时有序性依赖 skiplist 维护。大家可以看我之前的教程。所以直接看图:
Redis 的 hash 表 使用 ziplist 和 字典 实现的。
都满足的时候使用 ziplist,否则使用字典。
ziplist 的实现类似,类似 zset 的实现。两个entity成对出现。一个存储key,另一个存储 velue。
还是可以使用上面使用过的图。这个时候 entity 不用排序。key 是职位名称,velue 是对应的月薪。(好吧php还是世界上最好的语言)。与zset实现的区别就是查询是 O(n) 的,插入直接往tail后面插入就行时间复杂度O(1)。
使用字典实现一个 hash表。好像没有什么可以多说的。
这个参数是引用计数。Redis 自己管理内存,所以就使用了最简单的内存管理方式–引用计数。
这个参数记录了对象的最后一次活跃时间。
如果 Redis 开启了淘汰策略,且淘汰的方式是 LRU 的时候,这个参数就派上了用场。Redis 会优先回收 lru 最久的对象。
至此 Redis 的数据结构就介绍完了。
大家可以阅读之前的文章:
转载地址:http://odlzb.baihongyu.com/