A Concurrency-safe, Iterable Binary Search Tree

In today’s article, we will implement a simple, unbalanced, concurrency-safe binary search tree in Golang. We will use some nice patterns along the way that are worth knowing.

I assume that the valued reader has a basic understanding of the Go programming language and knows what a binary search tree is. What I want to show is how easy it is to create a concurrency-safe version of this basic data structure in Golang.

Let’s begin! The API for our binary search tree should offer the following actions:

  • Value(key) returns a node’s associated data (the value)
  • Upsert(key, value) updates or inserts the value for a node identified by key
  • Iter() iterates over all nodes of the tree in order

The key shall be a string unique to the instance of the tree. It is identifying an individual node. Regarding the value that is stored, we will be more agnostic and use an empty interface, thus allowing all kinds of data to be stored in our tree. From the data structure point of view, we do not care about the value. So why should we care about its type, then?

The Tree

For now, the tree is represented by a simple type that holds just the root node:

type BSTree struct {
	root *node
}

The Nodes

For the nodes we will be using a simple struct with fields for the key, value, and pointers to child nodes:

type node struct {
  key   string
  val   interface{}
  left  *node
  right *node
}

Retrieving the value of a node is, no surprise here, a recursive function. It leverages the fact that a binary search tree, per definition, is sorted. If we are searching for a key that is smaller then the key of the node we are looking at we have to proceed on to the left child. If the key is larger, we proceed on to the right child. If none of the above applies we have found the node we were looking for.

func (n *node) value(key string) (interface{}, error) {
	if n == nil {
		return nil, ErrorNotFound
	}
	if key < n.key {
		return n.left.value(key)
	} else if key > n.key {
		return n.right.value(key)
	}
	return n.val, nil
}

Upsert

Upsert, the union of the operations of updating and inserting, works very similar. The only difference is, that if we can not find a node, we create the node.

func (n *node) upsert(key string, val interface{}) {
	if key < n.key {
		if n.left == nil {
			n.left = &node{key: key, val: val}
		} else {
			n.left.upsert(key, val)
		}
	} else if key > n.key {
		if n.right == nil {
			n.right = &node{key: key, val: val}
		} else {
			n.right.upsert(key, val)
		}
	} else {
		n.val = val
	}
}

Concurrency-safe API using a Read-Write-Mutex

We will take two steps to ensure a concurrency-safe API:

  • Protect the tree from being written to by multiple writers at the same time by introducing a Read-Write-Mutex (a lock)
  • Create public wrapper methods honoring the mutex for the private method. For example the method Upsert() is concurrency-safe while the method upsert() is not. So Upsert() will have to take care of locking and unlocking.

It is considered good style to place the synchronizing entity directly above the field that it is protecting:

type BSTree struct {
	lock sync.RWMutex // <-- This one is protecting 'root'
	root *node
}

Here the sync.RWMutex is protecting the root node and all its descendants.

The public method Upsert() of the BSTree type is acquiring the lock and then calling the private method upsert() on the root node. The releasing of the lock is deferred for convenience.

func (b *BSTree) Upsert(key string, val interface{}) {
	b.lock.Lock()
	defer b.lock.Unlock()
	// if root node is empty, new node is root now
	if b.root == nil {
		b.root = &node{key: key, val: val}
	} else {}
		b.root.upsert(key, val)
	}
}

Using this simple pattern we can keep the actual data changing methods free of synchronization artifacts. At the same time, we have all the locking and unlocking concentrated in the public methods. I like his pattern because it helps me gain a quick overview of the entry points for calling functions into my library code.

Iterating using a Channel

Iterating over a binary tree in order is relatively easy. We recursively walk through all the nodes and return the left child’s value, then the node’s value, and finally the right child’s value. Assuming we want to send the values into a channel, the code might look like this:

func (n *node) iter(ch chan<- Item) {
	if n == nil {
		return
	}
	n.left.iter(ch)
	ch <- Item{
		Key: n.key,
		Val: n.val,
	}
	n.right.iter(ch)
}

The channel is of type Item which is a simple struct that holds the key and the value of a node. It looks like this:

type Item struct {
	Key string
	Val interface{}
}

Now comes the tricky part. We want the iter() method to be used by external code in a concurrency-safe way. This means we can allow one or more readers, each one having its own channel for Item retrieval, but no writer until the last reading channel is closed. The Read-Write synchronization is taken care of by the mutex already. Nice! However, parallel, non-blocking reading through multiple channels is not that easy. It asks for a smart use of channels and goroutines.

Let’s start simple: A reader calling Iter() shall receive a read-only channel. Obviously, we have to create this channel at the beginning of the method and return the channel when the method ends. This is easy:

func (b *BSTree) Iter() <-chan Item {
	ch := make(chan Item)
	b.lock.RLock()
	// here be dragons
	return ch
}

But wait, don’t we have to close the channel eventually? And how do we keep the program from blocking, given that the reader cannot receive from the channel before we have returned it? Furthermore, we can not (continuously) send to the channel until the reader has received from the channel, thus freeing up slots for us to write into. And when do we unlock the mutex?

The solution is to delegate all these tasks to a goroutine. The goroutine has access to the context from which it was called. This allows us to call the iter() method on the root node, unlock the mutex, and also close the channel all inside the goroutine. And suddenly, all we need is taken care of and we can return the channel we just created.

func (b *BSTree) Iter() <-chan Item {
	ch := make(chan Item)
	b.lock.RLock()
	go func() {
		b.root.iter(ch)
		b.lock.RUnlock()
		close(ch)
	}()
	return ch
}

It is OK to be confused by the code at first. A lot is happening here and the pattern might not be clear from the beginning. Feel free to take your time to grasp it.

Conclusion

Implementing a binary search tree in Golang is straightforward and does not require deep language knowledge. By adding synchronizing tools like mutexes and channels, data structures can be made ready for showtime in concurrent programs.

Source

A full implementation including a Delete() method and 100% test coverage can be found in the golibby repository.

Replying To Domain Abuse Mail

Once I heard about an abandoned World War II-era anti-aircraft platform that sits in the North Sea and hosts a self-proclaimed micronation called Principality of Sealand. One can hardly spot it on Google Maps, this is how micro it really is.

sealand on google maps,small

Here is an aerial shot of Sealand by Ryan Lackey:

sealand from the sky

Back then I was fascinated by the history of the platform and thought it was quite funny to establish a nation in the middle of nowhere. Years went by and I did not think about the story anymore.

One day, however, I found myself setting up a number of off-site backup systems and wanted to collect them under their own domain name for disaster recovery purposes. Thinking about an appropriate domain name the Sealand story came to my mind. So I ended up registering the sealand.io domain name. Skip ahead another couple of years and the off-site systems were eaten up by the cloud and the domain served no purpose anymore. Forgotten and abandoned it was sitting at a registrar’s account, just like the anti-aircraft platform was sitting abandoned in the North Sea.

And then I received an abuse notification via my registrar from an unrecognized sender, claiming to be representing the Government of Sealand.

Please find below a message we received regarding your domain name sealand.io:

From: [redacted address, appearing to be sent from a personal account]

Message: I would like gandi.net to help me contact the owner of Sealand.io I represent the government of Sealand (https://www.sealandgov.org). We would like to discuss the release of sealand.io from its current owner.

What to think about that? Usually, I do not follow up on emails like these. However, given my previous fascination with the platform’s history, I decided to contact the official address of the Government of Sealand.

Hi,

I received the attached message and wanted to check out if this is a legitimate request. If it is, I think we will find a way. I am open to talk.

Cheers

Dan

Now that I think about it, this was the most sloppy mail I ever wrote to a government. I probably assumed that folks who enter platforms in the sometimes unforgiving North Sea must be cool enough to deal with my sloppiness.

During the following conversation, I learned that the Principality of Sealand understands itself as a non-profit organization. A property I believe most governments share in one way or another. Furthermore, I learned about future plans regarding the platform management that would benefit from having a fancy domain like sealand.io. I do not want to go into details here to not endanger the success of the project. And also, to better not get into trouble with the Government of Sealand. Who knows what these bad ass guys are capable of? After all, they threw a bunch of pirate radio broadcasters from the platform in 1967.

Not having any idea what I could use the domain for I agreed to trade it in with the Government of Sealand for a title. A couple of days later my noble title arrived. There even was postage from Sealand on the parcel (which was delivered by UPS).

sealand stamp,small

The title certificate was inside a very fancy looking leather wrapper with the seal of the Principality of Sealand on it. If you look closely, you can see the slogan E Mare Libertas which means From The Sea, Freedom.

leather wrapper,small

Inside the leather wrapper was a 29-page fact sheet about the history of the micronation and, of course, the certificate to prove my surprisingly gained nobleness.

duke of sealand certificate

I am now officially a Duke of Sealand. 👑 Maybe I should read my abuse mail more often. 🤔

Protip: Do not ask your partner to address you as your highness in future conversations. Not a good idea. Funny, but not a good idea. 😬

Eight Queens: A Simple Backtracking Algorithm In Golang

The Eight Queens Puzzle, a popular computer science question reads:

How do you place eight queens on a chess board so that they do not attack each other?

The queen is the most powerful piece in a chess game. She can move in any direction and as far as she likes. This means a queen placed on the board attacks quite some fields. None of these fields can be used to place another queen because they would attack one another.

One solution to this problem includes backtracking, which is defined by Wikipedia as follows:

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.

The QueensBoard Package

Let’s implement a simple backtracking algorithm for the puzzle! It uses a package called QueensBoard which includes the following functions:

  • New() creates an 8x8 board.
  • board.Queens() returns the number of queens that are currently placed on the board. We will use this function to check if we have found a place for all the queens.
  • board.AvailableFields() returns a list of coordinates which are not under attack and therefore available to place a queen there.
  • board.PlaceQueen() takes coordinates as parameter and places a queen there if possible. It updates the board to mark all fields unavailable that are under attack.
  • board.RemoveQueen() takes coordinates as parameter and removes the queen from the field addressed by the coordinates.
  • board.Print() takes a Writer interface as parameter and writes a Unicode-powered human-readable representation of the state of the board to it. We will use it with os.Stdout to print the final result.

Recursive Approach

Backtracking and recursion often go very well together. We can use recursion to dive deeper and deeper into a prospective solution until

  • we either hit the base case and return the solution, or
  • we realize that we are on a path that will not lead to a solution.

If we barking up the wrong tree, we backtrack to the last state and try a different way. In our example, backtracking means, that we remove the last queen that we placed on the board if we realize that we can not place all eight queens. This usually happens when there are not enough unattacked fields left to place queens on.

Boringly, we will name then function queens(). It will take a *qb.Board as parameter and also return a pointer to a qb.Board struct. The base case will be the perfect board: One with eight queens that do not attack each other:

func queens(board *qb.Board) *qb.Board {
	if board.Queens() == 8 {
		return board
	}

	// here be magic

	return nil
}

Now we need to fill in the actual algorithm. First, we fetch the coordinates of all the fields that are currently not under attack. We are free to place a queen on any of them, so why not start with the first one? After placing the queen, we recursively dive into this prospective solution and place the next queen and the next queen and so on… If we did not reach our goal of placing eight queens, we remove the queen and try again with the next coordinate.

func queens(board *qb.Board) *qb.Board {
	if board.Queens() == 8 {
		return board
	}
	for _, coordinate := range board.AvailableFields() {
		board.PlaceQueen(coordinate)
		next := queens(board)
		if next != nil {
			return next
		}
		board.RemoveQueen(coordinate)
	}
	return nil
}

Find the full source at the end of the article. This algorithm is not the fastest one, however, on most machines, it should finish in less than a second. The final board should look like this:

Here is an animation of the first couple of steps of the algorithm:

small

Improve!

The QueensBoard package also offers the ability to create custom sized boards via the NewCustom() function.

  • Investigate how the algorithms scales for increasing board sizes?
  • Have you tried to randomize the list returned from board.AvailableFields()? How did this influence the average runtime of your algorithm?

Source Code

Here is the full source, ready to run:

package main

import (
	"os"

	qb "github.com/danrl/golibby/queensboard"
)

func queens(board *qb.Board) *qb.Board {
    // uncomment the next line to print intermediate steps
	//board.Print(os.Stdout)
	if board.Queens() == 8 {
		return board
	}
	for _, coordinate := range board.AvailableFields() {
		board.PlaceQueen(coordinate)
		next := queens(board)
		if next != nil {
			return next
		}
		board.RemoveQueen(coordinate)
	}
	return nil
}

func main() {
	board := qb.New()
	queens(board)
	board.Print(os.Stdout)
}