Permutation of a list

Let’s consider following requirement. We have list of objects, say questions, that we want to show our users. Let’s also assume that the list is very long, 500 messages.

Each message is unique and we want to

1. show each question only once for each user.
2. show the questions in different order to each user.

Each user responds to only few questions each day so it will take several months before they exhaust the list. We need to remember over each session where user left off.

Basic way to implement this is to take the list of questions, make a copy of it, shuffle it’s content and save it as part of users profile data. This has obvious drawbacks of the data duplication and maintenance. Also if the list changes, every single copy of the list has to be updated.

Cheaper way to implement this is to use prime walk. In this method we can keep only single copy of the list and store only number of answered questions in the users profile.

1. First define the list, say we have 500 items.
2. Find prime number that is greater than 500. For example 503.
3. Select seed for each user. This seed is any number that is constant for an user, like user id or time of account creation.

Then we define function that uses these values. Note that this implementation is tail-recursive for code simplicity, efficient implementation should not use recursion.

var prime = 503;
var list = ["question1", "question2", ... "question500"];

function pick_nth(seed, n, p, l) {
    if(!n) return l[seed % p];
    return pick_nth((seed + l.length) % p, n - 1, l);
}

Now picking up n:th question from list becomes easy. For example:

pick_nth(userId, 0, prime, list);  // first question
pick_nth(userId, 1, prime, list);  // second question
...
pick_nth(userId, 499, prime, list);  // 500th question

Function returns items from list in different order for every unique user id. Only thing needed to keep track of progress is to store the number of questions user has answered.

Changing list requires some care. To delete question, just mark the entry in list to null to skip it. To add questions, add another list that is used after user has exhausted the original one.
If you change the list length, the order of selection changes and it’s not anymore guaranteed that user sees every question and sees every question only once.

Selecting biased random objects from a set

Normal random pick from set of objects will return every object equally likely.
For example, following function returns any character with equal probability from the argument string.

function randomselect(s) {
    return s[~~(Math.random() * s.length)];
}

This is usually the desired functionality, but games often require to pick one thing more likely than another. Typical use case are random drops from enemies, the common loot should drop most often and the good stuff should be much more rare.

Biased random pick is selecting object from a set randomly, so that some of them selected more often than others.

Calling randomselect("abc") will return each “a”, “b” and “c” with 33% probability.
Selection can be biased by just adding more of characters in the string. Calling randomselect("aaabbc") will return “a” with 50%,”b” with 33% and “c” with 16% propability.

Just adding entries in a list is bit clumsy, and more generic method is to use integral of probability density.

// define elements and probability for each
var elems = [
  ['a', 0.5],
  ['b', 0.333],
  ['c', 0.166]
]

// Biased random entry selection
function select(elems) {
    var r = Math.random();
    var ref = 0;

    for(var i=0; i < elems.length; i++) {
        var elem= elems[i];
        ref += elem[1];
        if (r < ref) return elem[0];
    }
    // This happens only if probabilities do not add up to 1
    return null;
}

Calling select(elems) returns a with 50%, b with 33.3% and c with 16.6% probability.
If defined probabilities do not sum to 1 you can get null, i.e not selection. In this case 0.5 + 0.333 + 0.166 is 0.999 so there is 0.1% probability (one out 1000) to get nothing.

For example to pick 100 times randomly from the set.

var elems = [
  ['a', 0.5],
  ['b', 0.333],
  ['c', 0.166]
];

var s = '';
for(var i=0; i < 100; i++) {
	s += select(elems);
}
console.log(s);

Run this with node to get string of randomly picked characters. Here you can see that selection bias works, half of the letters are ‘a’, one third ‘b’ and rest ‘c’.

$ node biased.js
babbaaaabaabbaabaccbaacabbbabbacbaabacabccacacacbacaaaaacbcaaaababaccbcbbbcaabcaabaccabbbcbcbacaabaa

Simple Cooldown and Rate Control Algorithm

Software that accepts requests from external, potentially unfriendly sources often need to implement some kind of rate restrictions or cooldowns to limit the amount of resources single user or app client can use.

Typical uses for cooldowns are

• Limit number of login attempts per user
• Limit rate of API calls
• Batch incoming messages or jobs
• Throttle access to shared resource

There are several approaches how limitations are calculated, but it usually boils down to simple TPS limit, i.e. transactions per second.

Well behaving rate limiter must allow bursts, as client may not have control over the network buffering and even when it sends on steady rate server can receive requests as chunked together. Therefore it does not make sense to enforce strict TPS limit that only understands about seconds but it’s better to use average over time. Optimally rate limiter should also not require lot of data management nor storage.

The algorithm

This is proposal for implementing described rate limiter with minimal overhead as variant of Leaky Bucket algorithm.

• Let T be time span in seconds and n number of operations we want to allow per T. For example n = 3 and T = 60 would mean 3 operations per minute.
• Let S = 0 be initial score for rate limited resource.

Every time resource is accessed,

1. Compute trial score Sn where now is seconds since some globally fixed reference time.
   • Sn = now + T/n if S=0
   • Sn = Sn + T/n otherwise.
2. Compare trial score Sn and current time.
   • Update S = now + T/n and allow request if Sn < now.
   • Reject request if Sn > now + T
   • Otherwise update score S = Sn and allow request.

This algorithm has some performance benefits as it only needs to store a single integer for score for each throttle and it does not need to be updated if request is rejected so its system load characteristics are well bounded. Algorithm also accepts max n requests in T as burst and averages to (n/T) TPS for constant load.
Implementation also fits well in distributed environments where redis or memcached can be used to atomically increment the score value.

Example

Here is javascript example for reference, save it in file and run with node.js.

var n = 3; // # of requests
var T = 60; // timestamp

var S = 0;
function throttle() {

	var Sn = S;
	var now = ~~(Date.now() / 1000);
	if (!Sn) {
		Sn = now + T/n;
	} else {
		Sn += T/n;
	}
	if ( Sn < now ) {
		Sn = now + T/n; // reset back to initial value
	} else if ( Sn > now + T ) {
		console.log('REJECT', S - now);
		return false; // throttled
	}
	S = Sn;

	console.log('ALLOW', S - now);
	return true; // ok
}


console.log('Allow '+n+' requests per '+T+'s');
var readline = require('readline');
var rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
rl.setPrompt('hit>');
rl.prompt();
rl.on('line', function() {
	// each enter is request
	throttle();
	rl.prompt();
});

When you run the example, hit enter to simulate request. It tells if you if it was accepted or rejected with the current score delta.

~/work $ node throttle.js
Allow 3 requests per 60s
hit>
ALLOW 20
hit>
ALLOW 40
hit>
ALLOW 60
hit>
REJECT 59
hit>
REJECT 55
hit>
REJECT 50
hit>
REJECT 45
hit>
ALLOW 59
hit>
REJECT 58
hit>

Adjust n and T to your liking. This implementation is also easy to change to return number of seconds client has to wait until trying again.

See also Simple popularity algorithm with decay how to apply this method for popularity scoring.