README
¶
BigMap
Fast - Scaling - Concurrent map for serializeable data
Inspired by allegro/bigcache
Fast
Most operations are done in about 0.2μs and can therefore be done 5 Million times / second.
And all this per thread. This is achieved by storing the objects in one single byte-slice and having a Zero-Allocation, Share-Nothing oriented design.
Resulting in minimimal GC pressure and maximal performance.
Concurrent
The map has no global lock.
It is split into multiple shards which are locked individual.
As the benchmarks show bigmap gains from concurrent access.
With preallocations and items having a max size it is faster than the standard map.
Scaling
If you have more concurrent accesses, you can always increase the shard count.
As always: only benchmarking your usecase will reveal the optimal settings.
But as shown, with the default 16 shards, you still get a good access speed even with half a million routines.
Each shard can store gigabytes of data without loosing performance, so it is good for storing tons of tons of normalized data.
Benchmarks
The benchmarks are done on a machine with an i7-8750H CPU (12x 2.20 - 4GHz), 16GB RAM (2666 MHz), Windows 10 machine The key size is ~24 bytes and the value size is 100 bytes. All settings are default. We can see I reach up to ~15 million OPs per second in the 10% Write 10% Delete 80% Read parallel benchmark on my machine.
go version
go version go1.18.1 windows/amd64
go.exe test -benchmem -run=^$ -bench "BenchmarkGenKey.*|BenchmarkBigMap.*" github.com/worldOneo/bigmap --benchtime=2s
goos: windows
goarch: amd64
pkg: github.com/worldOneo/bigmap
cpu: Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
BenchmarkGenKey-12 20777691 116.3 ns/op 24 B/op 2 allocs/op
BenchmarkBigMap_Put-12 9230487 287.3 ns/op 290 B/op 0 allocs/op
BenchmarkBigMap_Get-12 12443001 246.9 ns/op 112 B/op 1 allocs/op
BenchmarkBigMap_Delete-12 17242245 180.2 ns/op 31 B/op 0 allocs/op
BenchmarkBigMap_Mix_Ballanced-12 49623379 52.27 ns/op 37 B/op 0 allocs/op
BenchmarkBigMap_Mix_Unballanced-12 14191022 198.2 ns/op 141 B/op 0 allocs/op
# Parallel benchmarks have allocations because of the key generation (116.3 ns/op; 24 B/op; 2 allocs/op)
# which also makes them slightly slower.
BenchmarkBigMap_10_10_80_Parallel-12 31258323 75.20 ns/op 92 B/op 2 allocs/op
BenchmarkBigMap_Put_Parallel-12 15186710 164.1 ns/op 409 B/op 2 allocs/op
BenchmarkBigMap_Get_Parallel-12 30183781 86.25 ns/op 129 B/op 3 allocs/op
BenchmarkBigMap_Delete_Parallel-12 27003519 84.30 ns/op 59 B/op 2 allocs/op
BenchmarkBigMap_Mix_Ballanced_Parallel-12 20456823 114.1 ns/op 187 B/op 2 allocs/op
BenchmarkBigMap_Mix_Unballanced_Parallel-12 24044000 86.45 ns/op 172 B/op 2 allocs/op
Attention
The map scales as more data is added but, to enable high performance, doesn't schrink. To enable the fast accessess free heap is held "hot" to be ready to use. This means the map might grow once realy big, which might seeme like a memory leak at first glance because it doesn shrink, but then never grows again.
Documentation
¶
Index ¶
Constants ¶
const ( // DefaultCapacity is the default initial capacity of an shard in bytes DefaultCapacity uint64 = 1024 // DefaultShards is the default amount of shards in a BigMap DefaultShards int = 32 // LengthBytes is the amount of bytes required to define the length LengthBytes uint64 = 8 // Offset64 is the offset for FNV64 Offset64 = 14695981039346656037 // Prime64 is the prime for FNV64 Prime64 = 1099511628211 )
Variables ¶
This section is empty.
Functions ¶
Types ¶
type BigMap ¶
type BigMap struct {
// contains filtered or unexported fields
}
BigMap is a distributed byte-array based map. It is made up of multiple shards therefore enabling efficient parallel accesses.
The BigMap doesn't have a global lock. Shards are only locked individually.
By default is it split into 16 shards each shard holding a 1KB (by default) byte-array the shards will double there size if they run out of space and will never shrink again. This enables the map to stay fast even with many accesses.
func New ¶
New creates a new BigMap and populates its shards.
The entrysize defines the maximum size of the items added. Smaller items are no problem, bigger will return an error.
A config may be provided to tune the map as needed and/or enable expiration of items. See bigmap.Config
func (*BigMap) Delete ¶
Delete removes an item from the map. Delete doesnt shrink the memory size of the map. It only enables the space to be reused.
func (*BigMap) Get ¶
Get retrieves an item for the key. It returns a copy of the corresponding byte slice and a boolean if the item was contained. If the boolean is false the slice will be nil.
type Config ¶
type Config struct {
// Shards is the amount of shards which
// the map holds. The default is 16 and is
// sufficient most of the time. Try to benchmark
// your application to find out the shard amount
// that fits you best.
//
// Default: 16
Shards int
// Capacity defines the initial capacity of shard.
// This doesn't make a big difference in the long run
// as shards just scale up and stop changing at some
// time. But if you know your max capacity you can safe
// some (if only very little) time avoiding the
// resizing of shards.
//
// Default: 1024
Capacity uint64
// ExpirationFactory is used to create expirationServices
// for expiring items. An value of nil will result in no
// expiration of items.
//
// Default: nil
ExpirationFactory ExpirationFactory
}
Config defines values for a BigMap. Values which are 0 will become the default values.
type ExpirationFactory ¶
type ExpirationFactory func(shardIndex int) ExpirationService
ExpirationFactory is a function which creates can create a new ExpirationService given the index of the shard
func Expires ¶
func Expires(duration time.Duration, policy ExpirationPolicy) ExpirationFactory
Expires creates a new ExpirationFactory based on the provided ExpirationPolicy.
type ExpirationPolicy ¶
type ExpirationPolicy uint64
ExpirationPolicy determines the way expiration is treated within the a shard.
const ( // ExpirationPolicyPassive checks an items // expiration on access and if the item is // expired nil, false is returned and // the item is removed. // // This policy might be better in terms of // performance but an removal of an item is // not guaranteed and could therefore lead // to a memory leak like behaviour if keys // are unique and expired items never removed. ExpirationPolicyPassive ExpirationPolicy = iota // ExpirationPolicySweep checks for any expired items when // the map is accessed and removes any expired // item if one is detected. // // This policy might be better in terms // of memory usage as items are guaranteed // to be removed after they expired. But it // could have a major impact in performance // as each item must is checked on access // and the shard must be writelocked while // being cleaned. ExpirationPolicySweep )
type ExpirationService ¶
type ExpirationService interface {
// BeforeLock is called before the shard was accessed (put or get
// and before the shard is locked with the key which is about to
// be accessed.
// Accessing the shard from this method can not cause
// any deadlock between the shard and the ExpirationService.
BeforeLock(key uint64, shard *Shard)
// Lock is called before the shard was accessed (put or get
// and after the shard is locked with the key which is about to
// be accessed.
//
//Accessing the shard from this method might cause a deadlock.
Lock(key uint64, shard *Shard)
// Access is called after something was the was inserted into the shard
// (put) and before it is unlocked.
//
// Accessing the shard from this method
// might cause a deadlock.
//
// If an item should be removed in the lock shard.UnsafeDelete
// is safe inside this function call.
Access(key uint64, shard *Shard)
// AfterAccess is called after the shard was accessed (put or get) after
// unlocking it.
// Accessing the shard from this method can not cause
// any deadlock between the shard and the ExpirationService.
AfterAccess(key uint64, shard *Shard)
// Remove is called before the shard is changed (the item associated
// with the key will be removed) and after it was locked.
// Accessing the shard from this method might cause a deadlock.
Remove(key uint64, shard *Shard)
}
ExpirationService is the interface used for expiring items within a shard
func NewPassiveExpirationService ¶
func NewPassiveExpirationService(expires time.Duration) ExpirationService
NewPassiveExpirationService creates a new expiration service which is working according to ExpirationPolicyPassive.
func NewSweepExpirationService ¶
func NewSweepExpirationService(expires time.Duration) ExpirationService
NewSweepExpirationService creates a new expiration service which is working according to ExpirationPolicySweep.
type PointerQueue ¶ added in v1.1.0
type PointerQueue struct {
// contains filtered or unexported fields
}
PointerQueue is an Unbound queue to store free pointers in a shard. It is unsafe to access it parallel.
func NewPointerQueue ¶ added in v1.1.0
func NewPointerQueue() PointerQueue
NewPointerQueue iniitates a new PointerQueue
func (*PointerQueue) Dequeue ¶ added in v1.1.0
func (P *PointerQueue) Dequeue() (v uint64, ok bool)
Dequeue returns the next pointer if available and true or 0 and false
func (*PointerQueue) Enqueue ¶ added in v1.1.0
func (P *PointerQueue) Enqueue(ptr uint64)
Enqueue pushes a new Pointer to the queue
type Shard ¶
type Shard struct {
// contains filtered or unexported fields
}
Shard is a fraction of a bigmap. A bigmap is made up of shards which are individuall locked to increase performance. A shard locks itself while Put/Delete and RLocks itself while Get
func NewShard ¶
func NewShard(capacity, entrysize uint64, expSrv ExpirationService) *Shard
NewShard initializes a new shard. The capacity is the initial capacity of the shard. The entrysize defines the size each entry takes. Smaller entries are no problem, but bigger will result in an error. Expires defines the time after items can be removed. If expires is smaller or equals 0 it will be ignored and items wont be removed automatically.
func (*Shard) Delete ¶
Delete removes an item from the shard. And returns true if an item was deleted and false if the key didn't exist in the shard. Delete doesnt shrink the size of the byte-array nor of the shard. It only enables the space to be reused.
func (*Shard) Get ¶
Get retrieves an item from the shards internal byte-array. It returns a slice representing the item. and a boolean if the items was contained if the boolean is false the slice will be nil.
The return value is mapped to the underlying byte-array. If you want to change it use GetCopy.
func (*Shard) UnsafeDelete ¶
UnsafeDelete deletes an object without locking the shard. If no manual locking is provided data races may occur.
Source Files
Directories