kakts-log

programming について調べたことを整理していきます

redis 4系から追加されたUNLINKについて

はじめに

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 文字通り、データを非同期的に削除する処理を行っています。

/* 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 == 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を使うことによって大きくパフォーマンス改善が図れるかと思います。