关于go:给hash表分片降低锁粒度提高锁性能

3次阅读

共计 1831 个字符，预计需要花费 5 分钟才能阅读完成。

锁就像漏斗，将并发解决的多个线程变成串行化的模式，咱们能够构建一个反对成千上万并发的零碎，然而如果锁解决的不好会重大影响零碎的性能，就像领有多条车道的高速公路变成了单行道。

举个例子，如果咱们应用 go 的map来实现一个简略的缓存，因为 map 不是并发平安, 所以咱们还要借助 sync 包的锁来保障并发平安，于是咱们很容易写出上面这样的代码：

package simple_cache

import ("sync")

type Cache struct {items map[string][]byte
    lock  *sync.RWMutex
}

func New() *Cache {
    return &Cache{items: make(map[string][]byte, 2000),
        lock:  new(sync.RWMutex),
    }
}

func (c *Cache) Get(key string) []byte {
    // 取数据只有加读锁
    c.lock.RLock()
    defer c.lock.RUnlock()
    return c.items[key]
}

func (c *Cache) Set(key string, data []byte) {c.lock.Lock()
    defer c.lock.Unlock()
    c.items[key] = data
}

这段代码思考到了锁其实曾经算是不错了，然而每次调用 set() 办法去设置缓存值的时候不仅将并发读写变成了串行化的模式，就连 get() 办法也会被阻塞住。在理论生产中应用这段代码作为缓存的时候，map中会缓存大量数据，set()调用可能会很频繁，而且在 set() 内还须要判断缓存的容量是否足够，这些都会使锁的工夫变长。

而后咱们不得不思考如何优化一下锁的性能。下面代码的问题是每次 set() 都锁住了整个 map, 于是咱们就想到能不能只锁住一部分，这样就能升高锁对性能的耗费。咱们能够把原先这个大的缓存分成若干个小的分片，每个分片就是原先的一个Cache, 而后再将这些分片放入一个大的map 中，依据缓存 key 值通过 hash 计算后的值找到对应的分片。对下面代码革新如下：

package simple_cache

import (
    "crypto/sha1"
    "fmt"
    "sync"
)

type Cache map[string]*ShardCache

type ShardCache struct {items map[string][]byte
    lock  *sync.RWMutex
}

func NewCache() *Cache {cache := make(Cache, 256)
    for i := 0; i < 256; i++ {cache[fmt.Sprintf("%02x", i)] = &ShardCache{items: make(map[string][]byte, 2000),
            lock:  new(sync.RWMutex),
        }
    }
    return &cache
}

func (c Cache) getShard(key string) *ShardCache {hasher := sha1.New()
    hasher.Write([]byte(key))
        // 转 16 进制后取前两位
    shardKey := fmt.Sprintf("%x", hasher.Sum(nil))[0:2]
    return c[shardKey]
}

func (c Cache) Get(key string) []byte {
    // 取数据只有加读锁
    shard := c.getShard(key)
    shard.lock.RLock()
    defer shard.lock.RUnlock()
    return shard.items[key]
}

func (c Cache) Set(key string, data []byte) {shard := c.getShard(key)
    shard.lock.Lock()
    shard.lock.Unlock()
    shard.items[key] = data
}

这里咱们一共给缓存设置了 256（16^2）个分片，对于任意的一个缓存 key 值通过 hash 后通过 fmt.Sprintf("%x", hasher.Sum(nil))[0:2] 转 16 进制后取前两位后都能在缓存中找到对应的分片

其实像 java 外面的 ConcurrencyHashmap 曾经是这样做的了，咱们通过 hash 计算数据存储的所在的分片，尽管耗费一点点计算资源然而解决了锁粒度大导致的锁性能问题，这是很值得的。