Go Left Right Concurrency
A Go implementation of the left-right concurrency control algorithm in paper
This library provides a concurrency primitive for high concurrency reads over a single-writer data structure. The micro benchmark shows the left-right pattern is 2-3x faster than the RWMutex.
Why
In Go, RWMutex is your best choice in most cases when handling concurrent read/write situation. However, in some special extreme cases: you do not want the high-concurrent reads to be blocked by infrequent writes.
In this library, an example left-right-pattern map was implemented to compare with the classic RWMutex-based map.
You can apply the same technique on slice, list, stack etc, to make them concurrent-safe if it meets your case: high concurrency reads over a single-writer.
// Only writes: RWMutex-Map is 2x faster than LR-Map
BenchmarkLRMap_Write 12231741 93.4 ns/op 0 B/op 0 allocs/op
BenchmarkLRMap_Write-2 12355836 93.3 ns/op 0 B/op 0 allocs/op
BenchmarkLRMap_Write-4 12448788 92.4 ns/op 0 B/op 0 allocs/op
BenchmarkLockMap_Write 20728842 54.1 ns/op 0 B/op 0 allocs/op
BenchmarkLockMap_Write-2 20953489 54.0 ns/op 0 B/op 0 allocs/op
BenchmarkLockMap_Write-4 20412688 54.0 ns/op 0 B/op 0 allocs/op
// Only reads: RWMutex-Map is slightly faster than LR-Map
BenchmarkLRMap_Read 4505625 224 ns/op 39 B/op 0 allocs/op
BenchmarkLRMap_Read-2 5114546 212 ns/op 34 B/op 0 allocs/op
BenchmarkLRMap_Read-4 5271961 212 ns/op 33 B/op 0 allocs/op
BenchmarkLockMap_Read 7331290 158 ns/op 11 B/op 0 allocs/op
BenchmarkLockMap_Read-2 6270297 162 ns/op 14 B/op 0 allocs/op
BenchmarkLockMap_Read-4 6244382 162 ns/op 14 B/op 0 allocs/op
// 5 readers vs 1 writer: on 2.4 CPUs, LR-map is 2-3x faster than RWMutex-map
BenchmarkLRMap_Read_Write_5_1 5794 205062 ns/op 46 B/op 1 allocs/op
BenchmarkLRMap_Read_Write_5_1-2 3088 405067 ns/op 72 B/op 1 allocs/op
BenchmarkLRMap_Read_Write_5_1-4 3014 415573 ns/op 81 B/op 1 allocs/op
BenchmarkLockMap_Read_Write_5_1 7491 160224 ns/op 27 B/op 1 allocs/op
BenchmarkLockMap_Read_Write_5_1-2 1210 1031627 ns/op 94 B/op 1 allocs/op
BenchmarkLockMap_Read_Write_5_1-4 1106 1067645 ns/op 101 B/op 1 allocs/op
// 10 readers vs 1 writer: on 2.4 CPUs, LR-map is 2-3x faster than RWMutex-map
BenchmarkLRMap_Read_Write_10_1 3236 354466 ns/op 70 B/op 1 allocs/op
BenchmarkLRMap_Read_Write_10_1-2 1609 772303 ns/op 123 B/op 1 allocs/op
BenchmarkLRMap_Read_Write_10_1-4 1593 726723 ns/op 132 B/op 1 allocs/op
BenchmarkLockMap_Read_Write_10_1 4263 271487 ns/op 36 B/op 1 allocs/op
BenchmarkLockMap_Read_Write_10_1-2 676 1726200 ns/op 154 B/op 1 allocs/op
BenchmarkLockMap_Read_Write_10_1-4 604 2007962 ns/op 172 B/op 1 allocs/op
// 50 readers vs 1 writer: on 2.4 CPUs, LR-map is 2x faster than RWMutex-map
BenchmarkLRMap_Read_Write_50_1 586 1733163 ns/op 310 B/op 1 allocs/op
BenchmarkLRMap_Read_Write_50_1-2 340 3532511 ns/op 527 B/op 1 allocs/op
BenchmarkLRMap_Read_Write_50_1-4 367 3192197 ns/op 493 B/op 1 allocs/op
BenchmarkLockMap_Read_Write_50_1 1004 1177003 ns/op 101 B/op 1 allocs/op
BenchmarkLockMap_Read_Write_50_1-2 223 5803691 ns/op 433 B/op 1 allocs/op
BenchmarkLockMap_Read_Write_50_1-4 195 5741745 ns/op 466 B/op 1 allocs/op
// 100 readers vs 1 writer: on 2.4 CPUs, LR-map is 2x faster than RWMutex-map
BenchmarkLRMap_Read_Write_100_1 384 3126528 ns/op 471 B/op 1 allocs/op
BenchmarkLRMap_Read_Write_100_1-2 182 6503080 ns/op 974 B/op 1 allocs/op
BenchmarkLRMap_Read_Write_100_1-4 182 6345014 ns/op 969 B/op 1 allocs/op
BenchmarkLockMap_Read_Write_100_1 500 2351661 ns/op 188 B/op 1 allocs/op
BenchmarkLockMap_Read_Write_100_1-2 100 10701998 ns/op 973 B/op 2 allocs/op
BenchmarkLockMap_Read_Write_100_1-4 124 10646446 ns/op 776 B/op 1 allocs/op
What
- Left-Right is a technique with some similarities with Double Instance Locking because it uses two instances, and has a mutex to serialize mutations. In this sense, it is reminiscent of the “Double Buffering” technique used in computer graphics.
- Left-Right is a generic, linearizable, technique that can provide mutual exclusivity for any object in memory or data structure
- Left-Right is non-blocking for read-only operations, and fast
- it is Wait-Free Population Oblivious
See all the details: link
How
go get github.com/csimplestring/go-left-right
Then you can use it to wrap any data structures. See the below example.
import github.com/csimplestring/go-left-right/primitive
type LRMap struct {
*primitive.LeftRightPrimitive
// you have to provides 2 identical instances
left map[int]int
right map[int]int
}
func newIntMap() *LRMap {
m := &LRMap{
left: make(map[int]int),
right: make(map[int]int),
}
m.LeftRightPrimitive = primitive.New()
return m
}
func (lr *LRMap) Get(k int) (val int, exist bool) {
// Go does not have generics, so have to use interface{} for lambda's arguments
lr.ApplyReadFn(lr.left, lr.right, func(instance interface{}) {
m := instance.(map[int]int)
val, exist = m[k]
})
return
}
func (lr *LRMap) Put(key, val int) {
lr.ApplyWriteFn(lr.left, lr.right, func(instance interface{}) {
m := instance.(map[int]int)
m[key] = val
})
}
