怎么处理锁分段

题目序号：（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各自的锁

}

主流的分段锁，即通过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的并发特性使得解决这类问题变得非常简单