README
¶
ShardedMap
Thread-safe concurrent maps for go. Initially inspired by
https://github.com/orcaman/concurrent-map, which is awesome, but doesn't let you
easily change the shards number upon creation, and doesn't provide ready-made
implementations for the most common keys, as it only supports string keys.
Later heavily influenced by https://github.com/tidwall/shardmap.
This implementation should be more performant than Orcaman's in most cases, due to the customizable number of shards, better default, and use of a faster hash.
Here we provide ready-made implementation for string, uint64,
and uuid. Of course, string keys are the more common, but if you can use
uint64 keys for your application, that could provide much better performance
in some cases.
Also, uuids are a common case of map keys. Instead of using their string
representation, here we provide ready-made [16]byte map key support, which
most Golang UUID libraries use as underlying type, so you can store them without
encoding/decoding, and with much less memory pressure.
Code generation for the exact value type has been considered, but for simplicity (or just lazyness) I'm not doing that at the moment. If you need to squeeze that extra performance, copy-paste and adapt the code to your usage. Also PRs and motivational issues are welcome!
Which concurrent map to use
That very much depends on your concurrency needs, your hardware, and your requirements, but a few rules of thumb that might or might not help:
- If you have less than 4 cores, a single map with an RWMutex is all you need.
- Many cores and goroutines:
- Tons of reads, not many writes:
sync.Mapis appropriate. - Mixed reads and writes, go for a sharded map implementation. At the moment
[1] is a veteran library,
well tested. [2] is a newcomer but
looks very good. This library is inspired on both. It should be a bit more
performant than [1], while
using standard Go maps and slightly less dependencies than
[2]. Also, this library has native
support for
uint64andUUIDkeys if you want that. However due to my lazyness and because I just use this for personal projects, this lib is not so well tested. Caveat Emptor (and PRs are welcome, or file an issue to motivate me into writing those tests!).
- Tons of reads, not many writes:
- Other invariants to keep together with the map semantics: Write your own data structure or pick one implementation you like and fork it, then add those invariants there.
- Mixed value types, TTL, queries... You don't want a map, you want either a cache or an in-memory database, depending on your exact requirements. Check for example [3] and [4].
Installation
go get -u github.com/antoniomo/shardedmap
Sample usage
package main
import (
"fmt"
"github.com/antoniomo/shardedmap"
)
type Data struct {
ID string
V int
}
func main() {
strmap := shardedmap.NewStrMap(64)
a := Data{ID: "a", V: 1}
b := Data{ID: "b", V: 2}
strmap.Store(a.ID, a)
strmap.Store(b.ID, b)
a2, ok := strmap.Load(a.ID)
if !ok {
panic("ARGH!")
}
b2, ok := strmap.Load(b.ID)
if !ok {
panic("ARGH!")
}
fmt.Println("Same with range (note the random order):")
strmap.Range(func(key string, value interface{}) bool {
fmt.Printf("Key: %s, Value: %+v\n", key, value)
return true
})
fmt.Println("LoadOrStore over a.ID")
los, ok := strmap.LoadOrStore(a.ID, b)
if !ok {
panic("ARGH!")
}
fmt.Printf("Key: %s, Value: %+v\n", a.ID, los)
strmap.Delete(a.ID)
strmap.Delete(b.ID)
_, ok = strmap.Load(a.ID)
if ok {
panic("ARGH!")
}
_, ok = strmap.Load(b.ID)
if ok {
panic("ARGH!")
}
}
The output of that should be:
Key: a, Value: {ID:a V:1}
Key: b, Value: {ID:b V:2}
Same with range (note the random order):
Key: b, Value: {ID:b V:2}
Key: a, Value: {ID:a V:1}
LoadOrStore over a.ID
Key: a, Value: {ID:a V:1}
As expected.
References
Documentation
¶
Index ¶
- type StrMap
- func (sm *StrMap) AsyncRange(f func(key string, value interface{}) bool)
- func (sm *StrMap) ConcRange(f func(key string, value interface{}) bool)
- func (sm *StrMap) Delete(key string)
- func (sm *StrMap) Load(key string) (interface{}, bool)
- func (sm *StrMap) LoadOrStore(key string, value interface{}) (actual interface{}, loaded bool)
- func (sm *StrMap) Range(f func(key string, value interface{}) bool)
- func (sm *StrMap) Store(key string, value interface{})
- type UUID
- type UUIDMap
- func (sm *UUIDMap) AsyncRange(f func(key UUID, value interface{}) bool)
- func (sm *UUIDMap) ConcRange(f func(key UUID, value interface{}) bool)
- func (sm *UUIDMap) Delete(key UUID)
- func (sm *UUIDMap) Load(key UUID) (interface{}, bool)
- func (sm *UUIDMap) LoadOrStore(key UUID, value interface{}) (actual interface{}, loaded bool)
- func (sm *UUIDMap) Range(f func(key UUID, value interface{}) bool)
- func (sm *UUIDMap) Store(key UUID, value interface{})
- type Uint64Map
- func (sm *Uint64Map) AsyncRange(f func(key uint64, value interface{}) bool)
- func (sm *Uint64Map) ConcRange(f func(key uint64, value interface{}) bool)
- func (sm *Uint64Map) Delete(key uint64)
- func (sm *Uint64Map) Load(key uint64) (interface{}, bool)
- func (sm *Uint64Map) LoadOrStore(key uint64, value interface{}) (actual interface{}, loaded bool)
- func (sm *Uint64Map) Range(f func(key uint64, value interface{}) bool)
- func (sm *Uint64Map) Store(key uint64, value interface{})
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type StrMap ¶
type StrMap struct {
// contains filtered or unexported fields
}
Implementation: This is a sharded map so that the cost of locking is distributed with the data, instead of a single lock. The optimal number of shards will probably depend on the number of system cores but we provide a general default.
func (*StrMap) AsyncRange ¶
AsyncRange is exactly like ConcRange, but doesn't wait until all shards are done. This is usually ok, although calls that appear to happen "sequentially" on the same goroutine might get the before or after AsyncRange values, which might be surprising behaviour. When that's not desirable, use ConcRange.
func (*StrMap) ConcRange ¶
ConcRange ranges concurrently over all the shards, calling f sequentially over each shard's key and value. If f returns false, range stops the iteration on that shard (but the other shards continue until completion).
No key will be visited more than once, but if any value is inserted concurrently, Range may or may not visit it. Similarly, if a value is modified concurrently, Range may visit the previous or newest version of said value.
func (*StrMap) LoadOrStore ¶
LoadOrStore ...
func (*StrMap) Range ¶
Range is modeled after sync.Map.Range. It calls f sequentially for each key and value present in each of the shards in the map. If f returns false, range stops the iteration.
No key will be visited more than once, but if any value is inserted concurrently, Range may or may not visit it. Similarly, if a value is modified concurrently, Range may visit the previous or newest version of said value.
type UUIDMap ¶
type UUIDMap struct {
// contains filtered or unexported fields
}
Implementation: This is a sharded map so that the cost of locking is distributed with the data, instead of a single lock. The optimal number of shards will probably depend on the number of system cores but we provide a general default.
func (*UUIDMap) AsyncRange ¶
AsyncRange is exactly like ConcRange, but doesn't wait until all shards are done. Since each shard is locked with an RWLock, it might be safe to use, but concurrent reads elsewhere might get the pre-range values, so don't use this one unless you don't care about that.
func (*UUIDMap) ConcRange ¶
ConcRange ranges concurrently over all the shards, calling f sequentially over each shard's key and value. If f returns false, range stops the iteration on that shard (but the other shards continue until completion).
No key will be visited more than once, but if any value is inserted concurrently, Range may or may not visit it. Similarly, if a value is modified concurrently, Range may visit the previous or newest version of said value.
func (*UUIDMap) LoadOrStore ¶
LoadOrStore ...
func (*UUIDMap) Range ¶
Range is modeled after sync.Map.Range. It calls f sequentially for each key and value present in each of the shards in the map. If f returns false, range stops the iteration.
No key will be visited more than once, but if any value is inserted concurrently, Range may or may not visit it. Similarly, if a value is modified concurrently, Range may visit the previous or newest version of said value.
type Uint64Map ¶
type Uint64Map struct {
// contains filtered or unexported fields
}
Implementation: This is a sharded map so that the cost of locking is distributed with the data, instead of a single lock. The optimal number of shards will probably depend on the number of system cores but we provide a general default.
func (*Uint64Map) AsyncRange ¶
AsyncRange is exactly like ConcRange, but doesn't wait until all shards are done. Since each shard is locked with an RWLock, it might be safe to use, but concurrent reads elsewhere might get the pre-range values, so don't use this one unless you don't care about that.
func (*Uint64Map) ConcRange ¶
ConcRange ranges concurrently over all the shards, calling f sequentially over each shard's key and value. If f returns false, range stops the iteration on that shard (but the other shards continue until completion).
No key will be visited more than once, but if any value is inserted concurrently, Range may or may not visit it. Similarly, if a value is modified concurrently, Range may visit the previous or newest version of said value.
func (*Uint64Map) LoadOrStore ¶
LoadOrStore ...
func (*Uint64Map) Range ¶
Range is modeled after sync.Map.Range. It calls f sequentially for each key and value present in each of the shards in the map. If f returns false, range stops the iteration.
No key will be visited more than once, but if any value is inserted concurrently, Range may or may not visit it. Similarly, if a value is modified concurrently, Range may visit the previous or newest version of said value.
Source Files