算法:最大最小公平算法

當我們管理資源分配時,總是會遇到如下問題:每個用戶具有相同的優先級,有的用戶需求的資源少,有的用戶需求的資源多,我們該如何分配才能儘量保證不會出現“餓死”的情況並保證公平的分配呢?對於這個問題,下面介紹大數據中資源管理利器YARN中的解決方案:最大最小公平算法。

最大最小公平算法的形式化定義

  • 資源按照需求遞增的順序進行分配
  • 不存在用戶得到的資源超過自己的需求
  • 未得到滿足的用戶等價的分享資源
  • 例:

    假設:有4個用戶,每個用戶需求的資源量分別為A:1,B:2,C:5,D:6,總資源量為10。

    第一輪:將10平均分成4份,每份是2.5,由於2.5大於了A的需求,故每個用戶首先分得與A相同的資源,即為1,則剩餘6。分配情況為:A:1,B:1,C:1,D:1;

    第二輪:將剩餘資源6平均分成3份,每份為2,累加第一輪分配的資源1,此時B的資源為3,超出了資源需求2。因此此輪每個用戶分得1個資源,剩餘資源量為3。分配情況為:A:1,B:2,C:2,D:2;

    第三輪:將剩餘資源3平均分成兩份,每份為1.5,此時均小於C與D的資源需求,將1.5分配給剩餘用戶後,分配結束。此時,分配情況:A:1,B:2,C:3.5,D:3.5。

    當用戶具有不同權重時,又該如何分配呢?

    此時我們可以根據之前的算法擴展到加權情況。

    例:

    假設:有4個用戶,每個用戶需求的資源量分別為A:1,B:9,C:6,D:4,權重為1,2,0.5,4,總資源量為15。

    首先歸一化權重,即將最小權重設為1,則此時權重分別為:2,4,1,8。此時,我們在拆分資源時,則不是平均分成4份,而是首先要根據權值,平均分成2+4+1+8=15份。

    第一輪:將15份資源平均分成15份,每份為1,則A分得1x2=2,B分得1x4=4,C分得1x1=1,D分得1x8=8,由於A超出了需求,多出了1,D也超出了需求,多出了4,故剩餘資源量為5,分配情況為,A:1,B:4,C:1,D:4;

    第二輪:此時剩餘B、C沒有滿足資源需求,其權值分別為4,1。將剩餘資源5平均分成4+1=5份,每份為1,此時,B可再分得1x4=4,累加上一輪分得的資源總共為8,D可再分得1x1=1,累加上一輪分得的資源總共為2,C和D均沒有滿足需求,此時分配結束。總體分配情況為A:1,B:8,C:2,D:4。

    最大最小公平被認為是一種很好權衡有效性和公平性的自由分配策略,在YARN中擔當重要的資源分配策略。


    分享到:


    相關文章: