Redisのziplistは、メモリ効率を高めるために設計されたデータ構造です。本記事では、ziplistの内部構造と基本的な操作について詳しく解説します。

1. データ構造

ziplistの全体的な構造は以下のようになっています（Redisのソースコードコメントから引用）：

1 /*
2 <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
3 */

各部分の意味は以下の通りです：

entryの詳細な構造は以下のようになります：

1 /*
2 <prevlen> <encoding> [<entry-data>]
3 */

prevlenは前のentryの長さを示し、逆方向のトラバーサルに使用されます。entryの長さが254未満の場合、1Bで表現できますが、それ以上の場合には5Bが必要となります。

encodingはentryデータの形式を決定します。以下はencodingの詳細です：

例として、"2" と "5" の2つのメンバーを持つziplistを考えます：

/*
[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
      |             |          |       |       |     |
   zlbytes        zltail     zllen    "2"     "5"   end
*/

この例では：

• zlbytes: 15B (全長)
• zltail: 12 (最後のentryのオフセット)
• zllen: 2 (entry数)

2. 基本的な操作

Redisは、多くのマクロ定義と関数を使用してziplistを操作します。

2.1 作成

新しいziplistを作成するための関数は以下のようになっています：

1 #define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
2 #define ZIPLIST_END_SIZE (sizeof(uint8_t))
3 #define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl)))
4 #define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
5 #define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
6 #define ZIP_END 255 
7 
8 unsigned char *ziplistNew(void) {
9     unsigned int bytes = ZIPLIST_HEADER_SIZE + ZIPLIST_END_SIZE;
10     unsigned char *zl = zmalloc(bytes);
11     ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
12     ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
13     ZIPLIST_LENGTH(zl) = 0;
14     zl[bytes-1] = ZIP_END;
15     return zl;
16 }

新しく作成されたziplistは、entryが存在せず、zlbytes、zltail、zllen、zlendのみが含まれています：

1 /*
2 [0b 00 00 00] [0a 00 00 00] [00 00] [ff]
3       |             |          |     |
4    zlbytes        zltail     zllen  end
5 */

2.2 挿入

既存のziplistに新しいentryを挿入する手順を説明します。例えば、"2" と "5" を持つziplistに "3" を挿入する場合：

1 /*
2 [0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
3       |             |          |       |       |     |
4    zlbytes        zltail     zllen    "2"     "5"   end
5 */

手順は以下の通りです：

1. 現在のentry "5" のprevlen (2) と prevlen_size (1) を取得。
2. 新しいentry "3" の実際の長さを取得。数字であれば、より小さなエンコーディングを使用できる。
3. 新しいentryの総長 (prevlen + encoding + entry-data) を計算 (1 + 1 = 2)。
4. 次のentryのprevlenが十分かどうか確認。
5. ziplistのスペースを再確保。
6. "5" 以降のentryを後ろに移動。
7. 新しいentry "3" を挿入。
8. zllenを更新。

2.3 検索

ziplistの検索は、entryを順番に解析しながら行われます。prevlen、encoding、entry-dataを解析し、比較を行います。文字列比較または直接の数値比較が行われます。

2.4 削除

最後のentryを削除する場合、zltailとzlbytesを更新し、サイズを調整します。中間のentryを削除する場合は、次のentryのprevlenも更新する必要があります。

例として、"5" を削除する場合：

1 /*
2 [0x118] [0x115] [04 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [06 f6] [ff]
3    |       |       |       |          |                 |             |
4 zlbytes  zltail  zllen    "2"         X                "3"           "5"  
5    4B      4B                        259B
6 */

手順は以下の通りです：

1. zltailを更新。
2. サイズを調整。
3. zllenを更新。

中間のentry "3" を削除する場合：

1 /*
2 [0x118] [0x115] [04 00] [00 41 00 ...] [FE 00 00 01 03 f4] [06 f3] [02 f6] [ff]
3    |       |       |          |                 |             |       |
4 zlbytes  zltail  zllen        X                "3"           "2"     "5"  
5    4B      4B                259B
6 */

手順は以下の通りです：

1. 次のentry "2" のprevlenを更新。
2. zltailを更新。
3. memmoveでデータを移動。
4. サイズを調整。
5. 必要に応じて連鎖的にprevlenを更新。