tzimmermann dot org
Nov 17, 2017 • 10 min read

Transactional Queues and Stacks

In last week’s blog post, we’ve examined transactional linked lists, a new feature coming in picotm 0.8. In this blog post, we are going to talk about transactional queues and stacks. Like lists, both data structures will be available in picotm at the end of November.

A Brief Recap of Transactional Lists

Like traditional linked lists, a transactional linked list is a data structure for storing data elements. In contrast to the traditional list, a transactional list can be shared by multiple threads safely and handles internal errors automatically. As the name suggests, programs use transactional lists from within a transaction, where they provide transactional ACID properties for all their operation.

Here’s an example program that uses a transactional list to store values of type unsigned long. There’s a full explanation of this code in the previous blog post,1 so let’s just go through the most important points. If you are familiar with the interface of C++’s Standard Template Library, you’ll find many similarities.

    struct ulong_item {
        struct txlist_entry list_entry;

        unsigned long value;
    };

    struct ulong_item item = ULONG_ITEM_INITIALIZER(0);

    struct txlist_state list_state = TXLIST_STATE_INITIALIZER(list_state);

The variable item is a list entry that holds a value of type unsigned long. The value is initialized to 0 by the initializer macro. The variable list_state is the global state of a transactional linked list. It stores all entries for this list. All actual list access is performed from within a transaction.

    // Inserting transaction
    //

    picotm_begin

        struct txlist* list = txlist_of_state_tx(&list_state);

        txlist_push_back_tx(list, &item->list_entry);

        // ... more transactional code ...

    picotm_commit
    picotm_end

    // ... more non-transactional code ...

The example’s first transaction inserts the entry item at the end of the transactional list. It first acquires an actual list from the list state by calling txlist_of_state_tx(). The returned txlist structure list provides the interface for operating on the list state, and it also holds the transaction-local state of the list. With the transactional list, the first transaction appends the entry to the list state by calling txlist_push_back_tx(). If other transactions access the list state concurrently, the list’s implementation detects and resolves all resulting conflicts automatically. When the transction commits, the list entry becomes part of the shared list state.

    // Iterating transaction
    //

    picotm_begin

        struct txlist* list = txlist_of_state_tx(&list_state);

        struct txlist_entry* beg = txlist_begin_tx(list);
        struct txlist_entry* end = txlist_end_tx(list);

        while (beg != end) {

            struct ulong_item* item = ulong_item_of_entry(beg);

            // ... do something with local item ...

            beg = txlist_entry_next_tx(beg);
        }

        // ... more transactional code ...

    picotm_commit
    picotm_end

    // ... more non-transactional code ...

The example’s second transaction iterates over the elements of a transactional list. Like the first transaction, it acquires a transactional list from the list state. It then gets the list’s beginning and end entries, which it uses to traverse the whole list from the first to the final entry. If other transactions try to modify the list state concurrently, the list detects and resolves any resulting conflicts automatically.

    // Removing transaction
    //

    picotm_begin

        struct txlist* list = txlist_of_state_tx(&list_state);

        // The list state already contains the entry.
        txlist_erase_tx(list, &item->list_entry);

        // ... more transactional code ...

    picotm_commit
    picotm_end

Finally, the example’s third transaction removes our list entry. It acquires a list from the list state and calls txlist_erase_tx() to remove the entry. As before, conflicts are detected and resolved automatically.

Transactional Queues

The list is a very generic data structure that serves a wide range of use cases. If all we want is to insert entries at one end and later retrieve them in the same order at the other end, we can use a transactional queue instead. The semantics of a queue allows for more concurrency and can thus improve performance in some situation. But first, an example.

    struct ulong_item {
        struct txqueue_entry queue_entry;

        unsigned long value;
    };

    struct ulong_item item = ULONG_ITEM_INITIALIZER(0);

    struct txqueue_state queue_state = TXQUEUE_STATE_INITIALIZER(queue_state);

    // Inserting transaction
    //

    picotm_begin

        struct txqueue* queue = txqueue_of_state_tx(&queue_state);

        txqueue_push_tx(queue, &item->queue_entry);

        // ... more transactional code ...

    picotm_commit
    picotm_end

    // ... more non-transactional code ...

As with lists, there are queue entries and shared queue states. In the example’s first transaction, we acquire a queue for the declared queue-state variable. And as with lists, the queue is the transactional interface for modifying the shared queue state. With a call to txqueue_push_tx(), we insert an entry into the queue. When the transaction commits, the entry becomes part of the shared queue state. As lists, queues detect and resolve conflicts with concurrent transactions automatically.

    // Removing transaction
    //

    picotm_begin

        struct txqueue* queue = txqueue_of_state_tx(&queue_state);

        struct txqueue_entry* item = txqueue_front_tx(queue);
        txqueue_pop_tx(queue);

        // ... do something with item ...

        // ... more transactional code ...

    picotm_commit
    picotm_end

The second transaction in the example removes the entry from the queue. It reads the next queue entry by calling txqueue_front_tx(). This is the entry we pushed into the queue in the first transaction. Then the second transaction removes the entry with a call to txqueue_pop_tx(). After the pop operation, the entry itself is still valid, so the transaction can use it’s stored value for further computation. After the successful commit of the second transaction, the entry is not part of the shared queue state any longer.

In contrast to lists, entries in a queue cannot be iterated over. Only the first or final entry can be retrieved. Furthermore, entries can only be inserted at one end and removed at the other end. These semantics allow for more concurrency an some situations.

    picotm_begin

        struct txqueue* queue = txqueue_of_state_tx(&queue_state);

        txqueue_push_tx(queue, &item->queue_entry);

        // ... more transactional code ...

    picotm_commit
    picotm_end

In this example we push an item into the queue. This is a local operation and because queues don’t allow for iteration, there’s no reason to integrate it into the global state just yet. An optimzation applied by picotm is to keep the push operation in the transaction-local state and only integrate it into the shared state during a commit. The transaction does not acquire a reader lock for the queue until it actually commits. Hence concurrent transactions can retrieve or even remove entries on the queue without being affected by our uncommitted push.

Transactional Stacks

Like queues, stacks have certain properties we can use for reducing conflicts and increasing concurrency among transactions. But let’s look at some code first. Here’s the queue example, modified for stacks.

    struct ulong_item {
        struct txstack_entry stack_entry;

        unsigned long value;
    };

    struct ulong_item item = ULONG_ITEM_INITIALIZER(0);

    struct txstack_state stack_state = TXSTACK_STATE_INITIALIZER(stack_state);

    // Inserting transaction
    //

    picotm_begin

        struct txstack* stack = txstack_of_state_tx(&stack_state);

        txstack_push_tx(stack, &item->stack_entry);

        // ... more transactional code ...

    picotm_commit
    picotm_end

    // ... more non-transactional code ...

    // Removing transaction
    //

    picotm_begin

        struct txstack* stack = txstack_of_state_tx(&stack_state);

        struct txstack_entry* item = txstack_top_tx(stack);
        txstack_pop_tx(stack);

        // ... do something with item ...

        // ... more transactional code ...

    picotm_commit
    picotm_end

Again we have entries and shared stack state. The stack is acquired with txstack_of_stack_tx() within each transaction. The first transaction in the example pushes an entry onto the stack, the second transaction retrieves the stack’s top-most entry and removes it. The interfaces are very similar to those of transactional lists and queues. Of course, each interface detects and resolves conflicts among transactions automatically.

Similar to queues, the stack allows us to reduce transaction conflicts and increase concurrency.

    picotm_begin

        struct txstack* stack = txstack_of_state_tx(&stack_state);

        txstack_push_tx(stack, &item->stack_entry);

        // ... more transactional code ...

        txstack_pop_tx(stack);

    picotm_commit
    picotm_end

In this example, the transaction pushes an entry onto the stack. As with queues, this operation is entirely local at this point. There’s no reason to acquire a writer lock on the stack state before the transaction actually commits the change. Concurrent transactions can read the stack state meanwhile.

Even more concurrency can be achieved within the pop operation. Like a push, a pop operation modifies the stack’s top. In the example above, we push an entry onto the transaction’s local stack top. When we later pop the entry, we again operate on the local stack top. So unless we pop an entry from the shared stack state, we don’t require any writer locks. If a transaction performs a number of push operations and afterwards an equal number of pop operations, effectively no change to the shared state was performed. In this case, the transaction can commit without acquiring a lock on the stack state at all.

Summary

In this blog post, we’ve looked at transactional queues and stacks.

If you like this blog post, please subscribe to the RSS feed, follow on Twitter or share on social networks.

Footnotes

  1. If you are curious what this is all about and what transactions can do for your software, you should go back and read the installments about the simpletm toy transaction manager

Post by: Thomas Zimmermann

Subscribe to news feed