Redis 数据结构与内存管理策略（下）

旧城等待， 2021-12-05 05:25 177阅读 0赞

*  Redis 数据类型特点与使用场景
    
     *  **String**、**List**、**Hash**、**Set**、**Zset**
     *  案例：沪江团购系统大促 **hot-top** 接口 **cache** 设计
 *  Redis 内存数据结构与编码
    
     *  **OBJECT** encoding key、**DEBUG OBJECT** key
     *  简单动态字符串（simple dynamic string）
     *  链表（linked list）
     *  字典（dict）
     *  跳表（skip list）
     *  整数集合（int set）
     *  压缩表（zip list）
     *  Redis Object 类型与映射
 *  Redis 内存管理策略
    
     *  键 过期时间、生存时间
     *  过期键删除策略
     *  **AOF** 、**RDB** 处理过期键策略
     *  Redis **LRU** 算法
 *  Redis 持久化方式
    
     *  **RDB** (Redis DataBase)
     *  **AOF** (Append-only file)

### 字典（dict） ###

**dict** 字典是基于 ***hash算法*** 来实现，是 **Hash** 数据类型的底层存储数据结构。我们来看下 **redis 3.0.0** 版本的 **dict.h** 头文件定义。

typedef struct dict {
        dictType *type;
        void *privdata;
        dictht ht[2];
        long rehashidx;
        int iterators; 
    } dict;

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

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

说到 ***hash table*** 有两个东西是我们经常会碰到的，首先就是 ***hash 碰撞*** 问题，**redis dict** 是采用链地址法来解决，***dictEntry->next*** 就是指向下个冲突 **key** 的节点。

还有一个经常碰到的就是 **rehash** 的问题，提到 **rehash** 我们还是有点担心性能的。那么redis 实现是非常巧妙的，采用 ***惰性渐进式 rehash 算法*** 。

在 **dict struct** 里有一个 **ht\[2\]** 组数，还有一个 **rehashidx** 索引。**redis** 进行 **rehash** 的大致算法是这样的，首先会开辟一个新的 **dictht** 空间，放在 **ht\[2\]** 索引上，此时将 **rehashidx** 设置为0，表示开始进入 **rehash** 阶段，这个阶段可能会持续很长时间，**rehashidx** 表示 **dictEntry** 个数。

每次当有对某个 **ht\[1\]** 索引中的 **key** 进行访问时，获取、删除、更新，**redis** 都会将当前 **dictEntry** 索引中的所有 **key** **rehash** 到 **ht\[2\]** 字典中。一旦 **rehashidx=-1** 表示 **rehash** 结束。

### 跳表（skip list） ###

**skip list** 是 **zset** 的底层数据结构，有着高性能的查找排序能力。

我们都知道一般用来实现带有排序的查找都是用 **Tree** 来实现，不管是各种变体的 **B Tree** 还是 **B+ Tree**，本质都是用来做顺序查找。

**skip list** 实现起来简单，性能也与 **B Tree** 相接近。

typedef struct zskiplistNode {
        robj *obj;
        double score;
        struct zskiplistNode *backward;
        struct zskiplistLevel {
            struct zskiplistNode *forward;
            unsigned int span;
        } level[];
    } zskiplistNode;
    
    typedef struct zskiplist {
        struct zskiplistNode *header, *tail;
        unsigned long length;
        int level;
    } zskiplist;

***zskiplistNode->zskiplistLevel->span*** 这个值记录了当前节点距离下个节点的跨度。每一个节点会有最大不超过 ***zskiplist->level*** 节点个数，分别用来表示不同跨度与节点的距离。

每个节点会有多个 **forward** 向前指针，只有一个 **backward** 指针。每个节点会有对象 \_\_\*obj\_\_ 和 **score** 分值，每个分值都会按照顺序排列。

### 整数集合（int set） ###

**int set** 整数集合是 **set** 数据类型的底层实现数据结构，它的特点和使用场景很明显，只要我们使用的集合都是整数且在一定的范围之内都会使用整数集合编码。

SADD set:userid 100 200 300
    (integer) 3

OBJECT encoding set:userid
    "intset"

**int set** 使用一块连续的内存来存储集合数据，它是数组结构不是链表结构。

typedef struct intset {
        uint32_t encoding;
        uint32_t length;
        int8_t contents[];
    } intset;

**intset->encoding** 用来确定 **contents\[\]** 是什么类型的整数编码，以下三种值之一。

#define INTSET_ENC_INT16 (sizeof(int16_t))
    #define INTSET_ENC_INT32 (sizeof(int32_t))
    #define INTSET_ENC_INT64 (sizeof(int64_t))

**redis** 会根据我们设置的值类型动态 **sizeof** 出一个对应的空间大小。如果我们集合原来是 **int16** ，然后往集合里添加了 **int32** 整数将触发升级，一旦升级成功不会触发降级操作。

### 压缩表（zip list） ###

**zip list** 压缩表是 **list**、**zset**、**hash** 数据类型的底层数据结构之一。它是为了节省内存通过压缩数据存储在一块连续的内存空间中。

typedef struct zlentry {
        unsigned int prevrawlensize, prevrawlen;
        unsigned int lensize, len;
        unsigned int headersize;
        unsigned char encoding;
        unsigned char *p;
    } zlentry;

它最大的优点就是压缩空间，空间利用率很高。缺点就是一旦出现更新可能就是连锁更新，因为数据在内容空间中都是连续的，最极端情况下就是可能出现顺序连锁扩张。

压缩列表会由多个 **zlentry** 节点组成，每一个 **zlentry** 记录上一个节点长度和大小，当前节点长度 **lensize** 和大小 **len** 包括编码 **encoding** 。

这取决于业务场景，**redis** 提供了一组配置，专门用来针对不同的场景进行阈值控制。

hash-max-ziplist-entries 512
    hash-max-ziplist-value 64

list-max-ziplist-entries 512
    list-max-ziplist-value 64

zset-max-ziplist-entries 128
    zset-max-ziplist-value 64

上述配置分别用来配置 **ziplist** 作为 **hash** 、**list**、**zset** 数据类型的底层压缩阈值控制。

## Redis Object 类型与映射 ##

redis 内部每一种数据类型都是对象化的，也就是我们所说的5种数据类型其实内部都会对应到 redisObject 对象，然后在由 redisObject 来包装具体的存储数据结构和编码。

typedef struct redisObject {
        unsigned type:4;
        unsigned encoding:4;
        unsigned lru:REDIS_LRU_BITS; 
        int refcount;
        void *ptr;
    } robj;

这是一个很 **OO** 的设计，***redisObject->type*** 是 **5** 种数据类型之一，***redisObject->encoding*** 是这个数据类型所使用的数据结构和编码。

我们看下 **redis** 提供的 **5** 种数据类型与每一种数据类型对应的存储数据结构和编码。

/* Object types */
    #define REDIS_STRING 0
    #define REDIS_LIST 1
    #define REDIS_SET 2
    #define REDIS_ZSET 3
    #define REDIS_HASH 4

#define REDIS_ENCODING_RAW 0     
    #define REDIS_ENCODING_INT 1    
    #define REDIS_ENCODING_HT 2
    #define REDIS_ENCODING_ZIPMAP 3
    #define REDIS_ENCODING_LINKEDLIST 4
    #define REDIS_ENCODING_ZIPLIST 5 
    #define REDIS_ENCODING_INTSET 6  
    #define REDIS_ENCODING_SKIPLIST 7  
    #define REDIS_ENCODING_EMBSTR 8

**REDIS\_ENCODING\_ZIPMAP 3** 这个编码可以忽略了，在特定的情况下有性能问题，在 **redis 2.6** 版本之后已经废弃，为了兼容性保留。

![Redis 数据结构与内存管理策略][Redis]

上图是 **redis 5** 种数据类型与底层数据结构和编码的对应关系，但是这种对应关系在每一个版本中都会有可能发生变化，这也是 **redisObject** 的灵活性所在，有着 **OO** 的这种多态性。

***redisObject->refcount*** 表示当前对象的引用计数，在 **redis** 内部为了节省内存采用了共享对象的方法，当某个对象被引用的时候这个 **refcount** 会加 *1*，释放的时候会减 *1*。

***redisObject->lru*** 表示当前对象的 ***空转时长***，也就是 **idle time** ，这个时间会是 **redis lru** 算法用来释放对象的时间依据。可以通过 **OBJECT idletime** 命令查看某个 **key** 的空转时长 **lru** 时间。

## Redis 内存管理策略 ##

**redis** 在服务端分别为不同的 **db index** 维护一个 **dict** 这个 **dict** 称为 **key space** 键空间 。每一个 **redis client** 只能属于一个 **db index** ，在 **redis** 服务端会维护每一个链接的 **redisClient** 。

typedef struct redisClient {
        uint64_t id;
        int fd;
        redisDb *db;
    } redisClient;

在服务端每一个 **redis** 客户端都会有一个指向 **redisDb** 的指针。

typedef struct redisDb {
        dict *dict;
        dict *expires;
        dict *blocking_keys;
        dict *ready_keys;
        dict *watched_keys;
        struct evictionPoolEntry *eviction_pool;
        int id;
        long long avg_ttl;
    } redisDb;

**key space** 键空间就是这里的 **redisDb->dict** 。**redisDb->expires** 是维护所有键空间的每一个 **key** 的过期时间。

### 键 过期时间、生存时间 ###

对于一个 **key** 我们可以设置它多少秒、毫秒之后过期，也可以设置它在某个具体的时间点过期，后者是一个时间戳。

> ***EXPIRE*** 命令可以设置某个 **key** 多少秒之后过期  
> ***PEXPIRE*** 命令可以设置某个 **key** 多少毫秒之后过期

> ***EXPIREAT*** 命令可以设置某个 **key** 在多少秒时间戳之后过期  
> ***PEXPIREAT*** 命令可以设置某个 **key** 在多少毫秒时间戳之后过期

> ***PERSIST*** 命令可以移除键的过期时间

其实上述命令最终都会被转换成对 **PEXPIREAT** 命令。在 ***redisDb->expires*** 指向的 **key** 字典中维护着一个到期的毫秒时间戳。

> ***TTL、PTTL*** 可以通过这两个命令查看某个 **key** 的过期秒、毫秒数。

**redis** 内部有一个 ***事件循环***，这个事件循环会检查键的过期时间是否小于当前时间，如果小于则会删除这个键。

### 过期键删除策略 ###

在使用 **redis** 的时候我们最关心的就是键是如何被删除的，如何高效的准时的删除某个键。其实 **redis** 提供了两个方案来完成这件事情。

**redis** 采用 ***惰性删除*** 、 ***定期删除*** 双重删除策略。

当我们访问某个 **key** 的时候 **redis** 会检查它是否过期，这是惰性删除。

robj *lookupKeyRead(redisDb *db, robj *key) {
        robj *val;
    
        expireIfNeeded(db,key);
        val = lookupKey(db,key);
        if (val == NULL)
            server.stat_keyspace_misses++;
        else
            server.stat_keyspace_hits++;
        return val;
    }

int expireIfNeeded(redisDb *db, robj *key) {
        mstime_t when = getExpire(db,key);
        mstime_t now;
    
        if (when < 0) return 0; /* No expire for this key */
        
        if (server.loading) return 0;
        
        now = server.lua_caller ? server.lua_time_start : mstime();
        if (server.masterhost != NULL) return now > when;
    
        /* Return when this key has not expired */
        if (now <= when) return 0;
    
        /* Delete the key */
        server.stat_expiredkeys++;
        propagateExpire(db,key);
        notifyKeyspaceEvent(REDIS_NOTIFY_EXPIRED,"expired",key,db->id);
        return dbDelete(db,key);
    }

**redis** 也会通过 ***事件循环*** 周期性的执行 **key** 的过期删除动作，这是定期删除。

int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) {
        /* Handle background operations on Redis databases. */
        databasesCron();
    }

void databasesCron(void) {
        /* Expire keys by random sampling. Not required for slaves
         * as master will synthesize DELs for us. */
        if (server.active_expire_enabled && server.masterhost == NULL)
            activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW);
    }

**惰性删除** 是每次只要有读取、写入都会触发惰性删除代码。**周期删除** 是由 **redis EventLoop** 来触发的。**redis** 内部很多维护性工作都是基于 **EventLoop** 。

### **AOF** 、**RDB** 处理过期键策略 ###

既然键会随时存在过期问题，那么涉及到持久化 **redis** 是如何帮我们处理的。

当 **redis** 使用 **RDB** 方式持久化时，每次持久化的时候就会检查这些即将被持久化的 **key** 是否已经过期，如果过期将直接忽略，持久化那些没有过期的键。当 **redis** 作为 ***master 主服务器*** 启动的时候，在载入 **rdb** 持久化键时也会检查这些键是否过期，将忽略过期的键，只载入没过期的键。

当 **redis** 使用 **AOF** 方式持久化时，每次遇到过期的 **key redis** 会追加一条 **DEL** 命令 到 **AOF** 文件，也就是说只要我们顺序载入执行 **AOF** 命令文件就会删除过期的键。

如果 **redis** 作为从服务器启动的化，它一旦与 ***master 主服务器*** 建立链接就会清空所有数据进行完整同步，当然新版本的 **redis** 支持 **SYCN2** 的半同步。如果是已经建立了 ***master/slave*** 主从同步之后，主服务器会发送 **DEL** 命令给所有从服务器执行删除操作。

### Redis **LRU** 算法 ###

在使用 **redis** 的时候我们会设置 **maxmemory** 选项，**64** 位的默认是 **0** 不限制。线上的服务器必须要设置的，要不然很有可能导致 **redis** 宿主服务器直接内存耗尽最后链接都上不去。

所以基本要设置两个配置：

> ***maxmemory 最大内存阈值***  
> ***maxmemory-policy 到达阈值的执行策略***

可以通过 ***CONFIG GET maxmemory/maxmemory-policy*** 分别查看这两个配置值，也可以通过 ***CONFIG SET*** 去分别配置。

**maxmemory-policy** 有一组配置，可以用在很多场景下：

> noeviction：客户端尝试执行会让更多内存被使用的命令直接报错  
> allkeys-lru： 在所有key里执行lru算法  
> volatile-lru：在所有已经过期的key里执行lru算法  
> allkeys-random：在所有key里随机回收  
> volatile-random：在已经过期的key里随机回收  
> volatile-ttl：回收已经过期的key，并且优先回收存活时间（TTL）较短的键

关于 **cache** 的命中率可以通过 **info** 命令查看 键空间的命中率和未命中率。

# Stats
    keyspace_hits:33
    keyspace_misses:5

**maxmemory** 在到达阈值的时候会采用一定的策略去释放内存，这些策略我们可以根据自己的业务场景来选择，默认是 **noeviction** 。

**redis LRU** 算法有一个取样的优化机制，可以通过一定的取样因子来加强回收的 **key** 的准确度。***CONFIG GET maxmemory-samples*** 查看取样配置，具体可以参考更加详细的文章。

## Redis 持久化方式 ##

**redis** 本身提供持久化功能，有两种持久化机制，一种是数据持久化 **RDB** ，一种是命令持久化 **AOF**，这两种持久化方式各有优缺点，也可以组合使用，一旦组合使用 **redis** 在载入数据的时候会优先载入 **aof** 文件，只有当 **AOF** 持久化关闭的时候才会载入 **rdb** 文件。

### **RDB** (Redis DataBase) ###

**RDB** 是 **redis** 数据库，**redis** 会根据一个配置来触发持久化。

#save <seconds> <changes>
    
    save 900 1
    save 300 10
    save 60 10000

CONFIG GET save
    1) "save"
    2) "3600 1 300 100 60 10000"

表示在多少秒之类的变化次数，一旦达到这个触发条件 redis 将触发持久化动作。redis 在执行持久化的时候有两种模式 ***BGSAVE、SAVE*** 。**BGSAVE** 是后台保存，**redis** 会 **fork** 出一个子进程来处理持久化，不会 **block** 用户的执行请求。而 **SAVE** 则会 **block** 用户执行请求。

struct redisServer {
    long long dirty;/* Changes to DB from the last save */
    time_t lastsave; /* Unix time of last successful save */
    long long dirty_before_bgsave;
    pid_t rdb_child_pid;/* PID of RDB saving child */
    struct saveparam *saveparams; /* Save points array for RDB */
    }

struct saveparam {
        time_t seconds;
        int changes;
    };

**redisServer** 包含的信息很多，其中就包含了有关于 **RDB** 持久化的信息。***redisServer->dirty*** 至上次 **save** 到目前为止的 **change** 数。***redisServer->lastsave*** 上次 **save** 时间。

**saveparam struct** 保存了我们通过 **save** 命令设置的参数，**time\_t** 是个 **long** 时间戳。

typedef __darwin_time_t     time_t;

typedef long    __darwin_time_t;    /* time() */

int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) {
             for (j = 0; j < server.saveparamslen; j++) {
                struct saveparam *sp = server.saveparams+j;
                if (server.dirty >= sp->changes &&
                    server.unixtime-server.lastsave > sp->seconds &&
                    (server.unixtime-server.lastbgsave_try >
                     REDIS_BGSAVE_RETRY_DELAY ||
                     server.lastbgsave_status == REDIS_OK))
                {
                    redisLog(REDIS_NOTICE,"%d changes in %d seconds. Saving...",
                        sp->changes, (int)sp->seconds);
                    rdbSaveBackground(server.rdb_filename);
                    break;
                }
             }
    }

**redis** 事件循环会周期性的执行 **serverCron** 方法，这段代码会循环遍历 **server.saveparams** 参数链表。

如果 **server.dirty** 大于等于 我们参数里配置的变化并且 ***server.unixtime-server.lastsave*** 大于参数里配置的时间并且 **server.unixtime-server.lastbgsave\_try** 减去 **bgsave** 重试延迟时间或者当前 **server.lastbgsave\_status==REDIS\_OK** 则执行 **rdbSaveBackground** 方法。

### **AOF** (Append-only file) ###

**AOF** 持久化是采用对文件进行追加对方式进行，每次追加都是 **redis** 处理的 命令。有点类似 ***command sourcing 命令溯源*** 的模式。

只要我们可以将所有的命令按照执行顺序在重放一遍就可以还原最终的 **redis** 内存状态。

**AOF** 持久化最大的优势是可以缩短数据丢失的间隔，可以做到秒级的丢失率。**RDB** 会丢失上一个保存周期到目前的所有数据，只要没有触发 **save** 命令设置的 ***save seconds changes*** 阈值数据就会一直不被持久化。

struct redisServer {
     /* AOF buffer, written before entering the event loop */
     sds aof_buf;
     }

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

**aof\_buf** 是命令缓存区，采用 **sds** 结构缓存，每次当有命令被执行当时候都会写一次到 **aof\_buf** 中。有几个配置用来控制 **AOF** 持久化的机制。

appendonly no 
    appendfilename "appendonly.aof"

**appendonly** 用来控制是否开启 **AOF** 持久化，**appendfilename** 用来设置 **aof** 文件名。

appendfsync always
    appendfsync everysec
    appendfsync no

**appendfsync** 用来控制命令刷盘机制。现在操作系统都有文件 **cache/buffer** 的概念，所有的写入和读取都会走 **cache/buffer**，并不会每次都同步刷盘，因为这样性能一定会受影响。所以 **redis** 也提供了这个选项让我们来自己根据业务场景控制。

> **always** ：每次将 **aof\_buf** 命令写入 **aof** 文件并且执行实时刷盘。  
> **everysec** ：每次将 **aof\_buf** 命令写入 **aof** 文件，但是每隔一秒执行一次刷盘。  
> **no** ：每次将 **aof\_buf** 命令写入 **aof** 文件不执行刷盘，由操作系统来自行控制。

**AOF** 也是采用后台子进程的方式进行，与主进程共享数据空间也就是 **aof\_buf**，但是只要开始了 **AOF** 子进程之后 ***redis 事件循环文件事件处理器*** 会将之后的命令写入另外一个 **aof\_buf** ，这样就可以做到平滑的切换。

**AOF** 会不断的追加命令进 **aof** 文件，随着时间和并发量的加大 **aof** 文件会极速膨胀，所以有必要对这个文件大小进行优化。**redis** 基于 **rewrite** 重写对文件进行压缩。

no-appendfsync-on-rewrite no/yes
    auto-aof-rewrite-percentage 100
    auto-aof-rewrite-min-size 64mb

**no-appendfsync-on-rewrite** 控制是否在 **bgrewriteaof** 的时候还需要进行命令追加，如果追加可能会出现磁盘 **IO** 跑高现象。

上面说过，当 **AOF** 进程在执行的时候原来的事件循环还会正常的追加命令进 **aof** 文件，同时还会追加命令进另外一个 **aof\_buf** ，用来做新 **aof** 文件的重写。这是两条并行的动作，如果我们设置成 **yes** 就不追加原来的 **aof\_buf** 因为新的 **aof** 文件已经包含了之后进来的命令。

***auto-aof-rewrite-percentage、auto-aof-rewrite-min-size 64mb*** 这两个配置前者是文件增长百分比来进行 **rewrite** ，后者是按照文件大小增长进行 **rewrite** 。

欢迎关注技术公众号：架构师成长营

![20190717210759107.jpeg][]

[Redis]: /images/20211205/12b6d50454884ba484d1139c2f3ade47.png
[20190717210759107.jpeg]: https://img-blog.csdnimg.cn/20190717210759107.jpeg