RedisのHash型を活用するとメモリ使用量が激減

ユーザ情報のように ID をキーにした大量のデータを Redis で管理する場合、ひと工夫して Hash 型を使うと、単純に string 型を使った場合に比べてメモリ使用量が激減することを教わったので、追試してみた。

データモデル

String 型を使う

各 ID のデータを Redis で管理する場合、素直にやるなら string 型で保存する。

> set object:123456 val123456
OK
> get object:123456
"val123456"

非常に原始的なキーとバリューのペア。

Hash 型を使う

Redis 2.2 以降では hash が機能改善され、フィールド数が一定数におさまり、フィールドのデータが一定サイズに収まると、メモリ使用量が平均して 1/5 に軽減されている。

Special encoding of small aggregate data types
Since Redis 2.2 many data types are optimized to use less space up to a certain size. Hashes, Lists, Sets composed of just integers, and Sorted Sets, when smaller than a given number of elements, and up to a maximum element size, are encoded in a very memory efficient way that uses up to 10 times less memory (with 5 time less memory used being the average saving).
http://redis.io/topics/memory-optimization

この特性をいかし、ID を一定数ごとにバケットで束ねて ハッシュ型で分割管理すると、メモリ使用量が大幅に削減される。

具体的には

object_id = bukect_id x BUCKET_SIZE + field_id (0 <= field_id < BUCKET_SIZE)

となるように bucket_id と field_id を決定する。仮に、 BUCKET_SIZE を 500 とすると 123456 = 246 * 500 + 456 となる。

Redis の ハッシュ型では HSET/HGET を使って、次のようにできる。

> hset object:246 456 val123456
(integer) 1
> hget object:246 456
"val123456"

メモリ使用量の比較

問題は String 型と Hash 型でメモリ使用量にどのくらい差がつくのか?

バケットサイズ 500 にして 100 万オブジェクトを String/Hash 型でつっこみ、INFO コマンドの used_memory でメモリ使用量を確認する。(Instagram のテストプログラムを流用)

計測すると String 型は 69 MB 消費するのに対し、Hash 型はわずか 16 MB しか消費しない。

String 型

$ python redis-memory-test.py redis-normal
531168 bytes, 0 MB
0
100000
200000
300000
400000
500000
600000
700000
800000
900000
72905552 bytes, 69 MB

$ redis-cli info memory
# Memory
used_memory:72904840
used_memory_human:69.53M
used_memory_rss:75907072
used_memory_peak:72904752
used_memory_peak_human:69.53M
used_memory_lua:31744
mem_fragmentation_ratio:1.04
mem_allocator:jemalloc-3.2.0

Hash 型

$ python redis-memory-test.py redis-hashes
552096 bytes, 0 MB
0
100000
200000
300000
400000
500000
600000
700000
800000
900000
17079456 bytes, 16 MB

$ redis-cli info memory
# Memory
used_memory:17057816
used_memory_human:16.27M
used_memory_rss:20127744
used_memory_peak:33764856
used_memory_peak_human:32.20M
used_memory_lua:31744
mem_fragmentation_ratio:1.18
mem_allocator:jemalloc-3.2.0

最適化されていない Hash 型

“smaller than a given number of elements, and up to a maximum element size” である限り、データは zipmap で管理され、メモリ効率が良くなる。閾値をこえると、通常のハッシュテーブルで管理される。この閾値は redis.conf で設定する。Hash 型の場合、次の hash-max-ziplist-entries と hash-max-ziplist-value が相当する。

# Hashes are encoded using a memory efficient data structure when they have a
# small number of entries, and the biggest entry does not exceed a given
# threshold. These thresholds can be configured using the following directives.
hash-max-ziplist-entries 512
hash-max-ziplist-value 64

• hash-max-ziplist-entries は 1バケットあたりのフィールドの数。
• hash-max-ziplist-value はフィールドの最大サイズ(byte)

バケットサイズ 500 のまま hash-max-ziplist-entries を 128 に変更してハッシュ型で保存すると、内部的には zipmap から hash table に変わるため、メモリ使用量も跳ね上がる。

$ python redis-memory-test.py redis-hashes
531168 bytes, 0 MB
0
100000
200000
300000
400000
500000
600000
700000
800000
900000
57045040 bytes, 54 MB

$ redis-cli info memory
# Memory
used_memory:57044328
used_memory_human:54.40M
used_memory_rss:80826368
used_memory_peak:70662648
used_memory_peak_human:67.39M
used_memory_lua:31744
mem_fragmentation_ratio:1.42
mem_allocator:jemalloc-3.2.0

閾値の決定は実際のアプリに合わせてチューニングが必要。

メモリ使用量をグラフで比較

ziplist のデータ構造

Redis-CLI からもキーが ziplist でエンコードされ(DEBUG OBJECT KEY)、どういうバイト列でエンコードされているのか(DUMP KEY)確認できる。

redis 127.0.0.1:6379> debug object foo
Value at:0x7f91acc83aa0 refcount:1 encoding:ziplist serializedlength:24 lru:2061650 lru_seconds_idle:0
redis 127.0.0.1:6379> dump foo
"\n\x17\x17\x00\x00\x00\x13\x00\x00\x00\x03\x00\x00\x03ccc\x05\x02bb\x04\x01a\xff\x06\x00\xccP\xab<\x87H\x9e\""

ziplist のデータ構造は src/ziplist.c のヘッダー部分のコメントやこのソースコードを元にした RDB ファイルフォーマットの解説を参考にすると良い。

References

• Redis Documentation : Memory optimization: Understand how Redis uses RAM and learn some tricks to use less of it.
  http://redis.io/topics/memory-optimization
• Instagram : Storing hundreds of millions of simple key-value pairs in Redis
  http://instagram-engineering.tumblr.com/post/12202313862/storing-hundreds-of-millions-of-simple-key-value-pairs
  http://news.ycombinator.com/item?id=3183276
• Redis ML : Understanding hash-max-zipmap-xxx values
  https://groups.google.com/forum/?fromgroups=#!topic/redis-db/9qM9iSeRAA4
• 作者の @antirez による Redis 2.2 で導入した Hash エンコードについてのノート
  http://oldblog.antirez.com/post/redis-weekly-update-7.html
• Josiah L. Carlson : “Redis In Action”, Manning Publications Co., 2013.
  “Ch. 9 Reducing memory use” に ziplist についての解説がある。