mirror of
https://github.com/luxfi/zapdb.git
synced 2026-10-30 15:12:20 +00:00
Ibrahim Jarif
8200905188
This commit introduces fast merge iterator which uses a tree-based
structure instead of a heap to maintain all the iterators. This
implementation is about 2X faster than the heap implementation.
master-x.txt and new-x.txt are the result of `ReadMerged`
benchmarks with x tables. Each table contains 10e6 entries.
```
benchstat master-5.txt new-5.txt
name old time/op new time/op delta
ReadMerged-16 826ms ± 1% 470ms ± 2% -43.14% (p=0.008 n=5+5)
benchstat master-16.txt new-16.txt
name old time/op new time/op delta
ReadMerged-16 4.22s ± 1% 2.08s ± 2% -50.72% (p=0.008 n=5+5)
benchstat master-32.txt new-32.txt
name old time/op new time/op delta
ReadMerged-16 10.6s ± 3% 4.8s ± 2% -54.58% (p=0.008 n=5+5)
benchstat master-64.txt new-64.txt
name old time/op new time/op delta
ReadMerged-16 25.1s ± 1% 11.0s ± 2% -55.94% (p=0.008 n=5+5)
benchstat master-128.txt new-128.txt
name old time/op new time/op delta
ReadMerged-16 58.5s ± 1% 25.8s ± 2% -55.95% (p=0.016 n=4+5)
```
Inspired by
https://github.com/coocood/badger/commit/d04b5eb3dcee6113188e82a0c8b11228c63fb4cb
(cherry picked from commit 4e104da867)
98 lines
2.4 KiB
Go
98 lines
2.4 KiB
Go
/*
|
|
* Copyright 2017 Dgraph Labs, Inc. and Contributors
|
|
*
|
|
* 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,
|
|
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
|
* See the License for the specific language governing permissions and
|
|
* limitations under the License.
|
|
*/
|
|
|
|
package y
|
|
|
|
import (
|
|
"bytes"
|
|
"encoding/binary"
|
|
)
|
|
|
|
// ValueStruct represents the value info that can be associated with a key, but also the internal
|
|
// Meta field.
|
|
type ValueStruct struct {
|
|
Meta byte
|
|
UserMeta byte
|
|
ExpiresAt uint64
|
|
Value []byte
|
|
|
|
Version uint64 // This field is not serialized. Only for internal usage.
|
|
}
|
|
|
|
func sizeVarint(x uint64) (n int) {
|
|
for {
|
|
n++
|
|
x >>= 7
|
|
if x == 0 {
|
|
break
|
|
}
|
|
}
|
|
return n
|
|
}
|
|
|
|
// EncodedSize is the size of the ValueStruct when encoded
|
|
func (v *ValueStruct) EncodedSize() uint16 {
|
|
sz := len(v.Value) + 2 // meta, usermeta.
|
|
if v.ExpiresAt == 0 {
|
|
return uint16(sz + 1)
|
|
}
|
|
|
|
enc := sizeVarint(v.ExpiresAt)
|
|
return uint16(sz + enc)
|
|
}
|
|
|
|
// Decode uses the length of the slice to infer the length of the Value field.
|
|
func (v *ValueStruct) Decode(b []byte) {
|
|
v.Meta = b[0]
|
|
v.UserMeta = b[1]
|
|
var sz int
|
|
v.ExpiresAt, sz = binary.Uvarint(b[2:])
|
|
v.Value = b[2+sz:]
|
|
}
|
|
|
|
// Encode expects a slice of length at least v.EncodedSize().
|
|
func (v *ValueStruct) Encode(b []byte) {
|
|
b[0] = v.Meta
|
|
b[1] = v.UserMeta
|
|
sz := binary.PutUvarint(b[2:], v.ExpiresAt)
|
|
copy(b[2+sz:], v.Value)
|
|
}
|
|
|
|
// EncodeTo should be kept in sync with the Encode function above. The reason
|
|
// this function exists is to avoid creating byte arrays per key-value pair in
|
|
// table/builder.go.
|
|
func (v *ValueStruct) EncodeTo(buf *bytes.Buffer) {
|
|
buf.WriteByte(v.Meta)
|
|
buf.WriteByte(v.UserMeta)
|
|
var enc [binary.MaxVarintLen64]byte
|
|
sz := binary.PutUvarint(enc[:], v.ExpiresAt)
|
|
buf.Write(enc[:sz])
|
|
buf.Write(v.Value)
|
|
}
|
|
|
|
// Iterator is an interface for a basic iterator.
|
|
type Iterator interface {
|
|
Next()
|
|
Rewind()
|
|
Seek(key []byte)
|
|
Key() []byte
|
|
Value() ValueStruct
|
|
Valid() bool
|
|
|
|
// All iterators should be closed so that file garbage collection works.
|
|
Close() error
|
|
}
|