本文共 6121 字，大约阅读时间需要 20 分钟。
1、与其他数据库的对比
最近系统中引入了Redis，在应用中发现Reids具有关系型数据库或其他缓存服务器所不具备的优点。
与关系型数据库如Mysql相比，Reids属于非关系型数据库，类似于Nosql，不同数据之间不需要有关联关系。 memcache也可以用来存储键值映射，同是对内存操作，和Redis性能差别不大，但是Redis具备以两种形式将数据写入硬盘的能力，并且除了存储普通的字符串键值外，还可以存储其他四种数据结构，而memcache只能存储字符串键。所以Redis可以用来解决更广泛的问题，而且不只可以用来当做缓存数据库，更可以用作主数据库使用。2、Redis的五种数据类型
Redis可以存储五种键和数据类型间的映射，分别是STRING、LIST、SET、HASH、ZSET，其中STRING、LIST、SET、HASH在大多数编程语言中都存在，在实现和作用上也比较相似。另外ZSET是特有的一种数据结构，是一种有序集合。
以下是五种数据类型之间的对比和特点。| 结构类型 | 结构存储的值 | 结构操作 |
|---|---|---|
| STRING | 字符串、整数、浮点数 | 可以对字符串或字符串一部分执行操作，对整数和浮点数进行++ –操作 |
| LIST | 链表，链表的每个节点包含一个字符串 | 可以在链表两端进行push pull（起到了栈的作用），根据偏移量进行trim，读取单个或多个元素，根据值查找或删除元素 |
| SET | 无序集合 | 添加/获取/移除元素，判断是否存在，交差并集合，随机获取元素 |
| HASH | 无序散列表 | 添加、移除、获取键值对，获取所有键值对 |
| ZSET | 有序集合，由字符串和分数组成，元素排列顺序根据分值 | 添加、获取、删除元素，根据分值获取元素 |
2.1 STRING
Redis的字符串映射的键和值都是字符串类型，可以存储字符串、整数或浮点数。和memcache的键值对作用相同。除了普通字符串类型，在存储一些复杂结构时，比如本次在系统中存储一个java对象，就是将对象序列化为字符串进行储存，另外，也可以将对象序列化为json或xml进行存储。
一般STRING类型有以下应用场景：- 缓存，存储基础数据信息（文章、用户、记录等）。仅当update/insert时访问数据库并更新缓存，其他时候只访问缓存，可以显著减轻数据库压力。
- 用作session服务器，一般服务器集群中共享session会存储在数据库、session服务器、redis中，存取较快。
- 计数器等操作频繁的数据请求，因为STRING类型可以存储整数或浮点数并可以自增，所以用作计数器、pingback等非常方便。
2.2 LIST
LIST就是我们经常用到的数据结构中的队列，Redis的LIST是双端队列，两端都可以进行Push和pull操作，所以也可以当做栈来使用，另外还可以获取一定范围内的列表。
LIST有以下应用场景：- 分布式系统中服务间调用可以使用LIST实现消息队列，实现异步调用，使应用间解耦。
- 高并发场景下可以使用LIST实现限流。
- 文章分页或者是有序的列表数据可以使用LIST，因为可以在某个范围内存取元素。
2.3 HASH
上文中提到了STRING可以用来存储序列化的对象，但是如果这个对象需要进行操作的话，需要先解析再修改再序列化保存，无法直接修改。而HASH类型可以解决这个问题，在Redis中，HASH结构可以解决这个问题，它的键也是一个键值对，用户可以直接修改HASH结构中某个属性的值。所以适合存储对象。
HASH有以下应用场景：- 存储用户数据，用户基础数据是请求频率较高的，但是属性较多且经常需要修改，所以可以存储在HASH，修改时update某个属性就可以。
2.4 SET
SET是数据结构中的集合，与列表不同的是它不保存重复数据，并且元素无序，所以不能获取一定范围内的元素，也不能根据索引获取。Redis支持对集合进行交并差集计算，在很多场景下都可以发挥作用。
SET有以下应用场景：- 数据排重，比如记录今天访问的用户，可以使用集合。
- 标签操作，系统中有个功能是打标签，每打一个标签，可以将该数据保存在以标签id为key的set中，展示时直接展示该set。
- 用户关系操作，比如计算用户的共同好友等。
2.5 ZSET
有序集合是一种特殊的集合，它既具备集合不重复元素的特点，又可以进行排序。但它和list不同的是，它不是根据下标排序，所以排序不固定，而是它的value中包含一个分值，分值可以是分数、访问量等等，根据自定义类别进行排序。
ZSET有以下应用场景：- 排行榜，排序操作最常用的应用就是排行榜，比如考试分数、访问量、点赞量。考虑的一个应用场景是在wiki中的精选文章中，对文章进行排序。因为精选文章相对固定但需要实时变动，应用ZSET比较合适。
3、底层数据结构的实现
我们知道Redis是使用ANSI C实现的，那它是怎么实现的集合等复杂数据结构，比较令人好奇，在阅读了《Redis设计与实现》这本书后，得到了比较准确的答案。首先我们需要了解一下Redis中使用到的数据结构。
3.1 简单动态字符串
最开始以为Redis是使用c++中的char数组来存储字符串类型，其实并不是这样，它定义了一个名为simple dynamic string（SDS）的结构体用来保存字符串类型，结构如下：
struct sdshdr{ int len; int free; int buf[];} 其中：
- len：buf中已用长度
- free:bug剩余可用长度
- buf[] : 字符数组
我们存储的字符串就是存储在buf数组中，这样做的原因是char[]并不能满足Redis的操作需求，或是会带来较大的性能消耗，比如append，获取长度等等。像一些高级语言，也普遍有这种实现方式，像之前在阅读PHP数据结构源码时，string类型也是由数组和一个标志长度的int值实现。这样获取长度的复杂度就是O(1)。另外还有一些好处：
- 防止缓冲区溢出 字符串长度增加时，如果内存相邻地址已有内容，则会发生缓冲区溢出的现象，而Redis在扩展字符串时，会先检查free长度，如果不够时，会先拓展空间。
- 减少内存分配次数 SDS的扩展策略是小于1MB时，每次扩展到之前的二倍大小，大于1MB时，每次扩展1MB，所以不需要每次变化都重新分配内存。另外由于释放空间时采用惰性空间释放，减少了内存分配次数。
- 惰性空间释放 SDS释放空间时并不真正释放内存空间，而是修改free的值，既能避免内存泄露，又减少内存分配次数。
- 二进制安全 c字符串末尾默认是空字符，所以在首次读入空字符时会被认为字符串结束。而SDS记录了len长度，可以通过长度获取内容，有空字符也不影响，所以可以用来存储二进制数据。
简单动态字符串是Redis最重要的数据结构，键值等字符串类型是使用它，另外还有AOF模块中的AOF缓冲区，以及客户端状态中的输入缓冲区也是由它实现。
3.2 链表
Redis中的LIST实现之一就是链表的。由链表和节点两种数据结构组成，节点用来存储数据和指针，链表结构封装了一些复制和删除节点的操作。
下面是节点的结构体：typedef struct listNode{ struct listNode *prev; struct listNode *next; void *value;}listNode; 普通链表节点一般只有一个指针指向下一个节点，而这里面有pre和next两个指针，实现了一个双向链表。
下面是链表结构体：typedef struct list{ listNode *head; listNode *tail; unsigned long len; void *(*dup) (void *ptr) void *(*free)(void *ptr) int (*match)(void *ptr,void *key);}list; list结构体中除了包含head头结点，tail尾节点，len长度外，还封装了复制节点、删除节点、匹配节点的方法。
3.3 hashtable
Redis中HASH的实现方式之一是hashtable，由dict和dictht两种数据结构实现。
其中字典dict的数据结构：typedef struct dict { dictType *type; void *privdata; dictht ht[2]; long rehashidx; /* rehashing not in progress if rehashidx == -1 */ int iterators; /* number of iterators currently running */ } dict; type 属性 和privdata 属性是针对不同类型的键值对，为创建多态字典而设置的。ht 属性是一个包含两个项（两个哈希表）的数组。指向了两个哈希表dictht。
typedef struct dictht { dictEntry **table; unsigned long size; unsigned long sizemask; unsigned long used; } dictht; 其中dictht中的table是用来存储kv元素的，每个dictEntry包含一对kv。
最后，哈希表节点dictEntry结构定义为：typeof struct dictEntry{ void *key; union{ void *val; uint64_tu64; int64_ts64; } struct dictEntry *next;} 其中的next指针是为了解决hash冲突时，使用了链地址法组成链表。在此不对如何解决hash冲突和使用的散列算法进行深入讨论。
如图所示：
图片来自 HASH的另一种实现方式是ziplist。 3.4 intset
Redis中SET的实现方式有两种，其中一种是hashtable，在上文中已经有过了解。另外一种是intset，这是一个整数集合，里面存的为某种同一类型的整数，支持如下三种长度的整数：
#define INTSET_ENC_INT16 (sizeof(int16_t)) #define INTSET_ENC_INT32 (sizeof(int32_t)) #define INTSET_ENC_INT64 (sizeof(int64_t))
intset结构体为：
typedef struct intset{ //编码方式 uint32_t enconding; //集合包含的元素数量 uint32_t length; //保存元素的数组 int8_t contents[];}intset; 其中里面的数据按照从大到小的元素排列。并且存储的类型由encoding决定。在集合中查找元素的复杂度为O(logN)。但插入时设计到从16位升级到32位或64位，所以复杂度不一定。并且升级后不能再降级。
3.5 skiplist
Redis的ZSET实现方式之一是跳跃表，另一种是ziplist。
跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。跳跃表是一种随机化的数据,跳跃表以有序的方式在层次化的链表中保存元素，效率和平衡树媲美 ——查找、删除、添加等操作都可以在对数期望时间下完成，并且比起平衡树来说，跳跃表的实现要简单直观得多。
跳跃表主要由链表和节点组成，下面是链表zskiplist的数据结构。
typedef struct zskiplist { struct zskiplistNode *header, *tail; unsigned long length; //最大节点成熟 int level; } zskiplist; 可以看到，和普通链表不同的是，多了一个level用来记录表中层数最大的节点的层数。
下面是节点的结构体：typedef struct zskiplistNode { // member robj *obj; // 分值 double score; // 后退指针 struct zskiplistNode *backward; // 层 struct zskiplistLevel { // 前进指针 struct zskiplistNode *forward; // 这个层跨越的节点数量 unsigned int span; } level[]; } zskiplistNode; 其中除了value和分数score外，还包含了一个level[]数组，这就是每个节点里的分层指针数组。
如图所示：
图片来自 其中每个节点的层数都是1到32的随机数，节点间是按照分值大小来进行排序。 3.6 ziplist
这是一种压缩列表，在LIST和HASH中使用，因为它保存在连续的内存空间中，所以比价节省内存空间，但在插入时每次都需要重新分配空间。
如图所示：
图片来自 其中，包含如下属性： - zlbytes:用于记录整个压缩列表占用的内存字节数
- zltail：记录要列表尾节点距离压缩列表的起始地址有多少字节
- zllen：记录了压缩列表包含的节点数量。
- entryX：要说列表包含的各个节点
- zlend：用于标记压缩列表的末端
3.7 Redis对象的实现
上面讲解了Reids实现中使用到的数据结构，其中Redis中的每个对象都不是由固定的数据结构实现，而是会根据数据类型大小选择不同的实现方式，以下为对应表。
| Redis对象 | 实现方式 |
|---|---|
| STRING | int 实现 |
| embstr编码的简单动态字符串（SDS）实现 | |
| SDS实现 | |
| LIST | ziplist压缩列表实现 |
| 链表实现 | |
| HASH | ziplist实现 |
| 字典hashtable实现 | |
| SET | intset整数集合实现 |
| hashtable实现 | |
| ZSET | ziplist实现 |
| 跳表skiplist、hashtable实现 |
总结
通过阅读《Redis设计与实现》前两章，对Redis的底层实现有了初步的了解。后续会继续研究Redis两种持久化方式和线程架构方面。
参考来源：
1. 《Redis设计与实现》 2. 《Redis实战》 3. 4. 5. 6.