天天看點
傳回

【并發程式設計】map 基本用法和常見錯誤以及如何實作線程安全的map類型

部落客介紹：

– 我是了 凡 微信公衆号【了凡銀河系】期待你的關注。未來大家一起加油啊~

前言

【并發程式設計】map 基本用法和常見錯誤以及如何實作線程安全的map類型

哈希表介紹

哈希表（Hash Table）這個資料結構，在Go語言基礎的時候就已經涉及過了。實作的就是key-value直接的映射關系，主要提供的方法包括Add、Lookup、Delete等。因為這種資料結構是一個基礎的資料結構，每個key都會有一個唯一的索引值，通過索引可以很快找到對應的值，是以使用哈希表進行資料的插入和讀取都是很快的。Go語言本身就内建了這樣一個資料結構，也就是map資料類型。

文章目錄

  • 前言
    • 哈希表介紹
  • map的基本使用方法
    • 總結
  • 常見錯誤
    • 第一種：未初始化
    • 第二種：并發讀寫
  • 如何實作線程安全的map類型？
    • 加讀寫鎖：擴充map，支援并發讀寫
    • 分片加鎖：更高效的并發map

map的基本使用方法

Go内建的map類型如下：

map[k]v

其中，key類型的K必須是可比較的（comparable），也就是可以通過 == 和 !=操作符進行比較；value的值和類型無所謂，可以是任意的類型，或者為nil。

在Go語言中，bool、整數、浮點數、複數、字元串、指針、Channel、接口都是可比較的、包含可比較元素的struct和數組，這倆也是可比較的，而slice、map、函數值都是不可比較的。

上面這些可比較的資料類型都可以作為map的key嗎？顯然不是。通常情況下，我們會選擇内建的基本類型，比如整數、字元串做key的類型、因為這樣最友善。

這裡有一點需要注意，如果使用struct類型做key其實是有坑的，以為你如果struct的某個字段值修改了，查詢map時無法擷取它add進去的值，如下例子：

type mapKey struct {
    key int
}

func main() {
    var m = make(mapKey]string)
    var key = mapKey{10}
    
    m[key] = "hello"
    fmt.Printf("m[key]=%s\n",m[key])
    
    // 修改key的字段的值後再次查詢map，無法擷取剛才add進去的值
    key.key = 100
    fmt.Printf("再次查詢m[key]=%s\n",m[key])
}

那該怎麼辦呢？如果要使用struct作為key，我們要保證struct對象在邏輯上是不可變的，這樣才會保證map的邏輯沒有問題。

以上就是選取key類型的注意點了。看一下使用map[key]函數時需要注意的一個知識點。在Go中，map[key]函數傳回結果可以是一個值，也可以是兩個值，這是容易讓人迷惑的地方。原因在于，如果擷取一個不存在的key對應的值時，會傳回零值。為了區分真正的零值和key不存在這兩種情況，可以根據第二個傳回值來區分，如下執行個體：

func main() {
    var m = make(map[string]int)
    m["a"] = 0
    fmt.Printf("a=%d; b=%d\n",m["a"],m["b"])
    
    av,aexisted := m["a"]
    bv,bexisted := m["b"]
    fmt.Printf("a=%d, existed: %t; b=%d, existed: %t\n", av, aexisted, bv, bexisted)
}

map是無序的，是以當周遊一個map對象的時候，疊代的元素的順序是不确定的，無法保證兩次周遊的順序是一樣的，也不能保證和插入的順序一直。是以，如果想要按照key的順序擷取map的值，需要先取出所有的key進行排序，然後按照這個排序的key依次擷取對應的值。而如果想要保證元素有序，比如按照元素插入的順序進行周遊，可以使用輔助的資料結構，比如orderedmap，來記錄插入順序。

總結

map的類型是map[key]，key類型的ke必須是可比較的，通常情況，會選擇内建的基本類型，比如整數、字元串做key的類型。如果要使用struct作為key，要保證struct對象在邏輯上是不可變的。在Go語言中，map[key]函數傳回結果可以是一個值，也可以是兩個值。map是無序的，如果我們想要保證周遊map時元素有序，可以使用輔助的資料結構，例如orderedmap。

常見錯誤

第一種：未初始化

和slice或者Mutex、RWmutex等struct類型不同，map對象必須在使用之前初始化。如果不初始化就直接指派的話，會出現panic異常，例如以下情況，m實力還沒有初始化就直接進行操作會導緻panic：

func main() {
    var m map[int]int
    m[100] = 100
}

解決辦法就是在第2行初始化這個執行個體 （m:=make(map[int]int)）。

從一個nil的map對象中擷取值不會panci，而且會得到零值，是以下面的代碼不會報錯：

func main() {
    var m map[int]int
    fmt.Println(m[100])
}

這樣應該可以意識到map的初始化問題。但有時候map作為一個struct字段的時候，就很容易忘記初始化了。

type Counter struct {
    Website string
    Start time.Time
    PageCounters map[string]int
}

func main() {
    var c Counter
    c.Website = "baidu.com"
    
    c.PageCounters["/"]++
}

是以，一定要記得“初始化不能忘”，目前還沒有檢測的工具。

第二種：并發讀寫

map類型是容易發生并發通路問題的。不注意就容易發生程式運作時并發讀寫導緻的panic。

Go語言内建的map對象不是線程安全的，并發讀寫的時候運作時會有檢查，遇到并發問題就會導緻panic。

例如：

func main() {
    var m = make(map[int],10) // 初始化一個map
    go func() {
        for {
            m[1] = 1 // 設定key
        }
    }()
    
    go func() {
        for {
            _ = m[2] // 通路這個map 
        }
    }
}

運作後根據錯誤資訊可以快速定位出來是哪一行出現了問題。

如何實作線程安全的map類型？

避免map并發讀寫panic的方式之一就是加鎖，考慮讀寫性能，可以使用讀寫鎖提供性能。

加讀寫鎖：擴充map，支援并發讀寫

比較高興的是，原本Go還沒有正式釋出泛型特性，是以不能實作一個通用的支援泛型的加鎖map。但是Go語言在2021.09.27 Go 1.18加入了泛型特性，當然也可以使用interface{}來模拟泛型寫，但是這樣就會很複雜，不如泛型方案更直接、性能更好。

map類型為例，示範利用讀寫鎖實作線程安全的map[int]int 類型：

// RWMap 一個讀寫鎖保護的線程安全的map
type RWMap struct { // 讀寫鎖保護下面的map字段
   sync.RWMutex
   m map[int]int
}

// NewRWMap 建立一個RWMap
func NewRWMap(n int) *RWMap  {
   return &RWMap{
      m: make(map[int]int, n),
   }
}

func (m *RWMap) Get(k int) (int, bool)  {
   m.RLock()
   defer m.RUnlock()
   v, existed := m.m[k]  // 設定一個鍵值對
   return v,existed
}

func (m *RWMap) Set(k int, v int) { // 設定一個鍵值對
   m.Lock()            // 鎖保護
   defer m.Unlock()
   m.m[k] = v
}

func (m *RWMap) Delete(k int)  {  // 删除一個鍵
   m.Lock()                     // 鎖保護
   defer m.Unlock()
   delete(m.m, k)
}

func (m *RWMap) Len() int  {  // map的長度
   m.RLock()           // 鎖保護
   defer m.RUnlock()
   return len(m.m)
}

func (m *RWMap) Each(f func(k, v int) bool)  {  // 周遊map
   m.RLock()   // 周遊期間一直持有讀鎖
   defer m.RUnlock()

   for k, v := range m.m {
      if !f(k, v){
         return
      }
   }
}

分片加鎖：更高效的并發map

雖然使用讀寫鎖可以提供線程安全的map，但是在大量并發讀寫的情況下，鎖的競争會非常激烈。鎖是性能下降的萬惡之源之一。

在并發程式設計中，一條原則就是盡量減少鎖的使用。一些單線程單程序的應用（比如redis等），基本上不需要使用鎖去解決并發線程通路的問題，是以可以取得很高的性能。但是對于Go開發的應用程式，并發是常用的一個特性，這種情況下，能做的就是，盡量減少鎖的粒度和鎖的持有時間。

當然，可以優化業務處理的代碼，以此來減少鎖的持有時間，比如将串行的操作程式設計并行的子任務執行。這次的重點是對同步原語的優化，如何減少鎖的粒度。

減少鎖的粒度常用的方法就是分片（Shard），将一把鎖分成幾把鎖，每個鎖控制一個分片。Go知名的分片并發map的實作是orcaman/concurrent-map。

它預設采用32個分片，GetShard是一個關鍵的方法，能夠根據key計算出分片索引。

var SHARD_COUNT = 32

// ConcurrentMap 分頁SHARD_COUNT個分片的map
type ConcurrentMap []*ConcurrentMapShared

type ConcurrentMapShared struct {
   items map[string]interface{}
   sync.RWMutex // Read Write mutex, guards access to internal map.
}

// New 建立并發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
}

func (m ConcurrentMap) GetShard(key string) *ConcurrentMapShared  {
   return m[uint(fnv32(key))%uint(SHARD_COUNT)]
}

增加或者查詢的時候，首先根據分片索引得到分片對象，然後對分片對象加鎖進行操作：

func (m ConcurrentMap) Set(key string, value interface{}) {
    // 根據key計算出對應的分片
    shard := m.GetShard(key)
    shard.Lock() // 對這個分片加鎖，執行業務操作
    shard.items[key] = value
    shard.Unlaock()
}

func (m ConcurrentMap) Get(key string) (interface{}, bool) {
    // 根據key計算出對應的分片
    shard := m.GetShard(key)
    shard.Rlock()
    // 從這個分片讀取key的值
    val, ok := shard.items[key]
    shard.RUnlock()
    return val, ok
}

除了GetShard方法，ConcurrentMap還提供了很多其他的方法。這些方法都是通過計算相應的分片實作的，目的是保證把鎖的粒度限制在分片上。

golang 并發程式設計 作業系統 map 加鎖
上一篇: 【并發程式設計】Once 基本用法和如何實作以及常見錯誤
下一篇: 【并發程式設計】Mutex （互斥鎖）發展分析

繼續閱讀