分类 redis 下的文章

原文:https://juejin.im/post/5c15048bf265da61223a3c29

本文主要关于:

  1. redis数据库实现的介绍
  2. 前面介绍的各种数据,在redis服务器中的内存模型是什么样的的。
  3. RDB文件将这些内存数据持久化后的格式是什么样的
  4. RDB和AOF序列化的区别是什么
  5. redis提供什么机制保障AOF文件不会一直增长
  6. RDB文件转储成json文件和内存分析工具介绍
  7. 客户端和服务端数据结构介绍

数据库

服务器的数据库

  • redis是内存型数据库,所有数据都放在内存中
  • 保存这些数据的是redisServer这个结构体,源码中该结构体包括大概300多行的代码。具体参考server.h/redisServer
  • 和数据库相关的两个属性是:

    • int类型的dbnum:表示数据库数量,默认16个
    • redisDb指针类型的db:数据库对象数组

167b228be8fb2489.webp

数据库对象

所在文件为server.h。数据库中所有针对键值对的增删改查,都是对dict做操作

typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB  */
    dict *expires;              /* Timeout of keys with a timeout set */
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP)*/
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    int id;                     /* Database ID */
    long long avg_ttl;          /* Average TTL, just for stats */
} redisDb;
  • dict:保存了该数据库中所有的键值对,键都是字符串,值可以是多种类型
  • expires:保存了该数据中所有设置了过期时间的key
  • blocking_keys:保存了客户端阻塞的
  • watched_keys:保存被watch的命令
  • id:保存数据库索引
  • avg_ttl

客户端切换数据库

  • 客户端通过select dbnum 命令切换选中的数据库
  • 客户端的信息保存在client这个数据结构中,参考server.h/client
  • client的类型为redisDb的db指针指向目前所选择的数据库

读写键空间时的其他操作

读写键空间时,是针对dict做操作,但是除了完成基本的增改查找操作,还会执行一些额外的维护操作,包括:

  • 读写键时,会根据是否命中,更新hit和miss次数。

    相关命令:info stats keyspace_hits, info stats keyspace_misses
  • 读取键后,会更新键的LRU时间,前面章节介绍过该字段
  • 读取时,如果发现键已经过期,会先删除该键,然后才执行其他操作
  • 如果watch监视了某个键,修改时会标记该键为脏(dirty)
  • 每修改一个键,会对脏键计数器加1,触发持久化和复制操作
  • 如果开启通知功能,修改键会下发通知

设置过期时间

  • expire key ttl:设置生存时间为ttl秒
  • pexpire key ttl:设置生存时间为ttl毫秒
  • expireat key timestamp:设置过期时间为timstamp的秒数时间戳
  • pexpireat key timestamp:过期时间为毫秒时间戳
  • persist key:解除过期时间
  • ttl key:获取剩余生存时间

167b25c77c3dd2a7.webp

保存过期时间

过期时间保存在expires的字典中,值为long类型的毫秒时间戳

过期键删除策略

各种删除策略的对比

策略类型描述优点缺点redis是否采用
定时删除通过定时器实现保证过期键能尽快释放对cpu不友好,影响相应时间和吞吐量
惰性删除放任不管,查询时才去检查对cpu友好没有被访问的永远不会被释放,相当于内存泄露
定期删除每隔一段时间检查综合前面的优点难于确定执行时长和频率

redis使用的过期键删除策略

redis采用了惰性删除和定期删除策略

  • 惰性删除的实现

    • 由db.c中的expireIfNeeded实现
    • 每次执行redis命令前都会调用该函数对输入键做检查
  • 定期删除的实现

    • server.c中的serverCron函数执行定时任务
    • 函数每次运行时,都从一定数量的数据库中取出一定数量的键进行检查,并删除过期键

数据库通知

  • 键空间通知:客户端获取数据库中键执行了什么命令。实现代码为notify.c文件的notifyKeyspaceEvent函数

    subscribe __keyspace@0__:keyname

  • 键事件通知:某个命令被什么键执行了

    subscribe __keyevent@0__:del

RDB持久化

  • redis是内存数据库,为了避免服务器进程异常导致数据丢失,redis提供了RDB持久化功能
  • 持久化后的RDB文件是一个经过压缩的二进制文件

RDB文件的创建与载入

  • 生成rdb文件的两个命令如下,实现函数为rdb.c文件的rdbSave函数:
  • SAVE:阻塞redis服务器进程,知道RDB创建完成。阻塞期间不能处理其他请求
  • BGSAVE:派生出子进程,子进程负责创建RDB文件,父进程继续处理请求

RDB文件的载入是在服务器启动时自动执行的,实现函数为rdb.c文件的rdbload函数。载入期间服务器一直处于阻塞状态

自动间隔保存

redis允许用户通过设置服务器配置的server选项,让服务器每隔一段时间(100ms)自动执行BGSAVE命令(serverCron函数)

//server.c中main函数内部创建定时器,serverCron为定时任务回调函数
if (aeCreateTimeEvent(server.el, 1, serverCron, NULL, NULL) == AE_ERR) {
    serverPanic("Can't create event loop timers.");
    exit(1);
}

配置参数

// 任意一个配置满足即执行
save 900 1 // 900s内,对服务器进行至少1次修改
save 300 10 // 300s内,对服务器至少修改10次

数据结构

// 服务器全局变量,前面介绍过
struct redisServer {
    ...
     /* RDB persistence */
    // 上一次执行save或bgsave后,对数据库进行了多少次修改
    long long dirty;                /* Changes to DB from the last save */
    long long dirty_before_bgsave;  /* Used to restore dirty on failed BGSAVE */
    pid_t rdb_child_pid;            /* PID of RDB saving child */
    struct saveparam *saveparams;   /* Save points array for RDB */
    int saveparamslen;              /* Number of saving points */
    char *rdb_filename;             /* Name of RDB file */
    int rdb_compression;            /* Use compression in RDB? */
    int rdb_checksum;               /* Use RDB checksum? */
    // 上一次成功执行save或bgsave的时间
    time_t lastsave;                /* Unix time of last successful save */
    time_t lastbgsave_try;          /* Unix time of last attempted bgsave */
    time_t rdb_save_time_last;      /* Time used by last RDB save run. */
    time_t rdb_save_time_start;     /* Current RDB save start time. */
    int rdb_bgsave_scheduled;       /* BGSAVE when possible if true. */
    int rdb_child_type;             /* Type of save by active child. */
    int lastbgsave_status;          /* C_OK or C_ERR */
    int stop_writes_on_bgsave_err;  /* Don't allow writes if can't BGSAVE */
    int rdb_pipe_write_result_to_parent; /* RDB pipes used to return the state */
    int rdb_pipe_read_result_from_child; /* of each slave in diskless SYNC. */
    ...
};
// 具体每一个参数对应的变量
struct saveparam {
    time_t seconds;
    int changes;
};

RDB文件结构

概览

167b667623041d7a.webp

  • 头五个字符为‘redis’常量,标识这个rdb文件是redis文件
  • dv_version:4字节,标识了rdb文件的版本号
  • databases:数据库文件内容
  • EOF:常量,1字节,标识文件正文结束
  • check_sum:8字节无符号整形,保存校验和,判定文件是否有损坏

dababases部分

167b66e96f4868d5.webp

每个database的内容:
167b66eeaad11736.webp

  • SELECTDB:常量,1字节。标识了后面的字节为数据库号码
  • db_number:数据库号码
  • key_value_pairs:数据库的键值对,如果有过期时间,也放在一起。

key_value_pairs部分

不带过期时间的键值对

type为value的类型,1字节,代表对象类型或底层编码,根据type决定如何读取value

167b672b832eca0a.webp

带过期时间的键值对

167b67471e295f85.webp

  • EXPIRETIME:常量,1字节,表示接下来要读入的是一个以毫秒为单位的过期时间
  • ms:8字节长的无符号整形,过期时间

value的编码

每个value保存一个值对象,与type对应。type不同,value的结构,长度也有所不同

字符串对象

  • type为REDIS_RDB_TYPE_STRING, value为字符串对象,而字符串对象本身又包含对象的编码和内容
  • 如果编码为整数类型,编码后面直接保存整数值

167ba47e2a4fde38.webp

  • 如果编码为字符串类型,分为压缩和不压缩

    • 如果字符串长度<=20字节,不压缩
      167ba485396f9e14.webp
    • 如果字符串长度>20字节,压缩保存
      167baa11aaf82b0a.webp

      • REDIS_RDB_ENC_LZF:常量,标识字符串被lzf算法压缩过
      • compressed_len:被压缩后的长度
      • origin_len:字符串原始长度
      • compressed_string:压缩后的内容

列表对象

  • type为REDIS_RDB_TYPE_LIST, value为列表对象
    167baa63aa0658ed.webp
  • set_size: 集合大小
  • elem:以字符串对象来处理

哈希对象

  • type为REDIS_RDB_TYPE_HASH, value为哈希对象
    167baa99c173b8b0.webp
  • hash_size:哈希对象大小
  • key-value都以字符串对象处理

有序集合对象

  • type为REDIS_RDB_TYPE_ZSET,value为有序集合对象

167baab37f85ab98.webp

intset编码集合

  • type为REDIS_RDB_TYPE_SET_INTSET, value为整数集合对象
  • 先将结合转换为字符串对象,然后保存。读入时,将字符串对象转为整数集合对象

ziplist编码的对象(包括列表,哈希,有序集合)

  • type为REDIS_RDB_TYPE_LIST_ZIPLIST, REDIS_RDB_TYPE_HASH_ZIPLIST, REDIS_RDB_TYPE_ZSET_ZIPLIST
  • 先将压缩列表转换为字符串对象,保存到rdb文件
  • 读取时根据type类型,读入字符串,转换为压缩列表对象

分析RDB文件

使用linux自带的od命令

使用linux自带的od命令可以查看rdb文件信息,比如od -c dump.rdb,以Ascii打印,下图显示docker创建的redis中,空的rdb文件输出的内容

167b9f284c484998.webp

工具

AOF持久化

AOF写入与同步

除了RDB持久化外,redis还提供了AOF持久化功能。区别如下:

  • RDB通过保存数据库中键值对记录数据库状态
  • AOF通过保存服务器执行的写命令来记录数据库状态

AOF持久化分为三步:

  1. 命令追加:命令append到redisServer全局变量的aof_buf成员中
  2. 文件写入
  3. 文件同步

事件结束时调用flushAppendOnlyFile函数,考虑是否将aof_buf内容写到AOF文件里(参数决定)

  • always:所有内容写入并同步到AOF文件(写入的是缓冲区,同步时从缓冲区刷到磁盘)
  • everysec:默认值。写入AOF文件,如果上次同步时间距现在草稿1s,同步AOF。
  • no:只写入AOF文件,由系统决定何时同步

AOF载入与还原

服务器只需要读入并执行一遍AOF命令即可还原数据库状态,读取的步骤如下:

  • 创建一个不带网络连接的伪客户端:因为命令只能在客户端执行
  • 从AOF读取一条写命令
  • 使用客户端执行该命令
  • 重复上面的步骤,直到完成

AOF重写

  • 随着时间流逝,AOF文件内容会越来越大,影响redis性能。redis提供重写功能解决该问题。
  • 重写是通过读取redis当前数据状态完成的,而不是解析AOF文件
  • 为了不影响redis正常响应,重写功能通过创建子进程(注意不是线程)完成
  • 为了解决父子进程数据不一致问题(父进程接收新的请求),redis设置了AOF重写缓冲区。新的命令在AOF缓冲区和AOF重写缓冲区中双写。

事件

redis是一个事件驱动程序,事件包括两大类:

  • 文件事件:socket通讯完成一系列操作
  • 时间事件:某些需要在给定时间执行的操作

文件事件

  • redis基于Reactor模式开发事件处理器,使用IO多路复用监听套接字。关于IO多路复用可参考之前的文章五种io模型对比,虽然事件处理器以单线程运行,通过io多路复用,能同时监听多个套接字实现高性能

事件处理器的构成

167bbec17e25c5e7.webp

  • 文件事件:套接字操作的抽象
  • io多路复用程序:同时监听多个套接字,并向事件分派器传送事件。多个套接字按队列排序
  • 文件事件分派器:接收套接字,根据事件类型调用相应的事件处理器
  • 事件处理器:不同的函数实现不同的事件

IO多路复用的实现

可选的io多路复用包括select,epoll,evport,kqueue实现。每种实现都放在单独的文件中。编译时根据不同的宏切换不同的实现
167bbf2f2b42de50.webp

事件类型

#define AE_NONE 0       /* No events registered. */
#define AE_READABLE 1   /* Fire when descriptor is readable. */
#define AE_WRITABLE 2   /* Fire when descriptor is writable. */

处理器

redis为文件事件编写了多个处理器,分别用于实现不同的网络需求,在networking.c文件中,包括:

  • 连接应答处理器:监听套接字,接收客户端命令请求。对应函数为acceptTcpHandler。内部调用socket编程的accpt函数
  • 命令请求处理器:负责读入套接字中的命令请求内容。对应函数为readQueryFromClient。内部调用socket编程的read函数
  • 命令回复处理器:负责将回复通过套接字返回给客户。对应函数为sendReplyToClient。内部调用socket班车的write函数

时间事件

分类

时间事件分类以下两大类,取决于时间处理器的返回值:

  • 定时事件:返回AE_NOMORE(-1)
  • 周期性事件:非AE_NOMORE值。单机版只有serverCron一个周期性事件

属性

时间事件包括三个属性:

  • id:服务器创建的全局唯一标识
  • when:事件到达时间
  • timeProc:处理器,一个函数

实现

  • 所有时间事件放在一个无序链表中
    167bc1026e0f71bf.webp
  • 执行时需要遍历链表
  • ae.c/aeCreateTimeEvent:创建时间处理器
  • aeSearchNearestTimer:返回距离当前时间最近的时间事件
  • ae.c/processTimeEvents:遍历时间处理器并执行

事件调度

  • 事件调度和执行由ae.c/aeProcessEvents函数负责
  • 该函数被放在ae.c/aeMain函数中的一段循环里面,不断执行直到服务器关闭
  • aeMain被server.c的main函数调用

    int main() {

    ...
    aeMain(server.el);
    ...

    }
    void aeMain(aeEventLoop *eventLoop) {

    eventLoop->stop = 0;
    while (!eventLoop->stop) {
        if (eventLoop->beforesleep != NULL)
            eventLoop->beforesleep(eventLoop);
        aeProcessEvents(eventLoop, AE_ALL_EVENTS|AE_CALL_AFTER_SLEEP);
    }

    }

客户端

redis服务器为每个连接的客户端建立了一个redisClient的结构,保存客户端状态信息。所有客户端的信息放在一个链表里。可通过client list命令查看

struct redisServer {
    ...
    list *clients;
    ...
}

客户端数据结构如下:

typedef struct client {
    uint64_t id;            /* Client incremental unique ID. */
    //客户端套接字描述符,伪客户端该值为-1(包括AOF还原和执行Lua脚本的命令)
    int fd;                 /* Client socket. */
    redisDb *db;            /* Pointer to currently SELECTed DB. */
    // 客户端名字,默认为空,可通过client setname设置
    robj *name;             /* As set by CLIENT SETNAME. */
    // 输入缓冲区,保存客户端发送的命令请求,不能超过1G
    sds querybuf;           /* Buffer we use to accumulate client queries. */
    size_t qb_pos;          /* The position we have read in querybuf. */
    sds pending_querybuf;   /* If this client is flagged as master, this buffer
                               represents the yet not applied portion of the
                               replication stream that we are receiving from
                               the master. */
    size_t querybuf_peak;   /* Recent (100ms or more) peak of querybuf size. */
    // 解析querybuf,得到参数个数
    int argc;               /* Num of arguments of current command. */
    // 解析querybuf,得到参数值
    robj **argv;            /* Arguments of current command. */
    // 根据前面的argv[0], 找到这个命令对应的处理函数
    struct redisCommand *cmd, *lastcmd;  /* Last command executed. */
    int reqtype;            /* Request protocol type: PROTO_REQ_* */
    int multibulklen;       /* Number of multi bulk arguments left to read. */
    long bulklen;           /* Length of bulk argument in multi bulk request. */
    // 服务器返回给客户端的可被空间,固定buff用完时才会使用
    list *reply;            /* List of reply objects to send to the client. */
    unsigned long long reply_bytes; /* Tot bytes of objects in reply list. */
    size_t sentlen;         /* Amount of bytes already sent in the current
                               buffer or object being sent. */
    // 客户端的创建时间
    time_t ctime;           /* Client creation time. */
    // 客户端与服务器最后一次互动的时间
    time_t lastinteraction; /* Time of the last interaction, used for timeout */
    // 客户端空转时间
    time_t obuf_soft_limit_reached_time;
    // 客户端角色和状态:REDIS_MASTER, REDIS_SLAVE, REDIS_LUA_CLIENT等
    int flags;              /* Client flags: CLIENT_* macros. */
    // 客户端是否通过身份验证的标识
    int authenticated;      /* When requirepass is non-NULL. */
    int replstate;          /* Replication state if this is a slave. */
    int repl_put_online_on_ack; /* Install slave write handler on ACK. */
    int repldbfd;           /* Replication DB file descriptor. */
    off_t repldboff;        /* Replication DB file offset. */
    off_t repldbsize;       /* Replication DB file size. */
    sds replpreamble;       /* Replication DB preamble. */
    long long read_reploff; /* Read replication offset if this is a master. */
    long long reploff;      /* Applied replication offset if this is a master. */
    long long repl_ack_off; /* Replication ack offset, if this is a slave. */
    long long repl_ack_time;/* Replication ack time, if this is a slave. */
    long long psync_initial_offset; /* FULLRESYNC reply offset other slaves
                                       copying this slave output buffer
                                       should use. */
    char replid[CONFIG_RUN_ID_SIZE+1]; /* Master replication ID (if master). */
    int slave_listening_port; /* As configured with: SLAVECONF listening-port */
    char slave_ip[NET_IP_STR_LEN]; /* Optionally given by REPLCONF ip-address */
    int slave_capa;         /* Slave capabilities: SLAVE_CAPA_* bitwise OR. */
    multiState mstate;      /* MULTI/EXEC state */
    int btype;              /* Type of blocking op if CLIENT_BLOCKED. */
    blockingState bpop;     /* blocking state */
    long long woff;         /* Last write global replication offset. */
    list *watched_keys;     /* Keys WATCHED for MULTI/EXEC CAS */
    dict *pubsub_channels;  /* channels a client is interested in (SUBSCRIBE) */
    list *pubsub_patterns;  /* patterns a client is interested in (SUBSCRIBE) */
    sds peerid;             /* Cached peer ID. */
    listNode *client_list_node; /* list node in client list */

    /* Response buffer */
    // 记录buf数组目前使用的字节数
    int bufpos;
    // (16*1024)=16k,服务器返回给客户端的内容缓冲区。固定大小,存储一下固定返回值(如‘ok’)
    char buf[PROTO_REPLY_CHUNK_BYTES];
} client;

服务器

服务器记录了redis服务器所有的信息,包括前面介绍的一些,罗列主要的如下:

struct redisServer {
    ...
    // 所有数据信息
    redisDb *db;
    // 所有客户端信息
    list *clients;
    
     /* time cache */
    // 系统当前unix时间戳,秒
    time_t unixtime;    /* Unix time sampled every cron cycle. */
    time_t timezone;    /* Cached timezone. As set by tzset(). */
    int daylight_active;    /* Currently in daylight saving time. */
    // 系统当前unix时间戳,毫秒
    long long mstime;   /* Like 'unixtime' but with milliseconds resolution. */
    
    // 默认没10s更新一次的时钟缓存,用于计算键idle时长
    unsigned int lruclock;      /* Clock for LRU eviction */
    
    // 抽样相关的参数
    struct {
        // 上次抽样时间
        long long last_sample_time; /* Timestamp of last sample in ms */
        // 上次抽样时,服务器已经执行的命令数
        long long last_sample_count;/* Count in last sample */
        // 抽样结果
        long long samples[STATS_METRIC_SAMPLES];
        int idx;
    } inst_metric[STATS_METRIC_COUNT];
    
    // 内存峰值
    size_t stat_peak_memory;        /* Max used memory record */
    // 关闭服务器的标识
    int shutdown_asap;          /* SHUTDOWN needed ASAP */
    // bgsave命令子进程的id
    pid_t rdb_child_pid;            /* PID of RDB saving child */
    // bgrewriteaof子进程id
    pid_t aof_child_pid;            /* PID if rewriting process */
    // serverCron执行次数
    int cronloops;              /* Number of times the cron function run */
    ...
}

原文:https://juejin.im/post/5bc672296fb9a05cee1e11f2

前言

  • redis性能为什么这么出色?它与其他缓存中间件有什么区别?
  • redis底层使用了哪些数据结构支撑它如此高效的性能?
  • 内部丰富的数据类型底层为什么都使用至少两种数据结构实现?分别是什么?
  • 如果合理的使用redis才能发挥它最大的优势?

概述

特点

  • c语言开发,性能出色,纯内存操作,每秒可处理超过10w读写(QPS)
  • 多种数据结构,单个最大限制可到1GB(memcached只支持字符串,最大1M)
  • 受物理内存限制,不能作海量数据的读写。适用于较小数据量的高性能操作和运算上
  • 支持事务,持久化
  • 单线程模型(memcached是多线程)

支持的数据类型

  1. Sring
  2. List
  3. Set
  4. SortedSet
  5. hash
  6. Bitmap
  7. Hyperloglogs
  8. Geo
  9. pub/sub

redis为什么这么快

  1. 纯内存操作,没有磁盘io
  2. 单线程处理请求,没有线程切换开销和竞争条件,也不存在加锁问题
  3. 多路复用模型epoll,非阻塞io(多路:多个网络连接;复用:复用同一个线程)
  4. 多路复用技术可以让单个线程高效的处理多个连接请求
  5. 数据结构简单,对数据操作也简单。还做了自己的数据结构优化

redis为什么是单线程的

  1. 单线程已经很快了,减少多线程带来的网络开销,锁操作
  2. 后续的4.0版本在考虑多线程
  3. 单线程是指处理网络请求的时候只有一个线程,并不是redis-server只有一个线程在工作。持久化的时候,就是通过fork一个子线程来执行。
  • 缺点:耗时的命令会导致并发的下降,比如keys *

redis的回收策略

  1. volatile-lru:从过期的数据集 server.db[i].expires中挑选最近最少使用的数据
  2. volatile-ttl:从过期的数据集 server.db[i].expires中挑选将要过期的数据淘汰
  3. volatile-random: server.db[i].expires中挑选任意数据淘汰
  4. allkeys-lru: 从数据集(server.db[i].dict)中挑选最近最少使用的数据淘汰
  5. allkeys-random:从数据集(server.db[i].dict)中任意选择数据淘汰
  6. no-enviction(驱逐):禁止驱逐数据

使用注意

  1. redis单线程无法发挥多核cpu性能,可以通过单机开多个redis实例来完善
  2. redis实现分布式锁:先用setnx(如果不存在才设置)争抢锁,抢到后,expire设置过期时间,防止忘记释放。
  3. redis实现一对多消息订阅:sub/pub数据结构
  4. redis实现延时消息队列:zadd时间戳作为score 消费的时候根据时间戳+延时时间做查询操作。

各大版本介绍

redis5版本新增功能:

  • zpopmax zpopmin以及阻塞变种:返回集合中给定分值最大最小的数据数量

reids4版本新增功能:

  • 模块功能,提供类似于插件的方式,自己开发一个.so模块,并加装作者本人提供了一个神经网络的module。
    可到redis-modules-hub上查看更多的module模块功能使得用户可以将 Redis 用作基础设施, 并在上面构建更多功能, 这给 Redis 带来了无数新的可能性。
  • PSYNC:解决了旧版本的 Redis 在复制时的一些不够优化的地方
  • 缓存清理策略优化
  • 新增last frequently used
  • 对已有策略进行优化
  • 非阻塞DEL FLUSHDB FLUSHALL
  • 解决了之前执行这些命令的时候导致阻塞的问题 Flushdb async, flushall async, unlink(替代del)
  • 添加了swapdb:交换数据库
  • 混合RDB-AOF的持久化格式
  • 添加内存使用情况命令:MEMORY

数据结构

  • redis里面每个键值对都是由对象组成的
  • 键总是一个字符串对象,
  • 值则可以是以下对象的一种:

    • 字符串对象
    • 列表对象
    • 哈希对象
    • 集合对象
    • 有序结合对象

简单动态字符串SDS

数据结构

struct sdshdr {
    uint8_t len; /* used,使用的字节数 */
    uint8_t alloc; /* excluding the header and null terminator,预分配总字节数,不包括结束符\0的长度 */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[]; /*c风格的字符,包括结束符\0*/
};
  • 位于sds.h文件
  • SDS遵循C字符串以0结尾的惯例,存储在buf中(不同于nginx的底层实现,nginx实现时不保存最后一个0)
  • 但是不计算最后一个字符的长度到len中
  • 保留c风格buf的好处是可以重用一部分c函数库的函数

167abed91fcbe05f.webp

分配和释放策略

空间预分配

  • 用于优化SDS字符串增长操作,以减少连续执行增长操作所需的内存重分配次数
  • 扩展SDS空间时,先检查未使用的空间是否足够,如果足够直接使用,如果不够,不仅分配够用,还预分配一些空间
  • 预分配策略:

    • 修改后的SDS长度(len的值)< 1MB,预分配同样len大小的空间
    • 修改后的SDS长度(len的值)>= 1MB,预分配1MB大小的空间
  • 惰性空间释放

    • 用于优化SDS字符缩短操作
    • 缩短SDS空间时,并不立即进行内存重分配释放空间,而是记录free的字节数
    • SDS提供相应api,有需要时真正释放空间

比C字符串的优势

  • 获取字符串的长度时间复杂度由O(N)降到O(1)
  • 避免缓冲区溢出
  • 减少修改字符串时带来的内存重分配次数。内存分配会涉及复杂算法,且可能需要系统调用,非常耗时。
  • 二进制安全:c语言的结束符限制了它只能保存文本数据,不能保存图片,音频等二进制数据

链表

数据结构

位于adlist.h文件

typedef struct listNode {
    struct listNode *prev; // 前置节点
    struct listNode *next; // 后置节点
    void *value;//节点值
} listNode;

typedef struct list {
    listNode *head; // 表头节点
    listNode *tail; // 表尾节点
    void *(*dup)(void *ptr); // 节点值复制函数
    void (*free)(void *ptr); // 节点值释放函数
    int (*match)(void *ptr, void *key); // 节点值对比函数
    unsigned long len; // 节点数量
} list;

特点

  • 双端队列,可以获取某个节点前置节点和后置节点,复杂度为O(1)
  • 无环
  • 获取表头和表尾复杂度为O(1)
  • 带长度,获取链表长度复杂度为O(1)
  • 多态:使用void*保存节点值,可保存不同类型的值

167abee9fcb2654c.webp

字典

数据结构

位于dict.h文件

哈希表

// 哈希表
typedef struct dictht {
    dictEntry **table; // 一个数组,数组中每个元素都是指向dictEntry结构的指针
    unsigned long size; // table数组的大小
    unsigned long sizemask; // 值总数size-1
    unsigned long used; // 哈希表目前已有节点(键值对)的数量
} dictht;

哈希节点

// 每个dictEntry都保存着一个键值对,表示哈希表节点
typedef struct dictEntry {
    void *key; // 键值对的键
    // 键值对的值,可以是指针,整形,浮点型
    union { 
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; // 哈希表节点指针,用于解决键冲突问题
} dictEntry;

167abef0d744699f.webp

字典类型

每个字典类型保存一簇用于操作特定类型键值对的函数

typedef struct dictType {
    // 计算哈希值的函数
    uint64_t (*hashFunction)(const void *key);
    // 复制键的函数
    void *(*keyDup)(void *privdata, const void *key);
    // 复制值的函数
    void *(*valDup)(void *privdata, const void *obj);
    // 对比键的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);  
    // 销毁键的函数
    void (*keyDestructor)(void *privdata, void *key);
    // 销毁值的函数
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

字典


// 字典
typedef struct dict {
    dictType *type; // 不同键值对类型对应的操作函数
    void *privdata; // 需要传递给对应函数的参数
    dictht ht[2]; // ht[0]用于存放数据,ht[1]在进行rehash时使用
    long rehashidx; /* rehashing not in progress if rehashidx == -1,目前rehash的进度*/
    unsigned long iterators; /* number of iterators currently running */
} dict;

哈希算法

  • redis使用MurmurHash2算法计算键的hash值
  • 哈希值与sizemask取或,得到哈希索引
  • 哈希冲突(两个或以上数量键被分配到哈希表数组同一个索引上):链地址法解决冲突

rehash

  • 对哈希表进行扩展或收缩,以使哈希表的负载因子维持在一个合理范围之内
  • 负载因子 = 保存的节点数(used)/ 哈希表大小(size)

rehash步骤包括

  • 为字典的ht[1]哈希表分配空间,大小取决于要执行的操作以及ht[0]当前包含的键值对数量

    • 扩展操作:ht[1]大小为第一个大于等于ht[0].used乘以2的2的n次幂
    • 收缩操作:ht[1]大小为第一个大于等于ht[0].used的2的n次幂
  • 将保存在ht[0]的所有键值对rehash到ht[1]上面:重新计算键的哈希值和索引值
  • 当所有ht[0]的键值对都迁移到ht[1]之后,释放ht[0],将ht[1]置为ht[0],并新建一个hash作为ht[1]

自动扩展的条件

  • 服务器没有执行BGSave命令或GBRewriteAOF命令,并且哈希表的负载因子 >= 1
  • 服务器正在执行BGSave命令或GBRewriteAOF命令,并且哈希表的负载因子 >= 5
  • BGSave命令或GBRewriteAOF命令时,服务器需要创建当前服务器进程的子进程,会耗费内存,提高负载因子避免写入,节约内存

自动收缩的条件

  • 哈希表负载因子小于0.1时,自动收缩

渐进式rehash

  • ht[0]数据重新索引到ht[1]不是一次性集中完成的,而是多次渐进式完成(避免hash表过大时导致性能问题)

渐进式rehash详细步骤

  • 为ht[1]分配空间,让自动同时持有两个哈希表
  • 字典中rehashidx置为0,表示开始执行rehash(默认值为-1)
  • rehash期间,每次对字典执行操作时,顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]
  • 全部rehash完毕时,rehashidx设为-1

注意点

  • rehash的所有操作会在两个哈希表进行
  • 新增加的值一律放入ht[1],保证数据只会减少不会增加

跳跃表

  • 跳跃表是一种有序数据结构,通过在每个节点维持多个指向其他节点的指针,达到快速访问节点的目的
  • 时间复杂度:最坏O(N),平均O(logN)
  • 大部分情况下,效率可与平衡树媲美,不过比平衡树实现简单
  • 有序集合的底层实现之一

数据结构

位于server.h文件中

// 跳跃表节点
typedef struct zskiplistNode {
    sds ele; // 成员对象
    double score; // 分值,从小到大排序
    struct zskiplistNode *backward; // 后退指针,从表尾向表头遍历时使用
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针
        unsigned long span; // 跨度,记录两个节点之间的距离
    } level[]; // 层,是一个数组
} zskiplistNode;

// 跳跃表相关信息
typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 表头和表尾
    unsigned long length; // 跳跃表长度(包含节点的数量)
    int level; // 跳跃表内层数最大那个节点的层数(不包括表头节点层数)
} zskiplist;

167ac8dd5c6d78ac.webp

  • level数组的大小在每次新建跳跃表的时候,随机生成,大小介于1-32直接
  • 遍历操作只使用前进指针,跨度用来计算排位(rank),沿途访问的所有层跨度加起来就是节点的排位
  • 多个节点可以包含相同的分支,但每个节点成员对象是唯一的

整数集合

  • intset是集合键的底层实现之一
  • 当一个集合只包含整数值原素,且数量不多时,会使用整数集合作为底层实现

数据结构

位于intset.h文件

typedef struct intset {
    uint32_t encoding; // 编码方式
    uint32_t length; // 长度
    int8_t contents[]; // 内容,数组内容类型取决于encoding属性,并不是int8_t。按照大小排序,没有重复
} intset;

升级

当我们要将一个新元素添加到整数集合里,并且新元素的类型比整数集合现有所有的元素类型都要长时,集合要先进行升级才能添加新数据
升级步骤包括三步:

  1. 根据类型,扩展大小,分配空间
  2. 将底层数组数据都转换成新的类型,并反倒正确位置
  3. 新元素添加到底层数组里面
  • 添加元素可能导致升级,所以添加新元素的世界复杂度为O(N)
  • 不支持降级,升级后将一直保持新的数据类型

升级的好处

  • 提高灵活性
  • 节约内存

压缩列表

  • ziplist是列表键和哈希键的底层实现之一
  • redis为了节约内存而开发的顺序型数据结构
  • 当列表键只包含少量列表项,且每个列表项要么是小整数,要么是短字符串,就使用ziplist作为列表键底层实现
  • 压缩列表遍历时,从表位向表头回溯遍历
  • ziplist没有专门的struct来表示

压缩列表的构成

167acb15d0535cca.webp

属性类型长度用途
zlbytesuint32_t4字节整个压缩列表占用的内存字节数
zltailuint32_t4字节表尾节点距离压缩列表起始地址有多少字节,无需遍历就可得到表尾节点
zllenuint16_t2字节节点数量,小于65535时是实际值,超过时需要遍历才能算出
entryN列表节点不定包含的各个节点
zlenduint8_t1字节特殊值0xFF,末端标记

压缩列表节点的构成

167acb9bf2ab4cae.webp

  • previos_entry_length:前一个节点的长度,用于从表尾向表头回溯用

    • 如果前面节点长度小于254字节,preivos_entry_length用1字节表示
    • 如果前面节点长度小于254字节,preivos_entry_length用5字节表示,第1个字节为0xFE(254),后面四个字节表示实际长度
  • encoding:记录content的类型以及长度,encoding分为两部分,高两位和余下的位数,最高两位的取值有以下情况:
最高两位取值表示是数据类型encoding字节数余下的bit数最大范围
00字符数组一个字节6bit63位
01字符数组两个字节14bit2^14-1
10字符数组五个字节4*8,第一个字节余下的6bit留空2^32-1位
11整数1个字节000000int16_t类型整数
11整数1个字节010000int32_t类型整数
11整数1个字节100000int64_t类型整数
11整数1个字节11000024位有符号整数
11整数1个字节1111108位有符号整数
11整数1个字节xxxxxx没有content,xxxx本身就表示了0-12的整数
  • content:保存节点的值

连锁更新

  • 连续多个节点大小介于254左右的节点,因扩展导致连续内存分配的情况。不过在大多数情况下,这种情况比较少。

对象

概述

  • redis并没有直接使用前面的数据结构来实现键值对的数据库,而是基于数据结构创建了一个对象系统,每种对象都用到前面至少一种数据结构
  • 每个对象都由一个redisObject结构来表示
//server.h
typedef struct redisObject {
   unsigned type:4; //类型
   unsigned encoding:4; // 编码
   // 对象最后一个被命令程序访问的时间
   unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                           * LFU data (least significant 8 bits frequency
                           * and most significant 16 bits access time). */
   int refcount; // 引用计数
   void *ptr; // 指向底层的数据结构指针
} robj;

使用对象的好处

  1. 在执行命令之前,根据对象类型判断一个对象是否可以执行给定的命令
  2. 针对不同厂家,Wie对象设置多种不同的数据结构实现,从而优化效率
  3. 实现了基于引用计数的内存回收机制,不再使用的对象,内存会自动释放
  4. 引用计数实现对象共享机制,多个数据库共享同一个对象以节约内存
  5. 对象带有时间时间积累信息,用于计算空转时间

redis中的对象

  1. 字符串对象
  2. 列表对象
  3. 哈希对象
  4. 集合对象
  5. 有序结合对象

对象的类型与编码

对象的类型

对象对象type属性type命令的输出
字符串对象REDIS_STRINGstring
列表对象REDIS_LISTlist
哈希对象REDIS_HASHhash
集合对象REDIS_SETset
有序集合对象REDIS_ZSETzset

对象的编码

  • 编码决定了ptr指向的数据类型,表明使用什么数据类型作为底层实现
  • 每种类型对象至少使用两种不同的编码
  • 通过编码,redis可以根据不同场景设定不同编码,极大提高灵活性和效率
编码常量对应的数据结构OBJECT ENCODING命令输出
REDIS_ENCODING_INTlong类型的整数“int”
REDIS_ENCODING_EMBSTRembstr编码的简单动态字符串“embstr”
REDIS_ENCODING_RAW简单动态字符串“raw”
REDIS_ENCODING_HT字典“hashtable”
REDIS_ENCODING_LINKEDLIST双端链表“linkedlist”
REDIS_ENCODING_ZIPLIST压缩列表“ziplist”
REDIS_ENCODING_INTSET整数集合“intset”
REDIS_ENCODING_SKIPLIST跳跃表和字典“skiplist”

字符串对象

  • 字符串对象的编码可以是

    • int
      167b15616ddb9ce3.webp
    • raw
      167b156e779c0e4a.webp
    • embstr
      167b1579b6f8ddcb.webp
  • 浮点数在redis中也是作为字符串对象保存,涉及计算时,先转回浮点数
字符串对象内容长度编码类型
整数值-int
字符串值小于32字节embstr
字符串值大于32字节raw

embstr编码是专门用于保存短字符串的一种优化编码方式。这种编码和raw编码一样,都使用redisObject结构和sdshdr结构来表示对象。区别在于:

  • raw编码调用两次内存分配函数来分别创建redisObject和sdrhdr结构
  • embstr则调用一次内存分配函数来创建一块连续空间,里面包括redisObject和sdrhdr

编码转换

int编码和embstr编码的对象满足条件时会自动转换为raw编码的字符串对象

  • int编码对象,执行命令导致对象不再是整数时,会转换为raw对象
  • embstr编码没有相应执行函数,是只读编码。涉及修改时,会转换为raw对象

字符串命令

redis中所有键都是字符串对象,所以所有对于键的命令都是针对字符串键来构建的

  1. set
  2. get
  3. append
  4. incrbyfloat
  5. incrby
  6. decrby
  7. strlen
  8. strrange
  9. getrange

列表对象

  • 列表对象的编码可以是

    • ziplist
      167b1586d405e8c1.webp
    • linkedlist
      167b15907ad103050.webp

编码转换

使用ziplist编码的两个条件如下,不满足的都用linkedlist编码(这两个条件可以在配置文件中修改):

  • 保存的所有字符串元素的长度都小于64字节
  • 列表的元素数量小于512个

列表命令

  1. lpush
  2. rpush
  3. lpop
  4. rpop
  5. lindex
  6. llen
  7. linsert
  8. lrem
  9. ltrim
  10. lset

哈希对象

哈希对象的编码可以是

  • ziplist
    167b1bf5d2e45469.webp

hashtable
167b1c05675034a3.webp

编码转换

  • 使用ziplist需要满足两个条件,不满足则都使用hashtable(这两个条件可以在配置文件中修改)

    • 所有键值对的键和值的字符串长度都小于64字节
    • 键值对数量小于512个

哈希命令

  1. hset
  2. hget
  3. hexists
  4. hdel
  5. hlen
  6. hgetall

集合对象

集合对象的编码可以是:

  • intset:所有元素保存在整数集合里
    167b1c7c861215e8.webp
  • hashtale:字典的值为null
    167b1c81ff7bbdaf.webp

编码转换

集合使用intset需要满足两个条件,不满足时使用hashtable(参数可通过配置文件修改)

  • 保存的所有元素都是整数值
  • 元素数量不超过512个

集合命令

  1. sadd
  2. scard
  3. sismember
  4. smembers
  5. srandmember
  6. spop
  7. srem

有序结合对象

有序集合的编码可以是

  • ziplist:每个元素使用两个紧挨在一起的节点表示,第一个表示成员,第二个表示分值。分值小的靠近表头,分值大的靠近表尾
    167b1d0b6c46fa95.webp
  • skiplist:使用zset作为底层实现,zset结构同时包含了字典和跳跃表,分别用于根据key查找score和分值排序或范围查询
// 两种数据结构通过指针共享元素成员和分值,不会浪费内存
typedef struct zset {
    zskplist *zsl; //跳跃表,方便zrank,zrange
    dict *dict; //字典,方便zscore
}zset;

167b1db35769bf51.webp

编码转换

当满足以下两个条件时,使用ziplist编码,否则使用skiplist(可通过配置文件修改)

  • 保存的元素数量少于128个
  • 成员长度小于64字节

有序集合命令

  1. zadd
  2. zcard
  3. zcount
  4. zrange
  5. zrevrange
  6. zrem
  7. zscore

类型检查和命令多态

redis的命令可以分为两大类:

  • 可以对任意类型的键执行,如

    • del
    • expire
    • rename
    • type
    • object
  • 只能对特定类型的键执行,比如前面各种对象的命令。是通过redisObject的type属性实现的

内存回收

redis通过对象的refcount属性记录对象引用计数信息,适当的时候自动释放对象进行内存回收

对象共享

  • 包含同样数值的对象,键的值指向同一个对象,以节约内存。
  • redis在初始化时,创建一万个字符串对象,包含从0-9999的所有整数值,当需要用到这些值时,服务器会共享这些对象,而不是新建对象
  • 数量可通过配置文件修改
  • 目前不包含字符串的对象共享,因为要比对字符串是否相同本身就会造成性能问题

对象空转时长

  • 空转时长=现在时间-redisObject.lru,lru记录对象最后一次被访问的时间
  • 当redis配置了最大内存(maxmemory)时,回收算法判断内存超过该值时,空转时长高的会优先被释放以回收内存

参考命令

# 设置字符串
set msg "hello world"
rpush numbers 1 2 3 4 5
llen numbers
lrange numbers 0 5
# 获取键值使用的底层数据结构
object encoding numbers
# 查看对象的引用计数值
object refcount numbers
# 对象空转时长: value=now-object.lru
object idletime numbers