これは Patrik Rak による巧妙なキューマネージャスケジューリング アルゴリズムについてのドキュメントの始まりです。長い間、このコードは オプションのモジュールとして "nqmgr(8)" (new queue manager) という 名前で使うことができました。Postfix 2.1 ではこれがデフォルトのキュー マネージャであり、これは常に "qmgr(8)" と 呼ばれます。古いキューマネージャはしばらくの間 "oqmgr(8)" という名前で使えます。
古い Postfix スケジューラには設計上、不運な選択に起因するいくつかの 制限がありました。
同じメッセージ配送 transport を使って配送されるメールの 配送先によるラウンドロビン選択。ラウンドロビン戦略は、一つの (配送先) サイトがメール配送リソースを使い果たしてしまうのを防ぐ ことを意図して選ばれました。しかし、その戦略は双方向ゲートウェイで 中に入ってくるメールに不利益をもたらしてしまいました。ひどく 苦しんでいる内向きの配送先は、他の配送先よりもメールが多いにも かかわらず 1/配送先数 の時間しか選択されないため、メールが遅延して しまったかもしれません。
Victor Duchovni が回避方法を見つけました: 別のメッセージ配送 transport を使い、そうすることで欠乏問題を避けます。Patrik Rak の スケジューラはこの問題を FIFO 選択を使うことで解決します。
古い Postfix スケジューラの2つ目の問題は、バルクメールの 配送が他の配送全てをブロックしてしまい、大きな遅延を引き起こすこと でした。Patrik Rak のスケジューラはすばらしい方法で、受信者の少ない メールがバルクメールをすり抜けられるようにします。
以下の文章は Patrik Rak が書いたもので、それぞれの設定パラメータを 詳細に記述した postconf(5) マニュアルと 合わせて読んでください。
ユーザの観点からは、配送エージェントが利用可能のなったときに次の メッセージを選ぶ方法を除いて、oqmgr(8) と qmgr(8) はどちらも同じです。すでに oqmgr(8) 配送先のラウンドロビンを使い、 qmgr(8) は割り込みのマジックを除いて、単純な FIFO を使っていることはおわかりでしょう。 postconf(5) マニュアルにはユーザが この割り込みマジックの制御に使える全ての取っ手が書かれています - そこに 示されているきわめて単純な条件以外には割り込みはありません。
プログラマレベルのドキュメントについては、Wietse と交わしたそのような メールを全て抜き出さなければいけません [あっ! それはきっと Patrik が 私のためにやってくれるでしょう -- Wietse] が、その会話の中で言い残した ことは全くないと思います。
しかしプログラマの観点からでも、メッセージスケジューリングの考え方 自身には何も付け足すものはありません。見かけが複雑になっているものが 少しありますが、アルゴリズムはユーザが理解しているものと同じです。 ユーザの観点とプログラマの観点の違いをまとめると:
ユーザに対する用語の簡略化: ユーザはメッセージと受信者に ついて知っています。プログラム自身はジョブ (1つのメッセージは複数の ジョブに分割され、それぞれにメッセージを配送する transport が 必要となります) とキューエントリ (それぞれのエントリは同じ配送先の 受信者をグループ化するかもしれません) で動きます。そして qmgr(8) によって導入された、キュー構造を 単にジョブごとに置き換えたようなピア構造があります。
並列数制限の扱い: 並列数制限によってメッセージ (つまり ジョブ) がスケジュールされた順番通りに配送されるとは限らないため、 実際の実装は複雑です。並列数制限に達したら "ブロックしている" ジョブを飛ばして、制限以下になったら再びそのジョブに戻る必要が あります。
リソース制限の扱い: 受信者が全て読み込まれるとは限らない ため、実際の実装は複雑です。そのため、それぞれのメッセージには メモリに読み込まれる受信者の他にファイルに残される受信者があるかも しれません。これは a) プリエンプティブアルゴリズムは実際の受信者数 ではなく見積もりを使って動く必要があり、b) 同時にメモリに読み 込まれる受信者の transport ごとのプールを扱うことが必要な特別な コードがあり、c) バッチ処理でメモリに受信者を読み込めることが 必要で、適切なときにそれを起動するコードが特別なコードがあることを 意味します。
効率的な動作: わかっている限りでは、重要なのは出来るだけ 最短の時間で (直接もしくは少なくとも償却計算量 (amotized complexity) が使われたときに) 処理することですが、現在のジョブに割り込ませる 最適な候補はどれかを選ぶためには、最大で全ての transport ジョブに 対して線形検索する必要があります (理論上最悪の場合 - 実際には もっとよい)。これは次に配送されるキューエントリが選ばれるときに 毎回おこなわれるため、キャッシュに加えてオーバーヘッドを最小に するのが適切と思われます。この候補キャッシュの管理は少しわかり にくいものです。
ポイント 2 および 3 は実装 (見かけ) を複雑にしているもので、実際の コーディング作業の部分ですが、スケジュールアルゴリズム自身を理解するのは (これは実際の思考作業の部分です) かなり簡単であると信じています。