Deadlocking is possible


#1

This has taken a long while to debug, but I think I’ve come to the cause of issues I’ve seen with the new Bolt KV implementation where the whole QuadStore (and underlying Bolt DB) will deadlock. This affects any other implementation that uses transactions when opening iterators.

When an iterator is created a transaction is created and a read lock is acquired. Within that iteration more iterators can be created meaning more than one read lock is acquired within the same go routine. To complete the first transaction, the second must be able to acquire a lock.
If another goroutine acquires a write lock between the two reads opening then nothing can proceed and nobody can open new reads or writes anymore. In the Go documentation of RWMutex it does explictly state that multiple read lockers should not be expected to work.

The original bolt implemenation didn’t have this issue as a read lock was obtained during every call to Next() instead.

Indeed if you wrap memstore with a RWMutex from https://github.com/sasha-s/go-deadlock so that when an iterator is opened RLock is called and when Close is called on the iterator RUnlock is called you get a warning message about multiple read lockers with a large path iteration.

This has caused unexpected halts to our application so now we’re using a copied version of the original bolt implementation.

The one way I can see to fix this for any implementation is to be able to provide some form of context to the iterator methods of a QuadStore so it knows if a real transaction must be opened or not, one could imagine an implementation like so:

// Transaction is an opaque value with no external controls
// That a QuadStore may use to track transactions across a single iteration.
type Transaction interface {
  ID() string
}

func (qs *QuadStore) NodesAllIterator(tx Transaction) graph.Iterator {
   // if tx is nil, create a transaction
   // if the transaction was created then unlock it when the returned iterator is closed.
}

#2

Another solution might be to have an OpenTransaction method on QuadStore, and all methods like NodesAllIterator will be available on that transaction.


#3