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

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

标签： Redis Redis数据结构 Redis内存管理策略 Redis数据类型 Redis类型映射

甘泉ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景，ssl证书未来市场广阔！成为创新互联的ssl证书销售渠道，可以享受市场价格4-6折优惠！如果有意向欢迎电话联系或者加微信：18980820575（备注：SSL证书合作）期待与您的合作！

• Redis 数据类型特点与使用场景
  • String、List、Hash、Set、Zset
  • 案例：沪江团购系统大促 hot-top接口 cache设计
• Redis 内存数据结构与编码
  • OBJECTencoding key、DEBUG OBJECTkey
  • 简单动态字符串（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索引中的所有 keyrehash到 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 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  

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。