JAWS DAYS 2025 で DB の競合解決が分かった気になる話をしてきました #jawsdays2025 #jawsdays2025_c
2025.03.04ウィスキー、シガー、パイプをこよなく愛する大栗です。
先日 JAWS DAYS 2025 で LT をしてきたので、内容をレポートします。CRDT は複数のユーザーが同時に編集するサービスなどでよく使用される考え方です。有名な例では Figma が同時編集の仕組みとして CRDT を使用していると公開されています[1]。
最近の DB の競合解決の仕組みが分かった気になってみた
先日の re:Invent 2024 のアップデートは、Amazon Aurora DSQL、Amazon DynamoDB global tables strong consistency、Amazon MemoryDB Multi-Region とマルチリージョンに関連するものが多数でした。世はまさに 大マルチリージョン時代 ！！！
本セッションでは特に Amazon MemoryDB Multi-Region に関するデータが競合したときの解決の仕組みを解説します。
Amazon MemoryDB Multi-Region は以下のような特徴があります
- Active/Active なマルチリージョンデータベース
- 最大 99.999％ の可用性、マイクロ秒の読み取り、1 桁ミリ秒の書き込みレイテンシー
- 最大 5 つのリージョンでレプリケーション
- シングルリージョンに比べて、一部機能制限がある
- データ階層化やベクトル検索のサポートなし
- read-modify-write コマンドのサポートなし
- Redis Transaction の原子性と一貫性の保証なし
- etc
特に「read-modify-write コマンドのサポートなし」と「Redis Transaction の原子性と一貫性の保証なし」はマルチリージョンでのデータ競合を解決するために必要となる制限です。
Amazon MemoryDB Multi-Region は結果整合性で、データ競合を解決するために Conflict-free Replicated Data Types（CRDT : 競合のない複製データ型）を実装しています。CRDT は 2011年にフランス国立情報学自動制御研究所)の論文で発表された複数のポンピュータ感で複製されるデータ構造です。
CRDT の特徴は、1. アプリケーションは、他のレプリカと協調せずに任意のレプリカを独立かつ並行して更新できる、2. アルゴリズム（データ型の一部）が起こりうる不整合を自動的に解決する、3. レプリカは特定の時点で異なる状態を持つ可能性があるが最終的には収束することが保証される、などがあります。実装のアプローチは操作ベースと状態ベース があり、MemoryDB Multi-Region では 操作ベース になっています。
CRDT のいちばん簡単な例がカウンターです。東京リージョンと大阪リージョンでカウントアップ操作を行い、その操作を別のリージョンへレプリケーションします。操作の反映順序に関わらずどちらのリージョンも最終的には 2 になる、という考え方が基本となります。
MemoryDB では Last Writer Wins（LWW）が基本戦略です。つまり後勝ちです。操作のタイムスタンプを確認して、新しい操作を反映して、古い操作を破棄します。
追加と削除が競合する場合は、先にデータを削除してしまうと、比較する元データがなくタイムスタンプを比較できないため、無条件にデータを追加してしまいます。それでは不整合になってしまうため、削除の再伝播を行い削除された状態で収束します。CRDT では一般的に Tombstone と呼ばれる論理削除を行うことによりタイムスタンプを保持して操作の前後を判断します。Tombstone を実装する場合はガベージコレクションが必要となるため、それを避けるために MemoryDB Multi-Region では削除の再伝播を行う実装にしたのかもしれません。
LWW 戦略の CRDT は、単一の値を扱う LWW-Register と複数要素を持つ LWW-element-Set があります。データ追加とデータ削除が別リージョンへレプリケーションされます。APPEND や RENAMENX は既存データが前提となる read-modify-write コマンドであるため利用できません。各操作の前後を交換したり、古い操作を破棄したりするため、トランザクションの原子性や一貫性は保証しません。
まとめ
- MemoryDB Multi-Region は CRDT を利用
- 基本的には Last Writer Wins の方針
- CRDT のデータ削除で整合性を保つためには、Tombstone という論理削除が一般的だが、MemoryDB では 削除の再伝播という手法を使用している
さいごに
あまり AWS の実践を行っていなかったため、実は LT のネタに困ってました。re:Invent の MemoryDB のセッションを見ていたらマルチリージョンの整合性の解決に CRDT という考え方を使用しているとの情報があったため調べてみました。CRDT を知っていても MemoryDB の使い方が上手くなる訳ではないですが、背後の考え方が勉強になり、Figma の 同時編集が必要なサービスを開発する時には思い出して頂きと良いかなと思います。
