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.
- Deleted nodes are not removed from the list, and are instead tagged with tombstone markers. This means that iteration times are proportional to the total number of nodes, rather than the number of live nodes.
Pedigree
This 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.
BenchmarkReadWrite/frac_0-8 5000000 490 ns/op
BenchmarkReadWrite/frac_10-8 5000000 479 ns/op
BenchmarkReadWrite/frac_20-8 5000000 448 ns/op
BenchmarkReadWrite/frac_30-8 5000000 440 ns/op
BenchmarkReadWrite/frac_40-8 5000000 424 ns/op
BenchmarkReadWrite/frac_50-8 5000000 384 ns/op
BenchmarkReadWrite/frac_60-8 5000000 361 ns/op
BenchmarkReadWrite/frac_70-8 5000000 315 ns/op
BenchmarkReadWrite/frac_80-8 10000000 306 ns/op
BenchmarkReadWrite/frac_90-8 10000000 267 ns/op
BenchmarkReadWrite/frac_100-8 100000000 25.2 ns/op
And even better than a simple map with read-write lock:
BenchmarkReadWriteMap/frac_0-8 2000000 691 ns/op
BenchmarkReadWriteMap/frac_10-8 3000000 566 ns/op
BenchmarkReadWriteMap/frac_20-8 3000000 562 ns/op
BenchmarkReadWriteMap/frac_30-8 3000000 560 ns/op
BenchmarkReadWriteMap/frac_40-8 3000000 519 ns/op
BenchmarkReadWriteMap/frac_50-8 3000000 436 ns/op
BenchmarkReadWriteMap/frac_60-8 5000000 484 ns/op
BenchmarkReadWriteMap/frac_70-8 5000000 399 ns/op
BenchmarkReadWriteMap/frac_80-8 5000000 400 ns/op
BenchmarkReadWriteMap/frac_90-8 5000000 319 ns/op
BenchmarkReadWriteMap/frac_100-8 30000000 43.6 ns/op
Documentation
¶
Index ¶
- Constants
- Variables
- type Align
- type Arena
- func (a *Arena) Alloc(size, overflow uint32, align Align) (uint32, error)
- func (a *Arena) Cap() uint32
- func (a *Arena) GetBytes(offset uint32, size uint32) []byte
- func (a *Arena) GetPointer(offset uint32) unsafe.Pointer
- func (a *Arena) GetPointerOffset(ptr unsafe.Pointer) uint32
- func (a *Arena) Reset()
- func (a *Arena) Size() uint32
- type Iterator
- func (it *Iterator) Add(key []byte, val []byte, meta uint16) error
- func (it *Iterator) Delete() error
- func (it *Iterator) Init(list *Skiplist)
- func (it *Iterator) Key() []byte
- func (it *Iterator) Meta() uint16
- func (it *Iterator) Next()
- func (it *Iterator) Prev()
- func (it *Iterator) Seek(key []byte) (found bool)
- func (it *Iterator) SeekForPrev(key []byte) (found bool)
- func (it *Iterator) SeekToFirst()
- func (it *Iterator) SeekToLast()
- func (it *Iterator) Set(val []byte, meta uint16) error
- func (it *Iterator) SetMeta(meta uint16) error
- func (it *Iterator) Valid() bool
- func (it *Iterator) Value() []byte
- type Skiplist
Constants ¶
const ( Align1 = 0 Align2 = 1 Align4 = 3 Align8 = 7 )
const MaxNodeSize = int(unsafe.Sizeof(node{}))
Variables ¶
var (
ErrArenaFull = errors.New("allocation failed because arena is full")
)
var ErrRecordDeleted = errors.New("record was deleted by another caller")
var ErrRecordExists = errors.New("record with this key already exists")
var ErrRecordUpdated = errors.New("record was updated by another caller")
Functions ¶
This section is empty.
Types ¶
type Arena ¶
type Arena struct {
// contains filtered or unexported fields
}
Arena should be lock-free.
type Iterator ¶
type Iterator struct {
// contains filtered or unexported fields
}
Iterator is an iterator over the skiplist object. Call Init to associate a skiplist with the iterator. The current state of the iterator can be cloned by simply value copying the struct. All iterator methods are thread-safe.
func (*Iterator) Add ¶
Add creates a new key/value record if it does not yet exist and positions the iterator on it. If the record already exists, then Add positions the iterator on the most current value and returns ErrRecordExists. If there isn't enough room in the arena, then Add returns ErrArenaFull.
func (*Iterator) Delete ¶
Delete marks the current iterator record as deleted from the store if it has not been updated since iterating or seeking to it. If the record has been updated, then Delete positions the iterator on the most current value and returns ErrRecordUpdated. If the record is deleted, then Delete positions the iterator on the next record.
func (*Iterator) Next ¶
func (it *Iterator) Next()
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()
Prev moves to the previous position. If there are no previous nodes, then Valid() will be false after this call.
func (*Iterator) Seek ¶
Seek searches for the record with the given key. If it is present in the skiplist, then Seek positions the iterator on that record and returns true. If the record is not present, then Seek positions the iterator on the following node (if it exists) and returns false.
func (*Iterator) SeekForPrev ¶
SeekForPrev searches for the record with the given key. If it is present in the skiplist, then SeekForPrev positions the iterator on that record and returns true. If the record is not present, then SeekForPrev positions the iterator on the preceding node (if it exists) and returns false.
func (*Iterator) SeekToFirst ¶
func (it *Iterator) SeekToFirst()
SeekToFirst seeks position at the first entry in list. Final state of iterator is Valid() iff list is not empty.
func (*Iterator) SeekToLast ¶
func (it *Iterator) SeekToLast()
SeekToLast seeks position at the last entry in list. Final state of iterator is Valid() iff list is not empty.
func (*Iterator) Set ¶
Set updates the value of the current iteration record if it has not been updated or deleted since iterating or seeking to it. If the record has been updated, then Set positions the iterator on the most current value and returns ErrRecordUpdated. If the record has been deleted, then Set keeps the iterator positioned on the current record with the current value and returns ErrRecordDeleted.
func (*Iterator) SetMeta ¶
SetMeta updates the meta value of the current iteration record if it has not been updated or deleted since iterating or seeking to it. If the record has been updated, then SetMeta positions the iterator on the most current value and returns ErrRecordUpdated. If the record has been deleted, then SetMeta keeps the iterator positioned on the current record with the current value and returns ErrRecordDeleted.
type Skiplist ¶
type Skiplist struct {
// contains filtered or unexported fields
}
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.
Source Files
Directories