This is the first post in which I go over random concurrent data structures.

This post is based on the Lazy List data structure introduced here: https://people.csail.mit.edu/shanir/publications/Lazy_Concurrent.pdf

Ideally this post can help you understand at a high level how we can optimize a regular set data structure and eventually end up with the one described in the paper.

What is it?

The data structure presented in the paper is known as the Lazy List. It functions like a regular sequential set in which as a user you can call the following APIs:

  • add(x) -> bool - Inserts x into the set.
  • remove(x) -> bool - Removes x from the set.
  • contains(x) -> bool - Checks if x is in the set.

It is also thread-safe, meaning multiple threads can access the data structure and it would work correctly! (We will talk more about what it means to be “correct” below)

So what makes this data structure special?

A question that you might be asking right now is “why not just wrap a set in a lock and call it a day?”. And you are right to be questioning that!

Before jumping into the presented data structure, let’s build up to it step by step.

Linked List Based Set.

We start with a sorted singly linked list. Each node in the list represents an element in our set.

“Wait, why a linked list? Wouldn’t you normally use a hash set?” Yeah… we’re mostly using a linked list here for the sake of introducing the lazy list as it is based off a linked list.

Below shows how our list with the values {1, 3, 7, 8, 67} would look like:

flowchart LR
    H["1"] --> A["3"]
    A --> B["7"]
    B --> C["8"]
    C --> T["67"]

Implementing each operation is simple:

  • The add(x) operation traverses the list and finds where to insert a new node and inserts it.

  • The remove(x) operation traverses the list and finds if x is present, removing the node if present.

  • The contains(x) operation simply traverses the list to find if x is present or not.

To make this data structure thread-safe, we simply have a big global lock and lock before each operation and release it after the operation is done.

Can we make this faster?

Of course we can, otherwise this post wouldn’t exist. One bottleneck with this locking approach is that each operation must wait for the lock. This is bad because all operations use the same lock. So each operation must wait for the other to finish and release the lock before it being able to do work.

In a theoretical worst case scenario, it’s possible the thread holding the lock keeps on getting yielded and therefore making all other concurrent operations wait longer.

So if we can make each operation not wait on the same lock, this issue is mitigated.

Fine Grained Locking (Optimistic List)

One observation you might notice with sorted lists is that adding and removing only requires modifying a few nodes.

To show what I mean, consider the following list:

flowchart LR
    H["1"] --> A["3"]
    A --> B["7"]
    B --> C["8"]
    C --> T["67"]

In the diagram above, when we want to:

  • add(6): We only need to touch the nodes 3 and 7.
  • remove(7): We only need to touch the nodes 3 and 7.

Let’s denote the nodes 3 and 7 here as pred and curr respectively to make things easier in the next sections.

If we lock only the nodes that matter (curr and pred), then we can improve the set’s performance, since we don’t have to wait for the global lock.

Naively doing this however, is dangerous. During our traversal, if we don’t hold a global lock the list itself might have changed!

To see what I mean, observe the following video:

But if we hold a global lock during the traversal, we go back to the performance of our first approach. To cope with this, once we hold the fine-grained lock, we should validate that nothing has changed.

Prior to holding the lock, the following cases might have occured:

  • curr node could have been removed
  • pred node could have been removed
  • Another entry was inserted in between curr and pred.

If the validation failed (one of the cases above was violated), then we simply restart the operation.

Note: A case I was wondering was when curr->next is modified? This is not a problem since curr->next requires locking curr, which we already hold (and any earlier update is already visible to us).

In a hand-wavy pseudocode, here is how we can write our code:

bool add(x) {
    while (true) {
        auto [pred, curr] = traverse(x);
        lock_guard(pred); // unlocks automatically at end of scope
        lock_guard(curr);

        if (validate(pred, curr)) {
            // same logic as seq. based
        }
    }
}

bool remove(x) {
    while (true) {
        auto [pred, curr] = traverse(x);
        lock_guard(pred);
        lock_guard(curr);

        if (validate(pred, curr)) {
            // same logic as seq. based
        }
    }
}

bool contains(x) {
    while (true) {
        auto [pred, curr] = traverse(x);
        lock_guard(pred);
        lock_guard(curr);

        if (validate(pred, curr)) {
            return curr.key == x;
        }
    }
}

How does validate work?

To validate that the two nodes are still valid (that is, neither node has been deleted nor has a node been inserted between them), a simple approach is to re-traverse from head until we reach pred (proving pred is still reachable in the list), and then check pred.next == curr:

bool validate(pred, curr) {
    Node* node = head;
    while (node.key <= pred.key) {
        if (node == pred) {
            return pred.next == curr;
        }
        node = node.next;
    }
    return false;
}

This means we have to retraverse the list (though we don’t need to use locks)

Can we make this faster?

Yes we can!!!

When using sets, contains() is usually the most common operation used by far. So if we can make contains() not lock at all (lock-free) and potentially have no retries (wait-free) then this will be blazingly fast!

The Lazy List

The Lazy List (the data structure in the paper) is based off the Optimistic List, except its contains operation is wait-free!

The trick is to add a logical deletion step (marking a node as deleted) before actually doing the physical deletion (updating the pointers).

Essentially each node should have an atomic boolean marked which states whether the node has been “removed” yet. The remove(x) operation should then set curr.marked = true when it’s trying to delete a node.

flowchart LR
    subgraph Step 1: Logical Deletion
        D1["1"] --> A1["3"]
        A1 --> B1["7 (marked: true)"]
        B1 --> C1["8"]
    end
flowchart LR
    subgraph Step 2: Physical Deletion
        D2["1"] --> A2["3"]
        A2 --> C2["8"]
        B2["7 (marked: true)"] -.-> C2
    end

A nice bonus is that marked makes validate(pred, curr) for add and remove go from an $O(N)$ operation to $O(1)$ since we don’t have to re-traverse the list to see if the nodes have been deleted:

bool validate(pred, curr) {
    return !pred.marked && !curr.marked && pred.next == curr;
}

The main improvement, however, is that contains(x) requires no locks and no retries:

bool contains(x) {
    curr = traverse(x); // no locks, no validation!
    return curr.key == x && !curr.marked;
}

Right now, you might be skeptical about the statement I just made about it requiring no lock and no retries. So let’s go into the correctness of this.

Correctness

So how do you determine what is “correct”? The standard of correctness for concurrent data structures is a condition called linearizability.

Linearizability

Linearizability is a condition in which between each operation’s invocation and response, there exists a point (call this a linearization point) in which the operation appears to take effect instantaneously at that point (and respects the real-time order of non-overlapping operations).

Why does linearizability matter? It means if we take these linearization points and replay them on a regular sequential set, it ends up in the exact same state as our concurrent Lazy List.

Lazy List is Linearizable

Let’s now provide some reasoning as to how the lazy list is linearizable.

For successful add and remove operations, every other thread can see that the operation has succeeded when the node is linked into the list (for add) or when marked is set to true (for remove). So those are their linearization points. Unsuccessful add and remove calls linearize when they observe curr after validation.

Now for contains. Suppose we are traversing the list. If in the middle of a traversal:

  • The current node we are visiting has been deleted: This is fine because the deleted node’s next still points to a valid node of our list.
  • If we have landed on curr, and another thread just deleted this node, then the marked tag has been set to true, thus we return that the item is no longer there.

Suppose we are in the middle of a traversal and a concurrent add(x) creates a new node at a place earlier than curr. Then there exists a point in time in which the add(x) had not occurred yet-we can linearize there! Sequentially, this means contains(x) finished before add(x). And if add(x) had already finished before contains(x) started, the node would already be in the list from the start of our traversal, so we are guaranteed to find it.

End

I think this is a good place for me to stop yapping. I’m not a good writer yet, so hopefully I get better the more I write. I find that writing helps me think clearer and helps me understand the concepts better (perhaps since it’s similar to rubber ducking).

I will try to keep making these data structure posts since I am forced to read these papers as part of my thesis anyways. So I think making these short posts is helpful for my understanding. Also there isn’t much resources online about these things which is a shame since its quite cool.

There is 1 more data structure I plan on writing about which is a non-blocking binary tree (Ellen tree). So that might be the next post :D