Heartbeat - ノードの死活監視
ハートビート（heartbeat）は、ノードが「自分は生きている」という短い信号を一定間隔で送り続け、受け取る側がその途絶をもって障害と判断する仕組みです。 ...
Distributed-Systems
Lease - 期限付きで権利を貸す仕組み
Lease（リース）は、ある権利を期限付きで貸し出し、期限が過ぎたら自動的に失効させる仕組みです。貸す側は「これから 10 秒間、あなたがリーダーです」と伝え、借りた側は期限が来る前に更新を続けます。更新が途切れれば、誰の操作も無しに権利は消えます。Gray 氏と Cheriton 氏が 1989 年の論文で、分散ファイルシステムのキャッシュの一貫性を保つ方法として提案しました。 ...
WAL - ログ先行書き込みと 2 つのウォーターマーク
WAL（Write-Ahead Log、ログ先行書き込み）は、DB（データベース）の表や索引をディスクに書き出す前に、その変更をログとして永続化する仕組みです。更新の途中で停止しても、ログを使って未反映の変更を適用できます。毎回すべてのデータページを同期する代わりに、追記するログを同期して応答できる点も利点です。 ...
Quorum - 過半数で決定を成立させる仕組み
Quorum（クォーラム、定足数）は、ある操作を成立させるために応答が必要なノードの最小数です。同じ値を複数のノードに持たせる複製の構成では、全ノードの応答を待たず、この数だけ集まった時点で操作を確定させます。最も広く使われるのは過半数を要求する構成で、N 台のクラスタなら N / 2 + 1 台（小数点以下は切り捨て）の応答で成立します。 ...
Leader and Followers - 更新を 1 台に集約する複製の型
Leader and Followers は、同じデータを複製して持つノードのうち 1 台を Leader に決め、更新を全て Leader が受け付けて残りの Follower に配る構成です。更新の受け口が 1 台に絞られるため、同じデータへの更新の順序は Leader が決めた 1 つに定まります。 ...
2PC - コミットか中止を全参加者で揃える
2PC（Two-Phase Commit、2 相コミット）は、複数の DB（データベース）にまたがる 1 つの更新について、関わった全員の最終的な判断がコミット（commit）か中止（abort）のどちらか一方に揃うようにする手順です。コミットできるかを全員に問い合わせる準備フェーズと、決めた結果を配る決定フェーズの 2 段階で進むことが名前の由来です。 ...
Idempotency - 同じ要求を何度受け取っても結果を 1 回分に保つ
冪等（べきとう、idempotent）は、同じ操作を 1 回実行した時と、繰り返し実行した時とで、要求した側が意図した結果が同じになる性質です。 決済 API に課金の POST を送り、504 Gateway Timeout が返ってきたとします。課金が成立したのか、要求が届かないまま終わったのかは、この応答からは分かりません。この POST が冪等なら、もう一度送っても課金は 1 回分に留まります。 ...
Transactional Outbox - id の順に読む relay は、コミット済みの行を飛ばす
注文を DB（データベース）に保存したら、在庫や配送のサービスに「注文が確定した」というイベントを送りたい場面があります。DB の更新とイベントの送信を食い違わせないために、注文と同じトランザクションで、送りたいイベントを outbox という表に 1 行書いておき、別のプロセスが後からその行を読んで送る仕組みを Transactional Outbox と呼びます。 ...
Consistent Hashing - サーバーを増やす時のデータ移動を減らす
Consistent Hashing（コンシステントハッシュ法）は、データを複数のサーバーに振り分ける時に、サーバーの追加・削除で保存先が変わるデータを少なくする方法です。Karger 氏らが 1997 年の論文で、Web キャッシュへの要求の集中を和らげる目的で提案しました。 ...
Byzantine Fault Tolerance - 嘘をつくノードがいても合意する
ビザンチン障害耐性（Byzantine Fault Tolerance、BFT）は、一部のノードが嘘をついても、正直なノード同士の決定を揃える性質です。ここで言う嘘は、誤った値を返すことに加えて、相手ごとに違う値を言うこと（equivocation、二枚舌）も含みます。止まったノードだけを想定する合意の仕組みは、この種の故障に耐えられません。 ...
Backpressure - 下流の詰まりを上流に伝えて流量を合わせる
バックプレッシャー（backpressure）は、下流の処理が追い付かない時に、その事実を上流に伝えて送る量を減らさせる仕組みです。データを作って送る側を Producer、受け取って処理する側を Consumer と呼ぶと、要求やデータは Producer から Consumer に流れ、「待って」の信号は逆向きに流れます。 ...
Distributed Tracing - 要求が通った経路と時間を因果関係付きで記録する
traceparent: 00-4bf92f3577b34da6a3ce929d0e0e4736-00f067aa0ba902b7-01 上記は、サービスが別のサービスを呼ぶ時に HTTP ヘッダとして付ける 1 行です。W3C Trace Context（W3C の勧告）が形式を定めており、「この要求は、どの処理の続きか」を受け取った側に伝えます。このように処理の間で受け渡す情報は、Context と呼ばれます。 ...
FLP Impossibility - 非同期の合意が必ず終わるとは限らない理由
FLP 不可能性（FLP impossibility）は、Fischer・Lynch・Paterson の 3 氏が論文「Impossibility of Distributed Consensus with One Faulty Process」（1985 年）で示した定理です。ここでの合意は、複数のサーバー（論文の用語ではプロセス）がそれぞれ持つ値から、1 つの値を全員で選ぶことです。 ...
Retry and Backoff - 失敗した要求を時間をずらして送り直す
再試行（retry）は、失敗した要求を同じ内容でもう一度送る処理です。HTTP や gRPC のクライアント、クラウドの SDK、メッセージの配送は、一時的な失敗を再試行で隠しています。バックオフ（backoff）は再試行の前に待つ時間のことで、失敗のたびに待ち時間を倍にしていく形を指数バックオフ（exponential backoff）、その待ち時間を乱数でばらつかせることをジッター（jitter）と呼びます。 ...
Saga - ローカルトランザクションをつなぎ、失敗したら補償で戻す
Saga は、複数のサービスにまたがる 1 つの業務の処理について、サービスごとのローカルトランザクション（1 つの DB の中で閉じたトランザクション）の列として順に確定させ、途中の段が失敗したら確定済みの段を補償トランザクション（compensating transaction）で打ち消す方法です。名前と考え方は、Hector Garcia-Molina 氏と Kenneth Salem 氏が 1987 年の SIGMOD で発表した論文「Sagas」（PDF）に由来します。 ...
Rate Limiting - 一定時間あたりの要求の数に上限を設ける
レート制限（rate limiting）は、利用者ごとに一定時間あたりに受け付ける要求の数に上限を設け、超えた分を断るか遅らせる仕組みです。公開 API の「1 分に 60 回まで」、ログイン画面の試行回数の制限、Web サーバーの nginx の limit_req などが、この仕組みにあたります。断る時は、HTTP の 429 Too Many Requests を返すのが一般的です。 ...