インメモリデータストアを現代風に再実装したら?

高速なデータアクセスのためのインメモリデータストアとしては、RedisやMemcachedが有名です。ただし、これらは10年以上前に設計されており、Memcachedに至っては、2003年と約20年前です。

長い年月を経て、機能追加や最適化が進む一方で、どうしても設計の古さも目立ってきます。

その課題を解決すべく開発されたのがDragonfly です。

全ての操作がアトミック
高スループットでもミリ秒未満のスループット

を目指し、Redis/Memcached互換なAPIを提供します。

Redisの25倍のスループットを誇り、1インスタンスで百万オーダーのQPSをさばけます。

開発者が実施したAWS EC2上のベンチマークによると、Dragonflyは本家RedisやRedisのマルチスレッドforkであるKeyDBよりも圧倒的なスループットを誇り、c6gn.16xlarge インスタンスタイプでは、GET/SET コマンドで 400万 QPS を叩き出しています。

コマンドをパイプライン化すると(N=10)、SET で 1000万 QPS、GET で 1500万 QPS まで到達するそうです。

When running in pipeline mode --pipeline=30, Dragonfly reaches 10M qps for SET and 15M qps for GET operations.
https://github.com/dragonflydb/dragonfly/blob/main/README.md

動かしてみる

DragonflydbahはLinuxカーネル5.1で追加された高速・効率的なI/Oを実現する io_uring
に依存します。最近のLinuxカーネルを利用したディストリビューション(Ubuntu 20.04など)を利用しましょう。

Docker

Dockerを利用する場合、以下の手順でサーバーを起動します。

$ docker pull docker.dragonflydb.io/dragonflydb/dragonfly && \
docker tag docker.dragonflydb.io/dragonflydb/dragonfly dragonfly

$ docker run --network=host --ulimit memlock=-1 --rm dragonfly

ソースコードからビルド

Ubuntu 20.04/22.04 では以下の手順でサーバーを起動します。

$ git clone --recursive https://github.com/dragonflydb/dragonfly && cd dragonfly

# to install dependencies
$ sudo apt install ninja-build libunwind-dev libboost-fiber-dev libssl-dev \
     autoconf-archive libtool cmake g++

# Configure the build
$ ./helio/blaze.sh -release

# Build
$ cd build-opt && ninja dragonfly

# Run
$ ./dragonfly --alsologtostderr

クライアントから接続

クライアントプログラムをインストールし、 redis-cli から接続しましょう。

$ sudo apt install -y redis-tools

$ redis-cli PING         # 同じホストの場合
$ redis-cli -h HOST PING

Dragonflyを支える技術

Dragonflyの高性能を支える技術を IO/CPU とメモリの観点から紹介します。

IO・ CPUをフル活用

Redis の特徴の一つはシングルスレッドで動作することです(例外あり)。マルチコアなサーバーでは、コア数だけRedisを起動させてスケールアウトさせます。

Redis is, mostly, a single-threaded server from the POV of commands execution (actually modern versions of Redis use threads for different things). It is not designed to benefit from multiple CPU cores. People are supposed to launch several Redis instances to scale out on several cores if needed.
https://redis.io/docs/reference/optimization/benchmarks/

スケールアップ戦略を取る Dragonfly はマルチスレッドで動作し、スレッドごとにメモリのキースペースも分離されています。

In our case, I believe that memory store can be designed as a multi-threaded, single-process system that utilizes the underlying CPUs using shared-nothing architecture. In other words, every cpu thread will handle its dictionary partition shard.
https://dragonflydb.io/blog/2021/12/09/single_threaded_redis/

起動時には、デフォルトではコア数分の IO スレッドが立ち上がっているのを確認できます。

$ ./build-opt/dragonfly --alsologtostderr
I20220606 11:06:45.825064  1210 init.cc:56] ./build-opt/dragonfly running in opt mode.
...
I20220606 11:06:45.828279  1210 dfly_main.cc:179] maxmemory has not been specified. Deciding myself....
I20220606 11:06:45.829610  1210 dfly_main.cc:184] Found 61.22GiB available memory. Setting maxmemory to 48.97GiB
I20220606 11:06:45.831333  1217 proactor.cc:456] IORing with 1024 entries, allocated 102720 bytes, cq_entries is 2048
I20220606 11:06:45.832515  1210 proactor_pool.cc:66] Running 8 io threads

この shard-per-core アーキテクチャーは、ScyllaDB で有名になりました。

このアーキテクチャーを支えているのが、ディスク・ネットワークIOのシステムコール io_uring です。
ScyllaDB VPによるLinux IOの発展とio_uringの解説記事は必見です。

How io_uring and eBPF Will Revolutionize Programming in Linux - ScyllaDB

優れたメモリ効率

インメモリデータベースの性質上、効率的にデータを管理できると、消費メモリを削減できます。

Dragonfly はパーシステント・メモリー向けのスケーラブルなハッシュ化 dash tableを用い、Redisに比べて通常時のメモリ消費量を3割減、ピーク時も1/3 に抑えています。dash tableの論文は2020年のProceedings of the VLDB Endowment(PVLDB)に掲載されています。

debug populate 5000000 key 1024 コマンドで大量のデータを生成し、info memoryコマンドでメモリ消費量を確認します。

Redis

# Memory
used_memory:6748017016
used_memory_human:6.28G
used_memory_rss:6811791360
used_memory_rss_human:6.34G
used_memory_peak:6748017016
used_memory_peak_human:6.28G
used_memory_peak_perc:100.00%
used_memory_overhead:267974000
used_memory_startup:844608
used_memory_dataset:6480043016
used_memory_dataset_perc:96.04%
allocator_allocated:6748020048
allocator_active:6748311552
allocator_resident:6812098560
total_system_memory:16444010496
total_system_memory_human:15.31G
used_memory_lua:32768
used_memory_lua_human:32.00K
used_memory_scripts:0
used_memory_scripts_human:0B
number_of_cached_scripts:0
maxmemory:0
maxmemory_human:0B
maxmemory_policy:noeviction
allocator_frag_ratio:1.00
allocator_frag_bytes:291504
allocator_rss_ratio:1.01
allocator_rss_bytes:63787008
rss_overhead_ratio:1.00
rss_overhead_bytes:-307200
mem_fragmentation_ratio:1.01
mem_fragmentation_bytes:63817080
mem_not_counted_for_evict:0
mem_replication_backlog:0
mem_clients_slaves:0
mem_clients_normal:20528
mem_aof_buffer:0
mem_allocator:jemalloc-5.1.0
active_defrag_running:0
lazyfree_pending_objects:0
lazyfreed_objects:0

Dragonfly

# Memory
used_memory:4715268264
used_memory_human:4.39GiB
used_memory_peak:4715268264
comitted_memory:5169545216
used_memory_rss:4742283264
used_memory_rss_human:4.42GiB
object_used_memory:4480000000
table_used_memory:231662480
num_buckets:6021120
num_entries:5000000
inline_keys:5000000
strval_bytes:4480000000
listpack_blobs:0
listpack_bytes:0
small_string_bytes:4480000000
maxmemory:12728523161
maxmemory_human:11.85GiB
cache_mode:store

used_memory_human からわかるように、 Redis : Dragonfly = 6.28 GiB: 4.39 GiB とほぼ3割減ですね。

2システム間でトータルのメモリ消費量(used_memory)のようなざっくりとした比較は可能ですが、そもそもデータ構造がことなるため、ブレイクダウンした個別の比較は単純にはできません。例えば、Redisだと、メタデータ(used_memory_overhead)と実データ(used_memory_dataset)を明確に分離していますが、Dragonflyは、ケースによって分離したり、インラインにしたり(inline_keys)します。

また、TTLつきのデータ管理も、大幅に効率化されています。

技術詳細は次のドキュメントで解説されています。

dragonfly/dashtable.md at main · dragonflydb/dragonfly

Dragonfly は発展途上

Dragonfly はまだ開発中のソフトウェアとみなすのが良いでしょう。

Pub/Sub
タイムシリーズデータ構造

を含め、実装されていないコマンド・データ型が存在します。

また、運用面でも、レプリケーションに対応していないため、インスタンス障害時のフェイルオーバー先が存在せず、高可用な運用は難しいなど、いくつかの課題があります。

とはいえ、Memcached/Redisは設計が古く、改善するようなデータベースがポツポツ出てきている。この流れに、新たに Dragonfly というデータベースが登場したことは、覚えておいても損はないと思います。

簡易ベンチマーク

現時点で、Dragonfly プロジェクトからは再現性のあるベンチマーク方法が提供されていません。

Seek for help on benchmarking of Dragonfly and KeyDB in Kubernetes · Issue #113 · dragonflydb/dragonfly

この前提の上で、AWS上で実施した簡易ベンチマーク結果を共有します。

EC2 /ElacheCache インスタンスタイプ : cache.r6g.2xlarge
サーバーとクライアントは別インスタンス
バージョン
- Redis : 6.2
- Dragonfly : 0.1
VPC : 同じサブネット
ElastiCache/Redis on EC2
- レプリケーションなし
- 非クラスターモード

redis-benchmark

コマンド : $ redis-benchmark -q --threads 8 -c 50 -n 100000 -h HOST

Command	Dragonfly on EC2	Redis on EC2	Elasticache
PING_INLINE	139470.02	139275.77	142653.36
PING_BULK	139664.8	140056.03	140845.08
SET	142045.45	135869.56	138888.89
GET	144717.8	138504.16	139860.14
INCR	140646.97	141043.72	139860.14
LPUSH	140646.97	136425.66	140056.03
RPUSH	143061.52	140646.97	140646.97
LPOP	144300.14	137741.05	141442.72
RPOP	145985.41	138121.55	140252.45
SADD	149253.73	139275.77	136239.78
HSET	149700.61	139860.14	141043.72
SPOP	150602.42	139470.02	140845.08
ZADD	149253.73	142450.14	141043.72
ZPOPMIN	147275.41	138696.25	141442.72
LPUSH (needed to benchmark LRANGE)	149031.3	136986.3	140845.08
LRANGE_100 (first 100 elements)	91491.3	83333.33	75700.23
LRANGE_300 (first 300 elements)	40306.33	39416.63	33388.98
LRANGE_500 (first 450 elements)	28050.49	27746.95	23359.03
LRANGE_600 (first 600 elements)	21758.05	21321.96	18224.89
MSET (10 keys)	146412.88	118483.41	113507.38

ほぼ差がないです。クライアント側でなにかサチっていそうですね。

memtier_benchmark

memtier_benchmark は ReidsLabs が開発するRedisベンチマークツールです。

Dragonflyのベンチマークは memtier_benchmark で実施されています。

コマンド $ memtier_benchmark --ratio 1:1 -t 8 -c 50 -n 10000 --hide-histogram --pipeline=10 -s HOST

Set Ops/sec

Engine	Ops/sec
Dragon on EC2	1937809.87
Redis on EC2	360974.02
ElastiCache	438172.64

Dragonflyの Ops/SecはRedisの4倍程度です。

Set Latency

Engine	Avg. Latency	p50 Latency	p99 Latency	p99.9 Latency
Dragonfly on EC2	1.91089	1.871	3.119	3.807
Redis on EC2	4.5627	3.967	7.871	8.319
ElastiCache	5.53104	5.535	6.335	8.255

DragonflyのレイテンシーはRedisの半分程度です。

Discussion