欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Golang sync.Map原理深入分析講解

 更新時間:2022年12月17日 14:33:46   作者:Onemorelight95  
go中map數(shù)據(jù)結(jié)構(gòu)不是線程安全的,即多個goroutine同時操作一個map,則會報錯,因此go1.9之后誕生了sync.Map,sync.Map思路來自java的ConcurrentHashMap

GO語言內(nèi)置的map

go語言內(nèi)置一個map數(shù)據(jù)結(jié)構(gòu),使用起來非常方便,但是它僅支持并發(fā)的讀,不支持并發(fā)的寫,比如下面的代碼:

在main函數(shù)中開啟兩個協(xié)程同時對m進行并發(fā)讀和并發(fā)寫,程序運行之后會報錯:

package main
func main()  {
	m := make(map[int]int)
	go func()  {
		for {
			_ = m[1]
		}
	}()
	go func()  {
		for {
			m[2] = 2
		}
	}()
	select {}
}

改進

既然不可以并發(fā)的寫,我們可以給map加一個讀寫鎖,這樣就不會有并發(fā)寫沖突的問題了:

import "sync"
func main() {
	m := make(map[int]int)
	var lock sync.RWMutex
	go func() {
		for {
			lock.RLock()
			_ = m[1]
			lock.RUnlock()
		}
	}()
	go func() {
		for {
			lock.Lock()
			m[2] = 2
			lock.Unlock()
		}
	}()
	select {}
}

這種方式的實現(xiàn)非常簡潔,但也存在一些問題,比如在map的數(shù)據(jù)非常大的情況下,一把鎖會導致大并發(fā)的客戶端共爭一把鎖。

sync.Map

sync.Map是官方在sync包中提供的一種并發(fā)map,使用起來非常簡單,和普通map相比,只有遍歷的方式有區(qū)別:

package main
import (
	"fmt"
	"sync"
)
func main() {
	var m sync.Map
	// 1. 寫入
	m.Store("apple", 1)
	m.Store("banana", 2)
	// 2. 讀取
	price, _ := m.Load("apple")
	fmt.Println(price.(int))
	// 3. 遍歷
	m.Range(func(key, value interface{}) bool {
		fruit := key.(string)
		price := value.(int)
		fmt.Println(fruit, price)
		return true
	})
	// 4. 刪除
	m.Delete("apple")
	// 5. 讀取或?qū)懭?
	m.LoadOrStore("peach", 3)
}

sync.Map是通過 read 和 dirty 兩個字段將讀寫分離,讀的數(shù)據(jù)存在只讀字段 read 上,將最新寫入的數(shù)據(jù)則存在 dirty 字段上。

讀取時會先查詢 read,不存在再查詢 dirty,寫入時則只寫入 dirty。

讀取 read 并不需要加鎖,而讀或?qū)?dirty 都需要加鎖,另外有 misses 字段來統(tǒng)計 read 被穿透的次數(shù)(被穿透指需要讀 dirty 的情況),超過一定次數(shù)則將 dirty 數(shù)據(jù)同步到 read 上,對于刪除數(shù)據(jù)則直接通過標記來延遲刪除。

在map + 鎖的基礎(chǔ)上,它有著幾個優(yōu)化點:

  • 空間換時間。 通過冗余的兩個數(shù)據(jù)結(jié)構(gòu)(read、dirty),實現(xiàn)加鎖對性能的影響。
  • 使用只讀數(shù)據(jù)(read),避免讀寫沖突。
  • 動態(tài)調(diào)整,miss次數(shù)多了之后,將dirty數(shù)據(jù)提升為read。
  • double-checking。
  • 延遲刪除。 刪除一個鍵值只是打標記,只有在提升dirty的時候才清理刪除的數(shù)據(jù)。
  • 優(yōu)先從read讀取、更新、刪除,因為對read的讀取不需要鎖。

sync.Map原理分析

sync.Map的結(jié)構(gòu)

sync.Map的實現(xiàn)在src/sync/map.go中,首先來看Map結(jié)構(gòu)體:

type Map struct {
    // 當涉及到臟數(shù)據(jù)(dirty)操作時候,需要使用這個鎖
    mu Mutex
    // read是一個只讀數(shù)據(jù)結(jié)構(gòu),包含一個map結(jié)構(gòu),
    // 讀不需要加鎖,只需要通過 atomic 加載最新的指正即可
    read atomic.Value // readOnly
    // dirty 包含部分map的鍵值對,如果操作需要mutex獲取鎖
    // 最后dirty中的元素會被全部提升到read里的map去
    dirty map[interface{}]*entry
    // misses是一個計數(shù)器,用于記錄read中沒有的數(shù)據(jù)而在dirty中有的數(shù)據(jù)的數(shù)量。
    // 也就是說如果read不包含這個數(shù)據(jù),會從dirty中讀取,并misses+1
    // 當misses的數(shù)量等于dirty的長度,就會將dirty中的數(shù)據(jù)遷移到read中
    misses int
}

上述結(jié)構(gòu)體中的read字段實際上是一個包含map的結(jié)構(gòu)體,該結(jié)構(gòu)體中的map是一個read map,對該map的訪問不需要加鎖,但是增加的元素不會被添加到這個map中,元素會被先增加到dirty中,后續(xù)才會被遷移到read只讀map中。

readOnly結(jié)構(gòu)體中還有一個amended字段,該字段是一個標志位,用來表示read map中的數(shù)據(jù)是否完整。假設(shè)當前要查找一個key,會先去read map中找,如果沒有找到,會判斷amended是否為true,如果為true,說明read map的數(shù)據(jù)不完整,需要去dirty map中找。

// readOnly is an immutable struct stored atomically in the Map.read field.
type readOnly struct {
    // m包含所有只讀數(shù)據(jù),不會進行任何的數(shù)據(jù)增加和刪除操作 
    // 但是可以修改entry的指針因為這個不會導致map的元素移動
    m       map[interface{}]*entry
    // 標志位,如果為true則表明當前read只讀map的數(shù)據(jù)不完整,dirty map中包含部分數(shù)據(jù)
    amended bool // true if the dirty map contains some key not in m.
}

entry

readOnly.mMap.dirty存儲的值類型是*entry,它包含一個指針p, 指向用戶存儲的value值,結(jié)構(gòu)如下:

type entry struct {
    p unsafe.Pointer // *interface{}
}

其中p對應著三種值:

  • p == nil: 鍵值已經(jīng)被刪除,且 m.dirty == nil,這個時候dirty在等待read的同步數(shù)據(jù)。
  • p == expunged: 鍵值已經(jīng)被刪除,但 m.dirty!=nil 且 m.dirty 不存在該鍵值(dirty已經(jīng)得到了read的數(shù)據(jù)同步,原來為nil的值已經(jīng)被標記為了expunged沒有被同步過來)。
  • 除以上情況,則鍵值對存在,存在于 m.read.m 中,如果 m.dirty!=nil 則也存在于 m.dirty

下面是sync.Map的結(jié)構(gòu)示意圖:

查找

查找元素會調(diào)用Load函數(shù),該函數(shù)的執(zhí)行流程:

  • 首先去read map中找值,不用加鎖,找到了直接返回結(jié)果。
  • 如果沒有找到就判斷read.amended字段是否為true,true說明dirty中有新數(shù)據(jù),應該去dirty中查找,開始加鎖。
  • 加完鎖以后又去read map中查找,因為在加鎖的過程中,m.dirty可能被提升為m.read。
  • 如果二次檢查沒有找到key,就去m.dirty中尋找,然后將misses計數(shù)加一。
// src/sync/map.go
// Load returns the value stored in the map for a key, or nil if no
// value is present.
// The ok result indicates whether value was found in the map.
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
    // 首先從只讀ready的map中查找,這時不需要加鎖
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    // 如果沒有找到,并且read.amended為true,說明dirty中有新數(shù)據(jù),從dirty中查找,開始加鎖了
    if !ok && read.amended {
        m.mu.Lock() // 加鎖
       // 又在 readonly 中檢查一遍,因為在加鎖的時候 dirty 的數(shù)據(jù)可能已經(jīng)遷移到了read中
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        // read 還沒有找到,并且dirty中有數(shù)據(jù)
        if !ok && read.amended {
            e, ok = m.dirty[key] //從 dirty 中查找數(shù)據(jù)
            // 不管m.dirty中存不存在,都將misses + 1
            // missLocked() 中滿足條件后就會把m.dirty中數(shù)據(jù)遷移到m.read中
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if !ok {
        return nil, false
    }
    return e.load()
}

misses計數(shù)

misses計數(shù)是有上限的,如果misses次數(shù)達到m.dirty的長度,就開始遷移數(shù)據(jù),程序會直接將m.dirty提升為m.read,然后將m.dirty置為nil,等到下次插入新數(shù)據(jù)的時候,程序才會把read map中的值全部復制給dirty map。

// src/sync/map.go
func (m *Map) missLocked() {
    m.misses++
    if m.misses < len(m.dirty) {//misses次數(shù)小于 dirty的長度,就不遷移數(shù)據(jù),直接返回
        return
    }
    m.read.Store(readOnly{m: m.dirty}) //開始遷移數(shù)據(jù)
    m.dirty = nil   //遷移完dirty就賦值為nil
    m.misses = 0  //遷移完 misses歸0
}

新增和更新

新增或者更新元素會調(diào)用Store函數(shù),該函數(shù)的前面幾個步驟與Load函數(shù)是一樣的:

  • 首先去read map中找值,不用加鎖,找到了直接調(diào)用tryStore()函數(shù)更新值即可。
  • 如果沒有找到就開始對dirty map加鎖,加完鎖之后再次去read map中找值,如果存在就判斷該key對應的entry有沒有被標記為unexpunge,如果沒有被標記,就直接調(diào)用storeLocked()函數(shù)更新值即可。
  • 如果在read map中進行二次檢查還是沒有找到key,就去dirty map中找,找到了直接調(diào)用storeLocked()函數(shù)更新值。
  • 如果dirty map中也沒有這個key,說明是新加入的key,首先要將read.amended標記為true,然后將read map中未刪除的值復制到dirty中,最后向dirty map中加入這個值。
// src/sync/map.go
// Store sets the value for a key.
func (m *Map) Store(key, value interface{}) {
   // 直接在read中查找值,找到了,就嘗試 tryStore() 更新值
    read, _ := m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok && e.tryStore(&value) {
        return
    }
    // m.read 中不存在
    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok {
        if e.unexpungeLocked() { // 未被標記成刪除,前面講到entry數(shù)據(jù)結(jié)構(gòu)時,里面的p值有3種。1.nil 2.expunged,這個值含義有點復雜,可以看看前面entry數(shù)據(jù)結(jié)構(gòu) 3.正常值
            m.dirty[key] = e // 加入到dirty里
        }
        e.storeLocked(&value) // 更新值
    } else if e, ok := m.dirty[key]; ok { // 存在于 dirty 中,直接更新
        e.storeLocked(&value)
    } else { // 新的值
        if !read.amended { // m.dirty 中沒有新數(shù)據(jù),增加到 m.dirty 中
            // We're adding the first new key to the dirty map.
            // Make sure it is allocated and mark the read-only map as incomplete.
            m.dirtyLocked() // 從 m.read中復制未刪除的數(shù)據(jù)
            m.read.Store(readOnly{m: read.m, amended: true}) 
        }
        m.dirty[key] = newEntry(value) //將這個entry加入到m.dirty中
    }
    m.mu.Unlock()
}

在Store函數(shù)中我們用到了兩個用于更新值的函數(shù):tryStore以及storeLockedtryStore函數(shù)是先判斷p有沒有被標記為expunged(軟刪除),如果被標記了就直接返回false,如果沒有被標記,就將p指向的值進行更新然后返回true。

storeLocked函數(shù)是直接將p指向的值進行更新。

// tryStore stores a value if the entry has not been expunged.
//
// If the entry is expunged, tryStore returns false and leaves the entry
// unchanged.
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
		}
	}
}
// storeLocked unconditionally stores a value to the entry.
//
// The entry must be known not to be expunged.
func (e *entry) storeLocked(i *interface{}) {
	atomic.StorePointer(&e.p, unsafe.Pointer(i))
}

將read map中的值復制到dirty map中:

m.dirtyLocked()函數(shù)用于將read map中的值復制到dirty map中:

func (m *Map) dirtyLocked() {
	if m.dirty != nil {
		return
	}
	read, _ := m.read.Load().(readOnly)
	m.dirty = make(map[interface{}]*entry, len(read.m))
	for k, e := range read.m {
		// 判斷值是否被刪除,被標記為expunged的值不會被復制到read map中
		if !e.tryExpungeLocked() {
			m.dirty[k] = e
		}
	}
}
// expunged實際上是一個指向空接口的unsafe指針
var expunged = unsafe.Pointer(new(interface{}))
func (e *entry) tryExpungeLocked() (isExpunged bool) {
	p := atomic.LoadPointer(&e.p)
	// 如果p為nil,就會被標記為expunged
	for p == nil {
		if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
			return true
		}
		p = atomic.LoadPointer(&e.p)
	}
	return p == expunged
}

下面是對sync.Map進行讀寫操作的示意圖,正常讀寫且read map中有數(shù)據(jù),程序只會訪問read map,而不會去加鎖:

刪除

刪除會調(diào)用Delete函數(shù),該函數(shù)的步驟如下:

  • 首先去read map中找key,找到了就調(diào)用e.delete()函數(shù)刪除。
  • 如果在read map中沒有找到值就開始對dirty map加鎖,加鎖完畢之后再次去read map中查找,找到了就調(diào)用e.delete()函數(shù)刪除。
  • 如果二次檢查都沒有找到key(說明這個key是被追加之后,還沒有提升到read map中就要被刪除),就去dirty map中刪除這個key。
// src/sync/map.go
// Delete deletes the value for a key.
func (m *Map) Delete(key interface{}) {
    // 從 m.read 中開始查找
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    if !ok && read.amended { // m.read中沒有找到,并且可能存在于m.dirty中,加鎖查找
        m.mu.Lock() // 加鎖
        read, _ = m.read.Load().(readOnly) // 再在m.read中查找一次
        e, ok = read.m[key]
        if !ok && read.amended { //m.read中又沒找到,amended標志位true,說明在m.dirty中
            delete(m.dirty, key) // 刪除
        }
        m.mu.Unlock()
    }
    if ok { // 在 m.read 中就直接刪除
        e.delete()
    }
}
func (e *entry) delete() (hadValue bool) {
	for {
		p := atomic.LoadPointer(&e.p)
		// 已標記為刪除
		if p == nil || p == expunged {
			return false
		}
		// 原子操作,e.p標記為nil,GO的GC會將對象自動刪除
		if atomic.CompareAndSwapPointer(&e.p, p, nil) {
			return true
		}
	}
}

key究竟什么時候會被刪除

我們可以發(fā)現(xiàn),如果read map中存在待刪除的key時,程序并不會去直接刪除這個key,而是將這個key對應的p指針指向nil。

在下一次read -> dirty的同步時,指向nil的p指針會被標記為expunged,程序不會將被標記為expunged的 key 同步過去。

等到再一次dirty -> read同步的時候,read會被dirty直接覆蓋,這個時候被標記為expunged的key才真正被刪除了,這就是sync.Map的延遲刪除。

到此這篇關(guān)于Golang sync.Map原理深入分析講解的文章就介紹到這了,更多相關(guān)Golang sync.Map內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • 使用Go構(gòu)建一款靜態(tài)分析工具Owl詳解

    使用Go構(gòu)建一款靜態(tài)分析工具Owl詳解

    Owl是一款開源項目依賴分析工具,可以快速在指定的項目目錄下查找符合某些特征的源代碼文件或者依賴文件,這篇文章主要介紹了使用Go構(gòu)建一款靜態(tài)分析工具,需要的朋友可以參考下
    2022-06-06
  • Golang文件操作之讀取與寫入方法全攻略

    Golang文件操作之讀取與寫入方法全攻略

    本文詳細介紹了在Go語言中進行文件操作的方法,包括文件的創(chuàng)建、打開、讀取、寫入和關(guān)閉等,解析了使用os、bufio和io包進行高效文件操作的技巧,并提供了錯誤處理與性能優(yōu)化的建議,以幫助開發(fā)者有效管理文件資源并提升應用性能,需要的朋友可以參考下
    2024-11-11
  • go語言中嵌套結(jié)構(gòu)體的實現(xiàn)

    go語言中嵌套結(jié)構(gòu)體的實現(xiàn)

    在Go語言中,嵌套結(jié)構(gòu)體可定義為一個結(jié)構(gòu)體內(nèi)包含另一個結(jié)構(gòu)體,嵌套可以是值嵌套或指針嵌套,兩者在內(nèi)存分配和修改影響上有顯著區(qū)別,本文就來詳細的介紹一下,感興趣的可以了解一下
    2024-09-09
  • Golang算法問題之整數(shù)拆分實現(xiàn)方法分析

    Golang算法問題之整數(shù)拆分實現(xiàn)方法分析

    這篇文章主要介紹了Golang算法問題之整數(shù)拆分實現(xiàn)方法,結(jié)合實例形式分析了Go語言數(shù)值運算與數(shù)組遍歷相關(guān)操作技巧,需要的朋友可以參考下
    2017-02-02
  • Golang觀察者模式優(yōu)化訂單處理系統(tǒng)實例探究

    Golang觀察者模式優(yōu)化訂單處理系統(tǒng)實例探究

    當涉及到訂單處理系統(tǒng)時,觀察者設(shè)計模式可以用于實現(xiàn)訂單狀態(tài)的變化和通知,在這篇文章中,我們將介紹如何使用Golang來實現(xiàn)觀察者設(shè)計模式,并提供一個基于訂單處理系統(tǒng)的代碼示例
    2024-01-01
  • go編程中g(shù)o-sql-driver的離奇bug解決記錄分析

    go編程中g(shù)o-sql-driver的離奇bug解決記錄分析

    這篇文章主要為大家介紹了go編程中g(shù)o-sql-driver的離奇bug解決記錄分析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2023-05-05
  • Go中過濾范型集合性能示例詳解

    Go中過濾范型集合性能示例詳解

    這篇文章主要為大家介紹了Go中過濾范型集合性能示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2023-03-03
  • golang 字符串切片去重實例

    golang 字符串切片去重實例

    這篇文章主要介紹了golang 字符串切片去重實例,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-12-12
  • 深入理解Go工作池

    深入理解Go工作池

    本文主要介紹了深入理解Go工作池,通過緩存通道控制goroutine數(shù)量,避免資源浪費,具有一定的參考價值,感興趣的可以了解一下
    2025-05-05
  • Go 語言中程序編譯過程詳解

    Go 語言中程序編譯過程詳解

    本文旨在深入探討Go語言的編譯機制和最新的模塊管理系統(tǒng)——Go Modules,通過詳細的示例和步驟,我們將演示從簡單的 “Hello World” 程序到使用第三方庫的更復雜項目的開發(fā)過程,感興趣的朋友跟隨小編一起看看吧
    2024-05-05

最新評論