Multithreaded Insertion in Binary Search Tree (BST)

Question

I have a task of inserting multiple elements into a BST. The task has to be optimized by use of multiple threads. There is no limit on how many threads can be launched.

Here is my approach. This is a theoretical approach. I have not tried implementing it and have no idea to what extent it will work. Please suggest your opinions on this idea.

The BST Node will look something like this:

class BSTNode {
    int val;
    BSTNode left, right;
    boolean leftLock, rightLock;
    Queue<BSTNode> leftQ, rightQ;
}

I am not using any Java locks, rather using two boolean variables to denote the state of lock.

Since insertion of any element first requires us to find the relevant position, this task can be carried out in parallel, since this will not modify the tree. The task can only work till the point a node on the path is unlocked. If a particular node is locked, then that particular insertion thread is put to sleep() and added to the corresponding left or right queue and waked up again when lock is released.

On the other hand, if none of the nodes on the path have a lock on them, we can proceed ahead with insertion. Before insertion and modifying the corresponding pointer of parent, a lock must be acquired on the parent.

Can anyone suggest their views on this implementation method?

Answer 1

I am trying to explain only 1 problem which shows the basic loophole in this approach.

Assume that you are supporting only insert operation for now and not any other operations. Following could be an implementation for the insert operation:

//Using C
BSTNode* insert(BSTNode* root,int value)
{
1    if(root == NULL){
2       return createNewNode(value);
3    }
4    
5    if(root->data == value){
6        return root;
7    } 
8    else if(root->data > value){
9        while(root->leftLock);
10        if(!root->left){
11            root->leftLock = true;
12            root->left = insert(root->left,value);
13            root->leftLock = false;
14        }
15        else{
16            root->left = insert(root->left,value);
17        }
18    }
19    else{
20        while(root->rightLock);
21        if(!root->right){
22            root->rightLock = true;
23            root->right = insert(root->right,value);
24            root->rightLock = false;
25        }
26        else{
27            root->right = insert(root->right,value);
28        }
29    }
30    
31    return root;
32    
}

In this approach, since only the children of the last node (leaf node) will get updated upon inserting a value, So we are not doing any locking while updating the parents (when recurring back).

I am avoiding insertion request queuing and using spinlocks only to keep it a little simple. However the point i am gonna raise will be same for that case too...

Consider this BST:

    10
   /  \
  5    15
 / \  /  \
2   6 13  20

Suppose 2 threads t1 and t2 are invoked simultaneously trying to insert values 25 and 26 respectively and currently are at BSTNode with value 20. (The rightmost node).

Now lets execute the above code with context switching between the threads:

a. t1:
          1. if(root == NULL)  //not true, will go to line 5.
          //switch

b. t2:
          1. if(root == NULL)  //not true, will go to line 5.
          //switch

c. t1:
          5. if(root->data == value){  //not true, will go to line 8.
          8. else if(root->data > value) //not true, will go to line 19.
          //switch

d. t2:
          5. if(root->data == value){  //not true, will go to line 8.
          //switch

e. t1:
          19    else{
          20        while(root->rightLock);  // lock is not held by anyone, so continue.
          21        if(!root->right){
          //switch
f. t2:
          8. else if(root->data > value) //not true, will go to line 19.
          19    else{
          20        while(root->rightLock);  // lock is not helpd by anyone, so continue.
          21        if(!root->right){
          22            root->rightLock = true;
          //switch

g. t1:
          22            root->rightLock = true;
          23            root->right = insert(root->right,value);
          //switch

h. t2: 
          23            root->right = insert(root->right,value);
          24            root->rightLock = false;
          //switch

Assume that line 23 covers complete execution of that line.

As you can see in section f,g and h that both t1 and t2 are entering into critical section without knowing the presence of each other. The code was not supposed to allow that.

Whats the problem then ???

The problem is that there is a piece of code which was supposed to be executed in one go:

20        while(root->rightLock);
21        if(!root->right){
22            root->rightLock = true;

So we may need some hardware control by making our own uninterruptible instruction which executes all 3 tasks mentioned above together.

Answer 2

This is really an exercise in trying to implement your own lock. What you've done is created an unpacked lock (boolean, waitingQueue). But, the only way this approach would work safely is if you externally synchronize access to the 'lock' boolean variables and queues. So to make this non-lock code work successfully you'd have to use a lock.

If you didn't use a lock you would have several problems relating to concurrency:

• There is no happens-before relationship between setting any of the values in the node. That is, none of the other threads may see updated values for any of the fields. This alone could cause all sorts of trouble. However, there are more concrete examples.
• No thread knows whether the assignment of the boolean lock was because it changed the value or any number of other threads changed the value (a race condition). Essentially, no thread would know whether it 'owns' the lock. There is a fix for this using a built in class but there are enough other problems this isn't worth persuing.
• There is another race condition between checking the lock and inserting yourself into the queue. One thread may see that another thread 'has' the lock (which is dubious given the second point), and add itself to the queue. But by the time it adds itself to the queue the lock may be unlocked and it may wait infinite time if no other threads touch that part of the tree.
• Poor performance. Each thread can only view on node at a time. Even if you converted the boolean/queue constructs to locks you're likely not going to have good performance because even search() type operations on the tree are going to require using locks to ensure the correct memory visibility and happens-before relationships.

If you want a thread-safe, ordered, mutable container with sub-linear search times use ConcurrentSkipListSet<Integer>

Answer 3

An interesting problem. And there are some points where you have to redefine in your approach.

Since insertion of any element first requires us to find the relevant position, this task can be carried out in parallel

• Actually this is wrong. It is true that it will not be modifying the tree, but since there are some threads in background who are trying to modify this tree (insertion of a node), you have to apply a Lock/semaphore here.
• And you have to do finding a suitable place + actual insertion with a single operation insert. The reason is that, in a situation where one thread (say t1) has finished finding a suitable place and then try actual insertion, but has to hold on because another thread (say t2) is doing the actual insertion, then the first thread (t1) will have to do the place calculation again because the tree has changed after the second thread's (t2) actual insertion. (I think you got what I say)

So in conclusion, parallel insertion for a Binary Search Tree would not benefit you, since A Binary Search Tree Insertion cannot be carried out independently from another insertion.