Lightweight almost lock-free transaction library

This is a very lightweight implementation of runtime transactions.

What are runtime transactions? They model a low-locking approach to deal with highly concurrent access to data structures. They are inspired by lock-free algorithms which are designed in a way that despite no locking is used in the code no data corruption will occur if data is accessed from multiple threads concurrently.

In a typical lock-free algorithm a variety of mechanism including atomic variables and sacrifice buffers will be used to manage consistency without locking.

While it may prove to be effective in highly concurrent systems, such algorithms have very high overhead and are complicated for understanding.

This library implements model which is much easier to understand while still can bring some benefits of lock-free computing and definitely won't rob you of fun of dealing with partially inconsistent data structures.

History

The origin of the idea of runtime transaction traces to my other project of a realtime microkernel operating system. In this system it could happen that a peripheral signalled CPU interrupt and interrupt handler routine called certain operating system routine.

The problem was that this routine wasn't atomic and could be called from non-interrupt context as well (e.g. by an application). As this routine was traversing internal data structure it was by no means atomic.

Mutexes were not a solution here as if userspace was the first to call this routine which in turn locked a mutex any interrupt that happened at that time which called the same routine would cause a deadlock.

Another solution was to disable interrupts for the duration of this routine. This would work but would introduce massive delays into interrupt processing as the data structure processed in the routine could potentially become quite large.

Ideal solution would provide fast lane for when this particular routine was called from interrupt context so interrupts won't get disabled nor delayed. Thus ideal solution would be a lock-free version of that routine. Unfortunately lock-free solution would have large memory overhead and was not suitable for embedded environment.

As it turns out, quite often a read-modify-write operation on some data structure is in fact find-read-modify-write one. Out of these four steps, find step usually takes the most time. If there was a solution that would allow find to run concurrently in multiple contexts and then allow one of them to lock the mutex just for the short time then both realtime properties and consistency would be maintained.

What about the other context which started searching for entry to modify but was raced by another context? Just prevent it from modifying the data.

This idea was actually implemented in the kernel and all potentially concurrent actions were rewritten to use transactions.

How it works

The transaction library works by closing data accesses in so-called transactions.

What is a transaction? Transaction is a modified critical section. In critical section the thread that locks a mutex has exclusive access to the whole data structure. It can assume that structure won't change unexpectedly until critical section is left.

While this provides strong guarrantees it may hold other threads for too long.

What transactions change is that if you open transaction, exclusivity is not guarranted. You may as well execute transaction accessing same data as some other thread.

How can this mechanism guarrantee consistency then?

Another modification exists in later stages. When the entry intended for modification is found then the transaction is committed. Commit may (similarly to databases) either succeed or fail. Lets focus on scenario when commit succeeds: only now a thread gains exclusive access to the data structure. It is free to modify the data structure.

Which brings us to scenarios when transaction commit fails: this happens if there was any other thread which committed its transaction after you opened your transaction and before you tried to commit it. In other words this means that the data structure has been modified since you opened your transaction.

It is then up on the application software to decide what to do now. In some cases it may make sense to retry the operation (this is actually what a lot of lock-free software does) or it can decide to abort the action and return.

The scenario with transaction commit failing is actually useful for one another use-case: read-only access to data. The information that data has been changed since transaction started is useful in this case too: it allows to maintain consistency.

This model is not anything unique. It actually resembles database transactions of read committed level: All participants immediately see each data modification and transaction mechanism guarantees that modification itself is atomic and serialized.

Fun world of lock-free algorithms

Lock-free algorithms come at a price and increased computational overhead is not the only factor here.

If you use traditional critical sections entirely enclosed in mutexes you have one firm guarrantee: the entire data structure will be consistent at all times. It is safe to traverse the structure.

With transactions this guarrantee is gone. If you read the data structure inside transaction then it may happen that it will become incosistent in certain structure-specific way. E.g. if your data structure contains exactly one entry of certain type, then with transactions it may appear that it contains zero, one or even two such items. Depending on how two threads align their execution.

Why bother with transactions if they force you to work with inconsistent data?

There is this one tiny difference between pure race condition scenario and transactions: with transactions you know when the data is inconsistent.

You still have to be able to handle working with such data structure (which is its own kind of fun after all). If you manage to do so the advantage gained is less contention of multi-threaded application.

Example

Example below is an implementation of hash table with interleave. In this case each hash table entry either contains value or is empty. There are no linked lists attached to hash table entry that deal with hash collisions.

This kind of hash table is marginally faster if it contains a lot of collisions as linked lists can only be searched linearly which slows lookup down a bit.

Example only provides an implementation of read and write routines. Read routine will read value based its key from table and return true. If such key does not exist in hash table, it will return false.

Write routine will write key-value pair into hash table. If key already exists in the table, it will be overwritten. If it doesn't exist it will be created occupying one more slot in the table.

#include <libtxn.h>

TxnDomain_t hash_map_txn;

typedef unsigned Hash_t;

typedef struct {
    unsigned long key;
    unsigned long value;
} HashTableEntry_t;


constexpr unsigned hash_table_size = 128;
constexpr Hash_t hash_entry_empty = ~0U;
constexpr unsigned hash_table_interleave = 7; // should be large prime smaller than hash_table_size
unsigned hasn_table_used = 0;

HashTableEntry_t hash_table[hash_table_size];

Hash_t hash_key(unsigned long key);

bool hash_read(unsigned long key, unsigned long * value)
{
    Txn_t txn = 0;
    unsigned long tmp;
    do {
        txn = txn_start(hash_map_txn);

        Hash_t hash = hash_key(key);
        
        while (hash_table[hash].key != key)
        {
            if (hash_table[hash].key == hash_entry_empty)
            {
                return false;
            }
            hash = (hash + hash_table_interleave) % hash_table_size;
        }
        
        tmp = hash_table[hash].value;
    } while (txn_commit(hash_map_txn, txn, TXN_READONLY));
    
    *value = tmp;
    
    return true;
}

bool hash_write(unsigned long key, unsigned long value)
{
    do {
        Txn_t txn = txn_start(hash_map_txn);
        
        if (hash_table_used == hash_table_size)
        {
            return false;
        }

        Hash_t hash = hash_key(key);
        
        while (hash_table[hash].key != hash_table_empty || hash_table[hash].key != key)
        {
            hash = (hash + hash_table_inerleave) % hash_table_size;
        }
        
        if (txn_commit(hash_map_txn, txn, TXN_READWRITE))
        {
            if (hash_table[hash].key) == key)
            {
                // update
            }
            else
            {
                // write new entry
                hash_table[hash].key = key;
                hash_table_used++;
            }

            hash_table[hash].value = value;
            
            txn_done(hash_map_txn);
            break;
        }
    } while (true);
    
    return true;
}

You can see that the implementation is pretty much generic. There are three major differences between generic thread-unsafe version of this code and transacted code above:

1. Both functions are implemented as cycles. This is due to the fact that hash table read and write semantics doesn't allow for spurious failure. Thus in case of commit failure, function will retry until it succeeds.
2. Read function opens transaction at the start of each iteration and commits a read-only transaction after value has been obtained into temporary. This gives guarantee that there was no hash table modification performed while routine was traversing the table.
3. Write function also opens transaction at the start of each iteration but commits it before modifying the structure. This ensures that this thread is the only one modifying the structure. Any other thread that might be iterating over the structure in an attempt to modify it will be notified that the structure was changed since the iterating started.

Hash table is a good example of a structure that is easy to work with using transactions as it is safe to traverse a hash table even if it modified under the hood. There is no possibility of invalid memory access due to concurrent hash table modification.