# 分散cron ## 定義 分散cron(distributed cron)とは、Unixの伝統的なcronユーティリティが前提としてきた単一マシン・単一障害ドメインの周期ジョブ起動を、複数マシン・複数レプリカからなる分散システムへ拡張したものである。中心的な難しさは、**cronジョブの多くがべき等でない**(複数回起動が許されない)ことに由来する: 単一マシンcronの`crond`は起動をfire-and-forgetで追跡しないが、分散環境ではリーダー障害・部分的なRPC失敗によって「起動したかどうか分からない」状態が生じうるため、べき等でないジョブに対して安全にリカバリするには、起動の状態そのものを一貫性を持って追跡する仕組みが必要になる。(Source: [[@2016__OReilly__SRE Book - Chapter 24 Distributed Periodic Scheduling with Cron]]) Googleの分散cronは、この問題を(1) [[分散コンセンサス]]([[Paxos]]の変種であるFast Paxos)によるリーダー・フォロワー間の起動状態複製、(2) 外部データセンタースケジューラ([[Borg]])への副作用をジョブ名の事前計算によってべき等性なしに再開可能にする設計、(3) crontab書式の拡張によるthundering herd回避、という3つの柱で解決する。(Source: [[@2016__OReilly__SRE Book - Chapter 24 Distributed Periodic Scheduling with Cron]]) ## スキップと二重実行のトレードオフ cronジョブの信頼性要件は個々のジョブの性質(べき等性の有無・起動失敗の許容度)ごとに異なり、単一の答えは存在しない。ガベージコレクションのようなべき等なジョブは複数回起動しても安全だが、ニュースレター配信や給与計算のようなべき等でないジョブは二重起動が許容できない。一方で、5分ごとのガベージコレクションは1回のスキップが許容できても、月1回の給与計算はスキップが許容できないこともある。この非対称性の中で、Googleの分散cronは「インフラが許す限り二重起動よりスキップを選ぶ」という一般方針(fail closed)を採用する。理由は、スキップされた起動からの復旧の方が二重起動からの復旧より御しやすいためである——ニュースレターの二重送信のように、二重起動は取り消しが困難、あるいは不可能な場合がある。この方針を機能させるには、cronジョブの所有者自身が自分のジョブを監視できる仕組み(cronサービスによる状態公開、または独立した効果監視)が前提になる。(Source: [[@2016__OReilly__SRE Book - Chapter 24 Distributed Periodic Scheduling with Cron]]) ## 外部副作用の耐久化 分散cronがプロセス起動をマシンから切り離すと、データセンタースケジューラへのジョブ起動は複数RPCを要することがあり、その一部だけが成功する部分実行失敗という新たな障害モードが生まれる。この状態からべき等でない副作用を安全に再開するには、次のいずれかを満たす必要がある。 - 再選出後に継続する外部システムへの全操作がべき等であること - 外部システム上の全操作の状態を曖昧さなく照会できること Googleの分散cronは後者を、Borg上のジョブ名をミューテーションなしに事前計算しレプリカへ配布しておく手法で実現する。新リーダーは事前計算済みの名前の状態を照会するだけで、未起動のジョブを特定して起動できる。さらに、この事前計算した名前にはスケジュールされた起動時刻を含める(あるいは起動時刻を紐づけて照会可能にしておく)ことが重要である。起動時刻を含めないと、短命だが頻繁なジョブで「新リーダーが完了済みのジョブを未完了と誤認し再起動してしまう」二重起動が起こりうる。(Source: [[@2016__OReilly__SRE Book - Chapter 24 Distributed Periodic Scheduling with Cron]]) ## 状態管理: Paxosログの圧縮とストレージ配置 分散cronは起動の開始・終了をPaxosでレプリカのクォーラムへ同期的に通知するが、Paxosは本質的に継続的に追記されるログであるため、無限成長を防ぐスナップショットによる圧縮が必要になる。Googleの実装は、Paxosログをレプリカのローカルディスクに(デフォルト3レプリカ分)保存し、スナップショットもローカルディスクに保存しつつ重要性の高さゆえに分散ファイルシステムへもバックアップする。ログ自体は分散ファイルシステムへ保存しない——これは「ログの喪失は直近の状態変更という有界な損失にとどまるが、スナップショットの喪失は内部状態の完全な喪失を意味する」という非対称なリスク評価に基づく意識的な設計判断である。(Source: [[@2016__OReilly__SRE Book - Chapter 24 Distributed Periodic Scheduling with Cron]]) ## thundering herdの回避 大規模cronでは、多数のチームが同じ慣習的な時刻(深夜0時など)にジョブを設定することでデータセンター使用量の急激なスパイクが生じる。Googleはcrontab書式にクエスチョンマーク拡張(値の選択をcronシステムに委ね、cronジョブ設定を指定範囲でハッシュして値を決める)を導入し、起動時刻をより均等に分散させた。ただしこの緩和策をもってしても、外部イベントへの時間的依存など特定時刻への起動集中要因は残るため、起動数のグラフには依然スパイクが頻発する。(Source: [[@2016__OReilly__SRE Book - Chapter 24 Distributed Periodic Scheduling with Cron]]) ## 横断的知見 - **同一書籍内で、thundering herd問題への対処がスケジューリング層とパイプライン実行層という異なるレイヤーで独立に扱われる**: 本ページ(第24章)は、cronジョブの起動時刻自体をハッシュベースで分散させることでthundering herdを緩和する、いわば「発生源での予防」を扱う。一方、[[周期パイプライン]](第25章)が記録するthundering herd問題は、既にスケジュールされ起動されたパイプラインが実行段階でワーカー数の過剰・不良なリトライロジックによって共有インフラを圧倒する現象であり、「起動後の増幅」を扱う。両章とも同じ現象名(thundering herd)を使うが、第24章の対策(起動時刻の分散)は第25章が記録する問題(起動後のリトライ雪崩・モアレ負荷パターン)を防げない——起動時刻を分散させても、個々の起動が実行段階で共有リソースへ与える負荷そのものは変わらないためである。この2章は、同じ用語が指す問題が発生する層によって対処法が異なることを示す。(Source: [[@2016__OReilly__SRE Book - Chapter 24 Distributed Periodic Scheduling with Cron]], [[@2016__OReilly__SRE Book - Chapter 25 Data Processing Pipelines]]) ## 未解決の問い - crontabのクエスチョンマーク拡張(ハッシュベースの時刻分散)を導入してもなお起動数グラフにスパイクが残る、と原本は述べるが、緩和前と緩和後でスパイクの振幅がどの程度縮小したかを示す定量データは原本にない。 - ジョブ名の事前計算によるべき等性回避は、Borgのように名前でジョブを一意に照会できるインフラを前提とする。名前による照会ができない、あるいはジョブ起動が単一RPCで完結しないより複雑なデータセンタースケジューラでは、この設計はどこまで一般化できるか。 - 「二重起動よりスキップを選ぶ」という方針は、月次の給与計算のようなスキップが許されないジョブにはそのまま適用できない。原本はこの種のジョブへの具体的な対処(例外的にどちらのリスクを許容するかの判断基準)を示していない。 ## 関連 - 概念: [[べき等性]](本ページの「スキップと二重実行のトレードオフ」の理論的基盤) / [[分散コンセンサス]](Fast Paxosによる状態複製) / [[複製ステートマシン]] / [[周期パイプライン]](同一書籍・隣接章が扱う別レイヤーのthundering herd問題) - 実体: [[Štěpán Davidovič]](著者) / [[Borg]](副作用の耐久化対象) / [[Paxos]] - ソース: [[@2016__OReilly__SRE Book - Chapter 24 Distributed Periodic Scheduling with Cron]] ## 出典 - [[@2016__OReilly__SRE Book - Chapter 24 Distributed Periodic Scheduling with Cron]]