数据存储是一个数据库的核心功能，对于redis来说，最重要的任务是缓存，redis默认有16个数据库，首次连接使用的是db0，可以用select语句来选择其他编号的数据库和客户端绑定。

存储格式

redisDb的数据结构以及重要的成员变量结构如下:

typedef struct redisDb {

    // 数据库键空间，保存着数据库中的所有键值对
    dict *dict;                 /* The keyspace for this DB */

    // 键的过期时间，字典的键为键，字典的值为过期事件 UNIX 时间戳
    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 */

    // 正在被 WATCH 命令监视的键
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */

    struct evictionPoolEntry *eviction_pool;    /* Eviction pool of keys */

    // 数据库号码
    int id;                     /* Database ID */

    // 数据库的键的平均 TTL ，统计信息
    long long avg_ttl;          /* Average TTL, just for stats */

} redisDb;

typedef struct dict {

    // 类型特定函数
    dictType *type;

    // 私有数据
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

    // 目前正在运行的安全迭代器的数量
    int iterators; /* number of iterators currently running */

} dict;


typedef struct dictht {
    
    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;
    
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;

    // 该哈希表已有节点的数量
    unsigned long used;

} dictht;


typedef struct dictEntry {
    
    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;

} dictEntry;


typedef struct redisObject {

    // 类型
    unsigned type:4;//有5种取值 
//#define REDIS_STRING 0
//#define REDIS_LIST 1
//#define REDIS_SET 2
//#define REDIS_ZSET 3
//#define REDIS_HASH 4

    // 编码
    unsigned encoding:4;

    // 对象最后一次被访问的时间
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */

    // 引用计数
    int refcount;

    // 指向实际值的指针
    void *ptr;

} robj;

其中最关键的结构是dictEntry，dictEntry是哈希表的节点，val指针存储着实际的数据，redis的key都是字符串格式的robj,value也是一个robj对象，encoding有8种编码取值,分别对应着几种redis的内部结构：

#define REDIS_ENCODING_RAW 0     /* Raw representation */
#define REDIS_ENCODING_INT 1     /* Encoded as integer */
#define REDIS_ENCODING_HT 2      /* Encoded as hash table */
#define REDIS_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
#define REDIS_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */
#define REDIS_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define REDIS_ENCODING_INTSET 6  /* Encoded as intset */
#define REDIS_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
#define REDIS_ENCODING_EMBSTR 8  /* Embedded sds string encoding */

可是redis的数据类型只有5种，他们的关系如下:

• string类型的数据:如果value是一个数字的话:小于10000的值存储在共享空间(相同的value对象的地址都是一样的,参考java装箱中-128～127的整数),大于10000小于21个字节的部分以REDIS_ENCODING_INT方式编码，这样robj的ptr指针可以直接存储这个整数(这里有疑问，为什么不把小于10000的值也以这种方式存储呢，反正指针的内存省不掉);除此之外，以REDIS_ENCODING_EMBSTR的方式编码,redis可存储的最大字符串是512M 。

• list类型的数据:如果list的长度小于配置，内部以ziplist存储，否则以linkedlist存储。配置项list-max-ziplist-entries,默认512。

• set类型的数据:如果插入的都是整形数据，那么存储在intset中，只要set中存入一个非整型数据，立刻转换成hash table。

• zset类型的数据:相比set多了一个排序的功能，zset数据默认以ziplist的结构存储，如果满足以下条件其一，转为skiplist。(1).zset节点数大于配置的zset-max-ziplist-entries，默认128；(2)zset插入的新节点长度大于配置项zset-max-ziplist-value,默认64字节。

• hash类型的数据: 默认是ziplist ，当满足以下条件之一，转化为dict方式存储。(1).hash的数量大于hash-max-ziplist-entries，默认512；(2)hash表有一个值的长度超过hash-max-ziplist-value，默认64。

blocking_keys参数主要用于brpoplpush（弹出a队列队尾，并插入b队列队首），brpop（弹出队尾）,blpop（弹出队首）命令,当alpha队列为空时，这些命令会阻塞请求的客户端一段时间，直到期间有其他客户端对这个key进行push操作或者超时,这些命令的语法为:(去掉前面的b即为对应的非阻塞语法)。

brpoplpush alpha reciver timeout

brpop alpha
blpop alpha

一个命令从发起到返回的过程

管中窥豹,我们以基本的set为例。1.分析指令参数;2.调用redisCommandTable中对应的函数进行处理;3.查询dict结构中是否有该键，有则更新，没有则创建一个新的，设置value;4.组好返回给客户端的报文。

如何处理过期的键？

所有带过期事件的键，均有一份备份位于字典expires中。redis内部有两种机制来清除过期数据，1.在时间事件周期内，主动调用activeExpireCycle来清除过期键，每个db最多随机取20个键来判断超时时间，超时了则执行删除逻辑，同时清除redisDb中的expires和dict两个字典。2.当有客户端主动来执行这个键相关操作的时候(get,expire ,incr,等等),主动检查此键在expires中是否过期，过期则执行删除。 可见redis不能保证数据一过期就立马删除的。

数据库字典的resize逻辑

当数据量少于hash表桶数量的10%，或者数据量大于桶的数量的时候，发生字典的resize()。每个字典有两个hash表，即dictht ht[2];ht[0]是实际使用的hash表，而ht[1]是在resize()的时候启用，resize()时启用rehashidx字段，标记着rehash进展到哪个桶了，数据将分次从ht[0]迁移到ht[1]，迁移和处理过期的键类似，也是有一个时间事件的周期每次最大处理100个桶，普通的查询修改等操作，每次处理一个桶。迁移完成时令ht[0] = ht[1]，然后置空ht[1]，恢复了常态，如此resize()调整完成。核心代码如下:

        // 略过数组中为空的索引，找到下一个非空索引
        while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;

        // 指向该索引的链表表头节点
        de = d->ht[0].table[d->rehashidx];
        /* Move all the keys in this bucket from the old to the new hash HT */
        // 将链表中的所有节点迁移到新哈希表
        // T = O(1)
        while(de) {
            unsigned int h;

            // 保存下个节点的指针
            nextde = de->next;

            /* Get the index in the new hash table */
            // 计算新哈希表的哈希值，以及节点插入的索引位置
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;

            // 插入节点到新哈希表
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;

            // 更新计数器
            d->ht[0].used--;
            d->ht[1].used++;

            // 继续处理下个节点
            de = nextde;
        }

可以看到，旧的一个桶分裂成了新的两个桶，新的hash表和旧表相比同一个桶内的元素是倒置的。

数据到达最大内存如何处理?

redis通过"zmalloc_"开头的一系列方法，将使用的内存做了统计，如果客户端发送了可能占用内存的命令，且当前统计的内存超过了设定，将会根据配置项maxmemory-policy，这个配置有如下取值:volatile-random,volatile-lru,volatile-ttl,allkeys-lru,allkeys-random,noeviction几种取值，采取一定的措施来减小内存。实现此步骤的函数是freeMemoryIfNeeded，下面一个个说明各个取值含义。

• noeviction ，不删除已有数据，给客户端返回失败。

• allkeys-random，从整个字典中随机选取键值对删除。

• volatile-random 从有过期时间的键值对中选取随机值。

• volatile-ttl 从带过期的键中选取5个比较找出最早的过期键。可以看出这个算法随机性还是比较强的，并不是从所有键值对中找出最早的过期键。

• allkeys-lru和volatile-lru lru机制是这几种里面最复杂的了，着重说一下，可能有些认识不足，每次访问会更新键值对(实际存储在value中)的最后访问时间，db->eviction_pool存储了redis中将要淘汰的键，一共存储16个键，值按照值是该键的最后访问距今的时间，所以idle值越大，说明数据越该淘汰，淘汰实现函数是evictionPoolPopulate，首先从目标字典中选取16个key，依次计算每个键值对的最后访问时间，判断是否比eviction_pool的记录都大，是则更新，产生一个更新后的eviction_pool。这里有几个问题，因为eviction_pool存储的数据可能是好几轮之前的旧数据了，所以如果有客户端删除了某个eviction_pool中的键值对，eviction_pool是感知不了的。即eviction_pool可能存在废数据，这个问题redis在代码中又做了查询处理，存在才删除。第二，同样是旧数据导致的， 如果原来处于eviction_pool的数据被触发了查询，更新了lru值，但eviction_pool中是不会更新的，下轮evictionPoolPopulate依然可能将此"热点数据"删除。第三，和第二条类似，旧数据的idle值是不会更新的，但是随着时间的推移，这个本该要更新的。总结一下redis中lru的缺点，1.redis的lru算法仅仅是局部数据间的比较，对比的不全面；2.redis每次淘汰的数据未必是eviction_pool中最应该淘汰的数据。