Zenn
⛅️

順序性の担保とスループットはトレードオフだという話

2024/06/23に公開
AWS
SQS
kinesis
Amazon SNS
tech

この記事について

AWS SQSからメッセージを受けとって処理するLambdaを書いているときに、

  • 標準キューだから順序保証されてないな、じゃあ順序バラバラできても捌けるように処理を書かないと！
  • → ...
  • → あれ？？？意外とこれ難しくない？？？

と思った経験、皆さんにもあるのではないでしょうか。

この記事では、筆者が上記のような壁にぶつかったときに「順序を保つってなんでそんなに難しいんだろう？」「保てないならどうやってそれに耐えうるようにすればいいんだろう？」と色々考察した結果を書いていきたいと思います。

使用する環境・バージョン

  • 2024/6/22時点で提供されている機能に基づき考察

読者に要求する前提知識

  • AWSのSQS, SNS, Kinesis Data Streamがどういうサービスなのかは既知という前提のもとで書きました

順序セマンティクスとは

順序セマンティクスとは「イベントやメッセージといったデータの配信順序がどれだけ保証されるか」を議論するトピックのことを指します。
ことAWSにおいては、以下の2パターンを考えることになるでしょう。

  • 順序保証あり
  • 順序保証なし

順序保証あり

「メッセージをA→Bの順番で受け取ったのならば、必ずA→Bの順で配信される」場合、順序保証がされているということになります。
First-In-First-Outの頭文字をとってFIFOと呼ぶこともあります。

順序保証なし

「メッセージをA→Bの順番で受け取ったとしても、必ずしもA→Bの順で配信されるとは限らない」場合、順序保証がされていないということになります。
実際にはA→BになるかB→Aになるかがほぼランダムにばらつくようなことはなく、なるべくA→Bになるようにベストエフォートでの挙動が提供されていることが多いです。
しかし、常にA→Bであることをサービスが担保できない場合は「B→Aになることもある」という前提のもとでユーザーはそれを利用しなくてはなりません。

順序保証をするために必要なこと

順序を担保できるのは同じ場所にあるもののみ

通常の感覚では「順序がバラバラになるリスクを背負うぐらいなら、最初から順序を担保してもらった方がいいに決まっているじゃないか」となるかと思います。
ですが、プロダクション環境のような大きな規模ででまともに動くシステムを組むことを考えるとそうもいかない現実があります。
なぜなら「順序を担保できるのは同じ場所にあるもののみ」という性質があるからです。

例えば、ある処理を行うLambda関数のインスタンスが2つできており、それらが同時刻に同じイベントを受け取ったとします。
そうなったときに、2つのLambda関数インスタンスがイベントを処理するのに同じ時間だけかかって、同じ時間にプロセス終了するかというとその保証はないのが現状です。どちらか一方が他方より長くなったり短くなったりすることが普通だと思います。
そのため、

  1. LambdaインスタンスAがイベントaを受け取る
  2. その後にLambdaインスタンスBがイベントbを受け取る

という時間関係だったとしても、処理終了の順番がイベントa→イベントbの順番、つまりFIFOになることを保証することはできません。
これは「2つのLambdaインスタンス」という別の場所でイベントを処理したからこそ起こる現象です。

また、これはLambda関数特有の話ではありません。ECSのジョブコンテナだったとしても、同じEC2インスタンスの別プロセスだったとしても、待ち合わせの機構がない別場所で処理したイベント・データの順序保証は基本的にはできません。

AWSサービスの仕様を見てみよう

ここで、AWSにおける各種「FIFOを謳うメッセージ配信機構」の仕様を確認してみて、それぞれどのような場合において順序保証がされるかを見てみたいと思います。

Kinesis Data Streams

PutRecord APIで順序保証オプションを利用することによって、同一シャード内での順序保証を提供しています。

PutRecord API

  • 単一の Kinesis データレコードを送信
  • 各シャードにつき 1 秒あたり 1000 レコードまたは 1 MiB の書き込みをサポート
  • SequenceNumberForOrdering オプションによるシャード内の厳密な順序保証をサポート

出典: Amazon Kinesis Data Streams - Amazon Black Belt Online Seminar

見方を変えると、シャードが同じであれば順序保証はできますが、シャードを超えたグローバルでの順序保証まではKinesisは提供していないということです。

また、Kinesis Data StreamsのデータをLambdaで処理することも考えてみます。
デフォルトではParallelization Factorというパラメータ値が1になっており、このときは「1つのLambda関数が処理できるデータは1つのシャードからのデータのみ」という挙動をします。同一シャード内のデータを同一Lambdaインスタンス内で処理できるため、同じシャードにPutされたデータの順序保証を保ったままLambda内で処理を行うことができます。

1つの Lambda 関数呼び出しは、一度に1つのシャードを処理します。
出典: AWSブログ - Kinesis と DynamoDB をイベントソースにする際の AWS Lambda の新しいスケーリング管理

Parallelization Factorを増やして「1つのシャードのデータを複数個のLambdaが処理する」という構図も作ることができます。
ただこの場合は、従来保証されていた「同一シャード内のデータを順序通りに処理する」という性質は担保されません。代わりに、同一partition keyのデータは同じLambdaに送るように内部でよしなにやってくれるそうなので、シャードよりも小さい単位にはなりますが、partition keyごとの順序保証は引き続き利用することができます。

並列化された各シャードには、同じパーティションキーを持つレコードが含まれます。つまり、同一のパーティションキーではレコード処理の順序が維持され、並列化された各シャードにおいては、次のデータを処理するためには前のデータ処理を完了する必要があります。
出典: AWSブログ - Kinesis と DynamoDB をイベントソースにする際の AWS Lambda の新しいスケーリング管理

SQS FIFOトピック

SQS FIFOトピックへのSendMessageの際には、MessageGroupIdと呼ばれる値を一つ指定することになっており、同じMessageGroupIdを持つメッセージの間では配信順序を保証するという仕様になっています。
トピック全体での順序保証ではなくてGroupIdごとの順序保証です。ここでも「同じ場所にあるもののみ順序保証ができる」という性質が透けて見えます。

メッセージ配信においても、順序が崩れないように配慮がなされています。
具体的には、とあるMessageGroupIdのメッセージをとあるコンシューマーに配信した後、それらに対するDeleteMessageのリクエストが来ていないのであれば、仮に他のコンシューマーからReceiveMessageリクエストがあったとしても、当該GroupIdのメッセージは配信しないように制御されています。
そのため「せっかくFIFOトピックに入れたのに、メッセージ消費の段階で複数個のコンピューティングリソースを使ったばかりに順序が崩れる」という心配はしなくて大丈夫になっています。

SNS FIFOトピック

SNSもSQSと同様に、メッセージ送信の際にはグループIDを指定することになります。そして同じグループに配信されたメッセージに関しては順序を保証するという仕組みになっています。

同じグループに属するメッセージは、グループに対する厳密な順序で1つずつ処理されます。
出典: AWS公式Doc - FIFO トピックのメッセージのグループ化

順序性の担保とスループットはトレードオフ

AWSにおけるメッセージングサービスを3つ見てきましたが、どれもグローバルでの順序保証は提供しておらず、特定条件下・同じグループやシャードに属するメッセージのみ順序保証をしていることがわかりました。

「順序を保てるのは同じ場所にあるもののみ」であるならば、順序性の担保とスケールは大変相性が悪いということになります。
なぜなら、水平スケールするためには処理に使うインスタンス数を増やすという方法をとるしかなく、これを行った瞬間に「順序を保つために同じ場所で処理する」という手段を潰されてしまうからです。

実際に、上記で取り上げたAWSリソースのクオータを確認することでもその様子を見てとることができます。

SQSの場合

例えばSQSの場合だと、標準キューとFIFOキューでメッセージスループットが異なります。(公式Doc)

  • 標準キュー: 1秒あたりほぼ無制限のAPIコールをサポート
  • FIFOキュー: 1秒あたり300トランザクションの割り当てをサポート
  • FIFOキュー(高スループット): (バージニアリージョンでは)デフォルトのスループットは、APIアクションごとに1秒あたり70000トランザクション

SNSの場合

SNSの場合、メッセージのPublishには以下のソフトクオータが存在します。(公式Doc)

  • 標準トピック: (バージニアリージョンでは) 1秒あたり30000件のメッセージをPublish可能
  • FIFOトピック: 1 秒あたり3000メッセージ、またはトピックあたり20MBまでPublish可能

Kinesisの場合

Kinesisの場合、順序が担保されるのは同じシャードにPutされたメッセージだけなのですが、1シャードあたり1000レコード/秒までしかPutできないというクオータが存在します。(公式Doc)

まとめ

どの場合においても、順序性を強力に担保するオプションはそうでないオプションに比べてスループットが劣るということが見て取れたかと思います。
つまり、「順序性の担保とスループットはトレードオフ」となってしまうのです。

昨今の「モノリスから分散システム」という動きにおいて、1つのサーバーだけでシステムの全機能を担うことは少なくなり、複数個のサーバー・複数個のプロセスで様々な処理を挟む形式が多く取られるようになってきました。
また、システム自体の規模が大きくなってくると、同一の役目のサーバーを複数個立ててその間で処理を水平スケールさせるということも普通になるかと思います。
そのため「とある処理のために流れ込んでくるデータを、複数台のコンピューティングリソースを使って捌く」ということは設計において絶対に考慮しないといけないポイントになってきます。

しかし、ここまで説明してきた通り順序性とスケールはそこまで相性が良くないのです。したがって、スケールできる柔軟性をシステムに残したいのであれば、順序保証なしで動かせるようにしないといけないのです。

順序保証なしでも耐えうる設計にするには

順序保証なしでも耐えうるシステム設計にするためには「メッセージをA→Bの順で捌いてもB→Aの順で捌いても破綻しないようにする(=可換性の担保)」必要があります。
しかし、これは言葉にするのは簡単ですが、実際にこの構成を目指して組もうとすると、初めての人は「あれ……？どう設計したら実現できるんだろう？」となってしまうかと思います。

そんな方に向けて、ここからは順序保証なしでも耐えうる設計を思いつくための手がかりとなる着眼点を述べていきたいと思います。

「すべてのイベント」に対して処理の可換性を担保するのは困難

とあるイベント・メッセージに対して処理をしていくことを考えるのであれば、多くの方はイベントがシステムに到着する時刻で並べて考えようとするかと思います。

  1. 12:00:04に到着したメッセージAを処理する
  2. 12:00:05に到着したメッセージBを処理する
  3. 12:00:07に到着したメッセージCを処理する
  4. 12:00:10に到着したメッセージDを処理する
  5. 12:00:11に到着したメッセージEを処理する
  6. ...

時刻で並べることのメリットは、すべてのメッセージに対して順序をつけることができることです。
すべてのメッセージに対して順序をつけられるのであれば、すなわち時刻を軸とした数直線上にメッセージを順番にマッピングすることができることとイコールであるため、メッセージ同士の関係性や流れがイメージしやすいのです。

しかし、現実問題この数直線上に乗ったすべてのイベントに対して「A→BでもB→Aでも整合性を保った処理をさせたい」というのはかなり困難です。
できるとしたら状態をもたないステートレスな処理か、処理を実行するための前提条件のチェックを行わず無条件で捌いていくような処理ぐらいかと思います。

ある特定のプロパティに着目してメッセージを分類する

繰り返しますが、「すべての」イベントに対して可換性を担保するのは非常に難しいです。
これを考えようとすると、データストアを参照するようなMutation処理に関しては絶対に「あ、この場合は順序担保されてないと正しく処理できない」というケースが見つかってしまうと思います。
ですが、構築したいシステムは本当に「すべての」イベントに対して順序を保証しないといけないのでしょうか。

上にあげた例をもう一度考えてみたいと思います。
例えばメッセージA~Eの内容が、実はとあるユーザーaに関するメッセージとユーザーbに関するメッセージというように2種類に分類できるとしましょう。

  1. 12:00:04に到着したメッセージAを処理する (ユーザーAのアクティビティ情報)
  2. 12:00:05に到着したメッセージBを処理する (ユーザーBのアクティビティ情報)
  3. 12:00:07に到着したメッセージCを処理する (ユーザーAのアクティビティ情報)
  4. 12:00:10に到着したメッセージDを処理する (ユーザーAのアクティビティ情報)
  5. 12:00:11に到着したメッセージEを処理する (ユーザーBのアクティビティ情報)
  6. ...

こうして考えてみると「ユーザーAに関するメッセージは時刻通り順番に処理したいが、ユーザーAに関するメッセージとユーザーBに関するメッセージは互いに関与しないので処理順がどうなってもいい」といった妥協点が見つかるかと思います。[1]
このように、とある特定のメッセージ属性(プロパティ)に着目してメッセージを分類し直してみて、その中でだけ順序が担保されていればいいのでは？と考えることで、逆に「異なるプロパティ値を持つメッセージに関しては可換性を担保できる」ということを発見することができます。

順序を担保したいメッセージだけ同じ箇所に集める

こうして「とあるプロパティが同じ値のメッセージだけ順序が保てていればいいんだ」ということを発見したら、そのメッセージのみを同じ場所にまとめればいいのです。
具体的には、以下のような手段が考えられます。

  • Kinesisの場合: パーティションキーにそのプロパティを指定することで、同じシャードにメッセージが配信されるようにする
  • SQSの場合: 同じMessageGroupIdを指定する
  • SNSの場合: 同じGroupIDを指定する

まとめ

ここまでお話ししてきた重要なポイントをまとめます。

  • 順序を担保できるのは同じ場所にあるもののみである
  • ゆえに、順序を担保しようと思うと水平スケール性能を犠牲にする必要がある
  • つまり、順序性の担保とスループットはトレードオフ
  • 全てのメッセージに対して順序を担保しようと考えると大変なので、「とある条件を満たしたメッセージ」「とあるグループのメッセージ」でのみ順序を保っていればいいというポイントを発見できると良い
  • そんなポイントを発見したら、そのメッセージだけ順序保証をするようにどうシャードに入れる・同一メッセージGroupに入れるなどしよう

わかっている人にとっては当たり前の事項なのかもしれませんが、順序性とスループットが両立できないのはなぜなのか・それに対抗するためには私たちはどう設計すればいいのかということを改めて考えてみるとなるほど！と腹落ちするものがありました。
メッセージを使うシステムを組み始めたばかりの方やジュニアなエンジニアの方に「FIFOでゴリ押ししちゃダメなんですか？」と聞かれたときにはぜひこの記事をシェアして頂ければなーと思います。

脚注

  1. 筆者は数学畑の出身なので、全順序集合の切り口を変えて半順序集合にバラす感じやなと勝手にイメージを組み立ててます。 ↩︎

Discussion