原文地址： xilidou.com/2018/03/15/…
前两篇文章介绍了 Redis 的基本数据结构动态字符串，链表，字典，跳跃表，压缩链表，整数集合，但是使用过 Redis 的同学会发现，平时根本没有使用过这些数据结构。 平时使用的数据结构，包括字符串，列表，哈希，集合，还有有序集合。 其实 Redis 的实现是将底层的一种或者几种数据结构进行结合成我们使用的数据结构。
所以今天这篇文章就是要解释 Redis 是怎么实现符串，列表，哈希，集合，还有有序集合的。
对象
对于 Redis 来说使用了 redisObject 来对所有的对象进行了封装：
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
:
/* 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 （字符串）
Redis 的字符串 String，主要由 int、raw 和 emstr 底层数据实现的。 Redis 遵循以下的原则来决定使用底层数据结构的使用。
- 如果数据是可以用 long 表示的整数，那就直接使用将ptr 的类型设置为long。将RedisObject 的 encoding 设置为 REDIS_ENCODING_INT。
- 如果是一个字符串，那就需要考察字符串的字节数。如果字节数小于 39 就是使用 emstr，encoding 就使用 REDIS_ENCODING_EMBSTR，底层依然是我们之前介绍的 SDS 。
- 如果字符串的长度超过 39 那就使用 raw，encoding 就是 REDIS_ENCODING_RAW。
问题来了：
- 为什么是 39 个字符？
我们所String对象是由一个 RedisObject 和 sdshdr 组成的。所以我们如下公式在 在64位的系统中，一个 emstr 最大占用 64bite。
RedisObject(16b) + sds header(8b) + emstr + “\0”(1b) <= 64
简单的 四则运算 emstr <= 39。
- 一直都是 39 么？
在 3.2 的版本的时候，作者对 sdshdr 做了修改，从 39 改成了 44。为什么？
之前我们说过一个 sdshdr 包含三个参数，
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 对内存真是 “斤斤计较”
- SDS 是动态的为什么要区分 emstr 和 raw？
区别在于生产 raw 的时候，会有两步操作，分别产生 redisObject 和 sdshdr。而 emstr 一次成型，同时生成 redisObject 和 sdshdr 。就是为了高效。同时注意 emstr 是不可变的。
- 他们之间是什么关系？
如果不能用 long 表示的数据，double 也是使用 raw 或者 emstr 来保存的。 按照 Redis 的套路这三个底层数据在条件满足的是是会发生装换的。REDIS_ENCODING_INT 的数据如果不是整数了，那就会变成 raw 或者 emstr。emstr 发生了变化就会变成 raw。
REDIS_LIST 列表
Reids 的列表，底层是一个 ziplist 或者 linkedlist。
- 当列表对象保存的字符串元素的长度都小于64字节。
- 保存的元素数量小于512个。
两个条件都满足使用ziplist编码，两个条件任意一个不满足时，ziplist会变为linkedlist。
3.2 以后使用 quicklist 保存。这个数据结构之前没有讲解过。
实际上 quicklist 是 ziplist 和双向链表结合的产物。我们这样理解，每个双向链表的节点上是一个ziplist。之所以这么设计，应该是空间和时间之间的取舍或者一个折中的方案。 具体的实现我会在以后的文章里面具体分析。
REDIS_SET （集合）
Redis 的集合底层是一个 intset 或者 一个字典（hashtable）。
这个比较容易理解：
- 当集合都是整数且不超过512个的时候，就使用intset。
- 剩下都是用字典。
使用字典的时候，字典的每一个 key 就是集合的一个元素，对应的 value 就是一个 null。
