はじめに
2017年7月にリリースされたredis4.0から、特定のキーの値を非同期的に削除するUNLINKコマンドがでました。
UNLINKコマンドの既存のDELコマンドとの違いついてまとめます。
redis4.0系リリース
2017年7月にredis4.0系がリリースされました。
主な機能に関しては、下記のqiitaの記事にまとめられています。
qiita.com
redis4.0.0のリリースノートは下記のリンクで見ることができます。
https://raw.githubusercontent.com/antirez/redis/4.0/00-RELEASENOTES
若干読みづらいですが、 UNLINKに関する記述を抜粋します。
Lazy freeing of keys. Redis is now able to delete keys in the background in a different thread without blocking the server.
The new UNLINK
command is the same as DEL
but working in a non blocking way.
UNLINKコマンドが生まれた経緯 シングルスレッドモデルにおける DELコマンドの問題点
redisはシングルスレッドモデルのため、既存のDELコマンドの場合だと 複数のクライアントからクエリを実行された時、1つのキューに並んで順番に処理されます。
そのため、データサイズの大きいデータセットに対してDELを実行すると、計算量が大きいため、後続の処理が遅れて大きなパフォーマンス低下の要因となってしまいます。
今回4.0系で登場したUNLINKは、ある値を削除する際にこの問題を解決するコマンドです。
UNLINKを使ったクエリが実行された際、文字通り、指定されたキーの値を即座に削除せず、非同期的にデータセット内のキーを格納したキースペースからUNLINKされ、実際のデータは後に削除されます。
これにより、ノンブロッキングな処理が可能となります。
クエリの実行的には即座に完了し、データセットのサイズに関係なく定数時間 O(1)で処理が完了します。
同時に複数のキーを指定した場合は キーの数N 文の時間の計算量O(N)となります。
UNLINKの内部処理を見る
UNLINKコマンドの内部処理が気になったので、githubに上がっているredisのソースを読んでみました。
関連のソースは、 src/lazyfree.cあたりにまとまっています。
UNLINKが実行されたときに、dbAsyncDeleteと呼ばれる関数が呼ばれます。
https://github.com/antirez/redis/blob/unstable/src/lazyfree.c#L49-L85
文字通り、データを非同期的に削除する処理を行っています。
#define LAZYFREE_THRESHOLD 64
int dbAsyncDelete(redisDb *db, robj *key) {
if (dictSize(db->expires) > 0) dictDelete(db->expires,key->ptr);
dictEntry *de = dictUnlink(db->dict,key->ptr);
if (de) {
robj *val = dictGetVal(de);
size_t free_effort = lazyfreeGetFreeEffort(val);
if (free_effort > LAZYFREE_THRESHOLD) {
atomicIncr(lazyfree_objects,1);
bioCreateBackgroundJob(BIO_LAZY_FREE,val,NULL,NULL);
dictSetVal(db->dict,de,NULL);
}
}
if (de) {
dictFreeUnlinkedEntry(db->dict,de);
if (server.cluster_enabled) slotToKeyDel(key);
return 1;
} else {
return 0;
}
}
さらに内部を辿っていくと、 src/dict.cの方で dictGenericDeleteと呼ばれるstatic関数を呼び出しています。
これは、データセット内の特定のキーへのリンクを解除しています。
https://github.com/antirez/redis/blob/06263485d46696ba76a653d2b594f3493103c001/src/dict.c#L361-L399
/* Search and remove an element. This is an helper function for
* dictDelete() and dictUnlink(), please check the top comment
* of those functions. */
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
unsigned int h, idx;
dictEntry *he, *prevHe;
int table;
if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;
if (dictIsRehashing(d)) _dictRehashStep(d);
h = dictHashKey(d, key);
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;
he = d->ht[table].table[idx];
prevHe = NULL;
while(he) {
if (key==he->key || dictCompareKeys(d, key, he->key)) {
/* Unlink the element from the list */
if (prevHe)
prevHe->next = he->next;
else
d->ht[table].table[idx] = he->next;
if (!nofree) {
dictFreeKey(d, he);
dictFreeVal(d, he);
zfree(he);
}
d->ht[table].used--;
return he;
}
prevHe = he;
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return NULL; /* not found */
}
更に細かくは見れていないですが、 データセットは内部的にlinked listのようなデータ構造でリストを保持していて、
dictGenericDelete内では、対象のキーへの参照を外すことで、UNLINKを行っているようです。
上記のコードをのwhileループ内の処理を抜粋してみると、おぼろげながらも理解ができるかと思います。
while(he) {
if (key==he->key || dictCompareKeys(d, key, he->key)) {
if (prevHe)
prevHe->next = he->next;
else
d->ht[table].table[idx] = he->next;
if (!nofree) {
dictFreeKey(d, he);
dictFreeVal(d, he);
zfree(he);
}
d->ht[table].used--;
return he;
}
prevHe = he;
he = he->next;
}
dictGenerictDeleteの第3引数nofree は2値の値で、1の場合は、直接データを消さずに参照だけ外し、
0の場合は直接データを消す、つまりメモリをfreeしているようです。
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
実際には下記の用な感じで呼び出されています。
nofree == 0 つまりメモリをfreeさせる場合
/* Remove an element, returning DICT_OK on success or DICT_ERR if the
* element was not found. */
int dictDelete(dict *ht, const void *key) {
return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
}
nofree == 1 つまり 今回紹介したUNLINKのように参照を外す場合
/* Remove an element from the table, but without actually releasing
* the key, value and dictionary entry. The dictionary entry is returned
* if the element was found (and unlinked from the table), and the user
* should later call `dictFreeUnlinkedEntry()` with it in order to release it.
* Otherwise if the key is not found, NULL is returned.
*
* This function is useful when we want to remove something from the hash
* table but want to use its value before actually deleting the entry.
* Without this function the pattern would require two lookups:
*
* entry = dictFind(...);
* // Do something with entry
* dictDelete(dictionary,entry);
*
* Thanks to this function it is possible to avoid this, and use
* instead:
*
* entry = dictUnlink(dictionary,entry);
* // Do something with entry
* dictFreeUnlinkedEntry(entry); // <- This does not need to lookup again.
*/
dictEntry *dictUnlink(dict *ht, const void *key) {
return dictGenericDelete(ht,key,1);
}
という感じになります。 このあたりの実装は読んでいて非常に勉強になるので、redisを使っている方は読んでみることをおすすめします。
まとめ
redis4.0系から、データセット内の特定のキーを非同期で削除できるUNLINKコマンドが追加されました。
UNLINKは、DELとは異なり、実際にクエリが実行されたときにデータを削除せず、あくまでデータセット内からキーの参照を非同期で UNLINKしています。
これにより、シングルスレッドモデルを採用しているredisで、データ容量が大きい場合にDELによって実行速度が遅くなってしまう問題を解消できます。
実際にパフォーマンスについては今回検証できていないですが、redis4.0系以上を使う場合は UNLINKを使うことによって大きくパフォーマンス改善が図れるかと思います。