Avoiding deadlocks

[prologic]

Hey @plar 👋

I know I asked this question in #9 once before and I answered it myself.

Been trying to solve a design issue with Bitcask and Deadlocks for a while now and looking for some help/guidance here.

Basic problem can be summarized as:

• In a .Fold() call we hold a Read lock on the tree
• If the user then calls .Get() this tries to also acquire a Read lock on the tree
• And boom we have a deadlock!

Example:

$ go build -o deadlock deadlock.go
$ ./deadlock
POTENTIAL DEADLOCK: Recursive locking:
current goroutine 1 lock 0xc000128000
../bitcask.go:122 bitcask.(*Bitcask).Get { b.mu.RLock() } <<<<<
../bitcask.go:121 bitcask.(*Bitcask).Get { func (b *Bitcask) Get(key []byte) ([]byte, error) { }
deadlock.go:22 main.main.func1 { val, err := db.Get(key) }
../bitcask.go:510 bitcask.(*Bitcask).Fold.func1 { b.trie.ForEach(func(node art.Node) bool { }
~/go/pkg/mod/github.com/plar/go-adaptive-radix-tree@v1.0.4/tree_traversal.go:51 go-adaptive-radix-tree.traverseFilter.func1 { if options&TraverseLeaf == TraverseLeaf && node.Kind() == Leaf { }
~/go/pkg/mod/github.com/plar/go-adaptive-radix-tree@v1.0.4/tree_traversal.go:70 go-adaptive-radix-tree.(*tree).recursiveForEach {  }
~/go/pkg/mod/github.com/plar/go-adaptive-radix-tree@v1.0.4/tree_traversal.go:36 go-adaptive-radix-tree.traverseOptions { options &= TraverseAll }
../bitcask.go:516 bitcask.(*Bitcask).Fold {  }
deadlock.go:29 main.main { return nil }
/usr/local/Cellar/go/1.18.2/libexec/src/runtime/proc.go:258 runtime.main { // Once it does, it will exit. See issues 3934 and 20018. }

Previous place where the lock was grabbed (same goroutine)
../bitcask.go:507 bitcask.(*Bitcask).Fold { b.mu.RLock() } <<<<<
../bitcask.go:506 bitcask.(*Bitcask).Fold { func (b *Bitcask) Fold(f func(key []byte) error) (err error) { }
deadlock.go:29 main.main { return nil }
/usr/local/Cellar/go/1.18.2/libexec/src/runtime/proc.go:258 runtime.main { // Once it does, it will exit. See issues 3934 and 20018. }

This repro can be found in the deadlock_repro branch and is as simple as:

package main

import (
	"fmt"
	"log"

	"git.mills.io/prologic/bitcask"
)

func main() {
	db, err := bitcask.Open("test.db")
	if err != nil {
		log.Fatal(err)
	}
	defer db.Close()

	if err := db.Put([]byte("Hello"), []byte("World")); err != nil {
		log.Fatal(err)
	}

	if err := db.Fold(func(key []byte) error {
		val, err := db.Get(key)
		if err != nil {
			log.Fatal(err)
		}

		fmt.Printf(string(val))

		return nil
	}); err != nil {
		log.Fatal(err)
	}
}

One way to solve this I think is to copy the tree. You don't currently expose an interface for though though so that's been quite hard to do. Would you consider this?

The downside of copying the tree is of course increased memory (2x) usage whilst performing search/scan operations on the database. But given we deadlock, maybe that's a good trade-off?

Keen to hear your thoughts, and I appreciate your time if you have any spare to offer up any helpful advice 🙏

[plar]

Hey! you can implement the copy feature with existing functionality using ForEach or Iterator but I still believe this is the wrong solution for your case.

I would consider using a reentrant mutex (just google it, there are multiple Go packages, and they are all based on Go runtime internals to get goroutine ID) or I would extend your current API in the way when the user can disable lock using optional argument. Something like:

package main

import "fmt"

type option int

const (
	OPT_NO_LOCK option = iota + 1
)

type options []option

func (opts options) Has(opt option) bool {
	for _, o := range opts {
		if o == opt {
			return true
		}
	}
	return false
}

type DB struct {
}

func (db *DB) Get(key string, opts ...option) ([]byte, error) {
	lock := !options(opts).Has(OPT_NO_LOCK)
	fmt.Printf("[enter] lock=%v\n", lock) // if (lock) { db.mu.RLock() }
	defer func() { fmt.Printf("[exit] lock=%v\n", lock) }()  // if (lock) { db.mu.Unlock() }
	return []byte("value"), nil
}

func (db *DB) Peek(key string) ([]byte, error) {
	return db.Get(key)
}

func main() {
	var db DB
	v, err := db.Get("key")
	fmt.Printf("get with lock v=%v, err=%v\n", v, err)
	v, err = db.Get("key", OPT_NO_LOCK)
	fmt.Printf("get w/o lock v=%v, err=%v\n", v, err)

	v, err = db.Peek("key")
	fmt.Printf("peek (no lock) v=%v, err=%v\n", v, err)

}

https://go.dev/play/p/MXA-d_lvt1h

You also can create a lock-free API and/or only lock-free methods. (ie: Peek method above)

Another option would be to completely redesign your API to use an event driver pattern and have only one place where you can control everything but I think it is out of your scope. :)

Let me know what you think.

[prologic]

@plar One thing I've noticed in your implementation of ART is that you already use some kind of lock-free patterns in many of the tree traversal methods by copying the root node or the current node to a local variable. If I'm reading the code right?

So I'm wondering whether I need to lock a hold at all whilst searching the tree at all? 🤔 experimenting with this idea seems to suggest I don't -- but I'd hardly call that patch very "scientific" 😅

[plar]

Problems can happen when you search and insert into the tree in parallel. For example, when the search goes through one node, and at the same moment, the same node is modified. `ErrConcurrentModification` has been implemented to avoid tree modification while using the iterator. This is a tribute to the Java iterator. :) Pavel

…

On Thu, Aug 4, 2022 at 4:09 PM James Mills ***@***.***> wrote: @plar <https://github.com/plar> One thing I've noticed in your implementation of ART is that you already use some kind of lock-free patterns in many of the tree traversal methods by copying the root node or the current node to a local variable. If I'm reading the code right? So I'm wondering whether I need to lock a hold at all whilst searching the tree at all? 🤔 experimenting with this idea <https://git.mills.io/prologic/bitcask/issues/238#issuecomment-12324> seems to suggest I don't -- but I'd hardly call that patch very "scientific" 😅 — Reply to this email directly, view it on GitHub <#25 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAARYI7R76KBX3PA3MHGBYLVXREQ7ANCNFSM55RI5OXQ> . You are receiving this because you were mentioned.Message ID: ***@***.*** com>