我爱编程Java 杂谈程序员技术栈

redis源码分析（四）：数据读写相关操作

2018-08-02  本文已影响6人  msrpp

数据存储是一个数据库的核心功能，对于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种，他们的关系如下:

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，下面一个个说明各个取值含义。

上一篇下一篇

猜你喜欢

热点阅读