Go言語のKey-Value (KV) databaseパッケージの速度を比較してみた

# はじめに

Go言語には、いくつかのKey-Value (KV) databaseのパッケージがあります。
TWSNMPシリーズ

https://note.com/twsnmp/n/na5c62f59833d

の開発のために速度比較をした結果の紹介です。


# 比較したKey-Value (KV) databaseパッケージ

## bbolt

https://github.com/etcd-io/bbolt

boltパッケージをetcdで使用するためにフォークしたもののようです。
B+ treeに基づく設計です。
TWSNMPシリーズは、これを使っていた安定した動作をしています。

## badger

https://github.com/dgraph-io/badger


LSM tree with value logに基づく設計です。
改良が進められているパッケージです。

## loutusdb

https://github.com/lotusdblabs/lotusdb

LSM と B+ treeの両方に基づく設計のようです。


# ベンチマークテスト

これらのパッケージを比較するためにベンチマークプログラムを作成しました。

- 連番キーの書き込み(seq)
- ランダムキーの書き込み(rand)
- 読み出し

を比較しました。

ベンチマークのソースコードは

```go

package main

import (
	"fmt"
	"math/rand"
	"os"
	"sort"
	"testing"
	"time"

	"github.com/dgraph-io/badger/v4"
	"github.com/lotusdblabs/lotusdb/v2"
	"go.etcd.io/bbolt"
)

// テストデータ
var data = "012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789"

// bbolt連番キー書き込み
func Benchmark_bbolt_seq(b *testing.B) {
	os.RemoveAll("./bbolt.db")
	db, err := bbolt.Open("./bbolt.db", 0600, nil)
	if err != nil {
		panic(err)
	}
	defer db.Close()
	b.ResetTimer()
	db.Batch(func(tx *bbolt.Tx) error {
		bkt, err := tx.CreateBucket([]byte("MyBucket"))
		if err != nil {
			panic(err)
		}
		for i := 0; i < b.N; i++ {
			id := fmt.Sprintf("%016x:0123456789abcdef:%016x", time.Now().UnixNano()+int64(i%1000), i)
			bkt.Put([]byte(id), []byte(data))
		}
		return nil
	})
}

// loutusdb連番キー書き込み
func Benchmark_lotusdb_seq(b *testing.B) {
	options := lotusdb.DefaultOptions
	options.DirPath = "./lotusdb_test"
	os.RemoveAll("./lotusdb_test")
	db, err := lotusdb.Open(options)
	if err != nil {
		panic(err)
	}
	defer db.Close()
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		id := fmt.Sprintf("%016x:0123456789abcdef:%016x", time.Now().UnixNano()+int64(i%1000), i)
		db.Put([]byte(id), []byte(data))
	}
}

// badger連番キー書き込み
func Benchmark_badger_seq(b *testing.B) {
	opt := badger.DefaultOptions("./badger_test")
	os.RemoveAll("./badger_test")
	opt.Logger = nil
	db, err := badger.Open(opt)
	if err != nil {
		panic(err)
	}
	defer db.Close()

	b.ResetTimer()
	txn := db.NewTransaction(true)
	for i := 0; i < b.N; i++ {
		id := fmt.Sprintf("%016x:0123456789abcdef:%016x", time.Now().UnixNano()+int64(i%1000), i)
		if err := txn.SetEntry(badger.NewEntry([]byte(id), []byte(data))); err != nil {
			if err == badger.ErrTxnTooBig {
				txn.Commit()
				txn = db.NewTransaction(true)
				txn.Set([]byte(id), []byte(data))
			} else {
				panic(err)
			}
		}
	}
	txn.Commit()
}

// bboltランダムキー書き込み
func Benchmark_bbolt_rand(b *testing.B) {
	os.RemoveAll("./bbolt.db")
	db, err := bbolt.Open("./bbolt.db", 0600, nil)
	if err != nil {
		panic(err)
	}
	defer db.Close()
	b.ResetTimer()
	db.Batch(func(tx *bbolt.Tx) error {
		bkt, err := tx.CreateBucket([]byte("MyBucket"))
		if err != nil {
			panic(err)
		}
		for i := 0; i < b.N; i++ {
			id := fmt.Sprintf("%016x:%x", rand.Uint64(), i)
			bkt.Put([]byte(id), []byte(data))
		}
		return nil
	})
}

// bboltランダムキー書き込み（ソート後に書き込み）
func Benchmark_bbolt_rand_sort(b *testing.B) {
	os.RemoveAll("./bbolt.db")
	db, err := bbolt.Open("./bbolt.db", 0600, nil)
	if err != nil {
		panic(err)
	}
	defer db.Close()
	b.ResetTimer()
	db.Batch(func(tx *bbolt.Tx) error {
		bkt, err := tx.CreateBucket([]byte("MyBucket"))
		if err != nil {
			panic(err)
		}
		ids := []string{}
		for i := 0; i < b.N; i++ {
			ids = append(ids, fmt.Sprintf("%016x:%x", rand.Uint64(), i))
		}
		sort.Strings(ids)
		for _, id := range ids {
			bkt.Put([]byte(id), []byte(data))
		}
		return nil
	})
}

// lotusdbランダムキー書き込み
func Benchmark_lotusdb_rand(b *testing.B) {
	options := lotusdb.DefaultOptions
	options.DirPath = "./lotusdb_test"
	os.RemoveAll("./lotusdb_test")
	db, err := lotusdb.Open(options)
	if err != nil {
		panic(err)
	}
	defer db.Close()
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		id := fmt.Sprintf("%016x:%x", rand.Uint64(), i)
		db.Put([]byte(id), []byte(data))
	}
}

// badgerランダムキー書き込み
func Benchmark_badger_rand(b *testing.B) {
	opt := badger.DefaultOptions("./badger_test")
	os.RemoveAll("./badger_test")
	opt.Logger = nil
	db, err := badger.Open(opt)
	if err != nil {
		panic(err)
	}
	defer db.Close()

	b.ResetTimer()
	txn := db.NewTransaction(true)
	for i := 0; i < b.N; i++ {
		id := fmt.Sprintf("%016x:%x", rand.Uint64(), i)
		if err := txn.SetEntry(badger.NewEntry([]byte(id), []byte(data))); err != nil {
			if err == badger.ErrTxnTooBig {
				txn.Commit()
				txn = db.NewTransaction(true)
				txn.Set([]byte(id), []byte(data))
			} else {
				panic(err)
			}
		}
	}
	txn.Commit()
}

// bbolt読み出し
func Benchmark_bbolt_read(b *testing.B) {
	os.RemoveAll("./bbolt.db")
	db, err := bbolt.Open("./bbolt.db", 0600, nil)
	if err != nil {
		panic(err)
	}
	defer db.Close()
	db.Batch(func(tx *bbolt.Tx) error {
		bkt, err := tx.CreateBucket([]byte("MyBucket"))
		if err != nil {
			panic(err)
		}
		for i := 0; i < b.N; i++ {
			id := fmt.Sprintf("%016x", i)
			bkt.Put([]byte(id), []byte(data))
		}
		return nil
	})
	b.ResetTimer()
	db.View(func(tx *bbolt.Tx) error {
		bkt := tx.Bucket([]byte("MyBucket"))
		for i := 0; i < b.N; i++ {
			id := fmt.Sprintf("%016x", i)
			if v := bkt.Get([]byte(id)); v == nil {
				panic("v==nil")
			}
		}
		return nil
	})
}

// lotusdb読み出し
func Benchmark_lotusdb_read(b *testing.B) {
	options := lotusdb.DefaultOptions
	options.DirPath = "./lotusdb_test"
	os.RemoveAll("./lotusdb_test")
	db, err := lotusdb.Open(options)
	if err != nil {
		panic(err)
	}
	defer db.Close()
	for i := 0; i < b.N; i++ {
		id := fmt.Sprintf("%016x", i)
		db.Put([]byte(id), []byte(data))
	}
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		id := fmt.Sprintf("%016x", i)
		if _, err := db.Get([]byte(id)); err != nil {
			panic(err)
		}
	}

}

// badger読み出し
func Benchmark_badger_read(b *testing.B) {
	opt := badger.DefaultOptions("./badger_test")
	os.RemoveAll("./badger_test")
	opt.Logger = nil
	db, err := badger.Open(opt)
	if err != nil {
		panic(err)
	}
	defer db.Close()
	txn := db.NewTransaction(true)
	for i := 0; i < b.N; i++ {
		id := fmt.Sprintf("%016x", i)
		if err := txn.SetEntry(badger.NewEntry([]byte(id), []byte(data))); err != nil {
			if err == badger.ErrTxnTooBig {
				txn.Commit()
				txn = db.NewTransaction(true)
				txn.Set([]byte(id), []byte(data))
			} else {
				panic(err)
			}
		}
	}
	txn.Commit()
	b.ResetTimer()
	db.View(func(txn *badger.Txn) error {
		for i := 0; i < b.N; i++ {
			id := fmt.Sprintf("%016x", i)
			if _, err := txn.Get([]byte(id)); err != nil {
				panic((err)
			}
		}
		return nil
	})
}
```

#  ベンチマークの実行結果

## 連番キー書き込み

```terminal
$go test -bench seq -benchmem
goos: darwin
goarch: arm64
pkg: kvdbbench
Benchmark_bbolt_seq-10      	  513792	      2348 ns/op	    8530 B/op	      56 allocs/op
Benchmark_lotusdb_seq-10    	  399568	      2855 ns/op	    3616 B/op	      41 allocs/op
Benchmark_badger_seq-10     	  901022	      1373 ns/op	    1563 B/op	      18 allocs/op
PASS
ok  	kvdbbench	5.282s

```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3874862/21e89790-5260-859e-9013-1463c3fe64e5.png)


## ランダムキー書き込み

```terminal
$go test -bench seq -benchmem
goos: darwin
goarch: arm64
pkg: kvdbbench
Benchmark_bbolt_rand-10         	  153877	     44199 ns/op	    6397 B/op	      48 allocs/op
Benchmark_bbolt_rand_sort-10    	  566760	      2217 ns/op	    7505 B/op	      56 allocs/op
Benchmark_lotusdb_rand-10       	  374421	      3267 ns/op	    3211 B/op	      42 allocs/op
Benchmark_badger_rand-10        	  773876	      1599 ns/op	    1327 B/op	      18 allocs/op
PASS
ok  	kvdbbench	12.527s

```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3874862/c990a230-49dd-004f-8c9f-7292a731eb46.png)

Benchmark_bbolt_rand_sortは、キーそソートしてから書き込む改良版です。


## 読み出し

```terminal
$go test -bench read -benchmem

goos: darwin
goarch: arm64
pkg: kvdbbench
Benchmark_bbolt_read-10      	 2521377	       511.7 ns/op	     263 B/op	      13 allocs/op
Benchmark_lotusdb_read-10    	 1000000	      1990 ns/op	    1075 B/op	      27 allocs/op
Benchmark_badger_read-10     	  847098	      2524 ns/op	    2545 B/op	      18 allocs/op
PASS
ok  	kvdbbench	18.016s

```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3874862/9d4dad31-3acb-2365-d3fd-f537cc2b2290.png)

# まとめ

bboltは、読み出しが早く、連番キーの書き込みも、そこそこの速度ですが、ランダムキーの書き込みが、ものすごく速度ダウンします。ランダムのキーをソートしてから書き込み改良した`bbolt_rand_sort` は、速度アップの効果があります。
lotisdbは、LSMとB+ Treeの良いところどりですが、中間的な速度です。
badgerは、ランダムキーの書き込み速度が抜群ですが、読み出しが遅い印象です。

これまで、bboltを開発に使ってきましたが、安定性などを考えても、それほど間違っていなかったと思います。ランダムキーの書き込みになる場合、ソートして書き込む工夫をするほがよいと思います。


# 余談

Go言語のベンチマークの結果をグラフにするためのプログラムは

https://qiita.com/twsnmp/items/36ecf3d188aeb2aed2fb

です。