I had the need for a priority queue today in golang so I implemented
container/heap.Interface which has the following methods:
Pretty simple interface, Push, Pop and a sorting interface, which contains Len,
Swap, and Less. Which ended up looking a lot like the priority queue example in
At this point we have a working priority queue. We use heap.Push and heap.Pop
to interface with the heap, and things are lovely. Until you try to use this in
a web application, that potentially has many go routines trying to push and pop
at the same time.
Much like Golang’s map implementation the container.heap implementation is not
thread safe, and is not thread safe for a reason, the application knows better if
this implementation needs to be safe or not.
With this in mind, we need to protect this data-structure.
The Wrong Way
The wrong way to try to protect this data-structure is to try to protect it within the
implementation of the heap.Interface interface. You might be tempted to use
channels for serialization of writes to the underlying data-structure. What
could go wrong, you can protect the physical underlying data-structure by having
a single go routine doing all of the writes to the data-structure, and being messaged from
many go routines.
Well, not really. You can not protect it in the implementation of the interface
mainly because the heap sorting is performed in the container.heap package, and
you can not be sure that each operation happens in the right order due to the
channel selection randomness.
The Right Way?
In the end I have decided to serialize the access to the heap.Push and heap.Pop
function calls in my application by doing what can be seen below:
This code now serializes the Push/Pops to the heap and should be thread safe.