You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
575 lines
13 KiB
575 lines
13 KiB
// Copyright 2019 PingCAP, Inc.
|
|
//
|
|
// Licensed under the Apache License, Version 2.0 (the "License");
|
|
// you may not use this file except in compliance with the License.
|
|
// You may obtain a copy of the License at
|
|
//
|
|
// http://www.apache.org/licenses/LICENSE-2.0
|
|
//
|
|
// Unless required by applicable law or agreed to in writing, software
|
|
// distributed under the License is distributed on an "AS IS" BASIS,
|
|
// See the License for the specific language governing permissions and
|
|
// limitations under the License.
|
|
|
|
package memdb
|
|
|
|
import (
|
|
"encoding/binary"
|
|
"math/rand"
|
|
"testing"
|
|
|
|
. "github.com/pingcap/check"
|
|
"github.com/pingcap/goleveldb/leveldb/comparer"
|
|
"github.com/pingcap/goleveldb/leveldb/memdb"
|
|
)
|
|
|
|
const (
|
|
keySize = 16
|
|
valueSize = 128
|
|
)
|
|
|
|
func TestT(t *testing.T) {
|
|
TestingT(t)
|
|
}
|
|
|
|
type testMemDBSuite struct{}
|
|
|
|
var _ = Suite(testMemDBSuite{})
|
|
|
|
func (s testMemDBSuite) TestGetSet(c *C) {
|
|
const cnt = 10000
|
|
p := s.fillDB(cnt)
|
|
|
|
var buf [4]byte
|
|
for i := 0; i < cnt; i++ {
|
|
binary.BigEndian.PutUint32(buf[:], uint32(i))
|
|
v := p.Get(buf[:])
|
|
c.Check(v, BytesEquals, buf[:])
|
|
}
|
|
}
|
|
|
|
func (s testMemDBSuite) TestIterator(c *C) {
|
|
const cnt = 10000
|
|
p := s.fillDB(cnt)
|
|
|
|
var buf [4]byte
|
|
var i int
|
|
it := p.NewIterator()
|
|
|
|
for it.SeekToFirst(); it.Valid(); it.Next() {
|
|
binary.BigEndian.PutUint32(buf[:], uint32(i))
|
|
c.Check(it.Key(), BytesEquals, buf[:])
|
|
c.Check(it.Value(), BytesEquals, buf[:])
|
|
i++
|
|
}
|
|
c.Check(i, Equals, cnt)
|
|
|
|
i--
|
|
for it.SeekToLast(); it.Valid(); it.Prev() {
|
|
binary.BigEndian.PutUint32(buf[:], uint32(i))
|
|
c.Check(it.Key(), BytesEquals, buf[:])
|
|
c.Check(it.Value(), BytesEquals, buf[:])
|
|
i--
|
|
}
|
|
c.Check(i, Equals, -1)
|
|
}
|
|
|
|
func (s testMemDBSuite) TestDiscard(c *C) {
|
|
const cnt = 10000
|
|
p := NewSandbox()
|
|
s.deriveAndFill(0, cnt, 0, p).Flush()
|
|
sz := p.Size()
|
|
|
|
s.deriveAndFill(0, cnt, 1, p).Discard()
|
|
c.Check(p.Len(), Equals, cnt)
|
|
c.Check(p.Size(), Equals, sz)
|
|
|
|
var buf [4]byte
|
|
|
|
for i := 0; i < cnt; i++ {
|
|
binary.BigEndian.PutUint32(buf[:], uint32(i))
|
|
v := p.Get(buf[:])
|
|
c.Check(v, BytesEquals, buf[:])
|
|
}
|
|
|
|
var i int
|
|
it := p.NewIterator()
|
|
for it.SeekToFirst(); it.Valid(); it.Next() {
|
|
binary.BigEndian.PutUint32(buf[:], uint32(i))
|
|
c.Check(it.Key(), BytesEquals, buf[:])
|
|
c.Check(it.Value(), BytesEquals, buf[:])
|
|
i++
|
|
}
|
|
c.Check(i, Equals, cnt)
|
|
|
|
i--
|
|
for it.SeekToLast(); it.Valid(); it.Prev() {
|
|
binary.BigEndian.PutUint32(buf[:], uint32(i))
|
|
c.Check(it.Key(), BytesEquals, buf[:])
|
|
c.Check(it.Value(), BytesEquals, buf[:])
|
|
i--
|
|
}
|
|
c.Check(i, Equals, -1)
|
|
}
|
|
|
|
func (s testMemDBSuite) TestFlushOverwrite(c *C) {
|
|
const cnt = 10000
|
|
p := NewSandbox()
|
|
s.deriveAndFill(0, cnt, 0, p).Flush()
|
|
sz := p.Size()
|
|
|
|
s.deriveAndFill(0, cnt, 1, p).Flush()
|
|
|
|
c.Check(p.Len(), Equals, cnt)
|
|
c.Check(p.Size(), Equals, sz)
|
|
|
|
var kbuf, vbuf [4]byte
|
|
|
|
for i := 0; i < cnt; i++ {
|
|
binary.BigEndian.PutUint32(kbuf[:], uint32(i))
|
|
binary.BigEndian.PutUint32(vbuf[:], uint32(i+1))
|
|
v := p.Get(kbuf[:])
|
|
c.Check(v, BytesEquals, vbuf[:])
|
|
}
|
|
|
|
var i int
|
|
it := p.NewIterator()
|
|
for it.SeekToFirst(); it.Valid(); it.Next() {
|
|
binary.BigEndian.PutUint32(kbuf[:], uint32(i))
|
|
binary.BigEndian.PutUint32(vbuf[:], uint32(i+1))
|
|
c.Check(it.Key(), BytesEquals, kbuf[:])
|
|
c.Check(it.Value(), BytesEquals, vbuf[:])
|
|
i++
|
|
}
|
|
c.Check(i, Equals, cnt)
|
|
|
|
i--
|
|
for it.SeekToLast(); it.Valid(); it.Prev() {
|
|
binary.BigEndian.PutUint32(kbuf[:], uint32(i))
|
|
binary.BigEndian.PutUint32(vbuf[:], uint32(i+1))
|
|
c.Check(it.Key(), BytesEquals, kbuf[:])
|
|
c.Check(it.Value(), BytesEquals, vbuf[:])
|
|
i--
|
|
}
|
|
c.Check(i, Equals, -1)
|
|
}
|
|
|
|
func (s testMemDBSuite) TestComplexUpdate(c *C) {
|
|
const (
|
|
keep = 3000
|
|
overwrite = 6000
|
|
insert = 9000
|
|
)
|
|
|
|
p := NewSandbox()
|
|
s.deriveAndFill(0, overwrite, 0, p).Flush()
|
|
c.Check(p.Len(), Equals, overwrite)
|
|
s.deriveAndFill(keep, insert, 1, p).Flush()
|
|
c.Check(p.Len(), Equals, insert)
|
|
|
|
var kbuf, vbuf [4]byte
|
|
|
|
for i := 0; i < insert; i++ {
|
|
binary.BigEndian.PutUint32(kbuf[:], uint32(i))
|
|
binary.BigEndian.PutUint32(vbuf[:], uint32(i))
|
|
if i >= keep {
|
|
binary.BigEndian.PutUint32(vbuf[:], uint32(i+1))
|
|
}
|
|
v := p.Get(kbuf[:])
|
|
c.Check(v, BytesEquals, vbuf[:])
|
|
}
|
|
}
|
|
|
|
func (s testMemDBSuite) TestNestedSandbox(c *C) {
|
|
p := NewSandbox()
|
|
sb0 := s.deriveAndFill(0, 200, 0, p)
|
|
sb1 := s.deriveAndFill(0, 100, 1, sb0)
|
|
sb2 := s.deriveAndFill(50, 150, 2, sb1)
|
|
sb3 := s.deriveAndFill(100, 120, 3, sb2)
|
|
sb4 := s.deriveAndFill(0, 150, 4, sb3)
|
|
sb4.Discard() // Discard (0..150 -> 4)
|
|
sb3.Flush() // Flush (100..120 -> 3)
|
|
sb2.Discard() // Discard (100..120 -> 3) & (50..150 -> 2)
|
|
sb1.Flush() // Flush (0..100 -> 1)
|
|
sb0.Flush() // Flush (0..100 -> 1) & (0..200 -> 0)
|
|
// The final result should be (0..100 -> 1) & (101..200 -> 0)
|
|
|
|
var kbuf, vbuf [4]byte
|
|
|
|
for i := 0; i < 200; i++ {
|
|
binary.BigEndian.PutUint32(kbuf[:], uint32(i))
|
|
binary.BigEndian.PutUint32(vbuf[:], uint32(i))
|
|
if i < 100 {
|
|
binary.BigEndian.PutUint32(vbuf[:], uint32(i+1))
|
|
}
|
|
v := p.Get(kbuf[:])
|
|
c.Check(v, BytesEquals, vbuf[:])
|
|
}
|
|
|
|
var i int
|
|
it := p.NewIterator()
|
|
for it.SeekToFirst(); it.Valid(); it.Next() {
|
|
binary.BigEndian.PutUint32(kbuf[:], uint32(i))
|
|
binary.BigEndian.PutUint32(vbuf[:], uint32(i))
|
|
if i < 100 {
|
|
binary.BigEndian.PutUint32(vbuf[:], uint32(i+1))
|
|
}
|
|
c.Check(it.Key(), BytesEquals, kbuf[:])
|
|
c.Check(it.Value(), BytesEquals, vbuf[:])
|
|
i++
|
|
}
|
|
c.Check(i, Equals, 200)
|
|
|
|
i--
|
|
for it.SeekToLast(); it.Valid(); it.Prev() {
|
|
binary.BigEndian.PutUint32(kbuf[:], uint32(i))
|
|
binary.BigEndian.PutUint32(vbuf[:], uint32(i))
|
|
if i < 100 {
|
|
binary.BigEndian.PutUint32(vbuf[:], uint32(i+1))
|
|
}
|
|
c.Check(it.Key(), BytesEquals, kbuf[:])
|
|
c.Check(it.Value(), BytesEquals, vbuf[:])
|
|
i--
|
|
}
|
|
c.Check(i, Equals, -1)
|
|
}
|
|
|
|
func (s testMemDBSuite) TestOverwrite(c *C) {
|
|
const cnt = 10000
|
|
p := s.fillDB(cnt)
|
|
var buf [4]byte
|
|
|
|
sz := p.Size()
|
|
for i := 0; i < cnt; i += 3 {
|
|
var newBuf [4]byte
|
|
binary.BigEndian.PutUint32(buf[:], uint32(i))
|
|
binary.BigEndian.PutUint32(newBuf[:], uint32(i*10))
|
|
p.Put(buf[:], newBuf[:])
|
|
}
|
|
c.Check(p.Len(), Equals, cnt)
|
|
c.Check(p.Size(), Equals, sz)
|
|
|
|
for i := 0; i < cnt; i++ {
|
|
binary.BigEndian.PutUint32(buf[:], uint32(i))
|
|
v := binary.BigEndian.Uint32(p.Get(buf[:]))
|
|
if i%3 == 0 {
|
|
c.Check(v, Equals, uint32(i*10))
|
|
} else {
|
|
c.Check(v, Equals, uint32(i))
|
|
}
|
|
}
|
|
|
|
it := p.NewIterator()
|
|
var i int
|
|
|
|
for it.SeekToFirst(); it.Valid(); it.Next() {
|
|
binary.BigEndian.PutUint32(buf[:], uint32(i))
|
|
c.Check(it.Key(), BytesEquals, buf[:])
|
|
v := binary.BigEndian.Uint32(it.Value())
|
|
if i%3 == 0 {
|
|
c.Check(v, Equals, uint32(i*10))
|
|
} else {
|
|
c.Check(v, Equals, uint32(i))
|
|
}
|
|
i++
|
|
}
|
|
c.Check(i, Equals, cnt)
|
|
|
|
i--
|
|
for it.SeekToLast(); it.Valid(); it.Prev() {
|
|
binary.BigEndian.PutUint32(buf[:], uint32(i))
|
|
c.Check(it.Key(), BytesEquals, buf[:])
|
|
v := binary.BigEndian.Uint32(it.Value())
|
|
if i%3 == 0 {
|
|
c.Check(v, Equals, uint32(i*10))
|
|
} else {
|
|
c.Check(v, Equals, uint32(i))
|
|
}
|
|
i--
|
|
}
|
|
c.Check(i, Equals, -1)
|
|
}
|
|
|
|
func (s testMemDBSuite) TestKVLargeThanBlock(c *C) {
|
|
p := NewSandbox()
|
|
p.Put([]byte{1}, make([]byte, 1))
|
|
p.Put([]byte{2}, make([]byte, 4096))
|
|
c.Check(len(p.arena.blocks), Equals, 2)
|
|
p.Put([]byte{3}, make([]byte, 3000))
|
|
c.Check(len(p.arena.blocks), Equals, 2)
|
|
c.Check(len(p.Get([]byte{3})), Equals, 3000)
|
|
}
|
|
|
|
func (s testMemDBSuite) TestEmptyDB(c *C) {
|
|
p := NewSandbox()
|
|
c.Check(p.Get([]byte{0}), IsNil)
|
|
it := p.NewIterator()
|
|
it.SeekToFirst()
|
|
c.Check(it.Valid(), IsFalse)
|
|
it.SeekToLast()
|
|
c.Check(it.Valid(), IsFalse)
|
|
it.SeekForPrev([]byte{0})
|
|
c.Check(it.Valid(), IsFalse)
|
|
it.SeekForExclusivePrev([]byte{0})
|
|
c.Check(it.Valid(), IsFalse)
|
|
it.Seek([]byte{0xff})
|
|
c.Check(it.Valid(), IsFalse)
|
|
}
|
|
|
|
func (s testMemDBSuite) TestRandom(c *C) {
|
|
const cnt = 500000
|
|
keys := make([][]byte, cnt)
|
|
for i := range keys {
|
|
keys[i] = make([]byte, rand.Intn(19)+1)
|
|
rand.Read(keys[i])
|
|
}
|
|
|
|
p1 := NewSandbox()
|
|
p2 := memdb.New(comparer.DefaultComparer, 4*1024)
|
|
for _, k := range keys {
|
|
p1.Put(k, k)
|
|
_ = p2.Put(k, k)
|
|
}
|
|
|
|
c.Check(p1.Len(), Equals, p2.Len())
|
|
c.Check(p1.Size(), Equals, p2.Size())
|
|
|
|
rand.Shuffle(cnt, func(i, j int) { keys[i], keys[j] = keys[j], keys[i] })
|
|
|
|
for _, k := range keys {
|
|
newValue := make([]byte, rand.Intn(19)+1)
|
|
rand.Read(newValue)
|
|
p1.Put(k, newValue)
|
|
_ = p2.Put(k, newValue)
|
|
}
|
|
s.checkConsist(c, p1, p2)
|
|
}
|
|
|
|
func (s testMemDBSuite) TestRandomDerive(c *C) {
|
|
s.testRandomDeriveRecur(c, NewSandbox(), memdb.New(comparer.DefaultComparer, 4*1024), 0)
|
|
}
|
|
|
|
func (s testMemDBSuite) testRandomDeriveRecur(c *C, sb *Sandbox, db *memdb.DB, depth int) {
|
|
var keys [][]byte
|
|
if rand.Float64() < 0.5 {
|
|
start, end := rand.Intn(512), rand.Intn(512)+512
|
|
cnt := end - start
|
|
keys = make([][]byte, cnt)
|
|
for i := range keys {
|
|
keys[i] = make([]byte, 8)
|
|
binary.BigEndian.PutUint64(keys[i], uint64(start+i))
|
|
}
|
|
} else {
|
|
keys = make([][]byte, rand.Intn(512)+512)
|
|
for i := range keys {
|
|
keys[i] = make([]byte, rand.Intn(19)+1)
|
|
rand.Read(keys[i])
|
|
}
|
|
}
|
|
|
|
vals := make([][]byte, len(keys))
|
|
for i := range vals {
|
|
vals[i] = make([]byte, rand.Intn(255)+1)
|
|
rand.Read(vals[i])
|
|
}
|
|
|
|
sbBuf := sb.Derive()
|
|
dbBuf := memdb.New(comparer.DefaultComparer, 4*1024)
|
|
for i := range keys {
|
|
sbBuf.Put(keys[i], vals[i])
|
|
_ = dbBuf.Put(keys[i], vals[i])
|
|
}
|
|
|
|
if depth < 1000 {
|
|
s.testRandomDeriveRecur(c, sbBuf, dbBuf, depth+1)
|
|
}
|
|
|
|
if rand.Float64() < 0.3 && depth > 0 {
|
|
sbBuf.Discard()
|
|
} else {
|
|
sbBuf.Flush()
|
|
it := dbBuf.NewIterator(nil)
|
|
for it.First(); it.Valid(); it.Next() {
|
|
_ = db.Put(it.Key(), it.Value())
|
|
}
|
|
}
|
|
s.checkConsist(c, sb, db)
|
|
}
|
|
|
|
func (s testMemDBSuite) checkConsist(c *C, p1 *Sandbox, p2 *memdb.DB) {
|
|
c.Check(p1.Len(), Equals, p2.Len())
|
|
c.Check(p1.Size(), Equals, p2.Size())
|
|
|
|
it1 := p1.NewIterator()
|
|
it1.SeekToFirst()
|
|
|
|
it2 := p2.NewIterator(nil)
|
|
|
|
var prevKey, prevVal []byte
|
|
for it2.First(); it2.Valid(); it2.Next() {
|
|
c.Check(it1.Key(), BytesEquals, it2.Key())
|
|
c.Check(it1.Value(), BytesEquals, it2.Value())
|
|
|
|
it := p1.NewIterator()
|
|
it.Seek(it2.Key())
|
|
c.Check(it.Key(), BytesEquals, it2.Key())
|
|
c.Check(it.Value(), BytesEquals, it2.Value())
|
|
|
|
it.SeekForPrev(it2.Key())
|
|
c.Check(it.Key(), BytesEquals, it2.Key())
|
|
c.Check(it.Value(), BytesEquals, it2.Value())
|
|
|
|
if prevKey != nil {
|
|
it.SeekForExclusivePrev(it2.Key())
|
|
c.Check(it.Key(), BytesEquals, prevKey)
|
|
c.Check(it.Value(), BytesEquals, prevVal)
|
|
}
|
|
|
|
it1.Next()
|
|
prevKey = it2.Key()
|
|
prevVal = it2.Value()
|
|
}
|
|
|
|
it1.SeekToLast()
|
|
for it2.Last(); it2.Valid(); it2.Prev() {
|
|
c.Check(it1.Key(), BytesEquals, it2.Key())
|
|
c.Check(it1.Value(), BytesEquals, it2.Value())
|
|
it1.Prev()
|
|
}
|
|
}
|
|
|
|
func (s testMemDBSuite) fillDB(cnt int) *Sandbox {
|
|
p := NewSandbox()
|
|
s.deriveAndFill(0, cnt, 0, p).Flush()
|
|
return p
|
|
}
|
|
|
|
func (s testMemDBSuite) deriveAndFill(start, end, valueBase int, parent *Sandbox) *Sandbox {
|
|
sb := parent.Derive()
|
|
var kbuf, vbuf [4]byte
|
|
for i := start; i < end; i++ {
|
|
binary.BigEndian.PutUint32(kbuf[:], uint32(i))
|
|
binary.BigEndian.PutUint32(vbuf[:], uint32(i+valueBase))
|
|
sb.Put(kbuf[:], vbuf[:])
|
|
}
|
|
return sb
|
|
}
|
|
|
|
func BenchmarkLargeIndex(b *testing.B) {
|
|
buf := make([][valueSize]byte, 10000000)
|
|
for i := range buf {
|
|
binary.LittleEndian.PutUint32(buf[i][:], uint32(i))
|
|
}
|
|
p := NewSandbox()
|
|
b.ResetTimer()
|
|
|
|
for i := range buf {
|
|
p.Put(buf[i][:keySize], buf[i][:])
|
|
}
|
|
}
|
|
|
|
func BenchmarkFlush(b *testing.B) {
|
|
const size = 10000
|
|
buf := make([][valueSize]byte, size)
|
|
for i := range buf {
|
|
binary.BigEndian.PutUint32(buf[i][:], uint32(i))
|
|
}
|
|
|
|
b.Run("naive-insert", func(b *testing.B) {
|
|
for n := 0; n < b.N; n++ {
|
|
b.StopTimer()
|
|
p1 := NewSandbox()
|
|
p2 := NewSandbox()
|
|
for i := range buf[:len(buf)/2] {
|
|
p1.Put(buf[i][:keySize], buf[i][:])
|
|
}
|
|
for i := range buf[len(buf)/2:] {
|
|
p2.Put(buf[i][:keySize], buf[i][:])
|
|
}
|
|
b.StartTimer()
|
|
it := p2.NewIterator()
|
|
for it.SeekToFirst(); it.Valid(); it.Next() {
|
|
p1.Put(it.Key(), it.Value())
|
|
}
|
|
}
|
|
})
|
|
|
|
b.Run("sandbox-flush", func(b *testing.B) {
|
|
for n := 0; n < b.N; n++ {
|
|
b.StopTimer()
|
|
p1 := NewSandbox()
|
|
for i := range buf[:len(buf)/2] {
|
|
p1.Put(buf[i][:keySize], buf[i][:])
|
|
}
|
|
|
|
p2 := p1.Derive()
|
|
for i := range buf[len(buf)/2:] {
|
|
p2.Put(buf[i][:keySize], buf[i][:])
|
|
}
|
|
b.StartTimer()
|
|
p2.Flush()
|
|
}
|
|
})
|
|
}
|
|
|
|
func BenchmarkPut(b *testing.B) {
|
|
buf := make([][valueSize]byte, b.N)
|
|
for i := range buf {
|
|
binary.BigEndian.PutUint32(buf[i][:], uint32(i))
|
|
}
|
|
|
|
p := NewSandbox()
|
|
b.ResetTimer()
|
|
|
|
for i := range buf {
|
|
p.Put(buf[i][:keySize], buf[i][:])
|
|
}
|
|
}
|
|
|
|
func BenchmarkPutRandom(b *testing.B) {
|
|
buf := make([][valueSize]byte, b.N)
|
|
for i := range buf {
|
|
binary.LittleEndian.PutUint32(buf[i][:], uint32(rand.Int()))
|
|
}
|
|
|
|
p := NewSandbox()
|
|
b.ResetTimer()
|
|
|
|
for i := range buf {
|
|
p.Put(buf[i][:keySize], buf[i][:])
|
|
}
|
|
}
|
|
|
|
func BenchmarkGet(b *testing.B) {
|
|
buf := make([][valueSize]byte, b.N)
|
|
for i := range buf {
|
|
binary.BigEndian.PutUint32(buf[i][:], uint32(i))
|
|
}
|
|
|
|
p := NewSandbox()
|
|
for i := range buf {
|
|
p.Put(buf[i][:keySize], buf[i][:])
|
|
}
|
|
|
|
b.ResetTimer()
|
|
for i := range buf {
|
|
p.Get(buf[i][:keySize])
|
|
}
|
|
}
|
|
|
|
func BenchmarkGetRandom(b *testing.B) {
|
|
buf := make([][valueSize]byte, b.N)
|
|
for i := range buf {
|
|
binary.LittleEndian.PutUint32(buf[i][:], uint32(rand.Int()))
|
|
}
|
|
|
|
p := NewSandbox()
|
|
for i := range buf {
|
|
p.Put(buf[i][:keySize], buf[i][:])
|
|
}
|
|
|
|
b.ResetTimer()
|
|
for i := 0; i < b.N; i++ {
|
|
p.Get(buf[i][:keySize])
|
|
}
|
|
}
|
|
|