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.

example_output

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$

probabilistic_strategy.py

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()