Read-and-Write-in-High-Concurrency
问题
今天遇到一个高并发读写的问题。
具体的场景是,有一个“策略”的集合,然后每秒有很多消息进来,每一条消息都要匹配有没有对应的策略,如果有的话就应用策略(更改消息的某个属性),没有的话就返回。
抽象来看,就是在N多读的同时,怎样去写数据。
一开始我的方法是策略存在数组里,消息来了就去遍历数组,如果匹配到了就返回对应的规则。这种方法最笨,因为每一条消息过来,我都要去循环遍历整个数组,如果数组很长的话(有很多规则),那么带来的无谓开销会很大,复杂度为O(n)。
而且还一个问题,如果在range数组的时候,数组发生了变化,那么就会读到错误的值,或者崩溃。
一种解决的方法是,在遍历之前,首先拷贝一份新的,遍历新的策略数组,而不是原有的全局变量。这种方法的问题在于,每次匹配规则的时候,都要进行一次拷贝,虽然简单,也能解决问题,但,太浪费资源,而且很丑。
最终的思路是,用哈希表的方式去匹配策略,从复杂度上来看是O(1)的操作,但问题在于并发读写哈希表。
复现
为了更容易的表示问题,用了大量的并发读写(实际情况没有下面那么频繁,写操作要比读操作少得多得多):
package main
import (
"fmt"
"time"
)
var biu map[int]int
func read() {
for i := 0; i < len(biu); i++ {
if biu[i] != i {
fmt.Printf("%d != %d\n", biu[i], i)
panic("!")
}
}
}
func write() {
for i := 0; i < time.Now().Second(); i++ {
biu[i] = i
}
}
func main() {
biu = make(map[int]int)
go func() {
for {
go write()
time.Sleep(time.Millisecond)
}
}()
for {
go read()
time.Sleep(time.Millisecond)
}
}
会遇到下面的错误:
➜ rw-cocurrency go run main.go
fatal error: concurrent map read and map write
goroutine 146 [running]:
runtime.throw(0x4bd628, 0x21)
/opt/go/src/runtime/panic.go:605 +0x95 fp=0xc42002bf30 sp=0xc42002bf10 pc=0x427415
runtime.mapaccess1_fast64(0x4a0e40, 0xc4200740f0, 0x1, 0xc4200900d8)
/opt/go/src/runtime/hashmap_fast.go:119 +0x1a8 fp=0xc42002bf58 sp=0xc42002bf30 pc=0x40aa98
...
...
尝试方案
互斥锁(Mutex)
首先想到的是在读写的时候加锁,确保读和写不会同时发生。
var m sync.Mutex
func read() {
m.Lock()
defer m.Unlock()
for i := 0; i < len(biu); i++ {
if biu[i] != i {
fmt.Printf("%d != %d\n", biu[i], i)
panic("!")
}
}
}
func write() {
m.Lock()
defer m.Unlock()
for i := 0; i < time.Now().Second(); i++ {
biu[i] = i
}
}
但随之而来了另一个问题,如果每秒有1w的读,每分钟有1个写,那么我这1w/s的Lock
和UnLock
岂不是很尴尬?而且读的时候并不关心别人,只关心是否有写就行了。
所以,互斥锁就变成了读写锁。
读写锁(RWMutex)
这种锁的好处在于,读是可以并发的,Read Locker
并不会影响其他的读操作,但Write Locker
又是优先于Read Locker
,而且读和写互斥,即,如果有写操作发生,那么读操作会等待写完成,然后再读。
var m sync.RWMutex
func read() {
m.RLock()
defer m.RUnlock()
for i := 0; i < len(biu); i++ {
if biu[i] != i {
fmt.Printf("%d != %d\n", biu[i], i)
panic("!")
}
}
}
func write() {
m.Lock()
defer m.Unlock()
for i := 0; i < time.Now().Second(); i++ {
biu[i] = i
}
}
但是(凡是总有个但是),这样还是不够“高性能”,因为读的时候加锁还是有点丑。有没有更好的方案?
很高兴,golang在1.9中发布了官方的sync.Map
有位大佬写了详细的介绍:http://colobu.com/2017/07/11/dive-into-sync-Map/
sync.Map
// Map is a concurrent map with amortized-constant-time loads, stores, and deletes.
// It is safe for multiple goroutines to call a Map's methods concurrently.
//
// It is optimized for use in concurrent loops with keys that are
// stable over time, and either few steady-state stores, or stores
// localized to one goroutine per key.
//
// For use cases that do not share these attributes, it will likely have
// comparable or worse performance and worse type safety than an ordinary
// map paired with a read-write mutex.
//
// The zero Map is valid and empty.
//
It is optimized for use in concurrent loops with keys that are stable over time, and either few steady-state stores, or stores localized to one goroutine per key.
这句话我的理解是,如果map中的key很稳定,不会经常变动,或者并发操作不同的key,那这个map是比较厉害的。(不理解 few steady-state stores 是啥意思,如果有朋友看到了希望能帮忙解释一下)
所以,在以上我的情境中(读多写少),使用sync.Map
是没差的。
最终的代码就变成了:
package main
import (
"fmt"
"sync"
"time"
)
var biu sync.Map
func read() {
biu.Range(func(k, v interface{}) bool {
if k.(int) != v.(int) {
fmt.Printf("%d != %d\n", k.(int), v.(int))
panic("!")
}
return true
})
}
func write() {
for i := 0; i < time.Now().Second(); i++ {
biu.Store(i, i)
}
}
func main() {
go func() {
for {
go write()
time.Sleep(time.Millisecond)
}
}()
for {
go read()
time.Sleep(time.Millisecond)
}
}
总结
- 匹配不要用数组,用哈希表效率会更高
- 哈希表不能并发读写
Metux
和RWMutex
要根据场景选用sync.Map
很牛,但也不要滥用- 不要着急,凡事总会有办法