Redis期限切れキー削除ポリシーおよびソースプロファイル
21754 ワード
一、何が期限切れのキーで、期限切れのキーはどのように保存します
Redisはキー値ペアに有効期限を設定することができ,このことはEXPIRE,PEXPIRE,EXPIREAT,PEXPIREATの4つのコマンドによって実現される.Redisデータベースは主に2つの辞書で構成されており、1つの辞書はキー値ペアを保存し、もう1つの辞書は保存された期限切れキーの期限切れ時間であり、この辞書を期限切れ辞書と呼ぶ.
typedef struct redisDb
{
dict *dict;
dict *expires;
....
}二、期限切れキーの削除ポリシー
総じて、期限切れキーには、タイミング削除、不活性削除、定期削除の3つの削除ポリシーがあります.1、タイミング削除:タイマーをメンテナンスすることで、期限が切れたらすぐに削除するのが最も有効ですが、cpu時間を最も浪費します.2、不活性削除:プログラムはキーを取り出したときに期限が切れたかどうかを判断し、期限が切れてから削除する.この方法はcpu時間に友好的で、メモリに友好的ではない.3、定期削除:一定時間ごとに期限切れのキーを削除する操作を行い、削除するたびの実行時間と頻度を制限する折衷です.Redisは、不活性な削除と定期的な削除のポリシーを採用しています.
三、惰性削除
データベースの読み書きを実行するたびにRedisコマンドは、実行前にキーが期限切れになったかどうかを判断し、期限切れになった場合は削除し、期限切れになっていない場合は何もしません.これは濾過されたものに相当します.読み書き検査が期限切れになるたびに、この考え方は漸進的なrehashのように、コマンドを実行するたびの操作に多くの操作を分散させ、できるだけ効率を高めます.
この不活性削除関数はdbである.cのexpireIfNeeded関数で実現される.このように成長しています
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 */
/* Don't expire anything while loading. It will be done later. */
// ，
if (server.loading) return 0;
/* If we are in the context of a Lua script, we claim that time is
* blocked to when the Lua script started. This way a key can expire
* only the first time it is accessed and not in the middle of the
* script execution, making propagation to slaves / AOF consistent.
* See issue #1525 on Github for more information. */
now = server.lua_caller ? server.lua_time_start : mstime();
/* If we are running in the context of a slave, return ASAP:
* the slave key expiration is controlled by the master that will
* send us synthesized DEL operations for expired keys.
*
* Still we try to return the right information to the caller,
* that is, 0 if we think the key should be still valid, 1 if
* we think the key is expired at this time. */
// replication
// key
//
//
//
if (server.masterhost != NULL) return now > when;
// ， ，
/* Return when this key has not expired */
// ， 0
if (now <= when) return 0;
/* Delete the key */
server.stat_expiredkeys++;
// AOF
propagateExpire(db,key);
//
notifyKeyspaceEvent(REDIS_NOTIFY_EXPIRED,
"expired",key,db->id);
//
return dbDelete(db,key);
}
この関数は実は簡単です.まず、このキーに期限が切れているかどうかを判断します.つまり、expiresという辞書に期限が切れているかどうかを判断します.ない場合は、戻り、ある場合は削除操作を実行します.
ここでは、レプリケーションモードで実行している場合、サーバから期限切れキーを自発的に削除しないため、プライマリサーバの削除コマンドを受信して削除操作を行う必要があることにも注意してください.プライマリ・サーバが自分で削除すると、サーバから削除されたことを通知する通知が送信されます.
expireIfNeeded関数では、Redisの下位データ構造を復習したり熟知したりするためにgetExpire関数も呼び出されます.
long long getExpire(redisDb *db, robj *key) {
dictEntry *de;
/* No expire? return ASAP */
//
// ，
// dictSize: ht[0].used + ht[1].used
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);
}この関数は、データベースredisDbとキーオブジェクトを受け入れ、キーオブジェクトは文字列オブジェクトです.オブジェクトの構造は次のとおりです.
typedef struct redisObject
{
unsigned type: 4;
unsigned enconding : 4;
...
void *ptr;
}このptrはsds,embstr,listなどの下層実装を指す.「de=dictFind(db->expires,key->ptr)」という関数を呼び出すことで、辞書のエントリ(dictEntry)を返すことができます.expiresもdictで実現されるので、dictEntryでキー値ペアを保存します.
不活性削除の使用シーンを見てください:キーの値を取り出すときに、不活性削除操作を実行できるかどうかを確認します.
*
* key db 。
*
* ， / 。
*
* ， NULL 。
*/
robj *lookupKeyRead(redisDb *db, robj *key) {
robj *val;
// key
// ， ，
// ， ， ， ，
expireIfNeeded(db,key);
//
val = lookupKey(db,key);
// /
// ：stat_keyspace_hits
// ：stat_keyspace_misses
if (val == NULL)
server.stat_keyspace_misses++;
else
server.stat_keyspace_hits++;
//
return val;
}
四、定期的に削除
定期的な削除は、acticeExpireCycle関数によって実現されます.この関数には、各操作の時間と頻度を制限するポリシーが必要です.だから複雑です.でも注釈も詳しくて読めます.
void activeExpireCycle(int type) {
/* This function has some global state in order to continue the work
* incrementally across calls. */
// ，
// current_db
static unsigned int current_db = 0; /* Last DB tested. */
static int timelimit_exit = 0; /* Time limit hit in previous call? */
//
static long long last_fast_cycle = 0; /* When last fast cycle ran. */
unsigned int j, iteration = 0;
// ， redis.h 16
unsigned int dbs_per_call = REDIS_DBCRON_DBS_PER_CALL;
//
long long start = ustime(), timelimit;
//
if (type == ACTIVE_EXPIRE_CYCLE_FAST) {
/* Don't start a fast cycle if the previous cycle did not exited
* for time limt. Also don't repeat a fast cycle for the same period
* as the fast cycle total duration itself. */
// timelimit_exit ，
if (!timelimit_exit) return;
// ，
// ACTIVE_EXPIRE_CYCLE_FAST_DURATION = 1000
if (start < last_fast_cycle + ACTIVE_EXPIRE_CYCLE_FAST_DURATION*2) return;
// ， ，
last_fast_cycle = start;
}
/* We usually should test REDIS_DBCRON_DBS_PER_CALL per iteration, with
* two exceptions:
*
* ， REDIS_DBCRON_DBS_PER_CALL ，
* ：
*
* 1) Don't test more DBs than we have.
* REDIS_DBCRON_DBS_PER_CALL
* 2) If last time we hit the time limit, we want to scan all DBs
* in this iteration, as there is work to do in some DB and we don't want
* expired keys to use memory for too much time.
* ， ，
*
*/
if (dbs_per_call > server.dbnum || timelimit_exit)
dbs_per_call = server.dbnum;
/* We can use at max ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC percentage of CPU time
* per iteration. Since this function gets called with a frequency of
* server.hz times per second, the following is the max amount of
* microseconds we can spend in this function. */
//
// ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC 25 ， 25 % CPU
timelimit = 1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100;
// 0 ， 1
timelimit_exit = 0;
if (timelimit <= 0) timelimit = 1;
//
// FAST_DURATION
// 1000 （ ）
if (type == ACTIVE_EXPIRE_CYCLE_FAST)
timelimit = ACTIVE_EXPIRE_CYCLE_FAST_DURATION; /* in microseconds. */
//
for (j = 0; j < dbs_per_call; j++) {
int expired;
//
redisDb *db = server.db+(current_db % server.dbnum);
/* Increment the DB now so we are sure if we run out of time
* in the current DB we'll restart from the next. This allows to
* distribute the time evenly across DBs. */
// DB ， do
// DB
current_db++;
/* Continue to expire if at the end of the cycle more than 25%
* of the keys were expired. */
do {
unsigned long num, slots;
long long now, ttl_sum;
int ttl_samples;
/* If there is nothing to expire try next DB ASAP. */
//
// 0 ，
// dictSize: ht[0].used + ht[1].used
if ((num = dictSize(db->expires)) == 0) {
// TTL，
// TTL:
db->avg_ttl = 0;
break;
}
//
// dictSlots:ht[0].size + ht[1].size
// dictSize
slots = dictSlots(db->expires);
// ，mstime: UNIX
now = mstime();
/* When there are less than 1% filled slots getting random
* keys is expensive, so stop here waiting for better times...
* The dictionary will be resized asap. */
// 1% ， （ MISS）
// ，
// DICT_HT_INITIAL_SIZE 4
if (num && slots > DICT_HT_INITIAL_SIZE &&
(num*100/slots < 1)) break;
/* The main collection cycle. Sample random keys among keys
* with an expire set, checking for expired ones.
*
*
*/
//
expired = 0;
// TTL
ttl_sum = 0;
//
ttl_samples = 0;
// LOOKUPS_PER_LOOP , 20
if (num > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP)
num = ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP;
//
while (num--) {
dictEntry *de;
long long ttl;
// expires
if ((de = dictGetRandomKey(db->expires)) == NULL) break;
// TTL
// dictGetSignedIntegerVal dictEntry，
ttl = dictGetSignedIntegerVal(de)-now;
// ， ， expired
if (activeExpireCycleTryExpire(db,de,now)) expired++;
if (ttl < 0) ttl = 0;
// TTL
ttl_sum += ttl;
//
ttl_samples++;
}
/* Update the average TTL stats for this database. */
// TTL
if (ttl_samples) {
//
long long avg_ttl = ttl_sum/ttl_samples;
// TTL ，
if (db->avg_ttl == 0) db->avg_ttl = avg_ttl;
/* Smooth the value averaging with the previous one. */
// TTL TTL
db->avg_ttl = (db->avg_ttl+avg_ttl)/2;
}
/* We can't block forever here even if there are many keys to
* expire. So after a given amount of milliseconds return to the
* caller waiting for the other active expire cycle. */
// ，
//
// ，
iteration++;
// 16
if ((iteration & 0xf) == 0 && /* check once every 16 iterations. */
(ustime()-start) > timelimit)
{
// 16
// timelimit
// timelimit_exit
timelimit_exit = 1;
}
// ，
if (timelimit_exit) return;
/* We don't repeat the cycle if there are less than 25% of keys
* found expired in the current DB. */
// 25 %
//
} while (expired > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4);
}
}ここで注意すべきは、時間制限は
timelimit = 1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100;によって実現され、0.25 cpu時間である.周波数制限はiterationによって実現され,16データベースを遍歴すると終了する.
redisDbという構造体にはもう一つのavg_ttlメンバー、このメンバーはデータベースのキー平均TTLを統計するために使用される統計であり、activeExpireCycleではサンプリングによって計算され、ランダム抽出(呼び出されたdictGetRandomKey関数)からのキー値ペアで計算されるこの値である.
このデータベースの使用率(used/size)が低いと、スキャンが難しくなり、辞書の縮小を待って次の操作が行われます.