给hash表分片：降低锁粒度，提高锁性能

原创

浩成聊技术

发布于 2022-12-16 00:17:14

5190

发布于 2022-12-16 00:17:14

文章被收录于专栏：go进阶

锁就像漏斗，将并发处理的多个线程变成串行化的模式，我们可以构建一个支持成千上万并发的系统，但是如果锁处理的不好会严重影响系统的性能，就像拥有多条车道的高速公路变成了单行道。

举个例子，假如我们使用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计算数据存储的所在的分片，虽然消耗一点点计算资源但是解决了锁粒度大导致的锁性能问题，这是很值得的。