はじめに
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
UNLINKcommand is the same asDELbut 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 文字通り、データを非同期的に削除する処理を行っています。
/* Delete a key, value, and associated expiration entry if any, from the DB. * If there are enough allocations to free the value object may be put into * a lazy free list instead of being freed synchronously. The lazy free list * will be reclaimed in a different bio.c thread. */ #define LAZYFREE_THRESHOLD 64 int dbAsyncDelete(redisDb *db, robj *key) { /* Deleting an entry from the expires dict will not free the sds of * the key, because it is shared with the main dictionary. */ if (dictSize(db->expires) > 0) dictDelete(db->expires,key->ptr); /* If the value is composed of a few allocations, to free in a lazy way * is actually just slower... So under a certain limit we just free * the object synchronously. */ dictEntry *de = dictUnlink(db->dict,key->ptr); if (de) { robj *val = dictGetVal(de); size_t free_effort = lazyfreeGetFreeEffort(val); /* If releasing the object is too much work, let's put it into the * lazy free list. */ if (free_effort > LAZYFREE_THRESHOLD) { atomicIncr(lazyfree_objects,1); bioCreateBackgroundJob(BIO_LAZY_FREE,val,NULL,NULL); dictSetVal(db->dict,de,NULL); } } /* Release the key-val pair, or just the key if we set the val * field to NULL in order to lazy free it later. */ 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)) { /* 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; }
dictGenerictDeleteの第3引数nofree は2値の値で、1の場合は、直接データを消さずに参照だけ外し、 0の場合は直接データを消す、つまりメモリをfreeしているようです。
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
実際には下記の用な感じで呼び出されています。
nofree == ０ つまりメモリを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を使うことによって大きくパフォーマンス改善が図れるかと思います。
