题目序号：（2270）
题目来源：网易互娱
频次：1
# 答案1：（ORVR）
在golang的原生map是非并发安全的，为了实现了map的并发安全，最安全有效的方式就是给map加锁，如果遇到大数据，高并发的场景下，直接对整个map进行加锁的话，就会显得整个并发访问控制及其缓慢，由此在sync.map还未出来之前，比较流行的做法就是使用分段锁，降低锁的颗粒度，从而使每个分片上的数据读写互不影响，从而提高map整体的读写效率
模拟分段锁实现
// Map 分片
type ConcurrentMap []*ConcurrentMapShared
// 每一个Map 是一个加锁的并发安全Map
type ConcurrentMapShared struct {
items map[string]interface{}
sync.RWMutex // 各个分片Map各自的锁
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
主流的分段锁，即通过hash取模的方式找到当前访问的key处于哪一个分片之上，再对该分片进行加锁之后再读写。分片定位时，常用有BKDR, FNV32等hash算法得到key的hash值。
func New() ConcurrentMap {
// SHARD_COUNT 默认32个分片
m := make(ConcurrentMap, SHARD_COUNT)
for i := 0; i < SHARD_COUNT; i++ {
m[i] = &ConcurrentMapShared{
items: make(map[string]interface{}),
}
}
return m
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
在初始化好分片后， 对分片上的数据进行读写时就需要用hash取模进行分段定位来确认即将要读写的分片。
func (m ConcurrentMap) GetShard(key string) *ConcurrentMapShared {
return m[uint(fnv32(key))%uint(SHARD_COUNT)]
}
// FNV hash
func fnv32(key string) uint32 {
hash := uint32(2166136261)
const prime32 = uint32(16777619)
for i := 0; i < len(key); i++ {
hash *= prime32
hash ^= uint32(key[i])
}
return hash
}
func (m ConcurrentMap) Set(key string, value interface{}) {
shard := m.GetShard(key) // 段定位找到分片
shard.Lock() // 分片上锁
shard.items[key] = value // 分片操作
shard.Unlock() // 分片解锁
}
func (m ConcurrentMap) Get(key string) (interface{}, bool) {
shard := m.GetShard(key)
shard.RLock()
val, ok := shard.items[key]
shard.RUnlock()
return val, ok
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
由此一个分段锁Map就实现了， 但是比起普通的Map, 常用到的方法比如获取所有key, 获取所有Val 操作是要比原生Map复杂的，因为要遍历每一个分片的每一个数据， 好在golang的并发特性使得解决这类问题变得非常简单