1 引言

Redis 作为基于内存的非关系型的 K-V 数据库。因读写响应快速、原子操作、提供了多种数据类型 String、List、Hash、Set、Sorted Set、在项目中有着广泛的使用,今天我们来探讨下下 Redis 的数据结构是如何实现的。

2 数据存储

2.1 RedisDB

Redis 将数据存储在 redisDb 中,默认 0~15 共 16 个 db。每个库都是独立的空间,不必担心 key 冲突问题,可通过 select 命令切换 db。集群模式使用 db0

typedef struct redisDb {
dict *dict; /* The keyspace for this DB */
dict *expires; /* Timeout of keys with a timeout set */
...
} redisDb;

2.2 Redis 哈希表实现

2.2.1 哈希字典 dict

K-V 存储我们最先想到的就是 map,在 Redis 中通过 dict 实现,数据结构如下:

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;

hash 数据存在两个特点:

针对 hash 数据的特点,存在 hash 碰撞的问题,dict 通过 dictType 中的函数能够解决这个问题

typedef struct dictType {
uint64_t (*hashFunction)(const void *key);
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
...
} dictType;

2.2.2 哈希表 dictht

dict.h/dictht 表示一个哈希表,具体结构如下:

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

键值对 dict.h/dictEntry

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

使用 hash 表就一定会存在 hash 碰撞的问题,hash 碰撞后在当前数组节点形成一个链表,在数据量超过 hash 表长度的情况下,就会存在大量节点称为链表,极端情况下时间复杂度会从 O(1) 变为 O(n);如果 hash 表的数据再不断减少,会造成空间浪费的情况。Redis 会针对这两种情况根据负载因子做扩展与收缩操作:

收缩操作:

Redis 在扩容时如果全量扩容会因为数据量问题导致客户端操作短时间内无法处理,所以采用渐进式 rehash 进行扩容,步骤如下:

  1. 同时持有 2 个哈希表
  2. 将 rehashidx 的值设置为 0,表示 rehash 工作正式开始
  3. 在 rehash 进行期间, 每次对字典执行添加、删除、查找或者更新操作时,程序除了执行指定的操作以外,还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] ,当 rehash 工作完成之后,程序将 rehashidx 属性的值增一
  4. 某个时间点上,ht[0] 的所有键值对都会被 rehash 至 ht[1] ,这时程序将 rehashidx 属性的值设为-1, 表示 rehash 操作已完成

在渐进式 rehash 进行期间,字典的删除(delete)、查找(find)、更新(update)等操作会在两个哈希表上进行;在字典里面查找一个键的话, 程序会先在 ht[0] 里面进行查找,如果没找到的话,就会继续到 ht[1] 里面进行查找;新添加到字典的键值对一律会被保存到 ht[1] 里面,而 ht[0] 则不再进行任何添加操作:这一措施保证了 ht[0] 包含的键值对数量会只减不增 (如果长时间不进行操作时,事件轮询进行这种操作),并随着 rehash 操作的执行而最终变成空表。

dict.h/redisObject

Typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS;
int refcount;
void *ptr;
}

完整结构图如下:

3 String 类型

3.1 String 类型使用场景

String 字符串存在有三种类型:字符串,整数,浮点。主要有以下使用场景

1)页面动态缓存

比如生成一个动态页面,首次可以将后台数据生成页面,并且存储到 redis 字符串中。再次访问,不再进行数据库请求,直接从 redis 中读取该页面。特点是:首次访问比较慢,后续访问快速。

2)数据缓存

在前后分离式开发中,有些数据虽然存储在数据库,但是更改特别少。比如有个全国地区表。当前端发起请求后,后台如果每次都从关系型数据库读取,会影响网站整体性能。

我们可以在第一次访问的时候,将所有地区信息存储到 redis 字符串中,再次请求,直接从数据库中读取地区的 json 字符串,返回给前端。

3)数据统计

redis 整型可以用来记录网站访问量,某个文件的下载量。(原子自增自减)

4)时间内限制请求次数

比如已登录用户请求短信验证码,验证码在 5 分钟内有效的场景。当用户首次请求了短信接口,将用户 id 存储到 redis 已经发送短信的字符串中,并且设置过期时间为 5 分钟。当该用户再次请求短信接口,发现已经存在该用户发送短信记录,则不再发送短信。

5)分布式 session

当我们用 nginx 做负载均衡的时候,如果我们每个从服务器上都各自存储自己的 session,那么当切换了服务器后,session 信息会由于不共享而会丢失,我们不得不考虑第三应用来存储 session。通过我们用关系型数据库或者 redis 等非关系型数据库。关系型数据库存储和读取性能远远无法跟 redis 等非关系型数据库。

3.2 String 类型的实现——SDS 结构

Redis 并没有直接使用 C 字符串实现 String 类型,在 Redis3.2 版本之前通过 SDS 实现

Typedef struct sdshdr {
int len;
int free;
char buf[];
};

3.3 SDS 与 C 字符串之间的区别

3.3.1 查询时间复杂度

C 获取字符串长度的复杂度为 O(N)。而 SDS 通过 len 记录长度,从 C 的 O(n) 变为 O(1)。

3.3.2 缓冲区溢出

C 字符串不记录自身长度容易造成缓冲区溢出(buffer overflow)。SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性,当需要对 SDS 进行修改时,会先检查 SDS 的空间是否满足修改所需的要求,如果不满足的话 SDS 的空间扩展至执行修改所需的大小,然后才执行实际的修改操作,所以使用 SDS 既不需要手动修改 SDS 的空间大小,也不会出现缓冲区溢出问题。

在 SDS 中,buf 数组的长度不一定就是字符数量加一,数组里面可以包含未使用的字节,而这些字节的数量就由 SDS 的 free 属性记录。通过未使用空间,SDS 实现了空间预分配和惰性空间释放两种优化策略:

3.3.3 二进制安全

C 字符串中的字符必须符合某种编码(比如 ASCII,并且除了字符串的末尾之外,字符串里面不能包含空字符, 否则最先被程序读入的空字符将被误认为是字符串结尾。

SDS 的 API 都是二进制安全的(binary-safe):都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据,程序不会对其中的数据做任何限制、过滤、或者假设 —— 数据在写入时是什么样的,它被读取时就是什么样。redis 不是用这个数组来保存字符,而是用它来保存一系列二进制数据。

3.4 SDS 结构优化

String 类型所存储的数据可能会几 byte 存在大量这种类型数据,但 len、free 属性的 int 类型会占用 4byte 共 8byte 存储,3.2 之后会根据字符串大小使用 sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64 数据结构存储,具体结构如下:

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[];
};

3.5 字符集编码

redisObject 包装存储的 value 值,通过字符集编码对数据存储进行优化,string 类型的编码方式有如下三种:

4 总结

redis 作为 k-v 数据存储,因查找和操作的时间复杂度都是 O(1) 和丰富的数据类型及数据结构的优化,了解了这些数据类型和结构更有利于我们平时对于 redis 的使用。下一期将对其它常用数据类型 List、Hash、Set、Sorted Set 所使用的 ZipList、QuickList、SkipList 做进一步介绍,对于文章中不清晰不准确的地方欢迎大家一起讨论交流。


作者:盛旭


↙↙↙阅读原文可查看相关链接,并与作者交流