Loading article…
優勢リソース公平性（DRF）は公平な分割のためのルールです。クラウドコンピューティング環境では、各ユーザーが異なるリソースの組み合わせを必要とする可能性があるため、コンピューティングリソースをユーザー間で分割するのに特に役立ちます。DRFは、2011年にAli Ghodsi、Matei Zaharia、Benjamin Hindman、Andy Konwinski、Scott Shenker、Ion Stoicaによって発表されました。[1]
モチベーション
リソースが 1 つの環境では、ユーザーに与えられるリソースの最小量を最大化することを目的とした、最大最小公平性の基準が広く使用されています。しかし、クラウド コンピューティングでは、メモリ、CPU、帯域幅、ディスク容量など、さまざまな種類のリソースを共有する必要があります。Apache Hadoopなどの以前の公平なスケジューラでは、各リソースの固定量 (例: 4 CPU、32 MB メモリなど) を持つノードを定義し、ノードの一部であるスロットを分割することで、マルチリソース設定を単一リソース設定に縮小していました。しかし、この方法は非効率的です。すべてのユーザーが同じ比率のリソースを必要としているわけではないからです。たとえば、一部のユーザーはより多くの CPU を必要とし、他のユーザーはより多くのメモリを必要とします。その結果、ほとんどのタスクはリソースを十分に活用しないか、過剰に活用します。
DRF は、ユーザーに与えられる主要なリソースの最小量を最大化することで問題を解決します(次に、語彙目録の順序で 2 番目に小さいものなど)。主要なリソースはユーザーごとに異なる場合があります。たとえば、ユーザー A が CPU を大量に使用するタスクを実行し、ユーザー B がメモリを大量に使用するタスクを実行する場合、DRF はユーザー A に与えられる CPU シェアとユーザー B に与えられるメモリ シェアを均等化しようとします。
意味
リソースはm 個あります。リソースの合計容量はr 1、...、r mです。
ユーザーはn人います。各ユーザーは個別のタスクを実行します。各タスクには、各リソースの必要量を表す需要ベクトル( d 1 ,.., d m ) があります。ユーザーの効用は、実行できるタスクの数に等しいと暗黙的に想定されています。たとえば、ユーザー A が需要ベクトル [1 CPU、4 GB RAM] でタスクを実行し、3 CPU と 8 GB RAM を受け取った場合、実行できるタスクは 2 つだけなので、効用は 2 です。より一般的には、x 1 ,..., x m個のリソースを受け取るユーザーの効用は min j ( x j / d j ) です。つまり、ユーザーにはレオンチェフ効用があります。
需要ベクトルは、容量の割合に正規化されます。たとえば、システムに 9 個の CPU と 18 GB の RAM がある場合、上記の需要ベクトルは [1/9 CPU、2/9 GB] に正規化されます。各ユーザーについて、需要割合が最も高いリソースは、主要リソースと呼ばれます。上記の例では、2/9 が最大の割合であるため、主要リソースはメモリです。ユーザー B が需要ベクトル [3 CPU、1 GB] ([1/3 CPU、1/18 GB] に正規化) でタスクを実行する場合、そのユーザーの主要リソースは CPU です。
DRF は、すべてのエージェントが少なくとも x の主要リソースを受け取ることができる最大 x を見つけることを目指します。上記の例では、この最大 x は 2/3 です。
- ユーザー A は 3 つのタスクを取得しますが、これには 3/9 の CPU と 2/3 GB が必要です。
- ユーザー B は 2 つのタスクを取得しますが、これには 2/3 の CPU と 1/9 GB が必要です。
最大値xは線形計画法を解くことで見つけることができます。辞書式最大最小最適化を参照してください。あるいは、DRFを順番に計算することもできます。[1] ：アルゴリズム1 アルゴリズムは、各ユーザーが使用した主要リソースの量を追跡します。各ラウンドで、これまでに割り当てられた主要リソースが最も小さいユーザーを見つけ、このユーザーに次のタスクを割り当てます。この手順により、同じユーザーが異なる需要ベクトルを持つタスクを実行できることに注意してください。
プロパティ
DRF には、リソース割り当てに関して他のポリシーに比べていくつかの利点があります。
- 比例性: すべてのリソースがユーザー間で均等に分割されるシステムでは、各ユーザーは少なくとも自分が取得できるのと同じ量のリソースを受け取ります (著者はこの状態を「インセンティブの共有」と呼んでいます)。
- 戦略的耐性: ユーザーは自分のニーズについて嘘をついて、より大きな割り当てを得ることはできません。クラウド オペレーターからの証拠によると、ユーザーはより良い割り当てを得るためにサーバーを操作しようとしているため、戦略的耐性は重要です。
- 嫉妬のなさ: 他のユーザーの割り当てを好むユーザーはいないでしょう。
- パレート効率: 他の割り当ては、一部のユーザーにとってより良く、他のユーザーにとってより悪くはありません。
- 人口単調性: ユーザーがシステムを離れても、残りのユーザーの割り当ては減少しません。
ボトルネック リソース(すべてのユーザーからの需要が高いリソース)が 1 つだけある場合、DRF は最大最小公平性にまで低下します。
ただし、DRF はリソースの単調性に違反します。つまり、システムにリソースが追加されると、一部の割り当てが減少する可能性があります。
拡張機能
加重DRFは、異なるユーザーが異なる重み（異なる権限を表す）を持つ設定へのDRFの拡張である。[1] ：4.3
Parkes、Procaccia、Shah [2]は、重み付きDRFを、一部のユーザーがすべてのリソースを必要としない（つまり、一部のリソースに対する需要が0である）設定に正式に拡張した。彼らは、拡張バージョンでも比例性、パレート効率、羨望のなさ、戦略的困難性、さらにはグループ戦略的困難性を満たすことを証明した。その一方で、DRFは功利主義的社会福祉が低下する可能性があること、つまり効用の合計が最適値の1/ mにしかならない可能性があることを示している。しかし、比例性、羨望のなさ、戦略的困難性のいずれかを満たすメカニズムは、同じように功利主義的福祉が低下する可能性があることを証明した。彼らはまた、ユーザーの需要が分割不可能な設定（公平なアイテム割り当てなど）にDRFを拡張した。分割不可能な設定では、羨望のなさがEF1に緩和されている。彼らは、戦略的困難性がPO+EF1またはPO+比例性と両立しないことを示している。しかし、SequentialMinMax と呼ばれるメカニズムは、効率性、比例性、EF1 を満たします。
Wang、Li、Liang [3]は、 DRFを複数の異種サーバーを備えたシステムに拡張したDRFHを発表した。
実装
DRF は、クラスター リソース マネージャーであるApache Mesosで最初に実装され、これまで使用されていた公平共有スキームよりも優れたスループットと公平性を実現しました。
参照
参考文献
- ^ abc 「主要リソースの公平性：複数のリソースタイプの公平な割り当て」2011年。
- ^ Parkes, David C.; Procaccia, Ariel D.; Shah, Nisarg (2015-03-27). 「優位なリソースの公平性を超えて: 拡張、制限、および不可分性」ACM Transactions on Economics and Computation . 3 (1): 3:1–3:22. doi :10.1145/2739040. ISSN 2167-8375.
- ^ Wang, Wei; Li, Baochun; Liang, Ben (2014). 異機種サーバを備えたクラウドコンピューティングシステムにおける優位なリソース公平性。pp. 583–591. arXiv : 1308.0083 . doi :10.1109/INFOCOM.2014.6847983. ISBN 978-1-4799-3360-0. 2023年12月20日閲覧。