導(dǎo)語?|?在召回排序業(yè)務(wù)中，由于上游請(qǐng)求量較大，對(duì)下游存儲(chǔ)服務(wù)造成較大壓力，業(yè)務(wù)場(chǎng)景要求高性能和非強(qiáng)一致性，所以我采用golang并發(fā)安全k-v緩存開源庫(kù)進(jìn)行性能優(yōu)化，以下是對(duì)其調(diào)研、對(duì)比分析。如有錯(cuò)誤，請(qǐng)多指正。

一、Golang map

（一）并發(fā)讀寫測(cè)試

在Golang中原生map在并發(fā)場(chǎng)景下，同時(shí)讀寫是線程不安全的，無論key是否一樣。以下是測(cè)試代碼：

package main
import "time"
func main() {  testMapReadWriteDiffKey()}
func testMapReadWriteDiffKey() {  m := make(map[int]int)  go func() {    for {      m[100] = 100    }  }()  go func() {    for {      _ = m[12]    }  }()  select {}}

如上圖的demo，并發(fā)讀寫map的不同key，運(yùn)行結(jié)果如下：

map讀的時(shí)候會(huì)檢查hashWriting標(biāo)志，如果有這個(gè)標(biāo)志，就會(huì)報(bào)并發(fā)錯(cuò)誤。寫的時(shí)候會(huì)設(shè)置這個(gè)標(biāo)志：h.flags|=hashWriting.設(shè)置完之后會(huì)取消這個(gè)標(biāo)記。map的并發(fā)問題不是那么容易被發(fā)現(xiàn), 可以利用-race參數(shù)來檢查。map并發(fā)讀寫沖突檢測(cè)機(jī)制不是本文的重點(diǎn)，不過感興趣的同學(xué)可以通過以下鏈接深入了解下。

相關(guān)文章分析：

https://medium.com/a-journey-with-go/go-concurrency-access-with-maps-part-iii-8c0a0e4eb27e

編譯時(shí)的選項(xiàng)-race，為何能分析出并發(fā)問題，詳見：

go官方博客：https://go.dev/blog/race-detector

文章分析：

https://medium.com/@blanchon.vincent/go-race-detector-with-threadsanitizer-8e497f9e42db

視頻講解：

https://www.youtube.com/watch?v=5erqWdlhQLA

（二）map+讀寫鎖

在官方庫(kù)sync.map沒出來前，Go maps in action推薦的做法是使用map+RWLock，比如定義一個(gè)匿名struct變量，其包含map、RWLock，如下所示：

var counter = struct{    sync.RWMutex    m map[string]int}{m: make(map[string]int)}

可以這樣從counter中讀數(shù)據(jù)

counter.RLock()n := counter.m["some_key"]counter.RUnlock()fmt.Println("some_key:", n)

可以這樣往counter中寫數(shù)據(jù)

counter.Lock()counter.m["some_key"]++counter.Unlock()

那Go 1.9版本實(shí)現(xiàn)的sync.map和上面的這種實(shí)現(xiàn)方式有什么不同？它適用于哪些場(chǎng)景呢？它在哪些方面做了性能優(yōu)化呢？

二、sync.map

sync.map是用讀寫分離實(shí)現(xiàn)的，其思想是空間換時(shí)間。和map+RWLock的實(shí)現(xiàn)方式相比，它做了一些優(yōu)化：可以無鎖訪問read map，而且會(huì)優(yōu)先操作read map，倘若只操作read map就可以滿足要求(增刪改查遍歷)，那就不用去操作write map(它的讀寫都要加鎖)，所以在某些特定場(chǎng)景中它發(fā)生鎖競(jìng)爭(zhēng)的頻率會(huì)遠(yuǎn)遠(yuǎn)小于map+RWLock的實(shí)現(xiàn)方式。

接下來著重介紹下sync.map的源碼，以了解其運(yùn)作原理。

sync.map源碼：

https://github.com/golang/go/blob/master/src/sync/map.go

（一）變量介紹

結(jié)構(gòu)體Map

type Map struct { // 互斥鎖mu，操作dirty需先獲取mu mu Mutex 
// read是只讀的數(shù)據(jù)結(jié)構(gòu)，訪問它無須加鎖，sync.map的所有操作都優(yōu)先讀read // read中存儲(chǔ)結(jié)構(gòu)體readOnly，readOnly中存著真實(shí)數(shù)據(jù)---entry（詳見1.3），read是dirty的子集 // read中可能會(huì)存在臟數(shù)據(jù)：即entry被標(biāo)記為已刪除(詳見1.3)read atomic.Value // readOnly
 // dirty是可以同時(shí)讀寫的數(shù)據(jù)結(jié)構(gòu)，訪問它要加鎖，新添加的key都會(huì)先放到dirty中 // dirty == nil的情況：1.被初始化 2.提升為read后，但它不能一直為nil，否則read和dirty會(huì)數(shù)據(jù)不一致。 // 當(dāng)有新key來時(shí)，會(huì)用read中的數(shù)據(jù) (不是read中的全部數(shù)據(jù)，而是未被標(biāo)記為已刪除的數(shù)據(jù)，詳見3.2)填充dirty // dirty != nil時(shí)它存著sync.map的全部數(shù)據(jù)（包括read中未被標(biāo)記為已刪除的數(shù)據(jù)和新來的數(shù)據(jù)） dirty map[interface{}]*entry 
 // 統(tǒng)計(jì)訪問read沒有未命中然后穿透訪問dirty的次數(shù) // 若miss等于dirty的長(zhǎng)度，dirty會(huì)提升成read，提升后可以增加read的命中率，減少加鎖訪問dirty的次數(shù)    misses int}

結(jié)構(gòu)體readOnly

type readOnly struct {  m       map[interface{}]*entry  amended bool }

第一點(diǎn)的結(jié)構(gòu)read存的就是readOnly，m是一個(gè)map，key是interface，value是指針entry，其指向真實(shí)數(shù)據(jù)的地址，amended等于true代表dirty中有readOnly.m中不存在的entry。

結(jié)構(gòu)體entry

type entry struct {       // p == nil：entry已從readOnly中刪除但存在于dirty中       // p == expunged：entry已從Map中刪除且不在dirty中       // p == 其他值：entry為正常值       p unsafe.Pointer // *interface{}}

entry中的指針p指向真正的value所在的地址，dirty和readOnly.m存的值類型就是*entry。這里的nil和expunged有什么作用呢？只要nil不可以嗎？對(duì)于這些問題后面會(huì)一一解讀。

（二）函數(shù)介紹

下面介紹下sync.Map的四個(gè)方法：Load、Store、Delete、Range

Load方法

圖解

源碼分析

Load方法用來加載sync.Map中的值，入?yún)⑹莐ey，返回值是對(duì)應(yīng)的value以及value存在與否

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {    // 從m.read中換出readOnly，然后從里面找key，這個(gè)過程不加鎖    read, _ := m.read.Load().(readOnly)    e, ok := read.m[key]
    // readOnly中不存在此key但Map.dirty可能存在    if !ok && read.amended {        // 加鎖訪問Map.dirty        m.mu.Lock()        // 雙重檢測(cè):若加鎖前Map.dirty被替換為readonly，則前面m.read.Load().(readOnly)無效，需                 // 要再次檢查        read, _ = m.read.Load().(readOnly)        e, ok = read.m[key]        // read.m沒有此key && dirty里有可能有（dirty中有read.m沒有的數(shù)據(jù)）        if !ok && read.amended {            // 從dirty中獲取key對(duì)應(yīng)的entry            e, ok = m.dirty[key]            // 無論Map.dirty中是否有這個(gè)key，miss都加一，若miss大小等于dirty的長(zhǎng)度，dirty中的元素會(huì)被            // 加到Map.read中            m.missLocked()        }        m.mu.Unlock()    }    if !ok {        return nil, false    }    // 若entry.p被刪除（等于nil或expunged）返回nil和不存在（false），否則返回對(duì)應(yīng)的值和存在（true）    return e.load()}

Map.dirty是如何提升為Map.read的呢？讓我們來看下missLocked方法

func (m *Map) missLocked() {        // 訪問一次Map.dirty，misses就要加一  m.misses++  if m.misses < len(m.dirty) {    return  }        // 當(dāng)misses等于dirty的長(zhǎng)度，m.dirty提升為readOnly，amended被默認(rèn)賦值成false  m.read.Store(readOnly{m: m.dirty})  m.dirty = nil  m.misses = 0}

小結(jié)：

Load方法會(huì)優(yōu)先無鎖訪問readOnly，未命中后如果Map.dirty中可能存在這個(gè)數(shù)據(jù)就會(huì)加鎖訪問Map.dirty。

Load方法如果訪問readOnly中不存在但dirty中存在的key，就要加鎖訪問Map.dirty從而帶來額外開銷。

Store方法

圖解

源碼解析

Store方法往Map里添加新的key和value或者更新value

func (m *Map) Store(key, value interface{}) {    // 把m.read轉(zhuǎn)成結(jié)構(gòu)體readOnly    read, _ := m.read.Load().(readOnly)    // 若key在readOnly.m中且entry.p不為expunged（沒有標(biāo)記成已刪除）即key同時(shí)存在于readOnly.m和dirty    // ,用CAS技術(shù)更新value 【注】：e.tryStore在entry.p == expunged時(shí)會(huì)立刻返回false，否則用CAS    // 嘗試更新對(duì)應(yīng)的value, 更新成功會(huì)返回true    if e, ok := read.m[key]; ok && e.tryStore(&value) {        return    }    // key不存在于readOnly.m或者entry.p==expunged(entry被標(biāo)記為已刪除)，加鎖訪問dirty    m.mu.Lock()    // 雙重檢測(cè)：若加鎖前Map.dirty被提升為readOnly，則前面的read.m[key]可能無效，所以需要再次檢測(cè)key是    // 否存在于readOnly中    read, _ = m.read.Load().(readOnly)    // 若key在于readOnly.m中    if e, ok := read.m[key]; ok {        // entry.p之前的狀態(tài)是expunged，把它置為nil        if e.unexpungeLocked() {            // 之前dirty中沒有此key，所以往dirty中添加此key              m.dirty[key] = e        }        // 更新（把value的地址原子賦值給指針entry.p）        e.storeLocked(&value)        // 若key在dirty中    } else if e, ok := m.dirty[key]; ok {         // 更新（把value的地址原子賦值給指針entry.p）        e.storeLocked(&value)      // 來了個(gè)新key    } else {         // dirty中沒有新數(shù)據(jù)，往dirty中添加第一個(gè)新key        if !read.amended {              // 把readOnly中未標(biāo)記為刪除的數(shù)據(jù)拷貝到dirty中            m.dirtyLocked()              // amended:true，因?yàn)楝F(xiàn)在dirty有readOnly中沒有的key            m.read.Store(readOnly{m: read.m, amended: true})        }        // 把這個(gè)新的entry加到dirty中        m.dirty[key] = newEntry(value)    }    m.mu.Unlock()}

func (e *entry) tryStore(i *interface{}) bool {  for {    p := atomic.LoadPointer(&e.p)    if p == expunged {      return false    }    if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {      return true    }  }}

func (e *entry) unexpungeLocked() (wasExpunged bool) {  return atomic.CompareAndSwapPointer(&e.p, expunged, nil)}

func (m *Map) dirtyLocked() {  if m.dirty != nil {  // 只要調(diào)用dirtyLocked，此時(shí)dirty肯定等于nil    return  }        // dirty為nil時(shí)，把readOnly中沒被標(biāo)記成刪除的entry添加到dirty  read, _ := m.read.Load().(readOnly)  m.dirty = make(map[interface{}]*entry, len(read.m))  for k, e := range read.m {                // tryExpungeLocked函數(shù)在entry未被刪除時(shí)【e.p!=expunged&&e.p!=nil】返回false，在                // e.p==nil時(shí)會(huì)將其置為expunged并返回true    if !e.tryExpungeLocked() {        m.dirty[k] = e  // entry沒被刪除，把它添加到dirty中    }  }}

小結(jié)：

Store方法優(yōu)先無鎖訪問readOnly，未命中會(huì)加鎖訪問dirty。

Store方法中的雙重檢測(cè)機(jī)制在下面的Load、Delete、Range方法中都會(huì)用到，原因是：加鎖前Map.dirty可能已被提升為Map.read，所以加鎖后還要再次檢查key是否存在于Map.read中。

dirtyLocked方法在dirty為nil（剛被提升成readOnly或者M(jìn)ap初始化時(shí)）會(huì)從readOnly中拷貝數(shù)據(jù)，如果readOnly中數(shù)據(jù)量很大，可能偶爾會(huì)出現(xiàn)性能抖動(dòng)。

sync.map不適合用于頻繁插入新key-value的場(chǎng)景，因?yàn)榇瞬僮鲿?huì)頻繁加鎖訪問dirty會(huì)導(dǎo)致性能下降。更新操作在key存在于readOnly中且值沒有被標(biāo)記為刪除(expunged)的場(chǎng)景下會(huì)用無鎖操作CAS進(jìn)行性能優(yōu)化，否則也會(huì)加鎖訪問dirty。

Delete方法

圖解

源碼解析

Delete方法把key從Map中刪掉，返回被刪除的值和是否刪除成功，它底層調(diào)用的是LoadAndDelete

func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {        // 從m.read中換出readOnly，然后從里面找key，此過程不加鎖  read, _ := m.read.Load().(readOnly)  e, ok := read.m[key]
        // readOnly不存在此key，但dirty中可能存在  if !ok && read.amended {                // 加鎖訪問dirty    m.mu.Lock()                // 雙重檢測(cè):若加鎖前Map.dirty被替換為readonly，則前面m.read.Load().(readOnly)無                 // 效，需要再次檢查    read, _ = m.read.Load().(readOnly)    e, ok = read.m[key]                // readOnly不存在此key，但是dirty中可能存在    if !ok && read.amended {      e, ok = m.dirty[key]      delete(m.dirty, key)      m.missLocked()    }    m.mu.Unlock()  }  if ok {                // 如果entry.p不為nil或者expunged，則把entry.p軟刪除（標(biāo)記為nil）    return e.delete()  }  return nil, false}

func (e *entry) delete() (value interface{}, ok bool) {  for {       p := atomic.LoadPointer(&e.p)    if p == nil || p == expunged {      return nil, false    }                // e.p是真實(shí)值，把它置為nil    if atomic.CompareAndSwapPointer(&e.p, p, nil) {      return *(*interface{})(p), true    }  }}

小結(jié)：

刪除readOnly中存在的key，可以不用加鎖。

如果刪除readOnly中不存在的或者M(jìn)ap中不存在的key，都需要加鎖。

Range方法

圖解

源碼解析

Range方法可遍歷Map，參數(shù)是個(gè)函數(shù)（入?yún)ⅲ簁ey和value，返回值：是否停止遍歷Range方法）

func (m *Map) Range(f func(key, value interface{}) bool) {      read, _ := m.read.Load().(readOnly)      if read.amended { // dirty存在readOnly中不存在的元素          // 加鎖訪問dirty         m.mu.Lock()          // 再次檢測(cè)read.amended，因?yàn)榧渔i前它可能已由true變成false         read, _ = m.read.Load().(readOnly)          if read.amended {              // readOnly.amended被默認(rèn)賦值成false              read = readOnly{m: m.dirty}              m.read.Store(read)              m.dirty = nil              m.misses = 0         }         m.mu.Unlock()     }     // 遍歷readOnly.m    for k, e := range read.m {          v, ok := e.load()          if !ok {             continue          }          if !f(k, v) {              break          }     } }

小結(jié)：

Range方法Map的全部key都存在于readOnly中時(shí)，是無鎖遍歷的，性能最高。

Range方法在readOnly只存在Map中的部分key時(shí)，會(huì)一次性加鎖拷貝dirty的元素到readOnly，減少多次加鎖訪問dirty中的數(shù)據(jù)。

（三）sync.map總結(jié)

使用場(chǎng)景

sync.Map更適合讀多更新多而插入新值少的場(chǎng)景（appendOnly模式，尤其是key存一次，多次讀而且不刪除的情況），因?yàn)樵趉ey存在的情況下讀寫刪操作可以不用加鎖直接訪問readOnly不適合反復(fù)插入與讀取新值的場(chǎng)景，因?yàn)檫@種場(chǎng)景會(huì)頻繁操作dirty，需要頻繁加鎖和更新read【此場(chǎng)景github開源庫(kù)orcaman/concurrent-map更合適】

設(shè)計(jì)點(diǎn):expunged

entry.p取值有3種，nil、expunged和指向真實(shí)值。那expunged出現(xiàn)在什么時(shí)候呢？為什么要有expunged的設(shè)計(jì)呢？它有什么作用呢？

什么時(shí)候expunged會(huì)出現(xiàn)呢？

當(dāng)用Store方法插入新key時(shí)，會(huì)加鎖訪問dirty，并把readOnly中的未被標(biāo)記為刪除的所有entry指針復(fù)制到dirty，此時(shí)之前被Delete方法標(biāo)記為軟刪除的entry（entry.p被置為nil）都變?yōu)閑xpunged，那這些被標(biāo)記為expunged的entry將不會(huì)出現(xiàn)在dirty中。

反向思維，如果沒有expunged，只有nil會(huì)出現(xiàn)什么結(jié)果呢？

直接刪掉entry==nil的元素，而不是置為expunged：在用Store方法插入新key時(shí)，readOnly數(shù)據(jù)拷貝到dirty時(shí)直接把為ni的entry刪掉。但這要對(duì)readOnly加鎖，sync.map設(shè)計(jì)理念是讀寫分離，所以訪問readOnly不能加鎖。

不刪除entry==nil的元素，全部拷貝：在用Store方法插入新key時(shí)，readOnly中entry.p為nil的數(shù)據(jù)全部拷貝到dirty中。那么在dirty提升為readOnly后這些已被刪除的臟數(shù)據(jù)仍會(huì)保留，也就是說它們會(huì)永遠(yuǎn)得不到清除，占用的內(nèi)存會(huì)越來越大。

不拷貝entry.p==nil的元素：在用Store方法插入新key時(shí)，不把readOnly中entry.p為nil的數(shù)據(jù)拷貝到dirty中，那在用Store更新值時(shí)，就會(huì)出現(xiàn)readOnly和dirty不同步的狀態(tài)，即readOnly中存在dirty中不存在的key，那dirty提升為readOnly時(shí)會(huì)出現(xiàn)數(shù)據(jù)丟失的問題。

（四）sync.map的其他問題

為什么sync.map不實(shí)現(xiàn)len方法？個(gè)人覺得還是成本和收益的權(quán)衡。

實(shí)現(xiàn)len方法要統(tǒng)計(jì)readOnly和dirty的數(shù)據(jù)量，勢(shì)必會(huì)引入鎖競(jìng)爭(zhēng)，導(dǎo)致性能下降，還會(huì)額外增加代碼實(shí)現(xiàn)復(fù)雜度。

對(duì)sync.map的并發(fā)操作導(dǎo)致其數(shù)據(jù)量可能變化很快，len方法的統(tǒng)計(jì)結(jié)果參考價(jià)值不大。

三、orcanman/concurrent-map

orcaman/concurrent-map的適用場(chǎng)景是：反復(fù)插入與讀取新值，其實(shí)現(xiàn)思路是：對(duì)go原生map進(jìn)行分片加鎖，降低鎖粒度，從而達(dá)到最少的鎖等待時(shí)間(鎖沖突)。

concurrent-map源碼地址：

https://github.com/orcaman/concurrent-map

它的實(shí)現(xiàn)比較簡(jiǎn)單，截取部分源碼如下：

（一）數(shù)據(jù)結(jié)構(gòu)

// SHARD_COUNT 分片大小var SHARD_COUNT = 32
type ConcurrentMap []*ConcurrentMapShared
// ConcurrentMapShared 分片的并發(fā)maptype ConcurrentMapShared struct {  items        map[string]interface{}  sync.RWMutex // 訪問內(nèi)部map都需要先獲取讀寫鎖}
// New 創(chuàng)建一個(gè)concurrent map.func New() ConcurrentMap {  m := make(ConcurrentMap, SHARD_COUNT)  for i := 0; i < SHARD_COUNT; i++ {    m[i] = &ConcurrentMapShared{items: make(map[string]interface{})}  }  return m}

（二）函數(shù)介紹?

GET方法

// 先hash拿到key對(duì)應(yīng)的分區(qū)號(hào)，然后加鎖，讀取值，最后釋放鎖和返回func (m ConcurrentMap) Get(key string) (interface{}, bool) {  // Get shard  shard := m.GetShard(key)  shard.RLock()  // Get item from shard.  val, ok := shard.items[key]  shard.RUnlock()  return val, ok}

?SET方法

// 先hash拿到key對(duì)應(yīng)的分區(qū)號(hào)，然后加鎖，設(shè)置新值，最后釋放鎖func (m ConcurrentMap) Set(key string, value interface{}) {  // Get map shard.  shard := m.GetShard(key)  shard.Lock()  shard.items[key] = value  shard.Unlock()}

Remove方法

// 先hash拿到key對(duì)應(yīng)的分區(qū)號(hào)，然后加鎖，刪除key，最后釋放鎖func (m ConcurrentMap) Remove(key string) {  // Try to get shard.  shard := m.GetShard(key)  shard.Lock()  delete(shard.items, key)  shard.Unlock()}

Count方法

// 分別拿到每個(gè)分片map中的元素?cái)?shù)量，然后匯總后返回func (m ConcurrentMap) Count() int {  count := 0  for i := 0; i < SHARD_COUNT; i++ {    shard := m[i]    shard.RLock()    count += len(shard.items)    shard.RUnlock()  }  return count}

Upsert方法

// 先hash拿到key對(duì)應(yīng)的分區(qū)號(hào)，然后加鎖，如果key存在就更新其value，否則插入新的k-v，釋放鎖并返回func (m ConcurrentMap) Upsert(key string, value interface{}, cb UpsertCb) (res interface{}) {  shard := m.GetShard(key)  shard.Lock()  v, ok := shard.items[key]  res = cb(ok, v, value)  shard.items[key] = res  shard.Unlock()  return res}

四、后續(xù)

當(dāng)然在其他業(yè)務(wù)場(chǎng)景中，我們可能更需要的是本地kv緩存組件庫(kù)并要求它們支持鍵過期時(shí)間設(shè)置、淘汰策略、存儲(chǔ)優(yōu)化、gc優(yōu)化等。這時(shí)候可能我們就需要去了解freecache、gocache、fastcache、bigcache、groupcache等組件庫(kù)了。

參考資料：

1.Golang fatal error: concurrent map read and map write.

2.sync: add Map.Len method?

3.concurrent map.?

?作者簡(jiǎn)介

clancyliang

騰訊后臺(tái)開發(fā)工程師

騰訊后臺(tái)開發(fā)工程師，個(gè)人微信公眾號(hào)：小梁編程匯，擅長(zhǎng)的編程語言有：golang、c、c++、java、python，擅長(zhǎng)的領(lǐng)域是后臺(tái)技術(shù)，諸如：計(jì)網(wǎng)：tcp/ip相關(guān)等、操作系統(tǒng)、算法（曾拿過ACM?ICPC亞洲區(qū)域賽銅牌）、分布式緩存、分布式事務(wù)等相關(guān)后臺(tái)技術(shù)。

?推薦閱讀

一探究竟！Whistle攔截HTTPS是如何實(shí)現(xiàn)的？

它來了，關(guān)于Golang并發(fā)編程的超詳細(xì)教程！

有的放矢，遠(yuǎn)程操控中實(shí)時(shí)音視頻的優(yōu)化之道

TVP三周年：聚力成長(zhǎng)，共赴新篇！