RedisにおけるZSETのZCARD動作の時間的複雑さ

最近ではRedisのZSET構造が用いられるが,あるRedisコマンド紹介サイトにZSETと表記されているZCARDコマンドの複雑さはO(1)である.しかし、私のコードの中でZCARDは頻繁に操作されています.念のため、Redisのソースコードをダウンロードして、ZCARDの操作に関するコードを見つけました.

unsigned long zsetLength(const robj *zobj) {
    unsigned long length = 0;
    if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
        length = zzlLength(zobj->ptr);
    } else if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
        length = ((const zset*)zobj->ptr)->zsl->length;
    } else {
        serverPanic("Unknown sorted set encoding");
    }
    return length;
}

ここでzsetオブジェクトのencodingを判断し,skiplist,すなわちホップテーブルであればlength属性を1つ直接取得すればよい,複雑度はO(1)であるがziplist圧縮チェーンテーブルで格納すると異なることが分かる.関連コードは次のとおりです.

unsigned int ziplistLen(unsigned char *zl) {
    unsigned int len = 0;
    if (intrev16ifbe(ZIPLIST_LENGTH(zl)) < UINT16_MAX) {
        len = intrev16ifbe(ZIPLIST_LENGTH(zl));
    } else {
        unsigned char *p = zl+ZIPLIST_HEADER_SIZE;
        while (*p != ZIP_END) {
            p += zipRawEntryLength(p);
            len++;
        }

        /* Re-store length if small enough */
        if (len < UINT16_MAX) ZIPLIST_LENGTH(zl) = intrev16ifbe(len);
    }
    return len;
}

このコードの意味は、マクロ操作によってziplistの長さが得られ、ziplistの長さがUINT 16_より小さい場合MAX、すなわち16ビット符号なし整数の最大値、65535は、直接戻り、そうでなければziplistを巡って長さを取得する.遍歴すると複雑度はO(N)です.マクロの操作は次のとおりです(理解できませんでした):

/* Return the length of a ziplist, or UINT16_MAX if the length cannot be
 * determined without scanning the whole ziplist. */
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))

著者らの注釈では,ziplistが直接取得できる最大長は実際には2^16−2であり,この数より大きいものはZCARDで遍歴すると述べている.
しかし、RedisがZSETを処理するポリシーは構成可能である.

if (zobj == NULL) {
        if (xx) goto reply_to_client; /* No key + XX option: nothing to do. */
        if (server.zset_max_ziplist_entries == 0 ||
            server.zset_max_ziplist_value < sdslen(c->argv[scoreidx+1]->ptr))
        {
            zobj = createZsetObject();
        } else {
            zobj = createZsetZiplistObject();
        }
        dbAdd(c->db,key,zobj);
    }

このコードから、新しいzsetを作成するときにzset_がmax_ziplist_entriesパラメータが0に等しいか、現在の挿入値の長さがzset-max-ziplist-valueパラメータより大きい場合、createZsetObject関数によってskiplist符号化zset(コードが貼られていない)が作成されます.そうでない場合、ziplist符号化zsetが作成されます.
したがって、confファイルでzset_を構成する限りmax_ziplist_entriesパラメータが0またはzset-max-ziplist-valueパラメータが小さい場合、ziplist構造ではなくskiplist構造が作成されることを保証し、ZCARDの複雑さがO(N)であることを保証することができます.ziplistの長さがzsetより大きい場合max_ziplist_entriesパラメータ設定の長さの場合も、自動的にskiplistに変わります.zset_max_ziplist_entriesのデフォルト値128.