In my precedent blog post, we introduced the way to install and start playing with Redis. Now, I propose you to go further, with a more advanced use case. In my personnal project development (f.ollow.us), I faced a new problem:

How can we manage efficiently a fixed number of “slots” that have a TTL (i.e. Time To Live) and can be held (i.e. be available or not) in a high concurrency context? Don’t look further, Redis is the solution!

The problem

To be more explicit about what we try to solve here, i’ll give you another example. This one involves phone operators. You are aware that they dispose of a (large) range of phone number that can be used or vacant. Sometimes, customers break their contract and their phone number becomes available after a while. Sometimes, new customers subscribe a phone plan and they are given a random phone number. It’s exactly the same problem here.

Actually, we have to answer at least four constraints:

• Know if a phone number is available or not
• Retrieve an available phone number (preferably, the oldest one)
• Ask for them transactionally (race condition support)
• Expire phone numbers with time (they become available)

What about the Redis TTL feature you’ll say, does it solve the problem? I think the response is no. Ho yeah, we can probably imagine a solution, in which you select all used slots (not expired, existing in the db), store them in a set, and finally make a difference with another set that contains all known slots… but these operations take time, CPU and memory.

Why bother when the solution is so close? The Redis “sorted set” data type is our solution.

The solution

What is a Sorted Set?

Accordingly to the official redis.io website, sorted sets are “non repeating collections of Strings”. In reality, this simple definition hides the most advanced Redis data type. Sorted sets are advanced Redis sets, that associate each element with a score. This score permits elements to be taken permanently in order (and not ordered afterwards), resulting great performances when accessing to the set entries.

Redis offers useful commands to access such data sets by score (ZSCORE) or by rank (ZRANK), or select only a range of them (once again) by score (ZRANGEBYSCORE) or by rank (ZRANGE). For the three last commands, time complexity is equivalent to O(log(N)), with N the number of elements in the sorted set: no longer doubt about performances! To get a full list of Sorted sets dedicated commands, you can have a see to this web page.

We don’t need more to achieve our task!

Code it with Java

The code you’ll find below is a Java implementation of what we need to solve the “slot management” problem. It boils down to a simple class named PhoneNumberManager, which contains some static methods.

To converse with a Redis instance, I used the Jedis API (the Java Redis client). Jedis instances are retrieved from the RedisManager described in my precedent post about Redis.

First, we have to populate the sorted set with all phone numbers that we wish to use. These numbers are stored as simple strings. Each element is associated with the default 0 score. This initialization is done by using the init() method.

Once initialized, we can retrieve available phone numbers with the method getAvailableSlot(). A retrieved phone number have to be held or released via respective methods hold() and release().

There are also three more useful methods:

• getSize() returns the current number of elements in the sorted set
• getExpirationTimestamp() returns the expiration timestamp for a given phone number
• isAvailable() checks the availability of a phone number

Each of these methods are atomic (unique read/write atomic access to Redis) except the getAvailableSlot() method, which use transaction mechanism (WATCH, MULTI, EXEC) to support race condition on giving available phone number.

I think it’s time to paste some Java code…

import java.util.Date;
import java.util.Set;

import redis.clients.jedis.Jedis;
import redis.clients.jedis.Response;
import redis.clients.jedis.Transaction;

/**
 * This class manage all available phone numbers via static methods.
 * It uses Jedis instances from a JedisPool.
 */
public class PhoneNumberManager {

	/**
	 * This method populates the "numbers" sorted set.
	 * @param number The number of slots to allocate
	 */
	public static void init(int number) {
		Jedis jedis = RedisManager.getJedis();
		// Delete the key if exists
		jedis.del("numbers");
		// Populate the sorted set
		int number = Integer.parseInt("600000000");
		for (int i = 0; i < 10; i++) {
			jedis.zadd("numbers", i, "+33" + Integer.toString(number++));
		}
		RedisManager.returnJedis(jedis);
	}

	/**
	 * Returns the number of phone number.
	 * @return the number of phone number
	 */
	public static long getSize() {
		Jedis jedis = RedisManager.getJedis();
		Long card = jedis.zcard("numbers");
		RedisManager.returnJedis(jedis);
		return card;
	}

	/**
	 * This methods searches for an available phone number.
	 * The operation is atomic: The phone number (if found) is owned
	 * only by the claimant.
	 * You can release the phone number by using {@link #release()}.
	 * You can hold the phone number by using {@link #hold()}.
	 * @return A free phone number
	 * @throws Exception If no one is available
	 */
	public static String getAvailableSlot() throws Exception {
		Jedis jedis = RedisManager.getJedis();
		// Start watching the sorted set (preventing any modification)
		jedis.watch("numbers");
		try {
			String number = null;
			// Try to get an available phone number
			Set<String> availableNumber = jedis.zrangeByScore("numbers",
					Double.NEGATIVE_INFINITY, new Date().getTime(), 0, 1);
			if (!availableNumber.isEmpty()) {
				number = availableNumber.iterator().next();
				// Start transaction to remove the phone number from list
				Transaction t = jedis.multi();
				Response<Long> poped = t.zrem("numbers", number);
				t.exec();
				if (poped.get() != 1)
					throw new Exception("Problem getting available" +
						" phone number, please retry");
				else return number;
			} else {
				throw new Exception("No phone number available");
			}
		} catch (Exception e) {
			throw e;
		} finally {
			jedis.unwatch();
			RedisManager.returnJedis(jedis);
		}
	}

	/**
	 * This method holds a phone number for a given time.
	 * @param number The phone number to hold
	 */
	public static void hold(String number) {
		long timestamp = (long)(new Date().getTime()*1E-3 + duration);
		Jedis jedis = RedisManager.getJedis();
		jedis.zadd("numbers", timestamp, number);
		RedisManager.returnJedis(jedis);
	}

	/**
	 * This method release a given phone number.
	 * @param number The phone number to release
	 */
	public static void release(String number) {
		Jedis jedis = RedisManager.getJedis();
		jedis.zadd("numbers", 0, number);
		RedisManager.returnJedis(jedis);
	}

	/**
	 * This method returns the expiration timestamp of a phone number
	 * @param number The phone number
	 * @return The phone number expiration timestamp, null if not found
	 */
	public static Long getExpirationTimestamp(String number) {
		Jedis jedis = RedisManager.getJedis();
		Double score = jedis.zscore("numbers", number);
		RedisManager.returnJedis(jedis);
		return score.longValue();
	}

	/**
	 * This method checks the availability of a phone number.
	 * @param number The phone number
	 * @return false if slot does not exist or already expired,
	 * true otherwise
	 */
	public static boolean isAvailable(String number) {
		Long timestamp = getExpirationTimestamp(number);
		if (timestamp == null) return false;
		if (timestamp <= (long)(new Date().getTime()*1E-3)) return false;
		return true;
	}

}