Key usage coding challenge

Last week, Cedric Beust posted a new coding challenge:

We want to make multiple calls to a site that only allows to use a key 500 times every 10mn. You are given a collection of keys (strings), a max count (e.g. 500) and a time period (e.g. 10mn) and your task is to implement getNextKey()...

(Go read the article, as there's a more detailed problem statement there.)

So we have a set of K keys, and each key is valid for X uses in a rolling window of T milliseconds. My first observation (made in the comments) is that we need never re-order our keys. If we use every key X times each in any order, then the next key that will be available for use is the first key that we used, exactly T milliseconds after we first used it. Then the second key, T milliseconds after we first used it. Whatever order we pick, we can just repeat it indefinitely. We might cycle all through the keys X times, or repeat each key X times before moving on to the next. For the rest of this discussion, we'll assume we have K keys that can each be used only once in the given period, and for which we won't bother keeping track of the different key names. We can easily adapt such a solution to handle the original problem, but it will be simpler to discuss. So here's the simplified problem we'll consider:

We want to make multiple calls to a site that only allows to use a key once every 10 minutes, and we have 500 keys. At any time we might be asked for a key to be used, and we must answer whether there is one free, and if there is, to consider it used up for the next 10 minutes. Your task is to implement tryUseKey(), returning true if a key was available and false if not.

My second observation is that to provide perfect answers, we cannot avoid storing the time-stamp of every one of the last K keys used. To observe this, imagine that over the last 10 minutes we have called tryUseKey() exactly K times. To recover the timestamps of all K invocations of tryUseKey(), we can just poll getNextKey() as fast as possible over the next 10 minutes. Every time it successfully returns a key, we know the approximate timestamp of one of the original invocations: about 10 minutes ago. By polling arbitrarily fast we can can obtain an arbitrarily accurate answer. If we can reconstruct this information, then it must be encoded somehow in our object's state, so we can place a lower bound on the working memory required by the data structure that is linear in K.

It's not especially hard to write a solution that solves the problem precisely by storing K timestamps, but it would be nice if we could trade off some precision in order to use substantially less memory. For that reason, we'll look for solutions that allow false negatives in specific circumstances. A false negative is to indicate that no keys are available when in fact some keys should be available. We never allow false positives – we will never say that a key is available when it should not be.

• We might allow a false negative when all the keys have been used in the last 11 minutes (rather than the last 10 minutes). We'll call this relaxed requirement A.
• We might allow a false negative when less that 50 (of 500) keys are available. We'll call this relaxed requirement B.
• We might allow a false negative only when less than 50 keys are available and all keys have been used in the last 11 minutes. We'll call this relaxed requirement AB.

I'm going to use graphs of keys used and available over time to illustrate a number of solutions. They're all going to look similar to this:

The orange line rises whenever keys are used. The blue line rises whenever used keys have "cooled down" over 10 minutes and become available for re-use. The blue area between the two lines shows how many keys are available for use – when the red and blue lines meet all keys have been used and none are available until the blue line rises again. You can see that the shape of the blue line in the top-right of the graph replicates the shape of the orange line in the bottom-left, as the keys that were used on the left become ready again on the right.

Buckets

All the solutions I'm going to discuss involve buckets. The general idea is that as we use keys we group them up in an "active" bucket, and at some point we set the active bucket aside (and don't add any more keys to it), and use another bucket as the active one. After a bucket has been set aside for 10 minutes to "cool down", we recover all the keys from that bucket. By grouping keys into buckets, we only need to store a timestamp for the bucket. By choosing when to set the buckets aside and how many buckets to use we can try to meet our relaxed requirements.

To meet requirement A we can use 10 buckets and swap out the active bucket every minute. Here's what it might look like:

The rectangles added to the diagram show keys held in buckets. In the light blue rectangles keys are added to the active bucket, while the dark blue rectangles show keys held in a cooling down bucket. The new green line shows the number of keys we consider free. It tracks closely to the blue line, but in places it is lower, the yellow area between them reflects where our algorithm will falsely report a smaller number of keys available than is accurate. The number of keys reported available may be a lot lower than the true value, but never for very long.

To meet requirement B we can use 10 buckets and swap out the active bucket every time it has 50 keys in it. Here's what that might look like:

As before, the yellow area shows where the algorithm will falsely report a smaller number of keys available than is accurate. This time the number of keys incorrectly reported unavailable is never very high, but can remain low for a long time.

Finally, to meet requirement AB, we can set aside a bucket after it has been active for 1 minute or after it has 50 keys in it, whichever comes first. It will look something like this:

The complication here is in figuring out how many buckets we might need. I believe it's 20. This can happen if, for example, we use 451 keys very rapidly, then use just one or two keys a minute for the rest of the time. So we need more buckets, but in return we obtain very strict bounds on how wrong our answers can be.

Generalizing

So far, we've been working with a specific example where the cooldown period is 10 minutes, there are 500 keys and we have allowed a 1 minute time threshold and a 50 key threshold for false negatives. We can change these parameters. The number of buckets we'll need for solution A is based on the cooldown period divided by the time threshold, the number of buckets needed for solution B is based on the number of keys divided by the key threshold, and the number of buckets needed for solution AB is the some of both these values.

The code

Here's an example implementation in Python:

import itertools
import time
from collections import deque

class Bucket(object):
    def __init__(self, close_time):
        self.keycount = 0
        self.close_time = close_time
    def add(self, now):
        self.keycount += 1
    def has_cooled_down(self, now, cooldown):
        return self.close_time + cooldown <= now
    def will_accept(self, limit, now):
        is_full = self.keycount == limit
        is_closed = now >= self.close_time
        return not is_full and not is_closed

def divide_rounded_up(dividend, divisor):
    return (dividend + divisor - 1) // divisor

class Throttler(object):
    def __init__(
            self,
            limit, cooldown, maximum_cooldown, key_threshold):
        '''
        limit: number of key usages allowed initially.
        cooldown: time in milliseconds before a used key can be
            re-used.
        maximum_cooldown: try_use_key is only allowed to give a
            false negative when all keys have been used within this
            amount of time in the past.
        key_threshold: try_use_key is only allowed to give a false
            negative when the true number of keys is less than this
            number.
        '''
        self.buckets = deque()
        self.cooldown = cooldown
        self.open_time = maximum_cooldown - cooldown
        buckets_a = divide_rounded_up(cooldown, self.open_time)
        buckets_b = divide_rounded_up(limit, key_threshold)
        self.num_buckets = buckets_a + buckets_b
        self.bucket_size = key_threshold
        self.free = limit
    def release_expired_buckets(self, now):
        while self.buckets:
            if self.buckets[0].has_cooled_down(now, self.cooldown):
                self.free += self.buckets.popleft().keycount
            else:
                return
    def try_use_key(self, now):
        '''
        Check if any keys are available. If so, use one and return
        True. Otherwise, return False.
        May return a false negative, but only if all keys were used
        within the last (maximum_cooldown) milliseconds, and if
        fewer than key_threshold keys are actually available.
        '''
        self.release_expired_buckets(now)
        if self.free == 0:
            return False
        should_create_bucket = (
            len(self.buckets) == 0 or
            not self.buckets[-1].will_accept(
                    self.bucket_size, now))
        if should_create_bucket:
            assert len(self.buckets) < self.num_buckets
            self.buckets.append(Bucket(now + self.open_time))
        self.buckets[-1].add(now)
        self.free -= 1
        return True

def now_ms():
    '''
    Return the current time in milliseconds.
    '''
    return int(time.time() * 1000)

class SlidingWindowMap(object):
    def __init__(self,
            keys, max_count, cooldown, maximum_cooldown,
            key_threshold, now_func=now_ms):
        '''
        keys: a sequence of key names.
        max_count: the maximum number of times any key can be used.
        cooldown: the time in milliseconds before a used key can be
            re-used.
        maximum_cooldown: try_use_key is only allowed to give a
            false negative when all keys have been used within this
            amount of time in the past.
        key_threshold: try_use_key is only allowed to give a false
            negative when the true number of keys is less than this
            number.
        now_func: a function that returns the current time in
            milliseconds.
        '''
        keylist = list(keys)
        num_keys = len(keylist) * max_count
        self.keys = itertools.cycle(list(keys))
        self.now_func = now_func
        self.throttle = Throttler(
                num_keys, cooldown,
                maximum_cooldown, key_threshold)
    def get_next_key(self):
        if self.throttle.try_use_key(self.now_func()):
            return self.keys.next()
        else:
            return None

Further questions

I've not given a proof of the formula for the maximum number of buckets required for solution AB. I actually thought it should be one less, but in practice this didn't seem to be true. I haven't quite figured out why.

For a fixed number of buckets, it's not clear when it would be better to be more strict about the time or the key thresholds. It might be interesting to see what percentage of full key utilization can be achieved with different levels of "burstiness" in key requests and different choices of threshold.