Skip to content

fairshare documentation

Jump to bottom
Christopher Moussa edited this page Sep 16, 2020 · 2 revisions

Fairshare Algorithm Documentation

Represents the portion of the computing resources that have been allocated to different projects

  • these allocations are assigned to an account
  • there can be multiple levels of allocations made as allocations of an account can be further divided to sub-accounts

EXAMPLE

Accounts Share
A 40%
B 25%
C 20%
D 15%
A's Subaccounts Share
A1 10%
A2 12%
A3 10%
A4 8%
A3's Subaccounts Share
a1 1%
a2 1%
...
a10 1%

A user's normalized shares:

S = (S_user / S_siblings) * (S_account / S_sibling-accounts) * (S_parent / S_parent-siblings) * ...

EXAMPLE: a1

S = (1/10) * (10/40) * (40/100) = 1/10 * 1/4 * 4/10 = 1/10 ➡️ 1% ✓

Normalized Usage

U_N = U_user / U_total

U_user = the processor * seconds consumed by all of a user's jobs in a given account for over a fixed time period

U_total = the total number of processor * seconds utilized across the cluster during that same time period

Simplified Fair-Share Formula

F = 2^(-U/S/d)

where

S = normalized shares

U = the normalized usage factoring in half-life decay

d = the FairShareDampeningFactor (a config parameter w/ a default value of 1)

F gives a value between 0 and 1, where 0 represents the lowest priority, 1 the highest

Value Meaning
0.5 the user's jobs use the exact portion allocated
> 0.5 the user's jobs use less than the exact portion allocated
< 0.5 the user's jobs use more than the exact portion allocated

Another layer of "fairness" is taking into account the usage from other users in that account

Fair Share Formula

F = 2^(-U_E/S)

where

U_E = U_A-child + ((U_E-parent - U_A-child) * S_child/S_all-siblings)

U_A-child = the actual usage of the child user or child account

U_E-parent = the effective usage of the parent account

S_child = the shares allocated to the child user or child account

S_all-siblings = the shares allocated to all the children of the parent account

Account A's Shares = 40%

  • sub account B = 30% (one user: U1)
  • sub account C = 10% (two user's: U2, U3, each get 5%)

Account D's Shares = 60%

  • sub account E = 25% (one user: U4)
  • sub account F = 35% (one user: U5)

Normalized Shares

A = 0.4

  • B = 0.3 (U1 = 0.3)
  • C = 0.1 (U2 = 0.05, U3 = 0.05)

D = 0.6

  • E = 0.25 (U4 = 0.25)
  • F = 0.35 (U5 = 0.35)

Users 1, 2, and 4 have run jobs that have consumed the machine's resources

Actual Usage

  • U1 = 0.2
  • U2 = 0.25
  • U4 = 0.25

A's effective usage = U_1-E + U_2-E = 0.2 + 0.25 = 0.45

  • B's effective usage = 0.2 + ((0.45 - 0.2) * 30/40) = 0.3875

  • C's effective usage = 0.25 + ((0.45 - 0.25) * 10/40) = 0.3

D's effective usage = U_4-E = 0.25

  • E's effective usage = 0.25 + ((0.25 - 0.25) * 25/60) = 0.25

  • F's effective usage = 0 + ((0.25 - 0) * 35/60) = 0.1458

Users Effective Usage

U1 = 0.2 + ((0.3875 - 0.2) * 1/1) = 0.3875

U2 = 0.25 + ((0.3 - 0.25) * 1/2) = 0.275

U3 = 0 + ((0.3 - 0) * 1/2) = 0.15

U4 = 0.25 + ((0.25 - 0.25) * 1/1) = 0.25

U5 = 0 + ((0.1458 - 0) * 1/1) = 0.1458

Fair Share Calculation

U1 = 2^(-.3875/.3) = 0.41

U2 = 2^(-.275/.05) = 0.02

U3 = 2^(-.15/.05) = 0.13

U4 = 2^(-.25/.25) = 0.5

U5 = 2^(-.1458/.35) = 0.75

Clone this wiki locally