乐趣区

关于java:搞定-Redis-数据存储原理别只会-setget-了

我的外围模块如图 1-10。

图 1-10

  • Client 客户端,官网提供了 C 语言开发的客户端,能够发送命令,性能剖析和测试等。
  • 网络层事件驱动模型,基于 I/O 多路复用,封装了一个短小精悍的高性能 ae 库,全称是 a simple event-driven programming library。
  • 在 ae 这个库外面,我通过 aeApiState 构造体对 epoll、select、kqueue、evport 四种 I/O 多路复用的实现进行适配,让下层调用方感知不到在不同操作系统实现 I/O 多路复用的差别。
  • Redis 中的事件能够分两大类:一类是网络连接、读、写事件;另一类是工夫事件,也就是特定工夫触发的事件,比方定时执行 rehash 操作。
  • 命令解析和执行层,负责执行客户端的各种命令,比方 SET、DEL、GET 等。
  • 内存调配和回收,为数据分配内存,提供不同的数据结构保留数据。
  • 长久化层,提供了 RDB 内存快照文件 和 AOF 两种长久化策略,实现数据可靠性。
  • 高可用模块,提供了正本、哨兵、集群实现高可用。
  • 监控与统计,提供了一些监控工具和性能剖析工具,比方监控内存应用、基准测试、内存碎片、bigkey 统计、慢指令查问等。

把握了整体架构和模块后,接下来进入 src 源码目录,应用如下指令执行 redis-server 可执行程序启动 Redis。

./redis-server ../redis.conf

每个被启动的服务我都会形象成一个 redisServer,源码定在 server.h 的 redisServer 构造体。

这个构造体蕴含了存储键值对的数据库实例、redis.conf 文件门路、命令列表、加载的 Modules、网络监听、客户端列表、RDB AOF 加载信息、配置信息、RDB 长久化、主从复制、客户端缓存、数据结构压缩、pub/sub、Cluster、哨兵等一些列 Redis 实例运行的必要信息。

构造体字段很多,不再一一列举,局部外围字段如下。

truct redisServer {
    pid_t pid;  /* 主过程 pid. */
    pthread_t main_thread_id; /* 主线程 id */
    char *configfile;  /*redis.conf 文件绝对路径 */
    redisDb *db; /* 存储键值对数据的 redisDb 实例 */
   int dbnum;  /* DB 个数 */
    dict *commands; /* 以后实例能解决的命令表,key 是命令名,value 是执行命令的入口 */
    aeEventLoop *el;/* 事件循环解决 */
    int sentinel_mode;  /* true 则示意作为哨兵实例启动 */

   /* 网络相干 */
    int port;/* TCP 监听端口 */
    list *clients; /* 连贯以后实例的客户端列表 */
    list *clients_to_close; /* 待敞开的客户端列表 */

    client *current_client; /* 以后执行命令的客户端 */
};

1.2.1 数据存储原理

其中 redisDb *db 指针十分重要,它指向了一个长度为 dbnum(默认 16)的 redisDb 数组,它是整个存储的外围,我就是用这玩意来存储键值对。

redisDb

redisDb 构造体定义如下。

typedef struct redisDb {
    dict *dict; 
    dict *expires; 
    dict *blocking_keys;
    dict *ready_keys;
    dict *watched_keys; 
    int id;          
    long long avg_ttl; 
    unsigned long expires_cursor;
    list *defrag_later; 
    clusterSlotToKeyMapping *slots_to_keys;
} redisDb;

dict 和 expires

  • dict 和 expires 是最重要的两个属性,底层数据结构是字典,别离用于存储键值对数据和 key 的过期工夫。
  • expires,底层数据结构是 dict 字典,存储每个 key 的过期工夫。


MySQL:“为什么离开存储?”

好问题,之所以离开存储,是因为过期工夫并不是每个 key 都会设置,它不是键值对的固有属性,离开后尽管须要两次查找,然而能节俭内存开销。

blocking_keys 和 ready_keys

底层数据结构是 dict 字典,次要是用于实现 BLPOP 等阻塞命令。

当客户端应用 BLPOP 命令阻塞期待取出列表元素的时候,我会把 key 写到 blocking_keys 中,value 是被阻塞的客户端。

当下一次收到 PUSH 命令执时,我会先查看 blocking_keys 中是否存在阻塞期待的 key,如果存在就把 key 放到 ready_keys 中,在下一次 Redis 事件处理过程中,会遍历 ready_keys 数据,并从 blocking_keys 中取出阻塞的客户端响应。

watched_keys

用于实现 watch 命令,存储 watch 命令的 key。

id

Redis 数据库的惟一 ID,一个 Redis 服务反对多个数据库,默认 16 个。

avg_ttl

用于统计均匀过期工夫。

expires_cursor

统计过期事件循环执行的次数。

defrag_later

保留逐个进行碎片整顿的 key 列表。

slots_to_keys

仅用于 Cluster 模式,当应用 Cluster 模式的时候,只能有一个数据库 db 0。slots_to_keys 用于记录 cluster 模式下,存储 key 与哈希槽映射关系的数组。

dict

Redis 应用 dict 构造来保留所有的键值对(key-value)数据,这是一个散列表,所以 key 查问工夫复杂度是 O(1)。

所谓散列表,咱们能够类比 Java 中的 HashMap,其实就是一个数组,数组的每个元素叫做哈希桶。

dict 构造体源码在 dict.h 中定义。

struct dict {
    dictType *type;

    dictEntry **ht_table[2];
    unsigned long ht_used[2];

    long rehashidx;

    int16_t pauserehash;
    signed char ht_size_exp[2];
};

dict 的构造体里,有 dictType type,*ht_table[2],long rehashidx 三个很重要的构造。

  • type 存储了 hash 函数,key 和 value 的复制等函数;
  • ht_table[2],长度为 2 的数组,默认应用 ht_table[0] 存储键值对数据。我会应用 ht_table[1] 来配合实现渐进式 reahsh 操作。
  • rehashidx 是一个整数值,用于标记是否正在执行 rehash 操作,-1 示意没有进行 rehash。如果正在执行 rehash,那么其值示意以后 rehash 操作执行的 ht_table[1] 中的 dictEntry 数组的索引。
  • pauserehash 示意 rehash 的状态,大于 0 时示意 rehash 暂停了,小于 0 示意出错了。
  • ht_used[2],长度为 2 的数组,示意每个哈希桶存储了多少个 键值对实体(dictEntry),值越大,哈希抵触的概率越高。
  • ht_size_exp[2],每个散列表的大小,也就是哈希桶个数。

重点关注 ht_table 数组,数组每个地位叫做哈希桶,就是这玩意保留了所有键值对,每个哈希桶的类型是 dictEntry。


MySQL:“Redis 反对那么多的数据类型,哈希桶咋保留?”

他的玄机就在 dictEntry 中,每个 dict 有两个 ht_table,用于存储键值对数据和实现渐进式 rehash。

dictEntry 构造如下。

typedef struct dictEntry {
    void *key;
    union {
       // 指向理论 value 的指针
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    // 散列表抵触生成的链表
    struct dictEntry *next;
    void *metadata[];} dictEntry;
  • *key 指向键值对的键的指针,指向一个 sds 对象,key 都是 string 类型。
  • v 是键值对的 value 值,是个 union(联合体),当它的值是 uint64_t、int64_t 或 double 数字类型时,就不再须要额定的存储,这有利于缩小内存碎片。(为了节俭内存操碎了心)当值为非数字类型,就是用 val 指针存储。
  • *next 指向另一个 dictEntry 构造,多个 dictEntry 能够通过 next 指针串连成链表,从这里能够看出,ht_table 应用链地址法来解决键碰撞:当多个不同的键领有雷同的哈希值时,哈希表用一个链表将这些键连接起来。

哈希桶并没有保留值自身,而是指向具体值的指针,从而实现了哈希桶能存不同数据类型的需要

redisObject

dictEntry 的 *val 指针指向的值实际上是一个 redisObject 构造体,这是一个十分重要的构造体。

我的 key 只能是字符串类型,而 value 能够是 String、Lists、Set、Sorted Set、散列表等数据类型。

键值对的值都被包装成 redisObject 对象,redisObject 在 server.h 中定义。

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS;
    int refcount;
    void *ptr;
} robj;
  • type:记录了对象的类型,string、set、hash、Lis、Sorted Set 等,依据该类型来确定是哪种数据类型,应用什么样的 API 操作。
  • encoding:编码方式,示意 ptr 指向的数据类型具体数据结构,即这个对象应用了什么数据结构作为底层实现 保留数据。同一个对象应用不同编码实现内存占用存在显著差别,外部编码对内存优化十分重要。
  • lru:LRU_BITS:LRU 策略下对象最初一次被拜访的工夫,如果是 LFU 策略,那么低 8 位示意拜访频率,高 16 位示意拜访工夫。
  • refcount:示意援用计数,因为 C 语言并不具备内存回收性能,所以 Redis 在本人的对象零碎中增加了这个属性,当一个对象的援用计数为 0 时,则示意该对象曾经不被任何对象援用,则能够进行垃圾回收了。
  • ptr 指针 :指向对象的底层实现数据结构,指向 值的指针

如图 1-11 是由 redisDb、dict、dictEntry、redisObejct 关系图:

图 1 -11

留神,一开始的时候,我只应用 ht_table[0] 这个散列表读写数据,ht_table[1] 指向 NULL,当这个散列表容量有余,触发扩容操作,这时候就会创立一个更大的散列表 ht_table[1]。

接着我会应用渐进式 rehash 的形式将 ht_table[0] 的数据迁徙到 ht_table[1] 上,全副迁徙实现后,再批改下指针,让 ht_table[0] 指向扩容后的散列表,回收掉原来的散列表,ht_table[1] 再次指向 NULL。

退出移动版