redis TTL實作原理

TTL存儲的資料結構

redis針對TTL時間有專門的dict進行存儲，就是redisDb當中的dict *expires字段，dict顧名思義就是一個hashtable，key為對應的rediskey，value為對應的TTL時間。

dict的資料結構中含有2個dictht對象，主要是為了解決hash沖突過程中重新hash資料使用。

dictEntry當中的dictEntry就是hashtable當中的hash桶，作用應該不言自明了吧。

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;

/*
 * 哈希表
 *
 * 每個字典都使用兩個哈希表，進而實作漸進式 rehash 。
 */
typedef struct dictht {
    
    // 哈希表數組
    dictEntry **table;

    // 哈希表大小
    unsigned long size;
    
    // 哈希表大小掩碼，用于計算索引值
    // 總是等于 size - 1
    unsigned long sizemask;

    // 該哈希表已有節點的數量
    unsigned long used;

} dictht;

TTL 設定過期時間

TTL設定key過期時間的方法主要是下面4個：

expire 按照相對時間且以秒為機關的過期政策
expireat 按照絕對時間且以秒為機關的過期政策
pexpire 按照相對時間且以毫秒為機關的過期政策
pexpireat 按照絕對時間且以毫秒為機關的過期政策

{"expire",expireCommand,3,"w",0,NULL,1,1,1,0,0},
{"expireat",expireatCommand,3,"w",0,NULL,1,1,1,0,0},
{"pexpire",pexpireCommand,3,"w",0,NULL,1,1,1,0,0},
{"pexpireat",pexpireatCommand,3,"w",0,NULL,1,1,1,0,0},

expire expireat pexpire pexpireat

從實際設定過期時間的實作函數來看，相對時間的政策會有一個目前時間作為基準時間，絕對時間的政策會以0作為一個基準時間。

void expireCommand(redisClient *c) {
    expireGenericCommand(c,mstime(),UNIT_SECONDS);
}

void expireatCommand(redisClient *c) {
    expireGenericCommand(c,0,UNIT_SECONDS);
}

void pexpireCommand(redisClient *c) {
    expireGenericCommand(c,mstime(),UNIT_MILLISECONDS);
}

void pexpireatCommand(redisClient *c) {
    expireGenericCommand(c,0,UNIT_MILLISECONDS);
}

整個過期時間最後都會換算到絕對時間進行存儲，通過公式基準時間+過期時間來進行計算。

對于相對時間而言基準時間就是目前時間，對于絕對時間而言相對時間就是0。

中途考慮設定的過期時間是否已經過期，如果已經過期那麼在master就會删除該資料并同步删除動作到slave。

正常的設定過期時間是通過setExpire方法儲存到 dict *expires對象當中。

/* 
 *
 * 這個函數是 EXPIRE 、 PEXPIRE 、 EXPIREAT 和 PEXPIREAT 指令的底層實作函數。
 *
 * 指令的第二個參數可能是絕對值，也可能是相對值。
 * 當執行 *AT 指令時， basetime 為 0 ，在其他情況下，它儲存的就是目前的絕對時間。
 *
 * unit 用于指定 argv[2] （傳入過期時間）的格式，
 * 它可以是 UNIT_SECONDS 或 UNIT_MILLISECONDS ，
 * basetime 參數則總是毫秒格式的。
 */
void expireGenericCommand(redisClient *c, long long basetime, int unit) {
    robj *key = c->argv[1], *param = c->argv[2];
    long long when; /* unix time in milliseconds when the key will expire. */

    // 取出 when 參數
    if (getLongLongFromObjectOrReply(c, param, &when, NULL) != REDIS_OK)
        return;

    // 如果傳入的過期時間是以秒為機關的，那麼将它轉換為毫秒
    if (unit == UNIT_SECONDS) when *= 1000;
    when += basetime;

    /* No key, return zero. */
    // 取出鍵
    if (lookupKeyRead(c->db,key) == NULL) {
        addReply(c,shared.czero);
        return;
    }

    /* 
     * 在載入資料時，或者伺服器為附屬節點時，
     * 即使 EXPIRE 的 TTL 為負數，或者 EXPIREAT 提供的時間戳已經過期，
     * 伺服器也不會主動删除這個鍵，而是等待主節點發來顯式的 DEL 指令。
     *
     * 程式會繼續将（一個可能已經過期的 TTL）設定為鍵的過期時間，
     * 并且等待主節點發來 DEL 指令。
     */
    if (when <= mstime() && !server.loading && !server.masterhost) {

        // when 提供的時間已經過期，伺服器為主節點，并且沒在載入資料

        robj *aux;

        redisAssertWithInfo(c,key,dbDelete(c->db,key));
        server.dirty++;

        /* Replicate/AOF this as an explicit DEL. */
        // 傳播 DEL 指令
        aux = createStringObject("DEL",3);

        rewriteClientCommandVector(c,2,aux,key);
        decrRefCount(aux);

        signalModifiedKey(c->db,key);
        notifyKeyspaceEvent(REDIS_NOTIFY_GENERIC,"del",key,c->db->id);

        addReply(c, shared.cone);

        return;
    } else {

        // 設定鍵的過期時間
        // 如果伺服器為附屬節點，或者伺服器正在載入，
        // 那麼這個 when 有可能已經過期的
        setExpire(c->db,key,when);

        addReply(c,shared.cone);

        signalModifiedKey(c->db,key);
        notifyKeyspaceEvent(REDIS_NOTIFY_GENERIC,"expire",key,c->db->id);

        server.dirty++;

        return;
    }
}

setExpire函數主要是對db->expires中的key對應的dictEntry設定過期時間。

/*
 * 将鍵 key 的過期時間設為 when
 */
void setExpire(redisDb *db, robj *key, long long when) {

    dictEntry *kde, *de;

    /* Reuse the sds from the main dict in the expire dict */
    // 取出鍵
    kde = dictFind(db->dict,key->ptr);

    redisAssertWithInfo(NULL,key,kde != NULL);

    // 根據鍵取出鍵的過期時間
    de = dictReplaceRaw(db->expires,dictGetKey(kde));

    // 設定鍵的過期時間
    // 這裡是直接使用整數值來儲存過期時間，不是用 INT 編碼的 String 對象
    dictSetSignedIntegerVal(de,when);
}

TTL 擷取過期時間

通過ttl或者pttl傳回剩餘過期時間的邏輯其實非常簡單，就是通過key去db->expires找到過期時間對象，然後與目前系統時間相比計算內插補點。

{"ttl",ttlCommand,2,"r",0,NULL,1,1,1,0,0},
{"pttl",pttlCommand,2,"r",0,NULL,1,1,1,0,0},

void ttlCommand(redisClient *c) {
    ttlGenericCommand(c, 0);
}

void pttlCommand(redisClient *c) {
    ttlGenericCommand(c, 1);
}

/*
 * 傳回鍵的剩餘生存時間。
 *
 * output_ms 指定傳回值的格式：
 *
 *  - 為 1 時，傳回毫秒
 *
 *  - 為 0 時，傳回秒
 */
void ttlGenericCommand(redisClient *c, int output_ms) {
    long long expire, ttl = -1;

    /* If the key does not exist at all, return -2 */
    // 取出鍵
    if (lookupKeyRead(c->db,c->argv[1]) == NULL) {
        addReplyLongLong(c,-2);
        return;
    }

    /* The key exists. Return -1 if it has no expire, or the actual
     * TTL value otherwise. */
    // 取出過期時間
    expire = getExpire(c->db,c->argv[1]);

    if (expire != -1) {
        // 計算剩餘生存時間
        ttl = expire-mstime();
        if (ttl < 0) ttl = 0;
    }

    if (ttl == -1) {
        // 鍵是持久的
        addReplyLongLong(c,-1);
    } else {
        // 傳回 TTL 
        // (ttl+500)/1000 計算的是漸近秒數
        addReplyLongLong(c,output_ms ? ttl : ((ttl+500)/1000));
    }
}

/* 
 * 傳回給定 key 的過期時間。
 *
 * 如果鍵沒有設定過期時間，那麼傳回 -1 。
 */
long long getExpire(redisDb *db, robj *key) {
    dictEntry *de;

    /* No expire? return ASAP */
    // 擷取鍵的過期時間
    // 如果過期時間不存在，那麼直接傳回
    if (dictSize(db->expires) == 0 ||
       (de = dictFind(db->expires,key->ptr)) == NULL) return -1;

    /* The entry was found in the expire dict, this means it should also
     * be present in the main dict (safety check). */
    redisAssertWithInfo(NULL,key,dictFind(db->dict,key->ptr) != NULL);

    // 傳回過期時間
    return dictGetSignedIntegerVal(de);
}

redis TTL實作原理

TTL存儲的資料結構

TTL 設定過期時間

expire expireat pexpire pexpireat

TTL 擷取過期時間

繼續閱讀

《Linux指令行與Shell腳本程式設計大全第2版.布盧姆》pdf

禁止ubuntu系統彈出報錯界面

MySQL的4種隔離級别？出現問題

Ubuntu Linux下Apache的配置檔案

XX系統實施過程問題總結

無元件上傳圖檔到資料庫中，最完整解決方案

【MySQL資料庫】資料庫索引事務1.索引2.事務

neo4j之cypher使用文檔

NOSQL安全攻擊

mybatis_入門程式Mybatis入門

samba伺服器的功能

登入plsql 報錯 the account is locked --使用者被鎖

【Linux】UDP廣播封包接收速率問題

SequoiaDB巨杉資料庫C++驅動概述

Linux裝置模型（中）之上層容器

PowerPC平台 Linux移植三