README
¶
shardmap
A performant, highly concurrent and simple sharded hashmap implementation using generics.
This package contains a ShardedMap and a FIFOMap.
ShardedMap
A ShardedMap is a simple map that uses a sharded design. A sharded map splits the map into
buckets or shards according to the key, where each shard has its own RWMutex. This ensures that lock contention
is heavily minimized compared to using one mutex for the whole map, making it very high throughput and low latency
in highly concurrent situations.
It has the following interface:
type ShardedMapInterface interface {
Get(key K) (val V, ok bool)
Put(key K, val V)
Has(key K) ok bool
Del(key K)
Len() int
}
Example
import "github.com/chainbound/shardmap"
func main() {
// Initialize a new sharded int -> string map with size 1000, and 10 shards.
// We need to provide the hash function for our key type, the defaults being contained
// in this package. You can also provide your own.
sm := shardmap.NewShardedMap[int, string](1000, 10, shardmap.HashInt)
sm.Put(1, "josh")
fmt.Println(sm.Get(1))
}
FIFOMap
The FIFOMap is a map with a FIFO eviction policy, meaning that the oldest values get removed once your map
reaches a certain size. Internally, it uses the sharded map above, and shares the same interface.
import "github.com/chainbound/shardmap"
func main() {
// Initialize a new sharded int -> string map with size 1000, and 10 shards.
// We need to provide the hash function for our key type, the defaults being contained
// in this package. You can also provide your own.
sm := shardmap.NewFIFOMap[int, string](1000, 10, shardmap.HashInt)
// Once the size is reached, the next put will remove the oldest inserted KV pair.
sm.Put(1, "josh")
fmt.Println(sm.Get(1))
}
Documentation
¶
Index ¶
- func HashBytes(b []byte) uint64
- func HashInt(i int) uint64
- func HashInt8(i int8) uint64
- func HashInt16(i int16) uint64
- func HashInt32(i int32) uint64
- func HashInt64(i int64) uint64
- func HashString(s string) uint64
- func HashUint(i uint) uint64
- func HashUint8(u uint8) uint64
- func HashUint16(u uint16) uint64
- func HashUint32(u uint32) uint64
- func HashUint64(u uint64) uint64
- type FIFOMap
- type HashFn
- type ShardedMap
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func HashString ¶
func HashUint16 ¶
func HashUint32 ¶
func HashUint64 ¶
Types ¶
type FIFOMap ¶
type FIFOMap[K hashable, V any] struct { // contains filtered or unexported fields }
func NewFIFOMap ¶
NewFIFOMap returns a FIFO map that internally uses the sharded map. It keeps count of all the items inserted, and when we exceed the size, values will be evicted using the FIFO (first in, first out) policy.
type HashFn ¶
type HashFn[K comparable] func(k K) uint64
type ShardedMap ¶
type ShardedMap[K hashable, V any] struct { // contains filtered or unexported fields }
func NewShardedMap ¶
func NewShardedMap[K hashable, V any](size, numShards int, hashFn HashFn[K]) *ShardedMap[K, V]
NewShardedMap returns a new sharded map with `numShards` shards. Each of the shards are pre-allocated with a length of `size` / `numShards`. `size` is not the max size by any means, but just an estimation. hashFn is used to hash the key.
func (*ShardedMap[K, V]) Del ¶
func (m *ShardedMap[K, V]) Del(key K)
Del deletes the value from the map.
func (*ShardedMap[K, V]) Get ¶
func (m *ShardedMap[K, V]) Get(key K) (v V, ok bool)
Get returns the value and true if the value is present, otherwise it returns the default value and false.
func (*ShardedMap[K, V]) Has ¶
func (m *ShardedMap[K, V]) Has(key K) bool
Has returns true if the key is present.
func (*ShardedMap[K, V]) Len ¶
func (m *ShardedMap[K, V]) Len() int
Len returns the count of all the items in the sharded map. It will RLock every one of the shards so use it scarcely.
func (*ShardedMap[K, V]) Put ¶
func (m *ShardedMap[K, V]) Put(key K, val V)
Put puts the key value pair in the map.
Source Files