A lock-free, wait-free, counting table

06Apr08

When consulting with a colleague, recently, I ran into an interesting use case: in order to monitor live performance, we needed to count the number of method invocations on a service (read: EJB/remoted call). Actually, it was a number of such services. The obvious answer was to place an interceptor around each method call, and increment a global counter. 

However, here’s the kicker: we don’t know how many services there are, and the system is highly concurrent. What would you use to store service/call count mappings?

• j.u.HashMap – Can’t, it’s not thread-safe
• Hashtable/Collections.synchronizedMap() – Nope, there’s a single lock–all invocations will queue up behind one another and kill performance
• j.u.c.ConcurrentHashMap – Even with a mighty (1:1) lock granularity it’s no good because a single EJB can be invoked concurrently. If there’s a popular EJB you end up with the one-giant-lock problem all over again

So that’s exhausted all obvious solutions. What we needed was a table where:

1. a key could be inserted atomically, and 
2. its counter incremented atomically 

…but these two operations are not atomic (together). Here’s roughly what we came up with (credit should mostly go to my colleagues):

public class CountingTable<K> {
    private final AtomicReferenceArray<K> keys = new AtomicReferenceArray(CAPACITY);
    private final AtomicIntegerArray counters = new AtomicIntegerArray(CAPACITY);

    public void count(K key) {
        int index = key.hashCode() & (keys.length() - 1);

        while(key != keys.get(index) && !keys.compareAndSet(index, null, key) 
                                     && key != keys.get(index))
            if (index < keys.length() -1)
                index++;
            else index = 0;  //wrap

        counters.incrementAndGet(index);
    }
}

What we end up with is a constant-time, fixed-size, lock-free, wait-free, open-addressing hashtable with linear reprobing. =)

How does it work?

• First, we hash into the array somewhere (sparse-array trick); I use & as it’s much faster than %
• Next, we test if the key is already there (if it is, drop out, increment and done)
• If not, we try to insert the key using CAS against null (if slot is empty, insert key, drop out, increment and done)
• If not, we recheck to ensure an interleaving thread didn’t insert our key (if it did, drop out, inc & done)
• If not, we move to the next slot in the array (linear reprobing); rinse, lather and repeat.

Does it really work?

• constant-time complexity – by hashing into an array, I guarantee O(1) puts in the average case
• lock-free – there is absolutely no mutex over the table, a stripe or even a single key!
• wait-free – during a single put, multiple threads can make make progress (even to the same key)
• linear-reprobing – by scanning forward into the array on collisions, we maintain constant time-complexity (degrades to linear in the worst case, i.e. if all keys collide)
• open-addressing – by storing keys and values in the array, we can vastly improve CPU cache performance over a traditional chaining hashtable like j.u.HashMap and j.u.c.ConcurrentHashMap in colliding cases

Send me your thoughts, I suspect this can be improved a lot. (And if you want to see another post on reading from this table =)

With due props to Cliff Click’s ideas on hashtables.

Filed under: 1   |  2 Comments
Tags: concurrent, counting, data structure, hashtable, java, lock-free, threading, wait-free