The work was split evenly and the workers were not

# Self-authored for the EML case corpus (no external origin). A batch of 2400
# documents is split across 8 workers. Every worker gets exactly 300. How long
# the batch takes, and how long the report says it takes, are computed below.
#
# An equal split is the right default and was chosen deliberately. It is the
# only allocation that needs no information about the workers, so it cannot go
# stale when a machine is replaced, it cannot be gamed, it is one line of code,
# and it is defensible to anyone who asks why they got the share they got. Every
# scheduler that has to run before it knows anything starts here.
#
# The fleet is not uniform. Four machines are current generation, two are a
# generation behind, one is the old box nobody has decommissioned, and one is a
# VM on shared hardware. Nobody chose this; it accumulated.
#
# A batch is not finished when the average worker is finished. It is finished
# when the last worker is finished. An equal split across unequal workers
# maximises the gap between those two numbers, because it gives the slowest
# machine exactly as much work as the fastest.

2400 => documents
8 => workers

# [worker, documents per minute]
[["w0", 100], ["w1", 100], ["w2", 100], ["w3", 100], ["w4", 60], ["w5", 60], ["w6", 40], ["w7", 25]] => fleet

int(documents / workers) => each

"documents: " + str(documents) + " split " + str(workers) + " ways = " + str(each) + " each" ^0
"" ^0

"worker   rate/min   assigned   seconds to finish" ^0
0 => makespan
0 => total_seconds
0 => capacity
for w in fleet:
    int(each * 60 / w[1]) => secs
    total_seconds + secs => total_seconds
    capacity + w[1] => capacity
    if secs > makespan:
        secs => makespan
    "  " + w[0] + "        " + str(w[1]) + "         " + str(each) + "         " + str(secs) ^0
"" ^0

int(total_seconds / workers) => mean_seconds

"  batch finishes when the LAST worker finishes : " + str(makespan) + " seconds" ^0
"  mean worker completion time                  : " + str(mean_seconds) + " seconds" ^0
"  the status page reported the mean" ^0
"" ^0

# ---- what the fleet could have done ----
#
# Allocation proportional to rate finishes every worker at the same moment,
# which is the shortest possible makespan for a fixed total.

int(documents * 60 / capacity) => ideal_seconds

"  fleet capacity                     : " + str(capacity) + " documents per minute" ^0
"  shortest possible batch time       : " + str(ideal_seconds) + " seconds" ^0
"  actual batch time                  : " + str(makespan) + " seconds" ^0
"  cost of the equal split            : " + str(makespan - ideal_seconds) + " seconds" ^0
"  that is " + str(int((makespan - ideal_seconds) * 100 / makespan)) + " percent of the wall clock" ^0
"" ^0

# ---- where the fleet was during those seconds ----

workers * makespan => worker_seconds_paid
worker_seconds_paid - total_seconds => idle_seconds

"  worker-seconds paid for   : " + str(worker_seconds_paid) ^0
"  worker-seconds working    : " + str(total_seconds) ^0
"  worker-seconds idle       : " + str(idle_seconds) ^0
"  utilisation               : " + str(int(total_seconds * 100 / worker_seconds_paid)) + " percent" ^0
"" ^0
"  the four fastest machines finished in " + str(int(each * 60 / 100)) + " seconds and waited " + str(makespan - int(each * 60 / 100)) + " more" ^0
"" ^0

# ---- the shape of the error ----

"quantity                      does the split shape it" ^0
"  documents processed         no, it is a sum" ^0
"  documents per worker        no, that is what was equalised" ^0
"  total worker-seconds        no, work is conserved" ^0
"  batch completion time       YES, it is a maximum" ^0
"  utilisation                 YES, it is a ratio against a maximum" ^0
"  the dashboard showed the first three" ^0
"" ^0
"a maximum is the only statistic an equal split gets wrong, and it is the" ^0
"only statistic the customer experiences" ^0
"" ^0

# ---- the control ----
#
# If the equal split were harming throughput, total documents would drop. It
# does not: every document is processed exactly once under any allocation. The
# allocation moves WHEN the work happens, never HOW MUCH. This is why the
# throughput graph looked fine for a year.

"control - a quantity no allocation can move" ^0
0 => done_equal
0 => shares_truncated
for w in fleet:
    done_equal + each => done_equal
    int(documents * w[1] / capacity) => share
    shares_truncated + share => shares_truncated
documents - shares_truncated => leftover
shares_truncated + leftover => done_proportional
"  documents completed, equal split      : " + str(done_equal) ^0
"  proportional shares before remainder  : " + str(shares_truncated) ^0
"  documents lost to truncation          : " + str(leftover) ^0
"  a real scheduler assigns the remainder, so it must hand out those " + str(leftover) ^0
"  documents completed, proportional     : " + str(done_proportional) ^0
"  difference                            : " + str(done_equal - done_proportional) ^0
"  work is conserved, so this cannot detect the problem" ^0
"" ^0

# ---- the null control ----
#
# A uniform fleet. Same equal split, same code path, and now the split is
# optimal. The split was never the defect on its own.

[["u0", 73], ["u1", 73], ["u2", 73], ["u3", 73], ["u4", 73], ["u5", 73], ["u6", 73], ["u7", 73]] => uniform_fleet

"null control - the same equal split across a uniform fleet" ^0
0 => u_makespan
0 => u_total
0 => u_capacity
for u in uniform_fleet:
    int(each * 60 / u[1]) => usecs
    u_total + usecs => u_total
    u_capacity + u[1] => u_capacity
    if usecs > u_makespan:
        usecs => u_makespan
"  batch time            : " + str(u_makespan) + " seconds" ^0
"  shortest possible     : " + str(int(documents * 60 / u_capacity)) + " seconds" ^0
"  cost of the split     : " + str(u_makespan - int(documents * 60 / u_capacity)) + " seconds" ^0
"  utilisation           : " + str(int(u_total * 100 / (workers * u_makespan))) + " percent" ^0
"  the same allocation is optimal here, so the rule is not 'equal is wrong'" ^0
"  it is 'equal is wrong exactly as far as the fleet is unequal'" ^0
"" ^0

"An equal split needs no information about the workers, which is what makes it" ^0
"safe to write and impossible to get stale. It is also what makes it assign the" ^0
"25-a-minute box the same 300 documents as the 100-a-minute box. The batch took" ^0
str(makespan) + " seconds against a possible " + str(ideal_seconds) + ", the fleet was idle for " + str(idle_seconds) ^0
"worker-seconds of the " + str(worker_seconds_paid) + " paid for, and every document was processed." ^0

documents = 2400
workers = 8
fleet = [["w0", 100], ["w1", 100], ["w2", 100], ["w3", 100], ["w4", 60], ["w5", 60], ["w6", 40], ["w7", 25]]
each = int(documents / workers)
print("documents: " + str(documents) + " split " + str(workers) + " ways = " + str(each) + " each")
print("")
print("worker   rate/min   assigned   seconds to finish")
makespan = 0
total_seconds = 0
capacity = 0
for w in fleet:
    secs = int(each * 60 / w[1])
    total_seconds = total_seconds + secs
    capacity = capacity + w[1]
    if secs > makespan:
        makespan = secs
    print("  " + w[0] + "        " + str(w[1]) + "         " + str(each) + "         " + str(secs))
print("")
mean_seconds = int(total_seconds / workers)
print("  batch finishes when the LAST worker finishes : " + str(makespan) + " seconds")
print("  mean worker completion time                  : " + str(mean_seconds) + " seconds")
print("  the status page reported the mean")
print("")
ideal_seconds = int(documents * 60 / capacity)
print("  fleet capacity                     : " + str(capacity) + " documents per minute")
print("  shortest possible batch time       : " + str(ideal_seconds) + " seconds")
print("  actual batch time                  : " + str(makespan) + " seconds")
print("  cost of the equal split            : " + str(makespan - ideal_seconds) + " seconds")
print("  that is " + str(int((makespan - ideal_seconds) * 100 / makespan)) + " percent of the wall clock")
print("")
worker_seconds_paid = workers * makespan
idle_seconds = worker_seconds_paid - total_seconds
print("  worker-seconds paid for   : " + str(worker_seconds_paid))
print("  worker-seconds working    : " + str(total_seconds))
print("  worker-seconds idle       : " + str(idle_seconds))
print("  utilisation               : " + str(int(total_seconds * 100 / worker_seconds_paid)) + " percent")
print("")
print("  the four fastest machines finished in " + str(int(each * 60 / 100)) + " seconds and waited " + str(makespan - int(each * 60 / 100)) + " more")
print("")
print("quantity                      does the split shape it")
print("  documents processed         no, it is a sum")
print("  documents per worker        no, that is what was equalised")
print("  total worker-seconds        no, work is conserved")
print("  batch completion time       YES, it is a maximum")
print("  utilisation                 YES, it is a ratio against a maximum")
print("  the dashboard showed the first three")
print("")
print("a maximum is the only statistic an equal split gets wrong, and it is the")
print("only statistic the customer experiences")
print("")
print("control - a quantity no allocation can move")
done_equal = 0
shares_truncated = 0
for w in fleet:
    done_equal = done_equal + each
    share = int(documents * w[1] / capacity)
    shares_truncated = shares_truncated + share
leftover = documents - shares_truncated
done_proportional = shares_truncated + leftover
print("  documents completed, equal split      : " + str(done_equal))
print("  proportional shares before remainder  : " + str(shares_truncated))
print("  documents lost to truncation          : " + str(leftover))
print("  a real scheduler assigns the remainder, so it must hand out those " + str(leftover))
print("  documents completed, proportional     : " + str(done_proportional))
print("  difference                            : " + str(done_equal - done_proportional))
print("  work is conserved, so this cannot detect the problem")
print("")
uniform_fleet = [["u0", 73], ["u1", 73], ["u2", 73], ["u3", 73], ["u4", 73], ["u5", 73], ["u6", 73], ["u7", 73]]
print("null control - the same equal split across a uniform fleet")
u_makespan = 0
u_total = 0
u_capacity = 0
for u in uniform_fleet:
    usecs = int(each * 60 / u[1])
    u_total = u_total + usecs
    u_capacity = u_capacity + u[1]
    if usecs > u_makespan:
        u_makespan = usecs
print("  batch time            : " + str(u_makespan) + " seconds")
print("  shortest possible     : " + str(int(documents * 60 / u_capacity)) + " seconds")
print("  cost of the split     : " + str(u_makespan - int(documents * 60 / u_capacity)) + " seconds")
print("  utilisation           : " + str(int(u_total * 100 / (workers * u_makespan))) + " percent")
print("  the same allocation is optimal here, so the rule is not 'equal is wrong'")
print("  it is 'equal is wrong exactly as far as the fleet is unequal'")
print("")
print("An equal split needs no information about the workers, which is what makes it")
print("safe to write and impossible to get stale. It is also what makes it assign the")
print("25-a-minute box the same 300 documents as the 100-a-minute box. The batch took")
print(str(makespan) + " seconds against a possible " + str(ideal_seconds) + ", the fleet was idle for " + str(idle_seconds))
print("worker-seconds of the " + str(worker_seconds_paid) + " paid for, and every document was processed.")

documents: 2400 split 8 ways = 300 each

worker   rate/min   assigned   seconds to finish
  w0        100         300         180
  w1        100         300         180
  w2        100         300         180
  w3        100         300         180
  w4        60         300         300
  w5        60         300         300
  w6        40         300         450
  w7        25         300         720

  batch finishes when the LAST worker finishes : 720 seconds
  mean worker completion time                  : 311 seconds
  the status page reported the mean

  fleet capacity                     : 585 documents per minute
  shortest possible batch time       : 246 seconds
  actual batch time                  : 720 seconds
  cost of the equal split            : 474 seconds
  that is 65 percent of the wall clock

  worker-seconds paid for   : 5760
  worker-seconds working    : 2490
  worker-seconds idle       : 3270
  utilisation               : 43 percent

  the four fastest machines finished in 180 seconds and waited 540 more

quantity                      does the split shape it
  documents processed         no, it is a sum
  documents per worker        no, that is what was equalised
  total worker-seconds        no, work is conserved
  batch completion time       YES, it is a maximum
  utilisation                 YES, it is a ratio against a maximum
  the dashboard showed the first three

a maximum is the only statistic an equal split gets wrong, and it is the
only statistic the customer experiences

control - a quantity no allocation can move
  documents completed, equal split      : 2400
  proportional shares before remainder  : 2398
  documents lost to truncation          : 2
  a real scheduler assigns the remainder, so it must hand out those 2
  documents completed, proportional     : 2400
  difference                            : 0
  work is conserved, so this cannot detect the problem

null control - the same equal split across a uniform fleet
  batch time            : 246 seconds
  shortest possible     : 246 seconds
  cost of the split     : 0 seconds
  utilisation           : 100 percent
  the same allocation is optimal here, so the rule is not 'equal is wrong'
  it is 'equal is wrong exactly as far as the fleet is unequal'

An equal split needs no information about the workers, which is what makes it
safe to write and impossible to get stale. It is also what makes it assign the
25-a-minute box the same 300 documents as the 100-a-minute box. The batch took
720 seconds against a possible 246, the fleet was idle for 3270
worker-seconds of the 5760 paid for, and every document was processed.

Trace event types