Redis设计与实现(一~五整合版)

项目中用到了redis,但用到的都是最最基本的功能,比如简单的slave机制,数据结构只使用了字符串。但是一直听说redis是一个很牛的开源项目,很多公司都在用。于是我就比较奇怪,这玩意不就和 memcache 差不多吗?仅仅是因为memcache是内存级别的,没有持久化功能。而redis支持持久化?难道这就是它的必杀技?

Redis设计与实现 第二版 高清PDF 下载 

带着这个疑问,我在网上搜了一圈。发现有个叫做huangz的程序员针对redis写了一本书叫做《redis设计与实现》,而且业界良心搞了一个reids2.6版本的注释版源码。这本书不到200页,估计2个星期能看完吧,之后打算再看下感兴趣部分的源码。当然,如果你不知道redis是干嘛的,请自行谷歌,简单说就是Key-Value数据库,而且 value 支持5种数据结构:

字符串

哈希表(map)

列表(list)

集合(set)

有序集

下面我们就从 redis 的内部结构开始说起吧:)

一、redis内部数据结构

首先需要知道,redis是用C写的。众所周知,任何系统对于字符串的操作都是最频繁的,而恰巧C语言的字符串备受诟病。然后作者就封装了一下 C 语言的字符串 char *。

总之,根据redis的业务场景,整个redis系统的底层数据支撑被设计为如下几种:

简单动态字符串sds(Simple Dynamic String)

双端链表

字典(Map)

跳跃表

下面我们就分别来说说这4种数据结构。

1. 简单动态字符串sds

redis的字符串表示为sds,而不是C字符串(以\0结尾的char*)

对比C字符串,sds有以下特性

可以高效执行长度计算O(1)

可以高效执行append操作(通过free提前分配)

二进制安全

sds会为追加操作进行优化,加快追加操作的速度,并降低内存分配的次数,代价是多占用内存,且不会主动释放

这个一看名字就能知道个大概了,因为字符串操作无非是增删查改,如果使用char[]数组,那是要死人的,任何操作都是O(N)复杂度。所以,要对某些频繁的操作实现O(1)级性能。但是我们还是得思考:

为什么要对字符串造轮子?

因为redis是一个key-value类型的数据库,而key全部都是字符串,value可以是集合、hash、list等等。同时,在redis的各种操作中,都会频繁使用字符串的长度和append操作,对于char[]来说,长度操作是O(N)的,append会引起N次realloc。而且因为redis分为client和server,传输的协议内容必须是二进制安全的,而C的字符串必须保证是\0结尾,所以在这两点的基础上开发sds

知道了上面几点就可以看下实现了,其实实现特别简单。它通过一个结构体来代表字符串对象,内部有个len属性记录长度,有个free用于以后的append操作,具体的值还是一个char[]。长度就不说了,只在插入的时候用一下,以后只需要维护len就可以O(1)拿到;对于free也很简单,vector不也是这么实现的嘛。就是按照某个阈值进行翻倍叠加。

2. 双端链表

redis自己实现了双端链表

双端链表主要两个作用:

作为redis列表类型的底层实现之一

作为通用数据结构被其他模块使用

双端链表及其节点的性能特征如下:

节点带有前驱和后继指针

链表是双向的,所以对表头和表尾操作都是O(1)

链表节点可以会被维护,LLEN复杂度为O(1)

这玩意当时刷数据结构与算法分析那本书看过,但是没怎么用到过。说白了双端链表就是有2个指针,一个指向链表头,一个指向链表尾。对每个节点而言,记录自己的父节点和子节点,这样双向移动速度会快很多。

还是老问题:

为什么要有双端链表?

Java或者C++中,都有现成的容器供我们使用,但是C没有。于是作者自己造了一个双端链表数据结构。而这个也是redis列表数据结构的基础之一(另外一个还是压缩列表)。而且双端链表也是一个通用的数据结构被其他功能调用,比如事务。

至于实现也是比较简单,双端链表,肯定有2个指针指向链表头和链表尾,然后内部维护一个len保存节点的数目,这样当使用LLEN的时候就能达到O(1)复杂度了。其他的,额,对每个节点而言,都有双向的指针,另外还有针对双端链表的迭代器,也是两个方向。

3. 字典(其实说Map更通俗)

字典是由键值对构成的抽象数据结构

redis中的数据库和哈希键值对都基于字典实现

字典的底层实现为哈希表,每个字典含有2个哈希表,一般只是用0号哈希表,1号哈希表是在rehash过程中才使用的

哈希表使用链地址法来解决碰撞问题

rehash可以用于扩展或者收缩哈希表

对哈希表的rehash是分多次、渐进式进行的

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/6be4ac5bc3f297e5261a68427fc4282e.html