Simulations for HPA

output.log

~$ python simulation.py 
############## 90 % #########
[Target 1 pods][Problem?! True] current=1 desired=1 ratio=1.0
[Target 2 pods][Problem?! True] current=2 desired=2 ratio=1.0
[Target 3 pods][Problem?! True] current=3 desired=4 ratio=1.0001000100010002
[Target 4 pods][Problem?! True] current=4 desired=4 ratio=1.0
[Target 5 pods][Problem?! True] current=5 desired=5 ratio=1.0
[Target 6 pods][Problem?! True] current=6 desired=7 ratio=1.0004001600640255
[Target 7 pods][Problem?! True] current=7 desired=8 ratio=1.0004001600640258
[Target 8 pods][Problem?! True] current=8 desired=8 ratio=1.0
[Target 9 pods][Problem?! True] current=9 desired=10 ratio=1.000100010001
[Target 10 pods][Problem?! False] current=9 desired=10 ratio=1.1111111111111112
[Target 11 pods][Problem?! False] current=10 desired=12 ratio=1.1001100110011002
[Target 12 pods][Problem?! True] current=11 desired=13 ratio=1.0913456291607553
[Target 13 pods][Problem?! True] current=12 desired=14 ratio=1.083658430862592
[Target 14 pods][Problem?! True] current=13 desired=15 ratio=1.0773540185304893
[Target 15 pods][Problem?! True] current=14 desired=16 ratio=1.0725010725010726
[Target 16 pods][Problem?! True] current=15 desired=16 ratio=1.0666666666666667
[Target 17 pods][Problem?! True] current=16 desired=18 ratio=1.0629251700680271
[Target 18 pods][Problem?! True] current=17 desired=19 ratio=1.0598834128245893
[Target 19 pods][Problem?! True] current=18 desired=20 ratio=1.0561892691170258
[Target 20 pods][Problem?! False] current=18 desired=20 ratio=1.1111111111111112
[Target 21 pods][Problem?! False] current=19 desired=22 ratio=1.105705440070765
[Target 22 pods][Problem?! False] current=20 desired=23 ratio=1.1013215859030836
[Target 23 pods][Problem?! True] current=21 desired=24 ratio=1.097213078779899
[Target 24 pods][Problem?! True] current=22 desired=25 ratio=1.0926573426573427
[Target 25 pods][Problem?! True] current=23 desired=25 ratio=1.0869565217391304
[Target 26 pods][Problem?! True] current=24 desired=27 ratio=1.0850694444444444
[Target 27 pods][Problem?! True] current=25 desired=28 ratio=1.0810810810810811
[Target 28 pods][Problem?! True] current=26 desired=29 ratio=1.0773540185304893
[Target 29 pods][Problem?! True] current=27 desired=30 ratio=1.0766580534022394
[Target 30 pods][Problem?! True] current=28 desired=31 ratio=1.0725010725010726
[Target 31 pods][Problem?! False] current=28 desired=32 ratio=1.109139307897072
[Target 32 pods][Problem?! False] current=29 desired=33 ratio=1.1052166224580018
[Target 33 pods][Problem?! False] current=30 desired=34 ratio=1.1001100110011
[Target 34 pods][Problem?! True] current=31 desired=35 ratio=1.097213078779899
[Target 35 pods][Problem?! True] current=32 desired=36 ratio=1.0964912280701755
[Target 36 pods][Problem?! True] current=33 desired=37 ratio=1.093972213105787
[Target 37 pods][Problem?! True] current=34 desired=38 ratio=1.0893246187363834
[Target 38 pods][Problem?! True] current=35 desired=39 ratio=1.0863661053775122
[Target 39 pods][Problem?! True] current=36 desired=40 ratio=1.0850694444444444
[Target 40 pods][Problem?! False] current=36 desired=40 ratio=1.1111111111111112
[Target 41 pods][Problem?! True] current=38 desired=42 ratio=1.0829542993285681
[Target 42 pods][Problem?! False] current=38 desired=43 ratio=1.105705440070765
[Target 43 pods][Problem?! False] current=39 desired=44 ratio=1.1052166224580018
[Target 44 pods][Problem?! False] current=40 desired=45 ratio=1.1013215859030836
[Target 45 pods][Problem?! True] current=41 desired=46 ratio=1.098659635245001
[Target 46 pods][Problem?! True] current=42 desired=47 ratio=1.097213078779899
[Target 47 pods][Problem?! True] current=43 desired=48 ratio=1.0969723562966212
[Target 48 pods][Problem?! True] current=44 desired=49 ratio=1.0926573426573427
[Target 49 pods][Problem?! True] current=45 desired=50 ratio=1.0893246187363834
[Target 50 pods][Problem?! False] current=45 desired=50 ratio=1.1111111111111112
[Target 51 pods][Problem?! False] current=46 desired=52 ratio=1.109139307897072
[Target 52 pods][Problem?! False] current=47 desired=53 ratio=1.1081560283687943
[Target 53 pods][Problem?! False] current=48 desired=54 ratio=1.1081560283687943
[Target 54 pods][Problem?! False] current=49 desired=55 ratio=1.1031439602868174
[Target 55 pods][Problem?! False] current=50 desired=56 ratio=1.1049723756906078
[Target 56 pods][Problem?! False] current=51 desired=57 ratio=1.1015642211940957
[Target 57 pods][Problem?! True] current=52 desired=58 ratio=1.098901098901099
[Target 58 pods][Problem?! True] current=53 desired=59 ratio=1.0969723562966214
[Target 59 pods][Problem?! True] current=54 desired=60 ratio=1.0957703265395573
[Target 60 pods][Problem?! True] current=55 desired=61 ratio=1.095290251916758
[Target 61 pods][Problem?! True] current=56 desired=62 ratio=1.0955302366345312
[Target 62 pods][Problem?! False] current=56 desired=63 ratio=1.109139307897072
[Target 63 pods][Problem?! False] current=57 desired=64 ratio=1.1103708638685321
[Target 64 pods][Problem?! False] current=58 desired=65 ratio=1.1052166224580018
[Target 65 pods][Problem?! False] current=59 desired=66 ratio=1.1077877478675084
[Target 66 pods][Problem?! False] current=60 desired=67 ratio=1.1037527593818983
[Target 67 pods][Problem?! False] current=61 desired=68 ratio=1.1002310485201894
[Target 68 pods][Problem?! True] current=62 desired=69 ratio=1.097213078779899
[Target 69 pods][Problem?! False] current=63 desired=70 ratio=1.1022927689594357
[Target 70 pods][Problem?! False] current=64 desired=71 ratio=1.1003521126760563
[Target 71 pods][Problem?! True] current=65 desired=72 ratio=1.0989010989010988
[Target 72 pods][Problem?! True] current=66 desired=73 ratio=1.097935880544576
[Target 73 pods][Problem?! True] current=67 desired=74 ratio=1.0974539069359088
[Target 74 pods][Problem?! False] current=67 desired=75 ratio=1.105583195135434
[Target 75 pods][Problem?! False] current=68 desired=76 ratio=1.105705440070765
[Target 76 pods][Problem?! False] current=69 desired=77 ratio=1.1063170704723975
[Target 77 pods][Problem?! False] current=70 desired=78 ratio=1.1074197120708749
[Target 78 pods][Problem?! False] current=71 desired=79 ratio=1.1003521126760563
[Target 79 pods][Problem?! False] current=72 desired=80 ratio=1.1022927689594355
[Target 80 pods][Problem?! False] current=72 desired=80 ratio=1.1111111111111112
[Target 81 pods][Problem?! True] current=74 desired=82 ratio=1.098659635245001
[Target 82 pods][Problem?! False] current=75 desired=83 ratio=1.1019283746556474
[Target 83 pods][Problem?! False] current=75 desired=84 ratio=1.1111111111111112
[Target 84 pods][Problem?! False] current=76 desired=85 ratio=1.105705440070765
[Target 85 pods][Problem?! False] current=77 desired=86 ratio=1.1100011100011098
[Target 86 pods][Problem?! False] current=78 desired=87 ratio=1.1052166224580018
[Target 87 pods][Problem?! False] current=79 desired=88 ratio=1.1103708638685321
[Target 88 pods][Problem?! False] current=80 desired=89 ratio=1.1061946902654867
[Target 89 pods][Problem?! False] current=81 desired=90 ratio=1.1022927689594355
[Target 90 pods][Problem?! True] current=82 desired=91 ratio=1.098659635245001
[Target 91 pods][Problem?! False] current=83 desired=92 ratio=1.1053387863380126
[Target 92 pods][Problem?! False] current=84 desired=93 ratio=1.1022927689594357
[Target 93 pods][Problem?! True] current=85 desired=94 ratio=1.0995052226498074
[Target 94 pods][Problem?! False] current=85 desired=95 ratio=1.1098779134295227
[Target 95 pods][Problem?! False] current=86 desired=96 ratio=1.1074197120708749
[Target 96 pods][Problem?! False] current=87 desired=97 ratio=1.1052166224580018
[Target 97 pods][Problem?! False] current=88 desired=98 ratio=1.1032656663724625
[Target 98 pods][Problem?! False] current=89 desired=99 ratio=1.1015642211940955
[Target 99 pods][Problem?! False] current=90 desired=100 ratio=1.1001100110011002
[Target 100 pods][Problem?! False] current=90 desired=100 ratio=1.1111111111111112
#############################
############## 80 % #########
[Target 1 pods][Problem?! True] current=1 desired=1 ratio=1.0
[Target 2 pods][Problem?! True] current=2 desired=2 ratio=1.0
[Target 3 pods][Problem?! True] current=3 desired=4 ratio=1.0001000100010002
[Target 4 pods][Problem?! True] current=4 desired=4 ratio=1.0
[Target 5 pods][Problem?! False] current=4 desired=5 ratio=1.25
[Target 6 pods][Problem?! False] current=5 desired=7 ratio=1.2004801920768307
[Target 7 pods][Problem?! False] current=6 desired=8 ratio=1.1671335200746966
[Target 8 pods][Problem?! False] current=7 desired=9 ratio=1.142857142857143
[Target 9 pods][Problem?! False] current=8 desired=10 ratio=1.125112511251125
[Target 10 pods][Problem?! False] current=8 desired=10 ratio=1.25
[Target 11 pods][Problem?! False] current=9 desired=12 ratio=1.222344456667889
[Target 12 pods][Problem?! False] current=10 desired=13 ratio=1.2004801920768307
[Target 13 pods][Problem?! False] current=11 desired=14 ratio=1.1821728336682824
[Target 14 pods][Problem?! False] current=12 desired=15 ratio=1.1671335200746966
[Target 15 pods][Problem?! False] current=13 desired=16 ratio=1.1550011550011552
[Target 16 pods][Problem?! False] current=13 desired=16 ratio=1.2307692307692308
[Target 17 pods][Problem?! False] current=14 desired=18 ratio=1.2147716229348884
[Target 18 pods][Problem?! False] current=15 desired=19 ratio=1.2012012012012012
[Target 19 pods][Problem?! False] current=16 desired=20 ratio=1.188212927756654
[Target 20 pods][Problem?! False] current=16 desired=20 ratio=1.25
[Target 21 pods][Problem?! False] current=17 desired=22 ratio=1.2357884330202669
[Target 22 pods][Problem?! False] current=18 desired=23 ratio=1.2236906510034262
[Target 23 pods][Problem?! False] current=19 desired=24 ratio=1.2127091923356779
[Target 24 pods][Problem?! False] current=20 desired=25 ratio=1.2019230769230769
[Target 25 pods][Problem?! False] current=20 desired=25 ratio=1.25
[Target 26 pods][Problem?! False] current=21 desired=27 ratio=1.2400793650793651
[Target 27 pods][Problem?! False] current=22 desired=28 ratio=1.2285012285012284
[Target 28 pods][Problem?! False] current=23 desired=29 ratio=1.217878455730118
[Target 29 pods][Problem?! False] current=24 desired=30 ratio=1.2112403100775195
[Target 30 pods][Problem?! False] current=25 desired=31 ratio=1.2012012012012012
[Target 31 pods][Problem?! False] current=25 desired=32 ratio=1.2422360248447204
[Target 32 pods][Problem?! False] current=26 desired=33 ratio=1.232741617357002
[Target 33 pods][Problem?! False] current=27 desired=34 ratio=1.2223444566678892
[Target 34 pods][Problem?! False] current=28 desired=35 ratio=1.2147716229348884
[Target 35 pods][Problem?! False] current=29 desired=36 ratio=1.209921355111918
[Target 36 pods][Problem?! False] current=29 desired=37 ratio=1.2448649321548613
[Target 37 pods][Problem?! False] current=30 desired=38 ratio=1.2345679012345678
[Target 38 pods][Problem?! False] current=31 desired=39 ratio=1.2265423770391266
[Target 39 pods][Problem?! False] current=32 desired=40 ratio=1.220703125
[Target 40 pods][Problem?! False] current=32 desired=40 ratio=1.25
[Target 41 pods][Problem?! False] current=33 desired=42 ratio=1.247038284075321
[Target 42 pods][Problem?! False] current=34 desired=43 ratio=1.2357884330202669
[Target 43 pods][Problem?! False] current=35 desired=44 ratio=1.2315270935960592
[Target 44 pods][Problem?! False] current=36 desired=45 ratio=1.2236906510034262
[Target 45 pods][Problem?! False] current=37 desired=46 ratio=1.2174336498660823
[Target 46 pods][Problem?! False] current=37 desired=47 ratio=1.2454851164528584
[Target 47 pods][Problem?! False] current=38 desired=48 ratio=1.2413108242303872
[Target 48 pods][Problem?! False] current=39 desired=49 ratio=1.232741617357002
[Target 49 pods][Problem?! False] current=40 desired=50 ratio=1.2254901960784315
[Target 50 pods][Problem?! False] current=40 desired=50 ratio=1.25
[Target 51 pods][Problem?! False] current=41 desired=52 ratio=1.2444001991040319
[Target 52 pods][Problem?! False] current=42 desired=53 ratio=1.2400793650793651
[Target 53 pods][Problem?! False] current=43 desired=54 ratio=1.2370113805047005
[Target 54 pods][Problem?! False] current=44 desired=55 ratio=1.2285012285012284
[Target 55 pods][Problem?! False] current=45 desired=56 ratio=1.2277470841006752
[Target 56 pods][Problem?! False] current=45 desired=57 ratio=1.2484394506866416
[Target 57 pods][Problem?! False] current=46 desired=58 ratio=1.2422360248447206
[Target 58 pods][Problem?! False] current=47 desired=59 ratio=1.2370113805047005
[Target 59 pods][Problem?! False] current=48 desired=60 ratio=1.232741617357002
[Target 60 pods][Problem?! False] current=49 desired=61 ratio=1.2294074256208507
[Target 61 pods][Problem?! False] current=50 desired=62 ratio=1.2269938650306749
[Target 62 pods][Problem?! False] current=50 desired=63 ratio=1.2422360248447204
[Target 63 pods][Problem?! False] current=51 desired=64 ratio=1.2410027302060065
[Target 64 pods][Problem?! False] current=52 desired=65 ratio=1.232741617357002
[Target 65 pods][Problem?! False] current=53 desired=66 ratio=1.2331976815883587
[Target 66 pods][Problem?! False] current=53 desired=67 ratio=1.2495314257153567
[Target 67 pods][Problem?! False] current=54 desired=68 ratio=1.2428535918468804
[Target 68 pods][Problem?! False] current=55 desired=69 ratio=1.2368583797155226
[Target 69 pods][Problem?! False] current=56 desired=70 ratio=1.2400793650793651
[Target 70 pods][Problem?! False] current=57 desired=71 ratio=1.2354830738818878
[Target 71 pods][Problem?! False] current=58 desired=72 ratio=1.2315270935960592
[Target 72 pods][Problem?! False] current=58 desired=73 ratio=1.2493753123438283
[Target 73 pods][Problem?! False] current=59 desired=74 ratio=1.246261216350947
[Target 74 pods][Problem?! False] current=60 desired=75 ratio=1.2345679012345678
[Target 75 pods][Problem?! False] current=61 desired=76 ratio=1.232589670898558
[Target 76 pods][Problem?! False] current=62 desired=77 ratio=1.2312238364934744
[Target 77 pods][Problem?! False] current=63 desired=78 ratio=1.2304663467454164
[Target 78 pods][Problem?! False] current=63 desired=79 ratio=1.2400793650793651
[Target 79 pods][Problem?! False] current=64 desired=80 ratio=1.2400793650793651
[Target 80 pods][Problem?! False] current=64 desired=80 ratio=1.25
[Target 81 pods][Problem?! False] current=66 desired=82 ratio=1.2318305001231828
[Target 82 pods][Problem?! False] current=67 desired=83 ratio=1.2335019119279635
[Target 83 pods][Problem?! False] current=67 desired=84 ratio=1.2437810945273633
[Target 84 pods][Problem?! False] current=68 desired=85 ratio=1.2357884330202669
[Target 85 pods][Problem?! False] current=69 desired=86 ratio=1.238696890870804
[Target 86 pods][Problem?! False] current=69 desired=87 ratio=1.249375312343828
[Target 87 pods][Problem?! False] current=71 desired=88 ratio=1.2354830738818878
[Target 88 pods][Problem?! False] current=71 desired=89 ratio=1.246416552411816
[Target 89 pods][Problem?! False] current=72 desired=90 ratio=1.2400793650793651
[Target 90 pods][Problem?! False] current=73 desired=91 ratio=1.2341108231519191
[Target 91 pods][Problem?! False] current=74 desired=92 ratio=1.2397718819737167
[Target 92 pods][Problem?! False] current=75 desired=93 ratio=1.234567901234568
[Target 93 pods][Problem?! False] current=75 desired=94 ratio=1.2461059190031154
[Target 94 pods][Problem?! False] current=76 desired=95 ratio=1.2413108242303872
[Target 95 pods][Problem?! False] current=77 desired=96 ratio=1.2368583797155224
[Target 96 pods][Problem?! False] current=77 desired=97 ratio=1.2487512487512487
[Target 97 pods][Problem?! False] current=78 desired=98 ratio=1.2447099825740602
[Target 98 pods][Problem?! False] current=79 desired=99 ratio=1.2410027302060065
[Target 99 pods][Problem?! False] current=80 desired=100 ratio=1.2376237623762376
[Target 100 pods][Problem?! False] current=80 desired=100 ratio=1.25
#############################

simulation.py

import math

def simulate(last_metric):
    for i in range(100):
        # 10000 divided by the number of pods we want. Floor to be safe.
        desiredMetricValue = math.floor(10000 / (i+1))
        
        currentReplicas = math.ceil(last_metric / desiredMetricValue)

        # When going to 100% we will have 10000. The current metric value is
        # the 10000 divided by the number of pods present
        currentMetricValue = 10000 / currentReplicas
        
        # Exactly as in https://kubernetes.io/docs/tasks/run-application/horizontal-pod-autoscale/#algorithm-details
        desiredReplicas = math.ceil(currentReplicas * (currentMetricValue / desiredMetricValue ))
        
        ratio = currentMetricValue / desiredMetricValue
        print("[Target {} pods][Problem?! {}] current={} desired={} ratio={}".format(i+1, abs(ratio-1)<=0.1, currentReplicas, desiredReplicas, ratio))


# In 90% max returned will be 9000
print("############## 90 % #########")
simulate(9000)
print("#############################")
print("############## 80 % #########")
# In 80% max returned will be 8000
simulate(8000)
print("#############################")

This is an amazing complex problem. I agree with your latest simulation formula. I developed a similar script:

#! /usr/bin/python
import math

limitMetricValue = 10000

for steps in range(19):
  desiredSteps = steps + 2
  scalingFailures = 0
  count = 0

  for pods in range(1000):
    desiredPods = pods + 1
    desiredMetricValue = math.floor(limitMetricValue / desiredPods)

    for last in range(desiredSteps - 1):
      lastMetric = (last + 1) * (limitMetricValue / desiredSteps)

      currentReplicas = math.ceil(lastMetric / desiredMetricValue)
      currentMetricValue = limitMetricValue / currentReplicas
      desiredReplicas = math.ceil(currentReplicas * (currentMetricValue / desiredMetricValue ))
      ratio = currentMetricValue / desiredMetricValue

      count = count + 1
      change = abs(ratio - 1.0)
      if (desiredReplicas != currentReplicas and change <= 0.1):
        print("[pods={}, steps={}, metric={}] [Problem?! {}] current={} desired={} ratio={}".format(
          desiredPods, desiredSteps, lastMetric, change <= 0.1, currentReplicas, desiredReplicas, ratio))
        scalingFailures = scalingFailures + 1
#        break

  print("[steps={}, failure={}, probability={}]".format(desiredSteps, scalingFailures, float(scalingFailures) / float(count)))

But the situation is not as simple. The moment you enable users to modify the number of steps it gets pretty unpredictable. For more than 12 steps you will have scaling failures on every desired pod number. Below, I get only failures on some desired pod numbers:

[steps=2, failures=0]
[steps=3, failures=0]
[steps=4, failures=1]
[steps=5, failures=1]
[steps=6, failures=1]
[steps=7, failures=4]
[steps=8, failures=9]
[steps=9, failures=19]
[steps=10, failures=44]
[steps=11, failures=812]

If I look at the probability it gets even more interesting

[steps=2, failure=0, probability=0.0]
[steps=3, failure=0, probability=0.0]
[steps=4, failure=1, probability=0.000333333333333]
[steps=5, failure=1, probability=0.00025]
[steps=6, failure=1, probability=0.0002]
[steps=7, failure=5, probability=0.000833333333333]
[steps=8, failure=10, probability=0.00142857142857]
[steps=9, failure=20, probability=0.0025]
[steps=10, failure=46, probability=0.00511111111111]
[steps=11, failure=814, probability=0.0814]
[steps=12, failure=996, probability=0.0905454545455]
[steps=13, failure=999, probability=0.08325]
[steps=14, failure=1000, probability=0.0769230769231]
[steps=15, failure=1002, probability=0.0715714285714]
[steps=16, failure=1006, probability=0.0670666666667]
[steps=17, failure=1007, probability=0.0629375]
[steps=18, failure=1012, probability=0.0595294117647]
[steps=19, failure=1024, probability=0.0568888888889]
[steps=20, failure=1044, probability=0.0549473684211]

As you can see the probability is increasing up to a max at 11 steps and slowly declining afterwards on a higher level.