iterate returns duplicate keys

[xiang90]

I expect iterating a bucket with cursor return keys in order, but it would return duplicated keys.

Here is the data

And here is the script to reproduce the problem

Here is the output:

key="\x00\x00\x00\x00\x00\x00\xfe\x9d_\x00\x00\x00\x00\x00\x00\x00\x00"
key="\x00\x00\x00\x00\x00\x00\xfe\x9c_\x00\x00\x00\x00\x00\x00\x00\x00"
key="\x00\x00\x00\x00\x00\x00\xfe\x9b_\x00\x00\x00\x00\x00\x00\x00\x00"
key="\x00\x00\x00\x00\x00\x00\xfe\x9a_\x00\x00\x00\x00\x00\x00\x00\x00"
duplicated key="\x00\x00\x00\x00\x00\x00\xfe\x9c_\x00\x00\x00\x00\x00\x00\x00\x00"!!!!
duplicated key="\x00\x00\x00\x00\x00\x00\xfe\x9b_\x00\x00\x00\x00\x00\x00\x00\x00"!!!!
duplicated key="\x00\x00\x00\x00\x00\x00\xfe\x9a_\x00\x00\x00\x00\x00\x00\x00\x00"!!!!

Am I missing something?

The key \x00\x00\x00\x00\x00\x00\xfe\x9c_\x00\x00\x00\x00\x00\x00\x00\x00 shows up twice during cursor iterating.

[xiang90]

I looked into it more. I think actually the db itself is corrupted during page split? (or we failed to reload the nodes correctly)

There are 3 duplicated keys in two adjacent pages:

load index 2 from page 1799
"\x00\x00\x00\x00\x00\x00\xfe\x9c_\x00\x00\x00\x00\x00\x00\x00\x00"
load index 1 from page 1799
"\x00\x00\x00\x00\x00\x00\xfe\x9b_\x00\x00\x00\x00\x00\x00\x00\x00"
load index 0 from page 1799
"\x00\x00\x00\x00\x00\x00\xfe\x9a_\x00\x00\x00\x00\x00\x00\x00\x00"
load index 32 from page 1798
"\x00\x00\x00\x00\x00\x00\xfe\x9c_\x00\x00\x00\x00\x00\x00\x00\x00"
load index 31 from page 1798
"\x00\x00\x00\x00\x00\x00\xfe\x9b_\x00\x00\x00\x00\x00\x00\x00\x00"
load index 30 from page 1798
"\x00\x00\x00\x00\x00\x00\xfe\x9a_\x00\x00\x00\x00\x00\x00\x00\x00"
load index 29 from page 1798

[benbjohnson]

@xiang90 Are you retaining and altering the []byte that you pass as a key or value to Bucket.Put()?

[xiang90]

@benbjohnson No. Each key is put only once without any buffering, so no future access. But I will double check.

[xiang90]

@benbjohnson I suspect the split code is the cause

	// Split inodes across two nodes.
	next.inodes = n.inodes[splitIndex:]
	n.inodes = n.inodes[:splitIndex]

We do not copy the backing array. So if we append one element to n.inodes, it will overwrite the first element of next.inodes.

See my example here:

https://play.golang.org/p/xjI9r6rpow

But this is just my guess by reading limited boltdb code. I am not sure.

[xiang90]

On the second thought, it might not be the exact cause.

We put keys sequentially. We do not miss any keys, but there are 3 duplicates in between. Basically it looks like:

<------- |dup|------->
1 2 3 4 5 3 4 5 6 7 8 9

[benbjohnson]

@xiang90 Do you have an example program that writes the data?

[xiang90]

@benbjohnson

package playground

import (
	"sync"

	"github.com/boltdb/bolt"
)

type store struct {
	sync.Mutex
	revision int
	tx       *bolt.Tx
	db       *bolt.DB
}

func (s *store) put(value []byte) {
	s.Lock()
	defer s.Unlock()

	bucket := tx.Bucket("keys")
	if bucket == nil {
		panic("bucket key does not exist")
	}

	// it is useful to increase fill percent when the workload is seq append.
	// this can delay the page split and reduce space usage.
	bucket.FillPercent = 0.9

	if err := bucket.Put(intToBytes(s.revision), value); err != nil {
		panic(err)
	}
	s.revision++
}

func (s *store) get(rev int) []byte {
	s.Lock()
	defer s.Unlock()

	bucket := tx.Bucket("keys")
	if bucket == nil {
		panic("bucket key does not exist")
	}

	b := bucket.Get(intToBytes(rev))
	nb := make([]byte, len(b))
	copy(nb, b)
	return nb
}

// called every 100ms, every 10000 puts
func (s *store) commit() {
	s.Lock()
	defer s.Unlock()

	if err := s.tx.Commit(); err != nil {
		panic(err)
	}

	var err error
	s.tx, err = s.db.Begin(true)
	if err != nil {
		panic(err)
	}
}

It looks pretty much like this.

[xiang90]

The put bytes are generated by marshaling a protobuf request, so it will never be accessed again.

The get part is not exactly accurate. we actually unmarshal the data into a protobuf response holding the lock. Protobuf unmarshalling should copy the data.

[jsvisa]

@xiang90 we occured the same issue, how could you fixed it?