これはなに？

メッセージング機能を実現するにあたり配信/再送の対象を管理するためにDynamoDBを使ってみました。ここでいうメッセージング機能とは「配信Aの内容をユーザー1、ユーザー2、ユーザー3に配信する」ような機能のことです。

メッセージング機能の配信対象は内容によって変わります。ある配信では特定のユーザーだけに配信することもあれば、また別のある配信では不特定多数のユーザーに配信することもあります。もし提供しているサービスでユーザー数に上限を設けていなければメッセージング機能の設計時点では将来どれくらいの配信数となるかを正確に予測することは難しいでしょう。

また、メッセージング機能では一つの配信が一人の対象に対し配信する内容は一つであることが多いです。この場合には設定した対象に配信されなかったり逆に何度も配信されてしまうのは望ましくないでしょう。もちろん意図していない対象へ配信してしまうことはもってのほかです。
そうした事態を避けるためには配信ごとに永続化された配信対象のリストを持つ必要があります。これは配信時にそのリストを参照し、配信が可能な対象のみに配信することで、未配信や誤配信、再送に伴う多重配信を防ぐということを意味します。

DynamoDBはこうした要件に対し特別な設定なしで柔軟なスケーラビリティを担保しつつ高いパフォーマンスが発揮できる点でマッチしていると判断しました。

ただ、今回は要件に「一人に一つの内容が確実に1件だけ届くようにする」、いわゆるExactly Onceの配信保証が含まれていました。

RDBとは違う特性を持ったDynamoDBではExactly Onceの配信保証を実現するためのテーブル設計に思った以上に時間が掛かりました。せっかくなので記憶が新しいうちに備忘録として記事にしてみようと思います。

この記事の構成

この記事では次の順序でDynamoDBの特性や機能を紹介し実際のテーブル設計について言及します。

1. DynamoDBによるパフォーマンス最適化と制約
2. パフォーマンスを最適化しつつExactly Onceを実現するテーブル設計

ホットパーティション問題や強力な整合性のある読み込みについては公式ドキュメントのおさらになっていますのでこれらの機能や特性をすでにご存知の方はテーブル設計まで読み飛ばしていただくことをお勧めします。

それではまずはDynamoDBのパフォーマンス最適化について説明していきます。

DynamoDBによるパフォーマンス最適化と制約

DynamoDBはフルマネージドのNoSQLデータベースで優れたパフォーマンスと高可用性、柔軟なスケーラビリティを特徴としていますが、これらを実現するために利用する際にいくつかの制約が存在します。この記事ではパーティショニングと読み込み整合性について紹介します。

パーティショニング

DynamoDBはkey-valueデータベースであり検索するにはキーが必要となります。このキーのことをパーティションキーといいます。パーティションキーはそれ単体を検索するためのユニークなキーとするか、ソートキーと組み合わせて複合ユニークキーとする必要があります（単体もしくは組み合わせでユニークとしたキーのことを主キーといいます）。つまりパーティションキーは必ず設定する必要があります。

パーティションキーを必ず設定しなければならない理由は、DynamoDBが内部で特定のテーブルの値を複数のパーティションに分けて格納しており、パーティションキーが文字通り特定のテーブルの値を異なるパーティションへ配置するために使うキーとなっているためです。

https://docs.aws.amazon.com/ja_jp/amazondynamodb/latest/developerguide/HowItWorks.Partitions.html

DynamoDBはパーティションキーが分からなければどのパーティションに格納されている値か分かりません。そのためSCAN（テーブル全体のフルスキャン）以外の読み込み（Query / GetItem / BatchGetItem）を行うには必ずパーティションキーを等価で指定しなければいけません。これはDynamoDBの仕組み上どのパーティションに格納されているかをパーティションキーのハッシュ値から計算しているためです（これはPartiQLについても同様でPartiQLは内部でQuery / GetItem / BatchGetItemなどの操作に変換するためのただのDSLです）。

この制約の結果、DynamoDBはSCAN以外のリクエストを受け付けた際には必ずパーティションキーが設定されていることが保証されます。これはつまりDynamoDBがどのパーティションに対し読み込み操作を行えば良いかが分かるということです。DynamoDBはパーティションキーの指定により操作を複数の異なるパーティションに対し並列で処理できるため高速でスケーラブルな読み書きを可能としています。

ホットパーティション問題

パーティションキーによる制約をまとめてみます。

• テーブル内でユニークな主キーはパーティションキー単体、またはソートキーとの組み合わせ
• SCAN以外の読み込み操作はパーティションキーの等価指定が必須

この制約により「特定の配信IDを持つ不特定多数の配信対象を取得したい」という要求では次のようなテーブルが考えられます。

delivery_id (partition key)	user_id (sort key)
1	1142
1	2321
1	4597
1	7768
1	18242
1	...
1	34729733
2	1490
2	...
3	2473
3	...
...	...

この例ではdelivery_idをパーティションキー、user_idをソートキーとしています。delivery_idは配信ID、user_idは配信対象IDです。

読み込み時にはdelivery_idを等価指定で要求することで「配信対象」を取得することができ、ソートキーとの組み合わせはユニークとなっており、ソートキーによる絞り込みや範囲検索が可能なため無駄なコストの発生を抑えられます。

一見良さそうな設計ですが、実はこのテーブル設計はDynamoDBだとアンチパターンとされます。なぜでしょう。

DynamoDBは先述したとおりパーティションを複数に分散することでパフォーマンスを向上させています。逆を言えばもし特定のパーティションに処理が偏ってしまうとDynamoDBは本来持つパフォーマンスを最大限発揮することはできなくなってしまいます。この状態をホットパーティションといいホットパーティションに起因する問題をホットパーティション問題といいます。

ホットパーティションを避けるためにはパーティションキーがテーブル内でカーディナリティの高い値になっていなければなりません。例えば次のようなテーブル設計であればホットパーティションを回避できます。

user_id (partition key)	delivery_id (sort key)
1142	1
2321	1
4597	1
7768	1
18242	1
...	1
34729733	1
1490	2
...	2
2473	3
...	3
...	...

主キーの組み合わせは先述の例と同じですが役割をそれぞれ入れ替えています。

これによりパーティションキーのカーディナリティは高い値となっておりホットパーティション問題を回避することができるようになりました。

ただ、この設計にも問題はあります。それはこの設計だと配信ごとの配信対象リストを取得できないことです。

DynamoDBでは上述したとおりSCAN以外の読み込み操作を行うためにはパーティションキーを等価で指定しなければいけません。このテーブル設計だとuser_id、つまり「配信対象を予め知る」必要があるということです。一方で配信時に読み込み操作で配信対象を取得する理由は「その配信を行うべき対象を取得するため」です。これでは矛盾してしまいます。

ここまでの内容をかんたんにまとめます。

• パーティションキーはカーディナリティを高くしなければならない
• フルスキャン以外の読み込み操作はパーティションキーを等価で指定しなければならない

読み込み整合性

ここまではDynamoDBのパーティショニングとそれによるテーブル設計時の制約について紹介しました。ここからは読み込みに関する制約を紹介したいと思います。

DynamoDBはキーに対応する値がパーティショニングされていることで高いパフォーマンスを実現していると説明しましたが高いパフォーマンスを実現するための仕組みは実はこれだけではありません。値が格納されるパーティションは3つのアベイラビリティゾーンでレプリケーションすることで冗長性を持たせています。

https://aws.amazon.com/jp/builders-flash/202206/awsgeek-dynamodb/?awsf.filter-name=*all

DynamoDB は単一障害点 (SPOF) を持たない構成になっていて、自動で同一リージョン内の 3 つのアベイラビリティーゾーンにデータをコピー (レプリケーション) します。

このデータレプリケーション機能により、予期しないサーバー障害やアベイラビリティーゾーンの停止からデータを保護します。

これにより高い可用性を実現しつつ、SCAN、Query、GetItemといった読み込み時に2パターンの読み込み方法を提供することで開発者が要件に合わせてどちらかを選択できるようにしており、これはそれぞれ「結果整合性のある読み込み（Eventually Consistent Reads）」と「強力な整合性のある読み込み（Strongly Consistent Reads）」と呼ばれます。

https://docs.aws.amazon.com/ja_jp/amazondynamodb/latest/developerguide/HowItWorks.ReadConsistency.html

結果整合性のある読み込みは最新の結果が返ってくるは保証されません。そのため確実に最新の状態を参照したい場合には強力な整合性のある読み込みを使う必要があります。

ただし強力な整合性のある読み込みは次のような制限があります。以下引用となります。

• 強力な整合性のある読み込みは、ネットワークの遅延または停止があった場合には利用できなくなる可能性があります。この場合、DynamoDB はサーバーエラー (HTTP 500) を返す場合があります。
• 強力な整合性のある読み込みでは、結果整合性のある読み込みよりもレイテンシーが高くなる場合があります。
• グローバルセカンダリインデックス (GSI) では、強力な整合性のある読み込みはサポートされていません。
• 強力な整合性のある読み込みでは、結果整合性のある読み込みよりも多くのスループット容量が使用されます。詳細については、「読み込み/書き込みキャパシティーモード」を参照してください。

この中でもこの記事で特筆する点はグローバルセカンダリインデックスについてです。

グローバルセカンダリインデックスは特定のテーブルに対し別構造を持つ読み込み専用のインデックステーブルを用意できます。これにより元のテーブルとは別のパーティションキーを設定できるため効率的なクエリが実現可能です。しかし残念ながら強力な整合性のある読み込みはサポートされていません。

• 強力な整合性のある読み込みを使わないと結果が最新であることは保証されない
• 強力な整合性のある読み込みを使うとグローバルセカンダリインデックスは使えない

パフォーマンスを最適化しつつExactly Onceを実現するテーブル設計

では実際にここからホットパーティション問題を避けつつ強力な整合性のある読み込みを行いExactly Onceを実現するためのテーブル設計を紹介します。

配信対象をリストとして値に持たせる

ホットパーティション問題の際に紹介した例では配信対象を個別の値として分けることで問題が難しくなっていました。再掲します。

user_id (partition key)	delivery_id (sort key)
1142	1
2321	1
4597	1
7768	1
18242	1
...	1
34729733	1
1490	2
...	2
2473	3
...	3
...	...

これをリストとしてキーの値として持たせることで「配信IDだけを指定する」「その配信IDに関連するリストを取得する」といったことが実現可能です。次のとおりです。

delivery_id (partition key)	user_ids
1	[1142,2321,4597,7768,18242,...,34729733]
2	[1490,...]
3	[2473,...]
...	...

配信IDはそれぞれユニークとなるためホットパーティション問題も回避できます。配信リストを取得後は中断による再送時における多重配信を防止するため配信の度にPutItemでリストを更新していきます。

この設計の問題点はリストに上限があることです。

DynamoDBは一つのキーと値の組み合わせに対し上限が設定されています（400KB）。

https://docs.aws.amazon.com/ja_jp/amazondynamodb/latest/developerguide/ServiceQuotas.html#limits-attributes

これはuser_idsをバイナリ型で格納したとしても一つの配信に対し格納可能なリストに上限があるということです。

また、ユーザーIDが上述の例のように桁数が可変な値となっている場合はサービスの成長に伴い裁判される値が大きくなるため格納できる件数は少なくなっていきます。そのため設計時に件数ベースで見積もりをしてしまうと書き込めなくなるといったことも想定されます。

上限に対し将来も含め十分に猶予が見込める場合に有効なアプローチといえます。

配信対象リストを複数に分割する

上限の問題を回避するためには配信対象リストを別々のキーを持つ値に分けてしまえば解決できます。

例えば配信A-1、配信A-2、配信A-3といった具合に、配信IDをパーティションキーに、添字をソートキーにするアプローチです。

delivery_id (partition key)	order (sort key)	user_ids
1	1	[1142,2321,4597,...]
1	2	[7768,18242,...]
1	3	[...,34729733]
...	...	...

もし特定の配信に対するリストが多くなってしまうようであればカーディナリティが低くなるよう添字と配信IDを逆にしても良いでしょう。

order (partition key)	delivery_id (sort key)	user_ids
1	1	[1142,2321,4597,...]
2	1	[7768,18242,...]
3	1	[...,34729733]
...	...	...

配信ID「1」に対する配信ではまず添字「1」から探索し、リストが空になったら次のリストといった具合に走査します。これにより配信対象のサイズに対する上限は取り払われます。

ただしこのままでは再送発生時に頭から走査しなければなりません。そこで順序の配列を持つ別テーブルを用意します。

delivery_id (partition key)	orders
1	[1,2,3]
2	[1]
3	[1,2]

この場合はまず順序テーブルへGetItemで読み込みを行い、次にordersの値をパーティションキーにしてQueryで配信対象リストへ読み込み操作を行います。

もしくは番号はインクリメントされることが分かっているので、配列単位でシーケンシャルに処理するのであればもっとシンプルに「開始位置」だけを格納しても良いでしょう。

delivery_id (partition key)	nextSequence
1	2
2	1
3	1

リストが終わるたびに順序テーブルの開始位置の値を繰り上げていけば無駄な走査を減らすことができます。

配信対象リストと配信対象を両方使う

配信対象リストの問題点は配信の度にリストを更新しなければならない点です。 これにより読み込み操作では問題がなくても書き込み操作でホットパーティション問題が発生する可能性があります。

これを避けるために配信対象リストと配信対象を分けて管理するアプローチが有効です。まずは配信対象リストです。

order (partition key)	delivery_id (sort key)	user_ids
1	1	[1142,2321,4597,...]
2	1	[7768,18242,...]
3	1	[...,34729733]
...	...	...

次に配信対象のテーブルも用意します。

user_id (partition key)	delivery_id (sort key)
1142	1
2321	1
4597	1
7768	1
18242	1
...	1
34729733	1
1490	2
...	2
2473	3
...	3
...	...

まず、配信対象リストへ読み込み操作を行います。これによりその配信対象リストが持つ配信対象のユーザーIDが分かります。

次にそのユーザーIDを使って配信対象へ読み込み操作を行います。ここで返ってきたアイテムのユーザーIDが配信対象です。

配信時には配信対象リストは更新せず配信対象を更新（削除）する設計とします。読み書きのキャパシティユニットはリストを展開している分だけ多く必要としますがホットパーティション問題を確実に回避できるため高いパフォーマンスを発揮できます。

テーブル分割

最後にテーブル分割です。

これはこれまで紹介してきた設計と違いパーティションキーには配信IDを指定しません。代わりに配信IDごとに別々のテーブルを作ります。

例えば次のように、「配信ID: 1」の専用テーブルを作ってしまうということです。

user_id (partition key)
1142
2321
4597
7768
18242
...
34729733

パーティションキーには配信対象のIDを指定することでユニークとなるためホットパーティション問題に遭遇することはありません。

ただしこの設計だと配信対象のIDは知り得ないためテーブルをフルスキャンしなければなりません。

フルスキャンはテーブルのサイズが大きくなるほど時間が掛かります。また、全ての値を読み込むので一度の操作で全ての値の分だけ読み込みキャパシティユニットを消費してしまいます。万が一配信中にエラーが発生し再度読み込みを行う必要が出た場合には読み込みキャパシティユニットが無駄となります。

まとめ

DynamoDBでホットパーティション問題を回避しつつ強力な整合性のある読み込みを行いExactly Onceの到達保証を実現するための配信対象テーブル設計について考え自分なりの答えをいくつか書いてみました。

そこまで難しい要件ではないと思っていたもののDynamoDBは調べるといろいろとできることや制約が多く、どのように組み合わせることがコスト面も含め最適となるか試行錯誤が必要でした。個人的にはそうした制約条件の中から答えを見つける作業はとてもやりがいがあり良い経験ができたと思っています。

何をしたいかによってテーブル設計は変わるかと思いますがこの記事が何か参考になれば幸いです。