Redis数据结构(一)-Redis的数据存储及String类型的实现

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;

• dict：数据库键空间，保存着数据库中的所有键值对
• expires：键的过期时间，字典的键为键，字典的值为过期事件UNIX时间戳

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;

• type：类型特定函数是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定函数。
• privdata：私有数据保存了需要传给那些类型特定函数的可选参数
• ht[2]：哈希表一个包含两个项的数组，数组中的每个项都是一个dictht哈希表，一般情况下，字典只使用ht[0] 哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用
• rehashidx：rehash 索引，当rehash不在进行时，值为 -1

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;

• hashFunction：用于计算key的hash值的方法
• keyCompare：key的值比较方法

2.2.2 哈希表 dictht

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

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

• table：数组指针，数组中的每个元素都是一个指向dict.h/dictEntry结构的指针，每个dictEntry结构保存着一个键值对。
• size：记录了哈希表的大小，也就是table数组的大小，大小总是2^n
• sizemask：总是等于size - 1，这个属性和哈希值一起决定一个键应该被放到table数组的哪个索引上面。
• used：记录了哈希表目前已有节点（键值对）的数量。

键值对dict.h/dictEntry

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

• key：保存着键值对中的键(SDS类型对象)
• val：保存着键值对中的值，可以是一个uint64_t整数，或者是一个int64_t整数，又或者是一个指针指向一个被redisObject包装的值
• next：指向下个哈希表节点，形成链表指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一次，以此来解决键冲突（collision）的问题

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

• 负载因子：哈希表已保存节点数量/哈希表大小，load_factor = ht[0].used/ht[0].size
• 扩展操作：
• 服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于 1；
• 服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5；

收缩操作：

• 当哈希表的负载因子小于 0.1 时， 程序自动开始对哈希表执行收缩操作。

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

• type:4：约束客户端操作时存储的数据类型，已存在的数据无法修改类型，4bit
• encoding:4：值在redis底层的编码模式，4bit
• lru:LRU_BITS：内存淘汰策略
• refcount：通过引用计数法管理内存，4byte
• ptr：指向真实存储值的地址，8byte

完整结构图如下：

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

• len：分配内存空间
• free：剩余可用分配空间
• char[]：value值实际数据

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实现了空间预分配和惰性空间释放两种优化策略：

• 空间预分配：当对一个SDS进行修改，并且需要对SDS进行空间扩展的时候，程序不仅会为SDS分配修改所必须要的空间，还会为SDS分配额外的未使用空间。扩展SDS 空间之前，会先检查未使用空间是否足够， 如果足够的话，就会直接使用未使用空间，而无须执行内存重分配。如果不够根据(len + addlen(新增字节)) * 2的方式进行扩容，大于1M时，每次只会增加1M大小。通过这种预分配策略，SDS将连续增长N次字符串所需的内存重分配次数从必定N次降低为最多N次。
• 惰性空间释放：惰性空间释放用于优化SDS的字符串缩短操作：当需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，并等待将来使用。

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

• unsign char flags：3bit表示类型，5bit表示未使用长度
• len：表示已使用长度
• alloc：表示分配空间大小，剩余空间大小可以使用alloc - len获得

3.5 字符集编码

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

• embstr:
  CPU每次按Cache Line 64byte读取数据，一个redisObject对象为16byte，为填充64byte大小，会向后再读取48 byte数据。但获取实际数据时还需要再通过*ptr指针读取对应内存地址的数据。而一个sdshdr8属性的信息占用4byte，其余44byte可以用来存储数据。如果value值小于44，byte可以通过一次读取缓存行获取数据。
  
• int:
  如果SDS小于20位，并且能够转换成整型数字，redisObject的*ptr指针会直接进行存储。
  
• raw:
  SDS
  

4 总结

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

作者：盛旭