ABL 「乗り越えられないキューバックログの回避」を読んだ
（2020/4/27 修正 コンシューマー、プロデューサーという原文の表現を、消費者、開発者という意味ではなく、本来のキューから情報を受け取る側、キューへ情報を渡す側、という意味に修正しました。）
輪読会に向けて、Amazon Builder's Library（以下、ABL） を読んだので、簡単にまとめてみました。
テーマは「乗り越えられないキューバックログの回避」です。
記事は AWS のシニアプリンシパルエンジニアが書いておりまして、項目は、以下の8つでした。
はじめに 生命を模倣するアルゴリズム
キューは短ければ短いほど良い。
前半はバックログにつながる流れを、後半はキューのバックログを適切に処理して蓄積するのを防ぐ方法が解説されている。
（考察）バックログは後から入ってきたデータで、処理待ちで溜まっているデータのことをさす？
キューとは、最も基本的なデータ構造の一つで、要素を入ってきた順に一列に並べ、先に入れた要素から順に取り出すという規則で出し入れを行うもの。
順番を待つ人の行列と同じ仕組みであるため「待ち行列」とも訳される。
待ち行列理論（まちぎょうれつりろん 英語: Queueing Theory）とは、顧客がサービスを受けるために行列に並ぶような確率的に挙動するシステムの混雑現象を数理モデルを用いて解析することを目的とした理論である。
応用数学のオペレーションズ・リサーチにおける分野の一つに数えられる。電話交換機や情報ネットワーク、生産システム、空港や病院などの設計や性能評価に応用される。
性能評価指標としては、待ち行列長・待ち時間・スループットなどが用いられる。
応用の場では、システムの性能がある設計目標を満たすために必要な設計パラメータを決定する際に、その逆問題を提供できる。
キューの二重の性質
キューを使うと、メッセージが処理されるまで保留されるため、システムの耐久性と可用性は上がるが、一方でレイテンシー増加の要因となる。
Amazonには、キューを使った非同期システムが多い。
通信を行う機器間でデータや信号の送信と受信のタイミングを合わせる動作や仕組みを用いずに通信することを非同期通信という。
ソフトウェア間のデータの送受信などに関して非同期通信という場合は、送信や受信の処理を他の処理から独立して並行に行う「非同期処理による通信」を指すことが多い。
（Amazon.comの注文処理、Amazon RDSがEC2 インスタンスをリクエストしDBを設定する流れ、CloudWatchのメトリクスとログの取込システム 等）
しかし、キューを使うと、可用性を下げてしまう可能性がある。
処理が止まってもメッセージが届き続け、処理時間がより遅くなる可能性があるからである。
キューをベースにしたシステムは、バックログがなければ高速に処理できるが、バックログがたまってくると処理を遅延させる要因になる。
キューベースのシステム
2つの例を挙げる。
① AWS Lambda
AWS Lamda は障害が発生しても処理を完了させるため、永続キューを採用している。
② AWS IoT Core
AWS IoT Core はデバイスがデータ受信できるよう待機することでリソースを消費してしまわないよう、非同期システムを採用している。
データ受信したデバイスがオフラインである可能性もあり、オンラインになったときにデータを受け取れるよう、永続キューを採用している。
WS IoT Core は、インターネットに接続されたデバイスから、クラウドアプリケーションやその他のデバイスに簡単かつ安全に通信するためのマネージド型クラウドサービスです。
キューベースのシステムは、永続キューを実装する。
永続キュー属性（-mオプションにpersistentを指定）
送信側アプリケーションが送信したメッセージは，受信側アプリケーションが受信するまでキューのあるDB上で永続的に管理されます。
DB障害以外によってメッセージが消滅しないため，通常は永続キュー属性を指定することをお勧めします。
SQSはメッセージが配信されたかどうかのセマンティクス（正しく動作したかの判断基準）を提供する。
LambdaやAWS IoT Coreもこれを利用している。
メッセージ処理が完了してからキューを削除している。
セマンティクス
プログラミング言語において、ソースコード中で利用されている変数や文が正しく動作するかを判断する基準のこと。
たとえば、ヌルが定数として定義されている値がアドレス参照のために使われていると、セマンティクスに違反しているとみなして、エラーと判断する。
非同期システムの障害
1時間停止した非同期システムは、停止した間にキュー処理が溜まるため、停止から回復後は、溜まったキュー処理と通常の処理を同時に処理するため、処理の負担が2倍になってしまう。
特にLambdaのような柔軟な処理を求められるシステムは、さらに負荷が増えて必要な能力が2倍以上になる。
これが処理能力を超えると、停止中はリクエストをカットする同期システムよりも、非同期システムのほうが回復に必要な時間がかかってしまうことになる。
したがって、非同期システムでもレイテンシー1秒以下の高い処理能力が求められる。
可用性とレイテンシーの測定
制作者の可用性は、使用しているシステムのキューの可用性に比例する。
SQSを使えばSQSの可用性と一致する。
Amazon Simple Queue Service (SQS) は、完全マネージド型のメッセージキューイングサービスで、マイクロサービス、分散システム、およびサーバーレスアプリケーションの切り離しとスケーリングが可能です。
SQS では、メッセージ指向ミドルウェアの管理や運用に関連する複雑さやオーバーヘッドを排除できるため、開発者が差別化作業に集中することができます。
（2020/4/27 修正 原文のプロデューサー、コンシューマーという表記から、プロデューサー＝開発者、コンシューマー＝エンドユーザーかと思ってしまったが、システムのキューへメッセージを渡す側をコンシューマー、システムのキューからメッセージを受け取る側をコンシューマーというそうです）
メッセージを送信するには、プロデューサーというコンポーネントがキューにメッセージを追加します。
コンシューマーという別のコンポーネントがメッセージを受信して処理するまで、メッセージはキューに保存されます。
エンドユーザーコンシューマー側から見ると、障害が起きると再試行になってしまうため、システムの可用性が実際よりも悪いという印象を抱く場合がある。
（補足：開発者の可用性＝スペック通り、エンドユーザーの可用性＝ちゃんと使えるかどうか、ということを言いたいのだろうか？）
再試行中に届いたメッセージは、ドロップされるか デッドレターキューの中に格納される。
（DeepL訳参考）メッセージキューイングにおいて，デッドレターキューは，以下の条件のうち1つ以上を満たすメッセージを格納するためのサービス実装である。
1.存在しないキューに送信されるメッセージ
2.長さ制限を超えたキュー
3.長さ制限を超えたメッセージ
4.他のキュー交換で拒否されたメッセージ
5.消費されないために、しきい値のリードカウンタ番号に達するメッセージで、 "バックアウトキュー "と呼ばれることがあります。これらのメッセージをもつデッドレターキューのおかげで、開発者が共通のパターンと潜在的なソフトウェアの問題に専念することができます。
デッドレターキューを組み込んだキューイングシステムには、Amazon Simple Queue Service、Apache ActiveMQ、HornetQ、Microsoft Message Queuing、Microsoft Azure Event Grid and Azure Service Bus、WebSphere MQ、Rabbit MQ、Apache Pulsarなどがあります。
ドロップされたメッセージまたはデッドレターキューに格納されたメッセージのレートは、可用性を図るよい指標となるが、問題の検出が遅すぎる場合がある。
デッドレターキューの容量について警告するのは良い考えだが、デッドレターキューの情報が到着するのが遅いので、問題を検出するために使うには不十分である。
マルチテナント非同期システムのバックログ
多くの非同期システムはマルチテナントである。
マルチテナントとは、SaaSやASPサービスなどで、機材やソフトウェア、データベースなどを複数の顧客企業で共有する事業モデル。
また、システムやソフトウェアが複数の利用者で共有できるような設計・構造になっていること。
（抜粋）マルチテナント型クラウドサービスの例
AWS
Azure
マルチテナントの利点は、個別管理が不要であり、運用のオーバーヘッドを節約してリソースを集中させられることである。
ITの分野では、コンピュータで何らかの処理を行う際に、その処理を行うために必要となる付加的、間接的な処理や手続きのことや、そのために機器やシステムへかかる負荷、余分に費やされる処理時間などのことをオーバーヘッドということが多い。
通信の分野でも、送りたいデータや信号そのものとは別に付加的に必要となる制御用のデータなどのことや、それを処理、伝送するために余計にかかる負荷や時間のことをオーバーヘッドという。
しかし、エンドユーザーは、他のエンドユーザーがどれだけ負荷をかけているかに関わらず、シングルテナントのように、高い可用性とレイテンシーが許容可能な範囲であることを求めてくる。
SaaS(サース)などのサービスにおいて、顧客企業が一つのシステムを専有する方式。
AWSのサービスは、内部キューを直接公開する代わりに、軽量なAPIと認証システムを実装している。
APIにより、エンドユーザーの公平性を保つことができる。
AWSは、顧客の規模に応じて、ある程度の柔軟性を持たせつつ、エンドユーザー個別の制限を設けている。
制限によって突発的なスパイク(負荷の増加)によるシステムダウンを防ぎ、裏でプロビジョニングを確保する。
プロビジョニングとは、必要に応じてネットワークやコンピューターの設備などのリソースを提供できるよう予測し、準備しておくことです。供給や設備等の意味を表すプロビジョン（provision）という単語がもととなって派生した言葉です。
非同期システムの公平性は、同期システムの調整と同じように機能するが、非同期システムは大量のバックログがたまる可能性があるため、同期システムの調整よりも重要である。
例として、非同期システムに制限がかかっていない状況で、1人のエンドユーザーがトラフィックを大きく増加させ、システム全体のバックログを増加させた場合を考えてみよう。
オペレータが状況を把握し、問題を対処するのに30分かかり、その間にスケーリングした容量の10倍の量がキューに入れられてしまうと、システムが正常に回復するのに、問題対処のため停止していた時間(30分)の10倍の300分かかる計算となる。
非同期システムの場合、短時間の突発的なスパイクでも、キューに大量のバックログがたまることで、長時間の停止が発生する可能性があるのである。
実際のAWSには、Auto Scalingのような防止する仕組みがある。
また、複数のキューを設定したり、最新のデータが処理されるためエンドユーザーにウケの良い後入後出になるよう設計するとよい。
AWS Auto Scaling は、安定した予測可能なパフォーマンスを可能な限り低コストで維持するためにアプリケーションをモニタリングし、容量を自動で調整します。
復元力のあるマルチテナント非同期システムを作成するための Amazon の戦略
マルチテナントの非同期システムを障害に強くするためにAmazonが採用している戦略パターン
① ワークロードを個別のキューに分離する
各顧客に独自のキューを割り当てる。
ただしコスパが悪く、エンドユーザーが多いと処理が手間になる。
② シャッフルシャーディング
1つしかキューがないと障害の原因につながりやすいため、予備として複数のキューを割り当てる。
（手前味噌ですがシャッフルシャーディングの詳細は以下）
③ 過剰なトラフィックを別のキューに並べる
過剰なトラフィックを選り分ける。
④ 古いトラフィックを別のキューに並べる
古いトラフィックを選り分けることで、新しいメッセージを素早く処理できる。
⑤ 古いメッセージのドロップ
一部のシステムでは、古いトラフィックを削除する。
⑥ ワークロードごとのスレッド (およびその他のリソース)の制限
1つのワークロードが割り当てたシェア以上のリソースを使えないよう、システムを設計する。
処理は遅くなるが、負荷が同じであれば同時に実行できる処理の量が増加する。
処理能力はリトルの法則で表される。
リトルの法則(Google 翻訳)
待ち行列理論、数学内の規律確率論、リトルの結果、定理、補題、法律、または式による定理であるジョン・リトル長期平均数のことを述べL Aの顧客の定常システムは、長期平均実効到着率λに顧客がシステムで費やす平均時間Wを掛けたものに等しい。
代数的に表現される法則は
（L:店舗の平均顧客数 λ :単位時間あたりの客数 W:平均滞在時間）
直感的には簡単に見えますが、「到着プロセスの分布、サービスの分布、サービスの順序など、実質的に何の影響も受けない」ため、驚くべき結果です。
ノンブロッキング I/O を使用して処理能力を確保する。
最も単純なシングルスレッド×ブロッキングIOです。
店員（スレッド）が１人しかいないので同時に１人のお客さんしか処理できません。マルチスレッド×ブロッキングIOです。ApacheなどノンブロッキングIOが登場する前のサーバアプリケーションはこのモデルでした。
単純にスレッド店員（スレッド）を増やすことで同時に処理可能なお客さんの数が増えました。店員の数を増やせば増やすほど同時に処理可能なお客さんを増やすことができますが、増やすことができるのはレジの数（CPU）までとなります。それ以上の店員がいても基本的には意味がありません。ノンブロッキングIOです。店員さんがスキルアップし、お弁当の温め中に次のお客さんの会計を行うことができるようになりました。
⑦ バックプレッシャーをアップストリームに送信する
バックプレッシャーはすべてのシステムに向いているわけではない。
バックプレッシャーとは、半二重接続のネットワーク機器などで用いられるフロー制御方式の一つで、受信側が記憶装置の容量の飽和を防ぐためにわざと送信側の送信動作を妨害・抑止する手法。
⑧ 遅延キューを使用して後まで作業を先送りにする
メッセージの配信を待機させれば、システムは最新のデータを処理することができる。
⑨ あまりにも多くの処理中のメッセージを避ける
デキューに失敗してメッセージが削除されないバグが発生する可能性があるので、この余計なメッセージを別のキューに移動するとよい。
⑩ 処理できないメッセージにデッドレターキューを使用する
一旦デッドレターキューに格納することで、バグが修正された後にメッセージを再処理することが可能。
⑪ ワークロードごとにポーリングスレッドで追加のバッファーを確保する
ポーリングスレッドが常にビジーになる場合は、バッファーが足りない可能性があるので、追加のバッファを準備する。
スレッド(thread)とは、プログラムが処理を実行する単位をプログラマの必要に応じて増やせるものです。
ポーリング(polling)とは、プログラミングでは定期的に問い合わせをする処理方法のことです。シンプルかつ直感的な処理方式です。
ポーリングでは、スレッドでの処理が終わったかを、スレッド自身へ定期的に問い合わせます。
スレッドが終わったと回答したなら、そこで結果を受け取るのです。
⑫ ハートビートの長期メッセージ
タイムアウトが生じて再試行を続けるときに、連鎖的に発生した電圧ダウンの可能性を考慮してメッセージのハートビートを続行することがある。
ハートビートとは、ネットワークで接続されたコンピューターやネットワーク機器が、接続が有効であることを確認するために、定期的に送信する信号のことである。
この場合、負荷が増加してしまい、システムのレイテンシーが可視性タイムアウトのしきい値を超えてしまうと、その行為自体がさらに負荷を発生させるフォーク爆弾になってしまうことがある。
可視性タイムアウトとは、 SQS のキューに入ったメッセージが処理開始直後に重複して処理されないように、処理中の場合、一時的に他のプロセスからは、メッセージが存在していることを見えないようにする設定です。
Fork爆弾（フォークばくだん）とは、コンピュータシステムへのDoS攻撃の一種で、新たなプロセスを生成するfork機能を使ったものである。
⑬ クロスホストデバッグを計画する
分散システムの障害は複雑すぎる。
これらのアプローチとしては、以下が挙げられる。
- キューの深さを定期的に計測する。
- AWS X-Rayを使って分析及びデバッグを行う。
開発者は、AWS X-Ray を使用して、本番環境や分散アプリケーション (マイクロサービスアーキテクチャを使用して構築されたアプリケーションなど) を分析およびデバッグできます。
X-Ray を使用すると、アプリケーションやその基盤となるサービスの実行状況を把握し、パフォーマンスの問題やエラーの根本原因を特定して、トラブルシューティングを行えます。
AWS X-Ray では、アプリケーション全体で転送されるユーザーリクエストがトレースされます。
- 複雑なワークフローの非同期システムがある場合は、AWS Step Functionsをつかってワークフローを整理する。
AWS Step Functions では、AWS の複数のサービスをサーバーレスのワークフローに整理できるため、すばやくアプリケーションをビルドおよび更新できます。
まとめ
非同期システムは、先入先出の仕組みを取っているため、レイテンシーが重要であるが、その重要性が見過ごされがちである。
非同期システムの場合は、サービスの復旧に時間がかかるとたまったバックログの処理にさらに膨大な時間がかかり、障害につながる可能性がある。
非同期システムを構築する場合は、バックログがどのようにたまるかを予測し、様々な手法を取ってこれを最小限に抑える必要がある。
以上になります、最後までお読みいただきありがとうございました。
おまけ
キュー処理をpythonで再現しているサイトを見つけましたので、やってみました。
# キュー処理を実行するためのクラス
class Queue(object):
def __init__(self):
self.queue_list = []# エンキュー(キューに入れる)処理の関数
def enqueue(self, value):
self.queue_list.append(value)# デキュー(キューから外す)処理の関数
def dequeue(self):
try:
# 先頭をとりだす
value = self.queue_list.pop(0)
except IndexError:
value = Nonereturn value
queue = Queue()
# a、b、c をそれぞれエンキューする
queue.enqueue("a")
queue.enqueue("b")
queue.enqueue("c")
# デキュー1回目。1番最初に入れた a が出力される
print(queue.dequeue())# デキュー2回目。2番目に入れた b が出力される
print(queue.dequeue())# デキュー3回目。3番目に入れた c が出力される
print(queue.dequeue())# デキュー4回目。全てデキュー済みなため、何も出力されない(None)
print(queue.dequeue())
出力結果
（参考）コードはこちら (python3)
元ネタ (ただし python2)
