Exponential backoff with hysteresis on recovery

backoff.py

import math
import time
import threading
import random

import numpy as np
import pandas as pd
import seaborn as sns
import matplotlib.pyplot as plt

class ExponentialBackoff:
  def __init__(self, base, top, mult):
    self.__success = 0
    self.__fail = 0
    self.__base = base
    self.__top = top
    self.__mult = mult

  def next(self, fail):
    if fail:
      self.__fail += 1
    else:
      self.__fail = 0
    backoff = self.__base * (self.__mult ** self.__fail)
    if backoff > self.__top:
      backoff = self.__top
    return round(random.random()*backoff, 1)

class ExponentialBackoffWithHyst:
  def __init__(self, base, top, mult):
    self.__success = 0
    self.__fail = 0
    self.__base = base
    self.__top = top
    self.__fail_top = int(math.ceil(math.log(top/base, mult)))
    self.__mult = mult
    self.__last_fail = False

  def next(self, fail):
    if fail:
      self.__fail += 1
    elif not self.__last_fail:
        self.__fail -= 1
    self.__last_fail = fail
    if self.__fail < 0:
      self.__fail = 0
    if self.__fail > self.__fail_top:
      self.__fail = self.__fail_top
    backoff = self.__base * (self.__mult ** self.__fail)
    if backoff > self.__top:
      backoff = self.__top
    return round(random.random()*backoff, 1)

class Server:
  def __init__(self, concurrency):
    self.__sem = threading.Semaphore(concurrency)

  def work(self):
    if not self.__sem.acquire(blocking=False):
      return False
    self.__sem.release()
    return True

class Client(threading.Thread):
  def __init__(self, name, start, server, backoff, rounds):
    threading.Thread.__init__(self)
    self.name = name
    self.__start = start
    self.__server = server
    self.__backoff = backoff
    self.__rounds = rounds
    self.backoff = {}

  def run(self):
    for r in range(self.__rounds):
      done = self.__server.work()
      backoff = self.__backoff.next(not done)
      self.backoff[round(time.time()-self.__start, 1)] = (r, 1 if done else 0, backoff)
      time.sleep(backoff/1000)

def run(clients):
  for c in clients:
    c.start()
  for c in clients:
    c.join()
  backoff = []
  done = []
  names = []
  ids = []
  rounds = []
  ts = []
  for c in clients:
    for k, v in c.backoff.items():
      name, id = c.name.split("-")
      names += [name]
      ids += [id]
      rounds += [v[0]]
      done += [v[1]]
      backoff += [v[2]]
      ts += [k]
  df = pd.DataFrame({
    "Client": names,
    "ID": ids,
    "Done": done,
    "Backoff": backoff,
    "Round": rounds,
    "TS": ts,
  })
  return df


server = Server(2)
clients = 1000
rounds = 100
backoff = [10, 120, 1.5]

df_exp = run([
  Client("exp-{}".format(i), time.time(), server, ExponentialBackoff(*backoff), rounds)
  for i in range(clients)
])
df_exp_hyst = run([
  Client("exp+hyst-{}".format(i), time.time(), server, ExponentialBackoffWithHyst(*backoff), rounds)
  for i in range(clients)
])

df = pd.concat([df_exp, df_exp_hyst])
print(df)

fig = plt.figure()
ax0 = fig.add_subplot(3, 1, 1)
ax1 = fig.add_subplot(3, 1, 2)
ax2 = fig.add_subplot(3, 1, 3)

hd = pd.pivot_table(df, values='Done', index=['Client'], columns='TS', aggfunc=np.mean)
print(hd)
sns.heatmap(hd, ax=ax0)

hd = pd.pivot_table(df, values='Done', index=['Client', "ID"], columns='TS', aggfunc=np.mean)
print(hd)
sns.heatmap(hd, ax=ax1)

hd = pd.pivot_table(df, values='Backoff', index=['Client', "ID"], columns='Round', aggfunc=np.mean)
print(hd)
sns.heatmap(hd, ax=ax2)

plt.show()