Documentation
¶
Overview ¶
Package shard provides a logically versioned map implementation backed by a collection of independently synchronized maps.
In the current iteration the parallel methods/helpers are not implemented with (safe?) parallelism.
Index ¶
- type Map
- func (m *Map[K, V]) Check(key K) bool
- func (m *Map[K, V]) Clocks() []uint64
- func (m *Map[K, V]) Delete(key K)
- func (m *Map[K, V]) Extend(seq iter.Seq2[K, V])
- func (m *Map[K, V]) Fetch(k K) MapItem[K, V]
- func (m *Map[K, V]) Get(key K) (out V)
- func (m *Map[K, V]) Items() iter.Seq[MapItem[K, V]]
- func (m *Map[K, V]) ItemsSharded() iter.Seq[iter.Seq[MapItem[K, V]]]
- func (m *Map[K, V]) Iterator() iter.Seq2[K, V]
- func (m *Map[K, V]) IteratorSharded() iter.Seq[iter.Seq2[K, V]]
- func (m *Map[K, V]) Keys() iter.Seq[K]
- func (m *Map[K, V]) KeysSharded() iter.Seq[iter.Seq[K]]
- func (m *Map[K, V]) Load(key K) (V, bool)
- func (m *Map[K, V]) Set(key K, value V) bool
- func (m *Map[K, V]) Setup(n int, mi MapType)
- func (m *Map[K, V]) Store(key K, value V)
- func (m *Map[K, V]) String() string
- func (m *Map[K, V]) Values() iter.Seq[V]
- func (m *Map[K, V]) ValuesSharded() iter.Seq[iter.Seq[V]]
- func (m *Map[K, V]) Version() uint64
- func (m *Map[K, V]) Versioned(k K) (*Versioned[V], bool)
- type MapItem
- type MapType
- type Versioned
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Map ¶
type Map[K comparable, V any] struct { // contains filtered or unexported fields }
Map behaves like a simple map but divides the contents of the map between a number of shards. The outer map itself is versioned (e.g. a vector clock which records the number of global modification operations against the map), as well as each shard.
All version numbers are strictly increasing and are incremented before the modification: no-op modifications (as in setting a key to itself) do increment the version numbers. Operations that return versions, will not report stale data or version numbers.
Use these versions to determine if the data you have is (potentially) stale. The versions, of course, track number of modifications
There are no fully synchronized global operations--counts and iteration would require exclusive access to all of the data and the implementation doesn't contain provisions for this.
func (*Map[K, V]) Clocks ¶
Clocks returns a slice of the versions for the map and all of the shards. The first value is the "global" version.
func (*Map[K, V]) Delete ¶
func (m *Map[K, V]) Delete(key K)
Delete removes a key--and its corresponding value--from the map, if it exists.
func (*Map[K, V]) Extend ¶ added in v0.14.0
Extend adds items from the sequence to the sharded map (sequentially.) Interleaving of operations is possible (and likely.)
func (*Map[K, V]) Fetch ¶
Fetch returns an item from the sharded map, reporting all of the relevant version numbers.
func (*Map[K, V]) Get ¶ added in v0.14.0
func (m *Map[K, V]) Get(key K) (out V)
Get returns the value stored in the map, or the zero value for that type if it isn't present.
func (*Map[K, V]) Items ¶ added in v0.14.0
Items provides an iterator over all items in the map. The MapItem type captures the version information and information about the sharded configuration.
func (*Map[K, V]) ItemsSharded ¶ added in v0.14.0
ItemsSharded provides an iterator holding the items of each shard's items. Use the sharded iterator to fan out workloads.
func (*Map[K, V]) Iterator ¶ added in v0.14.0
Iterator provides a unified sequence over all key value pairs in the sharded map..
func (*Map[K, V]) IteratorSharded ¶ added in v0.14.0
IteratorSharded provides access to independent iterators for each constituent shard in the map.
func (*Map[K, V]) Keys ¶
Keys returns an iterator for all the keys in the map. Items are provdied from shards sequentially, and in the same sequence, but are randomized within the shard. The keys are NOT captured in a snapshot, so keys reflecting different logical moments will appear in the iterator. No key will appear more than once.
func (*Map[K, V]) KeysSharded ¶ added in v0.14.0
KeysSharded returns an iterator of iterators, with each iterator provided access to the keys of one of the map's underlying shard. Use sharded iterators to fan out a workload.
func (*Map[K, V]) Load ¶
Load retrieves the value from the map. The semantics are the same as for maps in go: if the value does not exist it always returns the zero value for the type, while the second value indicates if the key was present in the map.
func (*Map[K, V]) Set ¶
Set adds a key and value to the map, replacing any existing values as needed. Returns true if the key was already present it the map and false otherwise.
func (*Map[K, V]) Setup ¶
Setup initializes the shard with non-default shard size and backing map implementation. Once the Map is initialized (e.g. after calling this function, modifying the map, or accessing the contents of the map, this function becomes a no-op.)
func (*Map[K, V]) Store ¶
func (m *Map[K, V]) Store(key K, value V)
Store adds a key and value to the map, replacing any existing values as needed.
func (*Map[K, V]) String ¶
String reports the type name, number of configured shards, and current version of the map.
func (*Map[K, V]) Values ¶
Values returns an iterator for all of the keys in the map. Values are provided from shards sequentially, and always in the same sequences, but randomized within each shard. The values are NOT captured in a snapshot, so values reflecting different logical moments will appear in the iterator.
func (*Map[K, V]) ValuesSharded ¶ added in v0.14.0
ValuesSharded returns an iterator of iterators, with each iterator provided access to the values of one of the map's underlying shard. Use sharded iterators to fan out a workload.
type MapItem ¶
type MapItem[K comparable, V any] struct { Exists bool GlobalVersion uint64 ShardVersion uint64 Version uint64 ShardID uint64 NumShards uint64 Key K Value V }
MapItem wraps the value stored in a sharded map, with synchronized sharding and versioning information. Returned by some map iterator methods.
type MapType ¶
type MapType uint32
MapType is the enum that allows users to configure what map implementation backs the sharded Map. There are (in theory) performance trade offs for different map implementations based on the workload and usage patterns.
const ( // MapTypeDefault is an alias for the default map type that's // used if the sharded map is not configured with a specific backing type. MapTypeDefault MapType = MapTypeSync // MapTypeSync is a map based on the sync.Map (via the // adt.Map[K,V]) type. This map implementation is optimized // for append-heavy/append-only workloads. MapTypeSync MapType = 1 // MapTypeMutex is a standard library map (map[K]V) with all // access protected with a sync.Mutex, ensuring exclusive // access to all operations. May perform better than the // SyncMap for write-heavy workloads with frequent // modifications of existing keys. MapTypeMutex MapType = 2 // MapTypeRWMutex is a standard library map (map[K]V) with all // access protected with a sync.RWMutex, ensuring exclusive // access for write operations and concurrent access for read // operations. Will perform better for read-heavy workloads, // with write workloads that are skewed towards modifications // rather than additions. MapTypeRWMutex MapType = 3 // MapTypeStdlib is a very minimal wrapper on top of a // standard library map (map[K]V). This is not safe for // concurrent writes, and is primarily useful for // benchmarking. MapTypeStdlib MapType = 4 )
type Versioned ¶
type Versioned[T any] struct { // contains filtered or unexported fields }
Versioned is a wrapper type that tracks the modification count for the wrapped value.
func Version ¶
Version constructs a new versioned object initialized with the given value. The initial version number will be 1. Uninitialized objects have version zero.
func (*Versioned[T]) Fetch ¶
Fetch atomically retrieves both the current value and its version number. This method uses a retry loop to ensure the value and version are consistent, protecting against races where the value changes between reading the value and version. Returns the value and its corresponding version number.
func (*Versioned[T]) Load ¶
func (vv *Versioned[T]) Load() (out T)
Load returns the current value stored in this versioned object. Returns the zero value if the object is nil. This operation is safe for concurrent access.
func (*Versioned[T]) Ok ¶
Ok returns true if this versioned object is not nil, false otherwise. This is a nil-safe way to check if the versioned object exists.
Source Files