Amazon MemoryDB for Redisの論文がSIGMOD 2024で採択されたので読んでみた

Amazon MemoryDB for RedisはAWSが2021年から提供するRedis互換でありながら高速なパフォーマンスと耐久性を兼ね備えたエンタープライズなインメモリデータベースです。このAmazon MemoryDBの仕組みについて説明した論文が、2024年6月にチリ・サンティアゴで開催される国際的なデータベース学会の「SIGMOD/PODS 2024」で採択されました。

• The 2024 ACM SIGMOD/PODS Conference: Santiago, Chile - Welcome
• Amazon MemoryDB: A fast and durable memory-first cloud database - Amazon ScienceBy Yacine Taleb, Kevin McGehee, Nan Yan, Shawn Wang, Stefan Mueller, Allen Samuels2024

Redisは機能が簡単で分かりやすく、Amazon MemoryDBは実際に利用できるサービスなので、論文の内容を具体的にイメージしやすくなっています。

AWSが提供するエンタープライズグレードのRDBであるAmazon Auroraはコンピューティングとストレージが分離されています。 同様に、Amazon MemoryDBでも、Redisコマンドを処理するコンピューティング部分と、耐久性･レプリケーションを担うをストレージ部分を分離することで、Redisの高速なパフォーマンスへのインパクトを最小限にデータの耐久性や一貫性を実現しています。

どのRedis?

論文では主に3種類のRedisが登場します。

本ブログでは、OSS版のRedisを単に「Redis」、AWSが2013年から提供するRedisマネージドサービス版のAmazon ElastiCache for Redisを「ElastiCache」、論文の対象であるAmazon MemoryDB for Redisを「MemoryDB」と呼びます。

MemoryDBはElastiCache Redisで言うところのクラスター版のみ提供され、シャード数、シャードを構成するノード数、ノードタイプ(ノードのスペック)を指定します。

Redisの永続性･レプリケーション機能のおさらい

キャッシュ用途で採用されることの多いインメモリデータベースRedisの永続性を簡単におさらいします。

OSS版のRedisには、ポイント・イン・タイム(PIT)なスナップショット(RDBファイル)と追記型トランザクションログファイル(AOFファイル)の2種類の永続化の仕組みがあります。

スナップショットはfork()して取得するため、親プロセスのメモリが書き換わると、Copy-On-Write(COW)によりメモリページをコピーしてメモリの消費が増えます。 追記ファイルは RPO に合わせて fsync() によるストレージ同期タイミングを制御できます。

また、Redisのレプリケーションは非同期に行われます。

ノード障害が起きると永続化ファイルは失われ、プライマリとレプリカのデータが同じとは限らないため、データロスのリスクがつきまといます。

参考

• Redis persistence | Docs
• Redis replication | Docs

論文まとめ

以下、各章のメモを共有します。

要旨

論文の論旨(Abstract)は短いため、そのまま引用します。

Amazon MemoryDB for Redis is a database service designed for 11 9s of durability with in-memory performance. In this paper, we describe the architecture of MemoryDB and how we leverage open-source Redis, a popular data structure store, to build an enterprise-grade cloud database. MemoryDB offloads durability concerns to a separate low-latency, durable transaction log service, allowing us to scale performance, availability, and durability independently from the in-memory execution engine. We describe how, using this architecture, we are able to remain fully compatible with Redis, while providing single-digit millisecond write and microsecond-scale read latencies, strong consistency, and high availability. MemoryDB launched in 2021.

1 : はじめに

OSS Redisはパフォーマンスに優れている一方で、ローカルストレージに依存した永続化や非同期なレプリケーションのためにデータロスを避けられず、キャッシュ目的でしか使えない。

AWS上でサービスを構築する場合、キャッシュのためのAmazon ElastiCache for Redisと耐久性のためのDynamoDBを組み合わせ、アプリケーションはこの2つのデータストアを行き来する必要がある。

Redisのインメモリの速さとDynamoDBの耐久性や強い整合性を1サービスで満たすために開発されたのがAmazon MemoryDB。 MemoryDBではデータ永続性をAWS内製のトランザクションログサービスにオフロードしている。

2 : 背景と動機

2.1 Redisについての背景

Redisはシャーディングで水平スケーリングし、スロットとシャードのマッピング情報をもっている。

プライマリ･レプリカ間はパッシブ論理レプリケーションで同期。

2.2 耐久性と一貫性

Redisにはスナップショットやトランザクションログ(Append-Only File;AOF)を利用した永続化の仕組みがある。 AOFの場合、ログ更新のたびにディスク同期(fsync()) する設定も可能。

ただし、ノード障害が起きると、データロスを避けられない。

また、レプリケーションは非同期に行われるため、クライアントの発行したコマンドをレプリカで復元できるとは限らない。 Redis 3.0から同期レプリケーションする WAIT コマンドも存在するが、強い一貫性を保証するものではない。

3 : 耐久性と一貫性

この章はAmazon Auroraストレージを念頭に置くと、理解しやすいと思います。

MemoryDBはマルチAZで稼働し、低遅延・強い一貫性を保証するAWS内製の分散トランザクションログサービスに耐久性をオフロード。

※図は論文からの引用

3.1 耐久性の分離

書き込みを受け付けるプライマリノードはログサービスへの同期的な書き込み後にACKすることで、イレブン9(99.9999999%)の耐久性を達成。このプライマリ-ログサービス間の処理は、レプリケーションにインターセプトして行っている。 レプリカへは、ログサービスから非同期に書き込まれるため、結果整合的。

ログサービスは安価でスケーラブル。 MemoryDBの利用費は、DRAMのサイズが支配的。

MemoryDBでは、ログサービスがマルチAZな耐久性を担保してくれるので、多くのユーザーは各シャードを1~2ノード(つまり、レプリカが0~1個)で運用している。

3.2 一貫性の維持

マルチAZなログサービスへの同期書き込みのおかげで、線形化可能性(linearizability)も実現できている。

非決定的なコマンドにも対応できるように、write-aheadではなくwrite-behind loggingを採用。 RedisにはMVCCがないので、2フェーズコミットに失敗したデータが見えないようにするためのレイヤーを追加している。更新コマンド処理時には、ログサービスへの書き込みが成功するまではトラッカーで管理され、他のリクエストからのコマンドを処理する際にはこのトラッカーでキーが更新中かチェックし、更新中の場合は進行中の更新が終わるまでブロックされる。レプリカではログに書き込まれた(2フェーズコミット後の)データだけがレプリケートされるため、ブロック処理は行われない。

プライマリからの読み取りは強い一貫性(strong consistency)、単一のレプリカからの読み取りは逐次一貫性(sequential consistency)、ロードバランシングされた複数のレプリカからの読み取りは結果整合性(eventual consistency)です。

参考

• Eventual Consistencyまでの一貫性図解大全 #分散システム - Qiita

4 : 可用性・リカバリ・レジリエンス

4.1 リーダー選出

Redisクラスタのアーキテクチャーはゴシッププロトコルを用い、多数決ベースのクォーラムを利用したリーダー・フォロワー型。

そのため、リーダーはいつでもたかだか一つしか存在しないこと(leader singularity)や一貫性のあるレプリカだけがリーダーになれるといったことを満たすことができない。

一方で、MemoryDBはトランザクションログサービス上でAppend APIやリースを用いてリーダー選出を行い、これらの課題を解決している。

リースやリースを用いたリーダー選出は以下の記事が参考になります。

• C. Gray & D. Cheriton : "Leases: an efficient fault-tolerant mechanism for distributed file cache consistency | ACM SIGOPS Operating Systems Review"
• Leader election in distributed systems | Amazon Builders' Library

4.2 リカバリ

※図は論文からの引用

MemoryDBでは、S3上の point-in-timeスナップショットからリストアし(Redisの機能)、その後トランザクションログを(おそらくログサービスの同期APIで)リプレイしてデータをリカバリする。

Redisはスナップショットの取得中も通常のリクエストを処理できるように fork() して行われるが、CPUやメモリなどのリソースを余分に消費する。

MemoryDBでは、リカバリと同じ手法でスナップショット取得目的の ephemeral なクラスタを非顧客環境に構築し、スナップショットを取得(Off-box Snapshotting)。 スナップショットの取得が顧客環境のクラスタのパフォーマンスに影響を与えることはない。

論文にはない補足として、ElastiCacheの場合について述べます。

サーバーレス型の場合、クラスタへのインパクトはありません。 非サーバーレス型(従来の self-designedクラスタ)はスナップショットの取得にBGSaveコマンド(=fork())を利用しているため、パフォーマンスへのインパクトがあるため、負荷の低い時間帯やレプリカでの実行が推奨されています。

参考

• Snapshot and restore - Amazon ElastiCache for Redis

5 : 運用

5.1 : クラスタ管理

MemoryDBクラスタはリージョナルなコントロールプレーン上で管理され、クラスタの作成命令に対して、構成に対応するEC2等が作成される。

クラスタの更新はBlue/GreenではなくN+1のローリングアップグレードで行われる。

5.2 : スケーリング

MemoryDB は以下の3点でスケーリング可能

• シャード数
  • スロットとシャードの関連付けを変更
• シャードあたりのレプリカ数
  • レプリカ分のEC2の増減
• インスタンスクラス
  • N+1ローリングアップデート

6 : 評価

RedisとMemoryDBのベンチマーク

6.1 : read/writeの比較

読み取りの場合、MemoryDBのIO マルチプレクシングのおかげでRedisより良い結果が得られる。

※ 引用元 https://aws.amazon.com/memorydb/features/

書き込みの場合、Redisは300K Op/sに対して、複数AZのトランザクションログにも書き込むMemoryDBは 185K Op/sと劣る。

レイテンシーでも同様の傾向。

6.2 スナップショット取得時の比較

Redisのスナップショットをノンブロッキングに取得する BGSave コマンドは fork() を利用しています ^*1。

Redisコマンドの処理とスナップショットの取得を同じボックスで行う場合、fork() 元のRedis本体で更新が走ると、 Copy-On-Write(COW)により子プロセスでメモリページがコピーされ、メモリを大量消費します。特に、DRAM不足によりスワップアウトが起こるとレイテンシーが著しく増加します。

スナップショット取得専用のクラスタを新規に構築するMemoryDBの場合、スナップショットが既存クラスタのパフォーマンスにインパクトを与えることはありません。

7 : スケール下での一貫性の検証と維持

AWSではS3を始めとして TLA+ を用いた分散システムに対する形式手法による検証が導入されており、MemoryDBでも活用されています。 詳細は割愛します。

The TLA+ Home Page

8 : 関連

MemoryDBがコマンド処理をデータベースノードで行い、レプリケーション・耐久性はトランザクション･ログ･サービスにオフロードしているように、Amazon AuroraやSinfoniaやHyderやPolarDBなどもデータベースの特定の機能を別サービスにオフロードしています。

ログベースのレプリケーションはコンセンサスアルゴリズムや分散ストレージシステムと共に耐久性のために広く使われてきた。 Multi-PaxosとRaftは実現するための代表的なプロトコルです。

近年の大規模ウェブアプリケーションでは、パフォーマンスのためにDRAMが不可欠になっており、インメモリのNoSQLストレージシステムや新しいデータはメモリに、古いデータはディスクに逃がすAnti-Cachingといったアーキテクチャーが誕生しています。

9 : まとめ

Amazon MemoryDBはRedis互換でありながら、高速で耐久性のあるインメモリデータベース。 AWS内部のトランザクションログサービスに同期レプリケートし、スケーラブルな耐久性、リーダー選出、強い一貫性をオフロード。

所感

RedisにAmazon Auroraストレージっぽいものをくっつけて耐久性をオフロードしたAmazon MemoryDBについてのSIGMOD 2024での論文を紹介しました。

トランザクションログサービスのおかげでプライマリノードの役割が大幅に軽減され(decouple)、レプリケーション、リカバリ、スナップショット取得のようなデータベースの重い機能がプライマリノードではなくログサービスにのみ依存しているのは美しいと思いました。

Amazon MemoryDBの耐久性やスケーリングについては、次のAWS Black Beltオンラインセミナーでも述べられています。

副読本として、林 昌吾さん(著)の『実践Redis入門』がほどよい粒度の解説として役に立ちました。

Redisの機能をできるだけ活かしながら課題を解決する、マネージドサービスの裏側を覗き見できるのは楽しいですね!

トップカンファレンスで採択された論文というと難しすぎて手も足も出ないという印象を持ってしまいがちですが、本論文に関しては、RedisとAmazon Auroraとシステムプログラミングに関しての少しばかりの知識があれば、理解できるところが多いのではないかと思います。

ゴールデンウィーク中の読書にいかがでしょうか?

参考

• Amazon MemoryDB: A fast and durable memory-first cloud database
• MemoryDB: Speed, Durability, and Composition. - Marc's Blog
• MemoryDB: A fast and durable memory-first cloud database | Hacker News

脚注