README
¶
Ash
Ash is a concurrent, lock-free Atomic Skiplist Hash map written in golang. It is intended as a drop-in replacement for sync.Map and is designed to operate concurrently without relying on locks, instead using atomic operations and pointer tagging techniques.
Motivation
As part of writing go code professionally, built-in map and sync.Map are certainly among the data structures that I have used the most, and not without some level of frustration.
sync.Map was a great addition to the standard library, but it's not ideal in every scenario: more often than not I find myself guarding a map's reads and writes using synchronization primitives like Mutex and/or RWMutex or some combination of both.
YunHao Zhang's talk[1] at Gophercon 2024 in Chicago was an inspiring introduction to the skip list data structure, which surprisingly enough is not implemented in any of the go standard lib.
This library explores a lock-free implementation of the skip list as a way to challenge myself and learn something new.
See the References section for the list of papers that inspired the implementation.
Features
- SkipList based design: uses a skip list as the underlying data structure, allowing efficient insertion, deletion, and search operations.
- Concurrent: lock-free atomic implementation
- Pointer Tagging: employs pointer tagging techniques to achieve a markable reference that encodes metadata (a mark bit) directly within pointer values, facilitating atomic updates to the structure.
- Compatibility: consistent with
sync.Map, straightforward adoption in existing codebases.
Status
This library is under active development.
At this time I have only tested on the following:
goos: darwin
goarch: arm64
pkg: ash
cpu: Apple M1
Usage
The usage of ash.Map mirrors that of sync.Map. The following example demonstrates basic operations:
package main
import (
"fmt"
"github.com/riraccuia/ash"
)
func main() {
m := new(ash.Map).From(ash.NewSkipList(32))
// Store a key-value pair
m.Store("key", "value")
// Retrieve a value
value, ok := m.Load("key")
if ok {
fmt.Println("Loaded:", value)
}
// Delete a key-value pair
m.Delete("key")
}
Pointer Tagging
Consider the below representation of a pointer in modern architectures[2]:
0-2 (3 bits) Alignment <--+
|
|
63 48 47 3 | 0
+-+---------------+---+------------------------------------------------+-----+-+
| 00000000 00000000 | -------- -------- -------- -------- -------- ----- | 000 |
+------------------------------------------------------------------------------+
High | Low
| +--> 0-47 (48 bits) Memory Address (pointer)
|
+--> 48-63 (16 bits) Reserved
Armed with this knowledge, we know that memory address (pointer) representations only use the lower 48 bits of a uint64, which gives us some options to improve logical deletion of nodes from the tree (markable reference).
This package currently encodes a deletion flag (mark) in the top byte (bits 56-63) of the address.
TBI[3] (Top Byte Ignore) should allow direct usage of the tainted pointer on linux/macOS with aarch64 but the top 8 bits of the address are being cleared prior to consuming it.
Benchmarks
% go test -v -run=NOTEST -bench=. -benchtime=5000000x -benchmem -cpu=8 -count=1
goos: darwin
goarch: arm64
pkg: ash
cpu: Apple M1
BenchmarkSyncMap_70Load20Store10Delete
map_bench_test.go:50: sync.Map total calls to Store/Delete/Load: 0 / 0 / 1 /
map_bench_test.go:55: Execution time: 62.917µs
map_bench_test.go:50: sync.Map total calls to Store/Delete/Load: 1000010 / 499183 / 3500807 /
map_bench_test.go:55: Execution time: 1.415291833s
BenchmarkSyncMap_70Load20Store10Delete-8 5000000 283.1 ns/op 52 B/op 0 allocs/op
BenchmarkAshMap_70Load20Store10Delete
map_bench_test.go:97: ash.Map total calls to Store/Delete/Load: 0 / 0 / 1 /
map_bench_test.go:103: Execution time: 10.75µs
map_bench_test.go:97: ash.Map total calls to Store/Delete/Load: 1000134 / 499997 / 3499869 /
map_bench_test.go:103: Execution time: 484.099ms
BenchmarkAshMap_70Load20Store10Delete-8 5000000 96.82 ns/op 84 B/op 1 allocs/op
Contributing
Contributions are encouraged. Issues and pull requests can be submitted through the GitHub repository.
License
This code is distributed under the MIT License. See the LICENSE file for details.
Credits
- https://github.com/cespare/xxhash : great Go implementation of the 64-bit xxHash algorithm, this is what ash uses to hash keys.
- https://www.cloudcentric.dev/implementing-a-skip-list-in-go/ : pseudo-random height generation.
- https://github.com/zhangyunhao116/skipmap : YunHao's work, thanks for the inspiration.
References
Documentation
¶
Index ¶
- Constants
- Variables
- func HashFunc(key any) uint64
- func IsPointerMarked(ptr unsafe.Pointer) bool
- func PointerFromTagPointer(tp unsafe.Pointer) unsafe.Pointer
- func TagPointer(ptr unsafe.Pointer, flag int) unsafe.Pointer
- type Map
- func (m *Map) Clear()
- func (m *Map) CompareAndDelete(key, old any) (deleted bool)
- func (m *Map) CompareAndSwap(key, old, new any) (swapped bool)
- func (m *Map) Delete(key any)
- func (m *Map) From(sl *SkipList) *Map
- func (m *Map) Len() (l int)
- func (m *Map) Load(key any) (value any, ok bool)
- func (m *Map) LoadAndDelete(key any) (value any, loaded bool)
- func (m *Map) LoadOrStore(key, value any) (actual any, loaded bool)
- func (m *Map) Range(f func(key, value any) bool)
- func (m *Map) Store(key, value any)
- func (m *Map) Swap(key, value any) (previous any, loaded bool)
- type Node
- type SkipList
- type Tower
- func (lvl *Tower) AddPtr(toLevel int, p unsafe.Pointer)
- func (lvl *Tower) AddPtrUnsafe(toLevel int, p unsafe.Pointer)
- func (lvl *Tower) CompareAndSwapNext(level int, old, new unsafe.Pointer) (swapped bool)
- func (lvl *Tower) NextPtr(forLevel int) unsafe.Pointer
- func (lvl *Tower) UpdateNext(level int, new unsafe.Pointer)
Constants ¶
const (
CapLevel = 64
)
Variables ¶
var ( // PValue defines the fixed probability that an element in level i appears in level i+1. // Defaults to 1/2, another commonly used value for it is 1/4. PValue = 0.5 // RandomHeightFunc is the function that returns the height for any new element to store in a skip list. // It is possible to override this function provided that the return value does not exceed maxLevel. RandomHeightFunc func(maxLevel int) int = randomHeight )
Functions ¶
func IsPointerMarked ¶
func PointerFromTagPointer ¶
PointerFromTagPointer clears the higher 8 bits from the pointer address, effectively removing all of the tagging that might have been applied to it. This is useful because on platforms where TBI is not or cannot be enabled, calling an object using the 'tainted' pointer will cause a crash.
func TagPointer ¶
TagPointer applies the flag to the higher 8 bits of the pointer address
Example:
normal ptr -> 00000000_00000000_00000001_01000000_00000000_00000000_11100001_10111000 (ptr|2<<56) -> 00000010_00000000_00000001_01000000_00000000_00000000_11100001_10111000
Types ¶
type Map ¶
type Map struct {
*SkipList
}
Map is a drop-in replacement for sync.Map backed by skip list. Use &ash.Map{*SkipList} or new(ash.Map).From(ash.NewSkipList(maxlevel)) to instantiate.
func (*Map) CompareAndDelete ¶
CompareAndDelete deletes the entry for key if its value is equal to old. The old value must be of a comparable type.
If there is no current value for key in the map, CompareAndDelete returns false (even if the old value is the nil interface value).
func (*Map) CompareAndSwap ¶
CompareAndSwap swaps the old and new values for key if the value stored in the map is equal to old. The old value must be of a comparable type.
func (*Map) Load ¶
Load returns the value stored in the map for a key, or nil if no value is present. The ok result indicates whether value was found in the map.
func (*Map) LoadAndDelete ¶
LoadAndDelete deletes the value for a key, returning the previous value if any. The loaded result reports whether the key was present.
func (*Map) LoadOrStore ¶
LoadOrStore returns the existing value for the key if present. Otherwise, it stores and returns the given value. The loaded result is true if the given value was loaded, false if stored.
type Node ¶
type Node struct {
// contains filtered or unexported fields
}
Node represents a node in a skip list, all of its methods. are concurrent safe
func (*Node) Next ¶
Next returns the next element, at the given level, that this node is pointing to. It will step over marked nodes that may be found while walking the tree.
type SkipList ¶
type SkipList struct {
// contains filtered or unexported fields
}
SkipList is a lock-free, concurrent safe skip list implementation.
func NewSkipList ¶
NewSkipList returns a lock-free, concurrent safe skip list with its maxlevel set to the given height. For p = 1/2, using maxlevel=16 should be appropriate for storing up to 2^16 elements. The p value is controlled by the `PValue` global and defaults to 1/2. Maxlevel is a number between 1 and 64.
func (*SkipList) Delete ¶
Delete removes the element from the list. It will start to mark from the top level until one level above the bottom level. After all upper level references are marked, it marks the bottom level to indicate logical deletion from the list.
func (*SkipList) FindNode ¶
FindNode performs a search from the top level to the bottom level to find the target element. Nodes with a reference mark will be ignored. The 'full' parameter, when set to false, makes FindNode stop and return when the element is found, without reaching to the bottom of the list. If the element is found, it is returned along with its predecessors and successors on all levels, note that on levels where the element is found, the successor is the node (element) itself. The preds and succs arguments are allocated by the caller, or set to nil.
func (*SkipList) Search ¶
Search calls FindNode() with the 'full' parameter set to false Returns the node, if found, or nil.
func (*SkipList) Store ¶
Store adds the element to the list. If the element exists, its value is updated. Otherwise it finds its predecessors and successors in all levels, creates the new node with all pointers pointing to the potential successors. It will first try to add the new node using CAS to the bottom level, then it will modify the pointers in all the previous nodes to point to the current node.
type Tower ¶
Tower embeds the skip list's levels, all of its methods are safe for concurrent use unless otherwise specified.
func (*Tower) AddPtrUnsafe ¶
AddPtrUnsafe sets the pointer to the next element at the given level. It is not safe for concurrent use.
func (*Tower) CompareAndSwapNext ¶
CompareAndSwapNext performs the atomic CAS operation for the element pointed to at the given level.
Source Files