読者です 読者をやめる 読者になる 読者になる

愛と勇気と缶ビール

ふしぎとぼくらはなにをしたらよいか

一体いつからRedisがSorted Setの実装にSkip Listしか使ってないと錯覚していた?

Redis

デフォルトの設定 (zset-max-ziplist-entries, zset-max-ziplist-value) では

  • 該当するSorted Setのエントリ数が128個以下
  • 該当するSorted Setに含まれるmember (not score) のデータ長が全て64byte以下

という2つの条件が成立している場合、Sorted Setの表現にはSkip ListではなくZip Listというデータ構造が使われる。ZADD, ZCOUNT等の実装もどちらのデータ構造を使っているかのフラグで分岐している。

Zip Listはポインタを使わずデータとそのオフセットだけで表現された双方向リストであるため、空間効率はよいが全体のサイズが大きくなるとすぐ使えなくなる。

Redisにおいては、Sorted Setへのinsertに際して上記条件のどちらかが満たされなくなった場合にZip ListからSkip Listへの変換が自動的に行われる。

実際にSorted Setがどちらのデータ構造でエンコーディングされているかは以下のコマンドで確認可能。

object encoding {key}

128個以下のデータしか入っていないSorted Setにおけるパフォーマンスなんか気にする人はあまりいないと思われるので、これはほとんど知る必要もない「実装の詳細」に近いレベルの話である。「RedisのSorted SetはSkip Listで実装されてるんだよ」と言って厳密なモヒカン族に狩られないための、豆知識程度に。