boltdb/bolt

An embedded key/value database for Go.

bolt's Issues

Rebalancing

Rebalance the b+tree after a value is deleted from the database.

Compaction

Hello,

I was just wondering what Bolt is planning for database compaction? I'm not sure if this is something designed into Lmdb, but I was just running some tests, putting a lot of data into a boltdb, then removing the keys, then adding some more (ones with the same name and others), and the database just kept growing.

Btw, great work on Bolt! It's very clean and happy to see it so active.

As a comparison, leveldb does compaction in a background thread that gets triggered at some event (not sure at which point).

Nested Keys

Overview

Add the ability to nest key/value data inside of keys. This is useful for building indexes and for certain types of nested data.

API

We'll need a function for retrieving a cursor to iterate over the nested values:

func (c *Cursor).Subcursor(key string) (*Cursor, error)

We'll also need functions to get/put/delete. These subkeys are essentially the same thing as buckets. Maybe we just return a Bucket:

func (b *Bucket) Sub(key string) *Bucket

Otherwise we'll have to create a bunch of methods on Bucket:

func (b *Bucket) SubGet(key []byte) []byte
func (b *Bucket) SubPut(key []byte, []byte) 
func (b *Bucket) SubDelete(key []byte, []byte) 

That's pretty ugly. I'm leaning toward just returning a sub-bucket.

Changes

• Add a flag on the leaf node element to distinguish it as having nested data.
• Add Subcursor() function to the Cursor().
• Delete subpages for when deleting the parent key.

Caveats

Only support single-level subcursors. Not only will it make it less confusing but it means that Cursor's can reuse a single subcursor during iteration.

Subbuckets introduce a new error condition where you could try to do a normal Bucket.Get() on a nested key. Currently Get() doesn't return an error which I'd like to keep. I will probably just have it return nil. The other option is to panic.

Proposal: Return an error instead of panic in (*DB).munmap

@benbjohnson Hi,
Could you please explain me why you panic in this method? I dare to say that returning error is more Go-idiomatic. No less important, that you'll be able to pass the error to the DB Close method, thereby implementing the classic io.Closer interface. What do you think?

Document thread safety guarantees

Better document which parts of Bolt are thread safe (DB) and what parts are not (Tx, Bucket, Cursor).

/cc @pkorotkov

Auto-resize mmap

Automatically resize the mmap() as needed.

• Obtain write lock to block all new reader transactions.
• Reopen mmap() with larger size.

golint

Make sure bolt reasonably passes golint.

suggestion: Simpler API with constructor-style Open

Mirroring os.File, if instead of DB.Open you had

func Open(name string, mode os.FileMode) (*DB, error)

that could save some error checking, and even more interestingly, that would almost remove the current only source of errors for DB.Transaction and .RWTransaction.

Almost because one could still run db.Close(); d.Transaction(). But that oughta be rare enough... so to make this idea complete, what if .Transaction and .RWTransaction, when run on a closed db, always successfully returned transactions, where all the operations will just fail? So in essence, this would delay the error checking to the point where you need to check errors anyway. This seems well aligned with http://talks.golang.org/2013/bestpractices.slide#5 and would, in my opinion, simplify typical code.

Unless you foresee other sources of errors for Transaction and RWTransaction.

P.S. Bolt looks really promising. No more fighting with cgo for me!

Index out of range crash

Hey, I've run into a crashing issue. It may be my fault, but my usage is pretty basic. I discovered this after doing some tests where I inserted many thousands of chat messages into Bolt, but fortunately I was able to reproduce with randomly generated messages as well.

Here's the repro code:

https://gist.github.com/cespare/9623b31999bbc0e5266a

All it does is insert 1000 20-word randomly generated messages into a Bolt database, keyed by an incrementing ID.

When you run this once, it's fine. On the second run, doing anything after opening the DB causes a crash. In my repro code I used db.Buckets() to cause the crash.

Note that if you insert fewer documents (say, 900), then the crash doesn't happen.

Race detection

Add testing/quick tests to check for thread safety.

Code Coverage

Increase code coverage to 99% or more.

Shouldn't NextSequence return uint64?

It seems right now NextSequence ends up having different behavior on 32-bit vs 64-bit platforms. I understand that mmap limits mean a 32-bit platform won't ever have a huge boltdb database, but what if one just e.g. cycles through primary key ids relatively quickly? Leaving id=1 allocated and then wrapping a 32-bit counter is definitely plausible.

Remove all hardcoded paths to /tmp

Every single one of these is a security problem:

[0 tv@brute ~/go/src/github.com/boltdb/bolt]$ git grep /tmp/
Makefile:COVERPROFILE=/tmp/c.out
bucket_test.go:                                                 db.CopyFile("/tmp/bolt.put.single.db", 0666)
bucket_test.go:                                         db.CopyFile("/tmp/bolt.put.multiple.db", 0666)
db_test.go:             assert.NoError(t, os.RemoveAll("/tmp/bolt.copyfile.db"))
db_test.go:             assert.NoError(t, db.CopyFile("/tmp/bolt.copyfile.db", 0666))
db_test.go:             assert.NoError(t, db2.Open("/tmp/bolt.copyfile.db", 0666))
db_test.go:     db := &DB{path: "/tmp/foo"}
db_test.go:     assert.Equal(t, db.String(), `DB<"/tmp/foo">`)
db_test.go:     assert.Equal(t, db.GoString(), `bolt.DB{path:"/tmp/foo"}`)
example_test.go:        os.RemoveAll("/tmp/bolt")
example_test.go:        os.MkdirAll("/tmp/bolt", 0777)
example_test.go:        db.Open("/tmp/bolt/db_do.db", 0666)
example_test.go:        db.Open("/tmp/bolt/db_with.db", 0666)
example_test.go:        db.Open("/tmp/bolt/db_put.db", 0666)
example_test.go:        db.Open("/tmp/bolt/db_delete.db", 0666)
example_test.go:        db.Open("/tmp/bolt/tx_foreach.db", 0666)
example_test.go:        db.Open("/tmp/bolt/tx.db", 0666)
example_test.go:        db.Open("/tmp/bolt/tx_rollback.db", 0666)
example_test.go:        db.Open("/tmp/bolt/db_copy.db", 0666)
example_test.go:        db.CopyFile("/tmp/bolt/db_copy_2.db", 0666)
example_test.go:        db2.Open("/tmp/bolt/db_copy_2.db", 0666)

cmd/bolt-fsck

Add a command line utility for performing an in-depth consistency check on Bolt databases.

Open API

Hey, I was curious about the initialization API:

var db bolt.DB
if err := db.Open("/path", 0666); err != nil {
  ...

I didn't see how this worked until I looked at an example. I was looking for a global function to open a database. The typical pattern I would expect to find (examples: net, database/sql, leveldb-go, mgo) is like this:

db, err := bolt.Open("/path", 0666); err != nil {
  ...

Was this a deliberate break from convention? Not a big deal, just curious. (I'd also be happy to send over a trivial PR to add this.)

Sequence

Add an autoincrementing sequence integer to the bucket:

func (*DB) NextSequence(name string) (int, error)
func (*RWTransaction) NextSequence(name string) (int, error)

API Documentation

• DB
• Transaction
• RWTransaction
• Bucket
• Cursor

Improve bulk load performance

Bulk loading more than 1000 items at a time is very slow. This is because nodes are not splitting before commit which causes large memmove() operations during insertion.

This should be (relatively) easy to fix.

Proposal: Change signature of (*DB).Stat

@benbjohnson
Looking at how you provide db statistics (it's great btw) I recalled a series of discussions about refactoring Memory (and GC) stat function in the Go standard library. The eventual form of them is based on that you pass a pointer of a stat struct (see for instance here and here) to reduce the number of stat objects created while polling statistics.
So, the proposal is to exchange
func (db *DB) Stat() (*Stat, error)
with
func (db *DB) UpdateStat(stat *Stat) error

Meta Checksum

• Add a checksum to the meta page to guarantee that it is uncorrupted.

Cursor.Last() index out of range

This bug was introduced in 7214e08

func TestCursorLast(t *testing.T) {
    withOpenDB(func(db *DB, path string) {
        db.CreateBucket("widgets")
        db.Do(func(txn *RWTransaction) error {
            c := txn.Bucket("widgets").Cursor()
            _, _ = c.Last()
            return nil
        })
    })
}

[0 tv@brute ((7214e08...)) ~/go/src/github.com/boltdb/bolt]$ git checkout 1eb9e0902824fff3e7a943d421e83c7d30f43176
Previous HEAD position was 7214e08... Merge pull request #57 from benbjohnson/node-aware-cursors
HEAD is now at 1eb9e09... Merge branch 'master' of https://github.com/boltdb/bolt
[0 tv@brute ((1eb9e09...)) ~/go/src/github.com/boltdb/bolt]$ go test -run=TestCursorLast
seed: 64196
quick settings: count=5, items=1000, ksize=1024, vsize=1024
PASS
ok      github.com/boltdb/bolt  0.007s
[0 tv@brute ((1eb9e09...)) ~/go/src/github.com/boltdb/bolt]$ git checkout 7214e089c0f78fce8fb1e00f09f7d2b54c88bdbe
Previous HEAD position was 1eb9e09... Merge branch 'master' of https://github.com/boltdb/bolt
HEAD is now at 7214e08... Merge pull request #57 from benbjohnson/node-aware-cursors
[0 tv@brute ((7214e08...)) ~/go/src/github.com/boltdb/bolt]$ go test -run=TestCursorLast
seed: 87363
quick settings: count=5, items=1000, ksize=1024, vsize=1024
--- FAIL: TestCursorLast (0.00 seconds)
panic: runtime error: index out of range [recovered]
    panic: runtime error: index out of range

goroutine 19 [running]:
runtime.panic(0x5cd580, 0x766da3)
    /home/tv/src/go/src/pkg/runtime/panic.c:249 +0xba
testing.func·006()
    /home/tv/src/go/src/pkg/testing/testing.go:416 +0x15d
runtime.panic(0x5cd580, 0x766da3)
    /home/tv/src/go/src/pkg/runtime/panic.c:232 +0x116
github.com/boltdb/bolt.(*Cursor).keyValue(0xc208031d70, 0x0, 0x0, 0x0, 0x0, ...)
    /home/tv/go/src/github.com/boltdb/bolt/cursor.go:249 +0x30d
github.com/boltdb/bolt.(*Cursor).Last(0xc208031d70, 0x0, 0x0, 0x0, 0x0, ...)
    /home/tv/go/src/github.com/boltdb/bolt/cursor.go:35 +0x26e
github.com/boltdb/bolt.func·047(0xc208028050, 0x0, 0x0)
    /home/tv/go/src/github.com/boltdb/bolt/bug_test.go:11 +0xef
github.com/boltdb/bolt.(*DB).Do(0xc20805e000, 0x6ac508, 0x0, 0x0)
    /home/tv/go/src/github.com/boltdb/bolt/db.go:354 +0x82
github.com/boltdb/bolt.func·048(0xc20805e000, 0xc20800dec0, 0x1b)
    /home/tv/go/src/github.com/boltdb/bolt/bug_test.go:13 +0x53
github.com/boltdb/bolt.func·075(0xc20805e000, 0xc20800dec0, 0x1b)
    /home/tv/go/src/github.com/boltdb/bolt/db_test.go:372 +0x132
github.com/boltdb/bolt.withDB(0x7ff0c96fdf38)
    /home/tv/go/src/github.com/boltdb/bolt/db_test.go:353 +0xfc
github.com/boltdb/bolt.withOpenDB(0x6ac510)
    /home/tv/go/src/github.com/boltdb/bolt/db_test.go:373 +0x5c
github.com/boltdb/bolt.TestCursorLast(0xc208052120)
    /home/tv/go/src/github.com/boltdb/bolt/bug_test.go:14 +0x27
testing.tRunner(0xc208052120, 0x7691a0)
    /home/tv/src/go/src/pkg/testing/testing.go:422 +0x9d
created by testing.RunTests
    /home/tv/src/go/src/pkg/testing/testing.go:503 +0x8d9

goroutine 16 [chan receive]:
testing.RunTests(0x6ac570, 0x768fc0, 0x54, 0x54, 0x1)
    /home/tv/src/go/src/pkg/testing/testing.go:504 +0x909
testing.Main(0x6ac570, 0x768fc0, 0x54, 0x54, 0x76a9a0, ...)
    /home/tv/src/go/src/pkg/testing/testing.go:435 +0x9e
main.main()
    /home/tv/tmp/go-build690133294/github.com/boltdb/bolt/_test/_testmain.go:229 +0x9c
exit status 2
FAIL    github.com/boltdb/bolt  0.009s
[1 tv@brute ((7214e08...)) ~/go/src/github.com/boltdb/bolt]$ 

Remove DB.Open()

Per @tv42's suggestion, only allow a database to be opened using bolt.Open().

Defer

Add the ability to execute closures after an RWTransaction is successfully committed. Deferred functions do not take any arguments and cannot return anything.

func (t *RWTransaction) Defer(func())

Package Documentation

Cursor.Get should land before non-existing key, not after it

Currently, you can't use Cursor to do range queries or walk a prefix, because if the exact key is not found, it can land after the range. One would expecting walking onward from "foo" to find "foobar":

package main

import (
    "fmt"
    "github.com/boltdb/bolt"
    "log"
)

const bucket = "xyzzy"

func main() {
    var db bolt.DB
    err := db.Open("db", 0666)
    if err != nil {
        log.Fatal(err)
    }
    defer db.Close()

    err = db.Do(func(tx *bolt.RWTransaction) error {
        if err = tx.CreateBucketIfNotExists(bucket); err != nil {
            return err
        }
        if err = tx.Put(bucket, []byte("foobar"), []byte("bork")); err != nil {
            return err
        }
        return nil
    })
    if err != nil {
        log.Fatal(err)
    }

    // this works
    err = db.With(func(tx *bolt.Transaction) error {
        c, err := tx.Cursor(bucket)
        if err != nil {
            return err
        }
        for k, v := c.First(); k != nil; k, v = c.Next() {
            fmt.Printf("walk all: %q %q\n", k, v)
        }
        return nil
    })
    if err != nil {
        log.Fatal(err)
    }

    // this also works
    exact := []byte("foobar")
    err = db.With(func(tx *bolt.Transaction) error {
        c, err := tx.Cursor(bucket)
        if err != nil {
            return err
        }
        for k, v := exact, c.Get(exact); k != nil && v != nil; k, v = c.Next() {
            fmt.Printf("walk exact: %q %q\n", k, v)
        }
        return nil
    })
    if err != nil {
        log.Fatal(err)
    }

    // this doesn't
    prefix := []byte("foo")
    err = db.With(func(tx *bolt.Transaction) error {
        c, err := tx.Cursor(bucket)
        if err != nil {
            return err
        }
        for k, v := prefix, c.Get(prefix); k != nil && v != nil; k, v = c.Next() {
            fmt.Printf("walk prefix: %q %q\n", k, v)
        }
        return nil
    })
    if err != nil {
        log.Fatal(err)
    }
}

Async Writes

Add an async flag to the DB to set whether writes are synchronous or asynchronous.

Writer Lock

Maintain a single DB-level lock while a RWTransaction is in-process.

Cursor Iteration

Allow for forward-only cursor iteration.

• Cursor.First()
• Cursor.Next()

QuickCheck error

Running the parallel tests using -quick-seed=36575 results in a consistency error after 1m23s. Failure happens consistently on Linux and Darwin.

See also: https://drone.io/github.com/boltdb/bolt/78

$ go test -v -race -quick.seed=36575 -quick.count=20 -test.run=Parallel
seed: 36575
quick settings: count=20, items=1000, ksize=1024, vsize=1024
=== RUN TestParallelTxs
....................
--- FAIL: TestParallelTxs (125.70 seconds)
        Location:       functional_test.go:66
    Error:      Not equal: []byte{0x21, 0x5d, 0x41, 0xd2, 0x34, 0x25, 0x90, 0x89, 0x20, 0xb0, 0x71, 0x59, 0xe5, 0x65, 0x3a, 0x7d, 0x44, 0x56, 0x8d, 0xa8, 0xd8, 0x1f, 0x69, 0x4f, 0xe4, 0x35, 0x38, 0xf1, 0x9c, 0x2, 0xcc, 0x9b, 0x6b, 0xf, 0x72, 0xa3, 0x13, 0xd8, 0x88, 0xa1, 0x1b, 0x20, 0x17, 0xb5, 0x30, 0x82, 0x10, 0x35, 0x67, 0xe3, 0x1d, 0x1a, 0x2c, 0x10, 0xef, 0x3a, 0x9a, 0xda, 0x92, 0x2a, 0x70, 0xe7, 0xad, 0x6, 0x7b, 0x15, 0xec, 0x1d, 0x94, 0xb1, 0x5c, 0x9d, 0x79, 0x64, 0x62, 0x81, 0x2d, 0xf0, 0x98, 0x8e, 0x77, 0x74, 0x4d, 0xec, 0xd1, 0xdd, 0xeb, 0xc1, 0x42, 0x75, 0xc8, 0xa7, 0xfd, 0x16, 0xab, 0x70, 0xda, 0xf6, 0x7f, 0x2e, 0xfc, 0x28, 0x5a, 0x85, 0xd9, 0x94, 0xe, 0x4, 0x17, 0x3b, 0xeb, 0xa4, 0x2b, 0x64, 0x20, 0x6f, 0x86, 0xb, 0x3c, 0x20, 0x36, 0xaa, 0x16, 0xc7, 0x5c, 0xdc, 0x6a, 0xa1, 0xcc, 0x98, 0xaf, 0xc2, 0xb5, 0x1d, 0xef, 0x3b, 0x50, 0xf2, 0xb9, 0x43, 0x2e, 0x9f, 0xf9, 0x77, 0xb0, 0xcf, 0xd0, 0x70, 0x31, 0x80, 0xb7, 0xa3, 0x2e, 0x24, 0x65, 0x88, 0xa3, 0xa1, 0xd7, 0xbb, 0xb5, 0x44, 0x7c, 0x4e, 0xb0, 0x33, 0x4c, 0x4e, 0x8a, 0x2e, 0xa0, 0xf0, 0xc5, 0xce, 0xc6, 0x3c, 0x20, 0x6b, 0xab, 0xdc, 0xa3, 0x35, 0x16, 0x51, 0x25, 0xa, 0x6c, 0x31, 0x92, 0x22, 0x4a, 0xd9, 0xf0, 0x5c, 0x85, 0x8, 0xa7, 0xb2, 0x27, 0x10, 0x60, 0x79, 0x38, 0xe6, 0x93, 0x53, 0xf2, 0xd2, 0x48, 0x57, 0x59, 0x95, 0xe4, 0x64, 0x97, 0x8b, 0x67, 0x85, 0x6c, 0x18, 0xa7, 0x2f, 0xb2, 0x97, 0xab, 0xb6, 0xb7, 0x81, 0xfd, 0xba, 0x9e, 0xf9, 0x82, 0xda, 0x4a, 0x71, 0xea, 0x85, 0xbc, 0x9, 0x9f, 0x55, 0xee, 0x7b, 0x7b, 0x2b, 0x5a, 0x40, 0x8a, 0x93, 0xa5, 0x30, 0x21, 0xea, 0xa2, 0xd8, 0x25, 0xb2, 0xe1, 0x3e, 0xa6, 0x82, 0x4e, 0x9f, 0x94, 0xd4, 0x66, 0x92, 0x75, 0x62, 0xfc, 0xe1, 0x86, 0x7f, 0x7e, 0x43, 0x1e, 0xc1, 0xbf, 0x3f, 0xf5, 0x55, 0x9, 0x4, 0x98, 0xa3, 0x16, 0x17, 0x29, 0x35, 0x8b, 0xb0, 0xbd, 0x41, 0x9a, 0xda, 0x1d, 0x25, 0x33, 0xeb, 0xef, 0xd, 0x4a, 0x13, 0xb9, 0x90, 0xb0, 0x70, 0x30, 0xe7, 0x2c, 0x9a, 0x78, 0x6c, 0x8b, 0xd3, 0xa0, 0xf4, 0x80, 0xc8, 0x9, 0xb5, 0xbc, 0x8f, 0x71, 0x4, 0x2e, 0x3b, 0x7e, 0x1c, 0xe7, 0xee, 0x33, 0xce, 0x49, 0x85, 0x2b, 0xf1, 0x29, 0x7, 0x46, 0x44, 0x8e, 0xd5, 0xaa, 0xf9, 0x76, 0xd2, 0x72, 0xb5, 0x48, 0x52, 0x98, 0x21, 0x2, 0x9d, 0xd1, 0xc0, 0xb4, 0x60, 0x68, 0x93, 0xba, 0xbc, 0x5c, 0x5, 0x3d, 0xb0, 0x2, 0x3a, 0x77, 0x18, 0x79, 0x9a, 0xb4, 0x1d, 0x98, 0x97, 0x6f, 0x26, 0x31, 0xb2, 0xf9, 0x84, 0xee, 0x8f, 0xf9, 0xf4, 0x94, 0xae, 0xd8, 0x7, 0x4d, 0xc1, 0xa, 0x5d, 0xd5, 0x86, 0x1a, 0x91, 0x7a, 0x32, 0x1a, 0x2f, 0x3f, 0xb1, 0x51, 0x23, 0x7e, 0xb4, 0x15, 0x1e, 0xef, 0xe2, 0xc0, 0x2f, 0x85, 0x4a, 0x4e, 0x9a, 0xdf, 0xb9, 0x70, 0x96, 0xf, 0xc4, 0xf7, 0x81, 0x8, 0xa4, 0x28, 0x9, 0x56, 0xd8, 0xc0, 0x34, 0xf8, 0xde, 0xbd, 0x9c, 0x16, 0x3b, 0xeb, 0x16, 0xf6, 0xc6, 0xeb, 0x69, 0x1f, 0x99, 0x51, 0xa7, 0x40, 0xa4, 0x7, 0x43, 0x77, 0xea, 0xe, 0x72, 0x4e, 0x37, 0xe5, 0x89, 0x72, 0xd5, 0x3, 0x30, 0x2c, 0x31, 0x76, 0xb0, 0xcb, 0x96, 0x60, 0xd9, 0x24, 0xa6, 0x16, 0x81, 0x3, 0xd8, 0xc5, 0xc5, 0xb6, 0xc2, 0xd1, 0xbe, 0xd2, 0x32, 0x26, 0x7b, 0xdc, 0x73, 0xe3, 0xe1, 0x5f, 0x23, 0x4, 0x8b, 0xb0, 0x55, 0x3e, 0x26, 0xdb, 0x1e, 0x84, 0xcb, 0x70, 0x43, 0xf2, 0x10, 0x45, 0x8d, 0x4f, 0x8e, 0xfe, 0xf0, 0x6b, 0x46, 0x8f, 0x8f, 0x32, 0xf0, 0xfb, 0x3b, 0x2b, 0x47, 0xf6, 0x84, 0xe9, 0xab, 0xf3, 0x84, 0xfa, 0x12, 0xae, 0xe0, 0x5c, 0xaa, 0x10, 0xaf, 0x72, 0x8f, 0x85, 0xb6, 0xf3, 0xb1, 0x51, 0x68, 0xdf, 0xb3, 0xd4, 0xd0, 0x7a, 0x25, 0x3b, 0x90, 0xb9, 0xce, 0x91, 0x2a, 0x17, 0x4e, 0xd8, 0x6f, 0x4e, 0xaa, 0x85, 0xab, 0xc6, 0x80, 0x11, 0x70, 0x28, 0x12, 0x66, 0x7, 0xa7, 0xa2, 0x56, 0x27, 0x27, 0x26, 0x65, 0xed, 0x9f, 0xed, 0x1d, 0x27, 0xca, 0xb3, 0xcd, 0xaf, 0x13, 0x2c, 0x86, 0xb7, 0xd5, 0x56, 0x50, 0xc3, 0x67, 0x34, 0xec, 0x8f, 0xc3, 0x6b, 0xe3, 0x6d, 0xc5, 0x5e, 0x2c, 0xd6, 0xce, 0x2e, 0x87, 0x9b, 0xd3, 0x5d, 0xb8, 0x2c, 0xb2, 0xd, 0xa8, 0x27, 0xca, 0x5b, 0x3d, 0xba, 0x11, 0x1a, 0x15, 0xa1, 0x5, 0x58, 0xbf, 0x29, 0xa0, 0xa8, 0xbf, 0x74, 0x5d, 0xb, 0xf0, 0x3, 0xbb, 0x4f, 0x3e, 0xaf, 0xcc, 0x20, 0x28, 0xc1, 0xe7, 0x61, 0xe8, 0x8c, 0x2a, 0x27, 0x5, 0x84, 0xe8, 0x73, 0x61, 0x5f, 0x6b, 0x7b, 0xc4, 0x3, 0x8d, 0x95, 0x27, 0x67, 0x50, 0xaf, 0xe0, 0x9b, 0xcf, 0x4b, 0x88, 0xe0, 0x36, 0x42, 0xf, 0x8, 0x71, 0xb8, 0xa3, 0x53, 0x37, 0x21, 0x79, 0x4c, 0xfb, 0x33, 0x8c, 0xd8, 0x6d, 0x75, 0x98, 0xb4, 0x94, 0x3, 0x7f, 0xd5, 0x8, 0x3d, 0xdb, 0xd3, 0xe3, 0x98, 0x31, 0x24, 0xbf, 0x83, 0xd1, 0x62, 0x6c, 0x18, 0xce, 0xbe, 0xa, 0xd7, 0xb3, 0x7c, 0xc5, 0xbd, 0x6d, 0x8e, 0x33, 0xe9, 0xce, 0xb9, 0x59, 0x33, 0xa1, 0xa2, 0x19, 0xb9, 0x4e, 0x9b, 0x6d, 0x47, 0xa4, 0x5, 0x59, 0xe, 0x7a, 0x9e, 0x9d, 0xc7, 0xd0, 0xd4, 0x49, 0xf6, 0xc5, 0xee, 0x67, 0x80, 0xe3, 0x39, 0xba, 0xca, 0x9d, 0xb5, 0xaf, 0x19, 0xa5, 0xdb, 0x72, 0x35, 0x3e, 0xfc, 0xa3, 0xc8, 0x54, 0x7d, 0x8e, 0xca, 0x9b, 0x37, 0x0, 0x92, 0xfa, 0x71, 0xe9, 0xf3, 0xc3, 0x95, 0x43, 0x10, 0x51, 0x7b, 0x40, 0xc4, 0x13, 0xc5, 0x95, 0x1c, 0x23, 0xfb, 0xc, 0x91, 0xde, 0x1c, 0x94, 0xdb, 0xb, 0xe6, 0x48, 0x70, 0x7e, 0x4, 0x82, 0xbb, 0x67, 0x5e, 0xcb, 0x59, 0x95, 0x69, 0x73, 0xc6, 0xb9, 0xc1, 0xe9, 0x22, 0xd4, 0x6e, 0x29, 0x65, 0x6, 0xc9, 0x2c, 0x94, 0x9, 0x77, 0x6a, 0x51, 0x6, 0x50, 0x9c, 0x32, 0x7, 0x4e, 0xf9, 0x47, 0xe6, 0xd5, 0x82, 0x24, 0xcd, 0x30, 0xe7, 0x32, 0xb9, 0xb, 0x1e, 0xc1, 0x58, 0xc0, 0x80, 0x70, 0x67, 0xb0, 0x6d, 0x39, 0xaf, 0x55, 0x57, 0xe9, 0xaa, 0xb7, 0xd6, 0x5c, 0x16, 0x69, 0xf0, 0x4a, 0x6a, 0xe2, 0x30, 0xe4, 0x9f, 0xeb, 0x16, 0xc4, 0x84, 0x91, 0xa0, 0x6c, 0x80, 0x4e, 0xc3, 0x5c, 0x42, 0x35, 0x57, 0x8, 0x1c, 0xd7, 0x96, 0x2f, 0x40, 0x49, 0xd, 0xf4, 0xe5, 0x8a, 0xbc, 0x5b, 0xb9, 0x71, 0xe4, 0xd, 0xf3, 0x1e, 0x1d, 0xb4, 0xbc, 0xc9, 0x84, 0x6d, 0x94, 0xa9, 0xa, 0x70, 0x96, 0xa5, 0x1c, 0x9b, 0x2c, 0xb3, 0xbf, 0xe6, 0x90, 0x4a, 0xcd, 0x1f, 0xca, 0x8e, 0x89, 0x39, 0x8, 0x50, 0x6f, 0x96, 0xf4, 0xef, 0x72, 0x7a, 0x45, 0x7f, 0x33, 0x28, 0x77, 0x57, 0x5a, 0x8a, 0x5a, 0x26, 0x71, 0x88, 0xe2, 0xae, 0xac, 0x65, 0xc6, 0x47, 0x16, 0x49, 0xfa, 0x56, 0x65, 0x96, 0xbd, 0x77, 0xee, 0x81, 0xd8, 0x10, 0xf1, 0x7d, 0x30, 0xa0, 0xca, 0xf1, 0x36, 0xcb, 0xe7, 0xdb, 0x27, 0x49, 0xb4, 0x1e, 0x6, 0xc, 0x3, 0x92, 0x7f, 0xf7, 0x6c, 0x9, 0xf0, 0xe9} != []byte{0x3, 0xc8, 0x89, 0xa4, 0x90, 0xe, 0x2f, 0xd7, 0x88, 0xda, 0x86, 0xa4, 0x41, 0x5b, 0x6c, 0xa7, 0x5f, 0xfd, 0xdd, 0x60, 0x44, 0x11, 0x24, 0x6f, 0x5a, 0x7c, 0x60, 0x9b, 0xb7, 0x8e, 0x1b, 0x9c, 0xe1, 0x48, 0x3e, 0x7a, 0xd7, 0xeb, 0xa1, 0x8f, 0x31, 0xa8, 0xd3, 0x0, 0x78, 0x84, 0x22, 0x4e, 0x8d, 0xf7, 0x98, 0xf2, 0x25, 0x3, 0xa4, 0x1b, 0x3d, 0xaf, 0xbd, 0x92, 0xef, 0xd5, 0x2f, 0x9f, 0x99, 0x81, 0xb4, 0x31, 0x6a, 0x41, 0x72, 0xf4, 0x26, 0xd4, 0xa9, 0x5e, 0x18, 0x54, 0x17, 0x1b, 0x4a, 0xde, 0xba, 0x75, 0x54, 0x1b, 0xbf, 0x4f, 0x5b, 0xcc, 0xb6, 0xa6, 0x77, 0xdf, 0xf7, 0x90, 0xda, 0x24, 0xb8, 0xeb, 0x17, 0xc0, 0xa2, 0x5e, 0xfa, 0xb0, 0xf2, 0x60, 0xb9, 0x82, 0xe, 0xc3, 0xe3, 0xf2, 0xa4, 0x5a, 0x6d, 0x2e, 0xe8, 0x7b, 0x4, 0xb3, 0x6e, 0xf9, 0x37, 0xbf, 0x2e, 0xf3, 0xc7, 0x5e, 0x70, 0x50, 0x91, 0xe8, 0x2a, 0xc0, 0x15, 0x7d, 0xb7, 0x67, 0x8a, 0xfb, 0xa7, 0xa0, 0x6a, 0xae, 0xa4, 0x76, 0xbb, 0xb9, 0xf6, 0xdd, 0x1f, 0xc1, 0x51, 0xb0, 0xd8, 0x64, 0xa4, 0xd9, 0x7a, 0x8, 0xdb, 0x3d, 0xef, 0x5e, 0xb3, 0x30, 0xbb, 0xb3, 0x24, 0x50, 0x64, 0x2c, 0xd7, 0x74, 0xd8, 0x72, 0xb0, 0xb4, 0xc1, 0x85, 0xbc, 0x4a, 0xd2, 0xf1, 0xcf, 0xa3, 0xda, 0x76, 0xe1, 0xbe, 0xb3, 0x15, 0x28, 0x20, 0x85, 0xb6, 0xbf, 0x5d, 0x98, 0x26, 0x1a, 0x11, 0xb, 0x21, 0x95, 0xc7, 0xfb, 0x5d, 0x62, 0x66, 0x87, 0x5b, 0x91, 0x2d, 0xf6, 0xce, 0x0, 0xb7, 0x4a, 0xd3, 0x2f, 0x41, 0x3b, 0xcb, 0xb8, 0x6c, 0x95, 0xd1, 0x35, 0xbd, 0x30, 0xf0, 0x82, 0x37, 0x66, 0x94, 0x1, 0x22, 0xb7, 0xfd, 0xb2, 0xe3, 0x13, 0x33, 0x3a, 0x65, 0xca, 0xfe, 0xb8, 0x28, 0xdb, 0xfc, 0x28, 0x73, 0x67, 0xf1, 0x81, 0x55, 0xec, 0xe6, 0xc5, 0x9f, 0xa8, 0xf3, 0xcf, 0xd7, 0x14, 0xb9, 0xe0, 0x8, 0xdc, 0x64, 0x3, 0xac, 0xac, 0x6b, 0x30, 0x70, 0xe7, 0x64, 0x9b, 0x7d, 0x9e, 0xef, 0x6e, 0xf8, 0x9, 0x79, 0xf4, 0xea, 0x1c, 0x2f, 0xe3, 0xb7, 0xe9, 0xa3, 0x27, 0x61, 0xdd, 0xd3, 0x9, 0xfa, 0xa7, 0x7f, 0x44, 0x76, 0x52, 0xa9, 0x5, 0xb8, 0xd1, 0x32, 0xbd, 0xb1, 0xf8, 0x26, 0x81, 0xa9, 0x7b, 0x78, 0xf3, 0xf6, 0xe9, 0x42, 0x32, 0xe2, 0xb3, 0xc3, 0x4a, 0xcf, 0x3b, 0xc9, 0x37, 0xcd, 0xf3, 0xbe, 0xce, 0xbd, 0x64, 0xe9, 0xaa, 0xc1, 0xbd, 0x21, 0xca, 0x21, 0x9a, 0x7a, 0x88, 0x53, 0x58, 0xe8, 0xd0, 0x9, 0xd3, 0x3, 0xab, 0x86, 0x19, 0x21, 0x3a, 0xfd, 0x78, 0xb2, 0x88, 0xcf, 0x22, 0x13, 0x16, 0x66, 0xe6, 0x32, 0x79, 0xa4, 0xf, 0xed, 0x80, 0xd4, 0xf6, 0x51, 0x59, 0xab, 0xde, 0x9, 0x6, 0x1e, 0x85, 0x28, 0x13, 0x85, 0xe, 0x88, 0x8, 0x90, 0xaf, 0xa7, 0x6b, 0x9d, 0xd3, 0xa9, 0x3d, 0xa2, 0xf2, 0xf3, 0xf3, 0xda, 0xad, 0x5e, 0xd5, 0x15, 0xbe, 0x7e, 0x75, 0xc8, 0x1a, 0xee, 0xca, 0x4, 0xd5, 0xec, 0x0, 0x54, 0x6c, 0xa8, 0xbe, 0xa1, 0xbb, 0x41, 0x20, 0x85, 0x9c, 0x90, 0xbb, 0x55, 0x62, 0x6e, 0x13, 0xa1, 0x9a, 0x91, 0x6e, 0x22, 0x1e, 0x48, 0x58, 0x6a, 0x84, 0x88, 0xd, 0x63, 0x3d, 0x71, 0x73, 0xb5, 0x82, 0x18, 0xda, 0xd0, 0x4a, 0x45, 0x6e, 0x31, 0x6f, 0xa7, 0xbf, 0x9f, 0x18, 0x50, 0xda, 0x19, 0x6e, 0x5c, 0x20, 0x54, 0x66, 0xdf, 0x86, 0x55, 0x21, 0xcb, 0x89, 0x48, 0x74, 0x82, 0x6d, 0x8d, 0xf4, 0xef, 0x76, 0x96, 0x4d, 0x41, 0x8a, 0xdb, 0xd, 0x37, 0xe3, 0x75, 0x5a, 0xf4, 0xc3, 0x68, 0xd8, 0x61, 0x7c, 0xc1, 0xce, 0x67, 0xa6, 0x34, 0xf7, 0x57, 0x41, 0x77, 0x52, 0x74, 0x1a, 0xf1, 0x4, 0xed, 0x5f, 0x9, 0x49, 0x72, 0x33, 0x6c, 0x8a, 0x19, 0xb3, 0xa0, 0x5a, 0x9e, 0x7a, 0xfb, 0x61, 0x2, 0xe9, 0xeb, 0x3a, 0x52, 0xda, 0xc2, 0x4a, 0xee, 0xde, 0x10, 0xe4, 0x66, 0xbb, 0x50, 0x8a, 0xa4, 0x78, 0x6b, 0xd1, 0xb4, 0x1a, 0x75, 0x53, 0x7e, 0xda, 0x65, 0x38, 0xc6, 0x37, 0xb2, 0xfd, 0xaf, 0xb2, 0xae, 0x5c, 0xf6, 0x32, 0xd3, 0x1e, 0xb7, 0xe1, 0x7, 0x5f, 0x57, 0x9b, 0xb3, 0x4, 0xf3, 0x5f, 0xad, 0x1, 0xb7, 0x6a, 0xe, 0x4f, 0x64, 0x1a, 0x4c, 0xfd, 0x7c, 0xa, 0x4a, 0xb2, 0xb9, 0xa2, 0xb8, 0xea, 0x18}
...

Bucket reclamation bug

The bucket page doesn't not seem to be getting reclaimed properly on the Scuttlebutt project which causes the DB to grow. Need to investigate further and add better consistency tests using tx.Page().

cmd/bolt-bench

Add a command line benchmarking program that can be used to test multiple Bolt use cases (small inserts, large inserts, bulk insert, random reads, sequential reads, etc).

Improve DB.Delete() performance

Deleting items from a bucket is really slow. Need to investigate why.

Add memory checks to test suite

Not sure how to do this yet but I need to be able to verify that there are no memory leaks in the test suite.

C Cursor

Implement a cursor in CGO in a separate github.com/boltdb/bolt/c package. This cursor will only be available on read-only Transaction objects.

Basic Go usage:

import "github.com/boltdb/bolt/c"

func fn(db *bolt.DB) {
    txn := db.Transaction()
    defer txn.Close()
    c := c.New(txn.Bucket("widgets"))
    // Do something with cursor.
}

Raw C API:

typedef struct bolt_val {
    uint32_t size;
    void     *data;
} bolt_val;

void bolt_cursor_init(bolt_cursor*, void *data, size_t pgsz, pgid root)

int bolt_cursor_first(bolt_cursor*, bolt_val *key, bolt_val *value)
int bolt_cursor_next(bolt_cursor*, bolt_val *key, bolt_val *value)
int bolt_cursor_seek(bolt_cursor*, bolt_val key, bolt_val *actual_key, bolt_val *value)

Copy/CopyFile does not guarantee consistent meta page

There's nothing synchronizing commit completion and Copy start. It currently relies on a1) os.File.Read not returning short reads and a2) io.Copy buffer being >= meta page size and a3) io.Copy buffer size not ending in middle of second meta page and AND b) the passed in writer not implementing io.ReaderFrom with a small buffer.

LMDB seems to do this by temporarily holding some extra lock, but I'm not quite familiar enough with the codebase to see what's going on.

Perhaps DB.Copy should just ask the tx.meta to serialize itself? Synthetize the content for the meta pages, copy the rest.

Also, to minimize error sources, it probably doesn't need to open a new fd for the read.. though I guess that gives you an independent read offset. This code achieves the same effect:

// Make an io.Reader out of an io.ReaderAt
func NewCursorReader(rat io.ReaderAt) io.Reader {
        // vastly overestimates the limit, but that shouldn't hurt it;
        // .Read() will just pass on the underlying ReaderAt's EOF.
        return io.NewSectionReader(rat, 0, math.MaxInt64)
}

Transactional Blocks

Overview

Add an easy way to execute a writer transaction that automatically closes.

func (db *DB) Do(func(t *RWTransaction) error) error

Returning a nil error will commit the transaction but returning a non-nil error will rollback the transaction.

Example

db.Do(func(t *RWTransaction) error {
    t.Put("widgets", []byte("foo"), []byte("bar"))
    t.Put("widgets", []byte("baz"), []byte("bat"))
    return nil
})

Tx.Commit on a non-writable transaction

Reading the code, this caught my eye:

https://github.com/boltdb/bolt/blob/master/tx.go#L160-L162

func (t *Tx) Commit() error {
    if t.db == nil {
        return nil
    } else if !t.writable {
        t.Rollback()
        return nil

so if I accidentally use a read-only transaction instead of a writable one, Commit silently drops the changes I made in good faith, and reports success.

That seems like a trap.

I feel like DB.Tx().Commit() should return an error, "not a writable transaction" or something, and code should use Rollback when it means to throw things away.

wishlist: Reverse iteration

I have a use case where I want to find the largest key. On leveldb, I seek to max and step backward once. With bolt.. I think I either have to store my keys as MAX-id (which happens to work for my numeric keys), or.. maybe do a binary search..

Is there a philosophical reason for not doing backwards iteration, or is it just tedious to write?

No rush, I can kludge my use case for now.

Cursor.Get docstring copy-paste error

"Get moves the cursor to a given key and returns its value. If the key does not exist then the cursor is left at the closest key and a nil key is returned."

should say "nil value is returned".

Perhaps Cursor.First and Cursor.Next could guarantee they'll return nil values also, so a for loop that wants to start at a specific key only needs to check value? This already seems true.

That is:
Cursor.First: "First moves the cursor to the first item in the bucket and returns its key and value. If the bucket is empty then a nil key is returned." -> "then a nil key and value are returned"
Cursor.Next: "If the cursor is at the end of the bucket then a nil key returned." -> "nil key and value are returned" (also missing "is" currently)

Bucket Reclamation

All pages used by a bucket need to be moved to the freelist after the bucket is deleted.

• Build a list of page ids used by the bucket by recursively traversing the tree.
• Add pages to freelist.

TestTransactionBuckets quickcheck failure

Just stumbled on this, running 64fcace:

$ go test ./...

seed: 92275
quick settings: count=5, items=1000, ksize=1024, vsize=1024
.....
00010000000000000000000000000000
--- FAIL: TestTransactionBuckets (0.00 seconds)
Location: transaction_test.go:24
Error: Not equal: "foo" != "bar"

    Location:       transaction_test.go:25
Error:      Not equal: "bar" != "baz"

    Location:       transaction_test.go:26
Error:      Not equal: "baz" != "foo"

.....
.....
FAIL
FAIL github.com/boltdb/bolt 1.924s

Add Windows support

Hello,
Thanks for a great project, I'm really happy that I encountered it lately.
Do you have plans to add Windows to the list of supported OSes? Correct me if I'm wrong, currently the only sticking point to port bolt is a bit tricky memory-mapping mechanism in Windows not given out of the box (standard Go syscall library). Well, if that's the case, a proper implementation of _syscall interface for Windows might not be a problem. Here you'll find a working package for handy dealing with memory-mapped files in a portable way.

Best regards,
Pavel

Getting Started

Add better documentation to the README for getting up and running with Bolt.

Remove Ease-of-Use Functions

Currently the DB type adds some ease of use functions for performing single actions within a transaction. e.g. DB.Put() opens a write transaction, sets the value for a key, and then commits.

After using Bolt in two projects I find that I don't use these ease of use functions at all and that they're kind of an anti-pattern. They're only useful for the most trivial of use cases.

Typically when I use Bolt in a project, I implement a logical layer on top of Bolt. For example, if I wrote a User management tool then I'd implement a DB and Tx in that project that wraps Bolt:

package usermgmt

import (
    "github.com/boltdb/bolt"
)

type DB struct {
    bolt.DB
}

// Open opens and initializes the database.
func (db *DB) Open(path string, mode os.FileMode) error {
    if err := db.DB.Open(path, mode); err != nil {
        return err
    }

    // Initialize all the required buckets.
    return db.Do(func(tx *Tx) error {
        tx.CreateBucketIfNotExists("users")
        // ... initialize more buckets as needed ...
        return nil
    })
}

func (db *DB) With(fn func(*Tx) error) error {
    return db.DB.With(func(tx *bolt.Tx) error {
        return fn(&Tx{tx})
    })
}

func (db *DB) Do(fn func(*Tx) error) error {
    return db.DB.Do(func(tx *bolt.Tx) error {
        return fn(&Tx{tx})
    })
}

type Tx struct {
    *bolt.Tx
}

// User retrieves a user by id from the database.
func (tx *Tx) User(id string) (*User, error) {
    u := &User{}
    if v := tx.Bucket("users").Get([]byte(id)); v == nil {
        return nil, nil
    } else if err := json.Unmarshal(v, &u); err != nil {
        return nil, err
    }
    return u, nil
}

Or I might attach the model objects to the transaction itself:

type User struct {
    tx *Tx
    ID string `json:"id"`
    Username string `json:"username"`
}

func (u *User) Save() error {
    b, err := json.Marshal(u)
    if err != nil {
        return err
    }
    return u.tx.Bucket("users").Put([]byte(u.ID), b)
}

The typical write transaction use case is to retrieve a value, do something with it, and then reinsert an updated value. e.g. updating a User's username requires retrieving the existing user first, updating its Username value, and then reinserting the entire object.

Trying to do all these actions outside a single transaction means race conditions can occur and you can lose data.

/cc @tv42: What do you think?

Examples

Add examples to the godoc.

• Opening and closing a database.
• Creating a bucket.
• Deleting a bucket.
• Setting a value and retrieving it.
• Setting a value and deleting it.
• Setting multiple values and iterating over them.
• Copying the database via writer.
• Copying the database to a new path.

Combine Tx() & RWTx()

The transaction API is currently:

func (db *DB) Tx() (*Tx, error)
func (db *DB) RWTx() (*Tx, error)

That made sense when there were separate transaction types (Transaction & RWTransaction) but now there's just one.

The new API would look like:

func (db *DB) Tx(writable bool) (*Tx, error)

This lines up better with the types and the underlying Tx.Writable() function.

/cc @tv42

Benchmarking / Profiling

Add benchmarks and setup pprof to figure out where to improve performance. Bolt is currently unoptimized so it needs some work.

Freelist

Maintain a list of free pages that are no longer used by any transactions.

• Maintain list of old pages by transaction id.
• Maintain list of current transactions.
• Reclaim free pages after oldest transaction closes.
• Save latest freelist to a p_freelist page.

Rename Transaction to Tx

For consistency with database/sql, I'm going to rename the transaction classes:

Transaction -> Tx
RWTransaction -> RWTx

/cc @tv42 @cespare

Improve file system testing

Bolt previously used the mock package of the Testify library to mock out the OS and Syscalls but it caused other issues so it was removed. I'd like to investigate using a FUSE mount to mock out file system failures.

@tv42 Is it possible to simulate file system failures using bazil.org/fuse?