乐趣区

关于redis:Redis数据结构一Redis的数据存储及String类型的实现

jiezi

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 做进一步介绍，对于文章中不清晰不精确的中央欢送大家一起探讨交换。

作者：盛旭

退出移动版