README
¶
batchskl
Fast, non-concurrent skiplist implementation in Go that supports forward and backward iteration.
Limitations
- The interface is tailored for use in indexing pebble batches. Keys and values are stored outside of the skiplist making the skiplist awkward for general purpose use.
- Deletion is not supported. Instead, higher-level code is expected to add deletion tombstones and needs to process those tombstones appropriately.
Pedigree
This code is based on Andy Kimball's arenaskl code.
The arenaskl code is based on the skiplist found in Badger, a Go-based KV store:
https://github.com/dgraph-io/badger/tree/master/skl
The skiplist in Badger is itself based on a C++ skiplist built for Facebook's RocksDB:
https://github.com/facebook/rocksdb/tree/master/memtable
Benchmarks
The benchmarks consist of a mix of reads and writes executed in parallel. The fraction of reads is indicated in the run name: "frac_X" indicates a run where X percent of the operations are reads.
name time/op
ReadWrite/frac_0 1.03µs ± 2%
ReadWrite/frac_10 1.32µs ± 1%
ReadWrite/frac_20 1.26µs ± 1%
ReadWrite/frac_30 1.18µs ± 1%
ReadWrite/frac_40 1.09µs ± 1%
ReadWrite/frac_50 987ns ± 2%
ReadWrite/frac_60 1.07µs ± 1%
ReadWrite/frac_70 909ns ± 1%
ReadWrite/frac_80 693ns ± 2%
ReadWrite/frac_90 599ns ± 2%
ReadWrite/frac_100 45.3ns ± 3%
Forward and backward iteration are also fast:
name time/op
IterNext 4.49ns ± 3%
IterPrev 4.48ns ± 3%
Documentation
¶
Index ¶
- Variables
- type Iterator
- func (it *Iterator) Close() error
- func (it *Iterator) First() *base.InternalKey
- func (it *Iterator) Head() bool
- func (it *Iterator) Key() *base.InternalKey
- func (it *Iterator) KeyInfo() (offset, keyStart, keyEnd uint32)
- func (it *Iterator) Last() *base.InternalKey
- func (it *Iterator) Next() *base.InternalKey
- func (it *Iterator) Prev() *base.InternalKey
- func (it *Iterator) SeekGE(key []byte, flags base.SeekGEFlags) *base.InternalKey
- func (it *Iterator) SeekLT(key []byte) *base.InternalKey
- func (it *Iterator) SetBounds(lower, upper []byte)
- func (it *Iterator) String() string
- func (it *Iterator) Tail() bool
- func (it *Iterator) Valid() bool
- type Skiplist
Constants ¶
This section is empty.
Variables ¶
var ( // ErrExists indicates that a duplicate record was inserted. This should never // happen for normal usage of batchskl as every key should have a unique // sequence number. ErrExists = errors.New("record with this key already exists") // ErrTooManyRecords is a sentinel error returned when the size of the raw // nodes slice exceeds the maximum allowed size (currently 1 << 32 - 1). This // corresponds to ~117 M skiplist entries. ErrTooManyRecords = errors.New("too many records") )
Functions ¶
This section is empty.
Types ¶
type Iterator ¶
type Iterator struct {
// contains filtered or unexported fields
}
Iterator is an iterator over the skiplist object. Use Skiplist.NewIter to construct an iterator. The current state of the iterator can be cloned by simply value copying the struct.
func (*Iterator) First ¶
func (it *Iterator) First() *base.InternalKey
First seeks position at the first entry in list. Final state of iterator is Valid() iff list is not empty. Note that First only checks the upper bound. It is up to the caller to ensure that key is greater than or equal to the lower bound (e.g. via a call to SeekGE(lower)).
func (*Iterator) Key ¶
func (it *Iterator) Key() *base.InternalKey
Key returns the key at the current position.
func (*Iterator) KeyInfo ¶
KeyInfo returns the offset of the start of the record, the start of the key, and the end of the key.
func (*Iterator) Last ¶
func (it *Iterator) Last() *base.InternalKey
Last seeks position at the last entry in list. Final state of iterator is Valid() iff list is not empty. Note that Last only checks the lower bound. It is up to the caller to ensure that key is less than the upper bound (e.g. via a call to SeekLT(upper)).
func (*Iterator) Next ¶
func (it *Iterator) Next() *base.InternalKey
Next advances to the next position. If there are no following nodes, then Valid() will be false after this call.
func (*Iterator) Prev ¶
func (it *Iterator) Prev() *base.InternalKey
Prev moves to the previous position. If there are no previous nodes, then Valid() will be false after this call.
func (*Iterator) SeekGE ¶
func (it *Iterator) SeekGE(key []byte, flags base.SeekGEFlags) *base.InternalKey
SeekGE moves the iterator to the first entry whose key is greater than or equal to the given key. Returns true if the iterator is pointing at a valid entry and false otherwise. Note that SeekGE only checks the upper bound. It is up to the caller to ensure that key is greater than or equal to the lower bound.
func (*Iterator) SeekLT ¶
func (it *Iterator) SeekLT(key []byte) *base.InternalKey
SeekLT moves the iterator to the last entry whose key is less the given key. Returns true if the iterator is pointing at a valid entry and false otherwise. Note that SeekLT only checks the lower bound. It is up to the caller to ensure that key is less than the upper bound.
func (*Iterator) SetBounds ¶
SetBounds sets the lower and upper bounds for the iterator. Note that the result of Next and Prev will be undefined until the iterator has been repositioned with SeekGE, SeekLT, First, or Last.
type Skiplist ¶
type Skiplist struct {
// contains filtered or unexported fields
}
Skiplist is a fast, non-cocnurrent skiplist implementation that supports forward and backward iteration. See arenaskl.Skiplist for a concurrent skiplist. Keys and values are stored externally from the skiplist via the Storage interface. Deletion is not supported. Instead, higher-level code is expected to perform deletion via tombstones and needs to process those tombstones appropriately during retrieval operations.
func NewSkiplist ¶
NewSkiplist constructs and initializes a new, empty skiplist.
func (*Skiplist) Add ¶
Add adds a new key to the skiplist if it does not yet exist. If the record already exists, then Add returns ErrRecordExists.
func (*Skiplist) NewIter ¶
NewIter returns a new Iterator object. The lower and upper bound parameters control the range of keys the iterator will return. Specifying for nil for lower or upper bound disables the check for that boundary. Note that lower bound is not checked on {SeekGE,First} and upper bound is not check on {SeekLT,Last}. The user is expected to perform that check. Note that it is safe for an iterator to be copied by value.
Source Files