道中道楽〜はてな別館〜 このページをアンテナに追加 RSSフィード

2018-07-12

[]マクドナルドは、頑なにフォーク並びを拒みますがなぜでしょう? 自発的に発生したフォーク並びさえ解散させています。に対するKenn Ejimaの回答 - Quora

マクドナルドは、頑なにフォーク並びを拒みますがなぜでしょう? 自発的に発生したフォーク並びさえ解散させています。

Kenn Ejima, ソフトウェア開発者
2018/05/02に回答されました 

そのマクドナルドは人気店なのではないですか。

これは応用数学の世界では待ち行列理論と呼ばれているもので、その性質はよく研究され、あらゆる場面で活用されています。

結論を先にいうと、フォーク並びは 「スループット(時間あたりの総処理量)」をやや犠牲にしてでも「公平性(後から来た人が先に窓口に到達することがない)」を優先したい場合に有効な並び方です。

フォーク並びの場合、窓口が空いてから次の人がくるまでの時間、仕事をしていないアイドリング時間が発生します。一件あたりの処理時間が短い単純作業の場合、これは無視できないオーバーヘッドになります。(極端な例でいうと、歩いて窓口にたどり着くまでに10秒、処理に10秒だと窓口の稼働率は半分になります)

このため、混雑の程度がそれほどでもなく余裕がある場合は一列のフォーク並び、そんなことは言ってられないぐらい混雑する場合にはパラレル並び、あるいはハイブリッド方式(複数列のフォーク並び)が採用されます。

フォーク並びは、効率よりも公平性に敏感な日本人の文化とうまくマッチしているのでよく使われますが、本当のところは「全員で平等に待ち時間が長くなってる」だけなので、本当はパラレル並びのほうが行列を抜けるまでの平均時間は短いのです。

実際には、これに加えてさらに土地の有効活用という側面もあります。フォーク並びは多少なりともデッドスペースが生まれるため、同一空間に収容できる人数自体が少なくなります。


この理論は、もともと電話回線業者が交換手の最適な割り当てのために考え出された理論でした。ポアソン過程、リトルの公式、M/M/Cなどのケンドールの記法、大群化効果などの重要なコンセプトがかかわってきます。

その歴史的経緯で、日本でこの分野は「トラフィック制御」ではなく「トラヒック制御」というNTTジャーゴンでの呼称が定着しています。

コンピュータサイエンスの世界では、スループット(処理量)とレイテンシ(遅延)がトレードオフの関係になることは多々あります。CPU/GPU、メモリ、ディスク、ネットワークなど全てのレイヤーで出現するトレードオフです。

たとえば、Webアプリケーションの世界では、集中する負荷を分散させるための道具として、nginxやHAProxyといったロードバランサ・リバースプロキシがあります。

これらがバックエンドにジョブを渡すとき、ラウンドロビンで順番に均等に割り付けるのが、一般的にはもっともスループットが高くできます。

しかし、これだと処理に時間のかかるジョブが走っているとき、その窓口に割り当てられた後続の人たちはみんな長時間待たされてしまいます。(=高レイテンシ)

そこで、ラウンドロビンのかわりに最小コネクション法という、まさにフォーク並びを選択することで、クライアントからみたレスポンス時間のばらつきを小さくすることができるようになります。

その結果、サーバのコストと平均的な遅延(待ち時間)は少しだけ悪化しますが、100msの平均応答時間が150msになっても人間にはほとんど知覚できないので、ほとんどの場合にはラウンドロビンよりも良い方法です。

このように、それぞれの方式には向き不向きがあり、適材適所で使い分けられているのです。


回答者の紹介
Kenn Ejima
京都大学で情報数理工学を専攻
サンフランシスコに住んでいた












https://jp.quora.com/%E3%83%9E%E3%82%AF%E3%83%89%E3%83%8A%E3%83%AB%E3%83%89%E3%81%AF-%E9%A0%91%E3%81%AA%E3%81%AB%E3%83%95%E3%82%A9%E3%83%BC%E3%82%AF%E4%B8%A6%E3%81%B3%E3%82%92%E6%8B%92%E3%81%BF%E3%81%BE%E3%81%99%E3%81%8C%E3%81%AA/answers/81845856?ref=fb_page&uiv=10&txtv=4&source=fb&medium=ad&campaign=uad_i18n_jp_acq&set=japan_all_fb_desktop_a6&content=mcd_a10_10_fg

トラックバック - http://d.hatena.ne.jp/ruminn/20180712/1531344801