怎么处理锁分段

怎么处理锁分段

题目来源：网易互娱

答案1：

在golang的原生map是非并发安全的，为了实现了map的并发安全，最安全有效的方式就是给map加锁，如果遇到大数据，高并发的场景下，直接对整个map进行加锁的话，就会显得整个并发访问控制及其缓慢，由此在sync.map还未出来之前，比较流行的做法就是使用分段锁，降低锁的颗粒度，从而使每个分片上的数据读写互不影响，从而提高map整体的读写效率

模拟分段锁实现

// Map 分片
type ConcurrentMap []*ConcurrentMapShared
// 每一个Map 是一个加锁的并发安全Map
type ConcurrentMapShared struct {
    items map[string]interface{}
    sync.RWMutex // 各个分片Map各自的锁
}

主流的分段锁，即通过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
}

在初始化好分片后，对分片上的数据进行读写时就需要用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
}

由此一个分段锁Map就实现了，但是比起普通的Map, 常用到的方法比如获取所有key, 获取所有Val 操作是要比原生Map复杂的，因为要遍历每一个分片的每一个数据，好在golang的并发特性使得解决这类问题变得非常简单

参与讨论

211.怎么处理锁分段

怎么处理锁分段