README
¶
arenaskl
Fast, lock-free, arena-based Skiplist implementation in Go that supports iteration in both directions.
Advantages
Arenaskl offers several advantages over other skiplist implementations:
- High performance that linearly scales with the number of cores. This is achieved by allocating from a fixed-size arena and by avoiding locks.
- Iterators that can be allocated on the stack and easily cloned by value.
- Simple-to-use and low overhead model for detecting and handling race conditions with other threads.
- Support for iterating in reverse (i.e. previous links).
Limitations
The advantages come at a cost that prevents arenaskl from being a general-purpose skiplist implementation:
- The size of the arena sets a hard upper bound on the combined size of skiplist nodes, keys, and values. This limit includes even the size of deleted nodes, keys, and values.
- 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:
https://github.com/andy-kimball/arenaskl
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.
The results are much better than skiplist and slist.
name time/op
ReadWrite/frac_0-8 470ns ±11%
ReadWrite/frac_10-8 462ns ± 3%
ReadWrite/frac_20-8 436ns ± 2%
ReadWrite/frac_30-8 410ns ± 2%
ReadWrite/frac_40-8 385ns ± 2%
ReadWrite/frac_50-8 360ns ± 4%
ReadWrite/frac_60-8 386ns ± 1%
ReadWrite/frac_70-8 352ns ± 2%
ReadWrite/frac_80-8 306ns ± 3%
ReadWrite/frac_90-8 253ns ± 4%
ReadWrite/frac_100-8 28.1ns ± 2%
Note that the above numbers are for concurrent operations using 8x parallelism. The same benchmarks without concurrency (use these numbers when comparing vs batchskl):
name time/op
ReadWrite/frac_0 1.53µs ± 1%
ReadWrite/frac_10 1.46µs ± 2%
ReadWrite/frac_20 1.39µs ± 3%
ReadWrite/frac_30 1.28µs ± 3%
ReadWrite/frac_40 1.21µs ± 2%
ReadWrite/frac_50 1.11µs ± 3%
ReadWrite/frac_60 1.23µs ±17%
ReadWrite/frac_70 1.16µs ± 4%
ReadWrite/frac_80 959ns ± 3%
ReadWrite/frac_90 738ns ± 5%
ReadWrite/frac_100 81.9ns ± 2%
Forward and backward iteration are also fast:
name time/op
IterNext 3.97ns ± 5%
IterPrev 3.88ns ± 3%
Documentation
¶
Index ¶
- Variables
- func MaxNodeSize(keySize, valueSize uint32) uint64
- type Arena
- type Inserter
- type Iterator
- func (it *Iterator) Close() error
- func (it *Iterator) Error() error
- func (it *Iterator) First() (*base.InternalKey, base.LazyValue)
- func (it *Iterator) Head() bool
- func (it *Iterator) Last() (*base.InternalKey, base.LazyValue)
- func (it *Iterator) Next() (*base.InternalKey, base.LazyValue)
- func (it *Iterator) NextPrefix(succKey []byte) (*base.InternalKey, base.LazyValue)
- func (it *Iterator) Prev() (*base.InternalKey, base.LazyValue)
- func (it *Iterator) SeekGE(key []byte, flags base.SeekGEFlags) (*base.InternalKey, base.LazyValue)
- func (it *Iterator) SeekLT(key []byte, flags base.SeekLTFlags) (*base.InternalKey, base.LazyValue)
- func (it *Iterator) SeekPrefixGE(prefix, key []byte, flags base.SeekGEFlags) (*base.InternalKey, base.LazyValue)
- func (it *Iterator) SetBounds(lower, upper []byte)
- func (it *Iterator) String() string
- func (it *Iterator) Tail() bool
- type Skiplist
- func (s *Skiplist) Add(key base.InternalKey, value []byte) error
- func (s *Skiplist) Arena() *Arena
- func (s *Skiplist) Height() uint32
- func (s *Skiplist) NewFlushIter(bytesFlushed *uint64) base.InternalIterator
- func (s *Skiplist) NewIter(lower, upper []byte) *Iterator
- func (s *Skiplist) Reset(arena *Arena, cmp base.Compare)
- func (s *Skiplist) Size() uint32
Constants ¶
This section is empty.
Variables ¶
var ( // ErrArenaFull indicates that the arena is full and cannot perform any more // allocations. ErrArenaFull = errors.New("allocation failed because arena is full") )
var ErrRecordExists = errors.New("record with this key already exists")
ErrRecordExists indicates that an entry with the specified key already exists in the skiplist. Duplicate entries are not directly supported and instead must be handled by the user by appending a unique version suffix to keys.
Functions ¶
func MaxNodeSize ¶
MaxNodeSize returns the maximum space needed for a node with the specified key and value sizes. This could overflow a uint32, which is why a uint64 is used here. If a key/value overflows a uint32, it should not be added to the skiplist.
Types ¶
type Arena ¶
type Arena struct {
// contains filtered or unexported fields
}
Arena is lock-free.
type Inserter ¶
type Inserter struct {
// contains filtered or unexported fields
}
Inserter TODO(peter)
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. All iterator methods are thread-safe.
func (*Iterator) First ¶
func (it *Iterator) First() (*base.InternalKey, base.LazyValue)
First seeks position at the first entry in list. Returns the key and value if the iterator is pointing at a valid entry, and (nil, nil) otherwise. 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) Last ¶
func (it *Iterator) Last() (*base.InternalKey, base.LazyValue)
Last seeks position at the last entry in list. Returns the key and value if the iterator is pointing at a valid entry, and (nil, nil) otherwise. 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, base.LazyValue)
Next advances to the next position. Returns the key and value if the iterator is pointing at a valid entry, and (nil, nil) otherwise. Note: flushIterator.Next mirrors the implementation of Iterator.Next due to performance. Keep the two in sync.
func (*Iterator) NextPrefix ¶
NextPrefix advances to the next position with a new prefix. Returns the key and value if the iterator is pointing at a valid entry, and (nil, nil) otherwise.
func (*Iterator) Prev ¶
func (it *Iterator) Prev() (*base.InternalKey, base.LazyValue)
Prev moves to the previous position. Returns the key and value if the iterator is pointing at a valid entry, and (nil, nil) otherwise.
func (*Iterator) SeekGE ¶
func (it *Iterator) SeekGE(key []byte, flags base.SeekGEFlags) (*base.InternalKey, base.LazyValue)
SeekGE moves the iterator to the first entry whose key is greater than or equal to the given key. Returns the key and value if the iterator is pointing at a valid entry, and (nil, nil) 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, flags base.SeekLTFlags) (*base.InternalKey, base.LazyValue)
SeekLT moves the iterator to the last entry whose key is less than the given key. Returns the key and value if the iterator is pointing at a valid entry, and (nil, nil) 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) SeekPrefixGE ¶
func (it *Iterator) SeekPrefixGE( prefix, key []byte, flags base.SeekGEFlags, ) (*base.InternalKey, base.LazyValue)
SeekPrefixGE moves the iterator to the first entry whose key is greater than or equal to the given key. This method is equivalent to SeekGE and is provided so that an arenaskl.Iterator implements the internal/base.InternalIterator interface.
type Skiplist ¶
type Skiplist struct {
// contains filtered or unexported fields
}
Skiplist is a fast, concurrent skiplist implementation that supports forward and backward iteration. See batchskl.Skiplist for a non-concurrent skiplist. Keys and values are immutable once added to the skiplist and deletion is not supported. Instead, higher-level code is expected to add new entries that shadow existing entries and perform deletion via tombstones. It is up to the user to process these shadow entries and tombstones appropriately during retrieval.
func NewSkiplist ¶
NewSkiplist constructs and initializes a new, empty skiplist. All nodes, keys, and values in the skiplist will be allocated from the given arena.
func (*Skiplist) Add ¶
func (s *Skiplist) Add(key base.InternalKey, value []byte) error
Add adds a new key if it does not yet exist. If the key already exists, then Add returns ErrRecordExists. If there isn't enough room in the arena, then Add returns ErrArenaFull.
func (*Skiplist) Height ¶
Height returns the height of the highest tower within any of the nodes that have ever been allocated as part of this skiplist.
func (*Skiplist) NewFlushIter ¶
func (s *Skiplist) NewFlushIter(bytesFlushed *uint64) base.InternalIterator
NewFlushIter returns a new flushIterator, which is similar to an Iterator but also sets the current number of the bytes that have been iterated through.
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