Skip to content

Instantly share code, notes, and snippets.

@jdmaturen
Last active August 29, 2015 14:16
Show Gist options
  • Save jdmaturen/1bc4bc34afc2ee599908 to your computer and use it in GitHub Desktop.
Save jdmaturen/1bc4bc34afc2ee599908 to your computer and use it in GitHub Desktop.
From an individual box's viewpoint probabilistically limit the global concurrency of requests of a given actor based on observed local concurrency, the cluster size, and a set threshold.
burp-2:foo jd$ python probabilistic_strategy.py 1000 16 64
request_count: 1000 cluster_size: 16 threshold: 64
probability of being quotad at a given local concurrency:
1 0.015070684079
2 0.07629533815
3 0.202571187171
4 0.378831226431
mean observed global concurrency limit: 64.033
2.5, 50, 97.5: [56.0, 64.0, 73.0]
burp-2:foo jd$
burp-2:foo jd$ python probabilistic_strategy.py 1000 64 64
request_count: 1000 cluster_size: 64 threshold: 64
probability of being quotad at a given local concurrency:
1 0.359283609803
2 0.724181026008
3 0.912331256239
4 0.977987846997
mean observed global concurrency limit: 63.86
2.5, 50, 97.5: [52.0, 64.0, 76.0]
burp-2:foo jd$
from random import randint
from numpy import percentile, mean
from scipy.stats import nbinom
import sys
__author__ = 'jd'
"""
Apache 2 license.
"""
def accept_request(concurrency, cluster_size, threshold):
p = 1./cluster_size
random_value_sample = nbinom.rvs(concurrency, p) + concurrency # have to add in what we've seen
# print "\t".join(map(str, [concurrency, random_value_sample, threshold, random_value_sample <= threshold]))
return random_value_sample <= threshold
def trial(request_count, cluster_size, threshold):
"distribute requests and check strategy"
servers = [0 for _ in xrange(cluster_size)]
successful_requests = 0
for _ in xrange(request_count):
server = randint(0, cluster_size-1)
servers[server] += 1
concurrency = servers[server]
if accept_request(concurrency, cluster_size, threshold):
successful_requests += 1
return successful_requests
def run_trials():
if len(sys.argv) < 4:
print "usage:", sys.argv[0], 'REQUEST_COUNT CLUSTER_SIZE THRESHOLD'
sys.exit()
request_count = int(sys.argv[1])
cluster_size = int(sys.argv[2])
threshold = int(sys.argv[3])
print 'request_count:', request_count, 'cluster_size:', cluster_size, 'threshold:', threshold
print
print 'probability of being quotad at a given local concurrency:'
for i in (1, 2, 3, 4):
print "\t".join(map(str, [i, nbinom.sf(threshold, i, 1./cluster_size)]))
print
trials = [trial(request_count, cluster_size, threshold) for _ in xrange(1000)]
print 'mean observed global concurrency limit:', mean(trials)
print '2.5, 50, 97.5:', percentile(trials, [2.5, 50, 97.5])
if __name__ == '__main__':
run_trials()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment