go src - sync.Map

来源:https://www.cnblogs.com/xpunch/archive/2023/07/01/sync_map.html
-Advertisement-
Play Games

前言 在併發編程中，我們經常會遇到多個goroutine同時操作一個map的情況。如果在這種情況下直接使用普通的map，那麼就可能會引發競態條件，造成數據不一致或者更嚴重的問題。 sync.Map是Go語言中內置的一種併發安全的map，但是他的實現和用法與普通的map完全不同，這篇文章將詳細介紹這些 ...


前言

在併發編程中，我們經常會遇到多個goroutine同時操作一個map的情況。如果在這種情況下直接使用普通的map，那麼就可能會引發競態條件，造成數據不一致或者更嚴重的問題。

sync.Map是Go語言中內置的一種併發安全的map，但是他的實現和用法與普通的map完全不同，這篇文章將詳細介紹這些區別。

一、使用方法

創建sync.Map非常簡單，只需要聲明即可：

var m sync.Map

使用Store方法存儲鍵值對：

m.Store("hello", "world")

使用Load方法獲取值：

value, ok := m.Load("hello")
if ok {
    fmt.Println(value) // 輸出：world
}

使用Delete方法刪除鍵值對：

m.Delete("hello")

二、原理

sync.Map的核心實現依賴於兩個主要的數據結構：一個只讀的read欄位，以及一個可寫的dirty欄位。

讀操作：

當我們進行讀取操作(Load)時，首先會嘗試從read欄位讀取數據，這個過程是完全無鎖的。

如果read中沒有找到，那麼會嘗試加鎖後從dirty中讀取。這個設計保證了在大部分讀多寫少的場景下，讀操作是無鎖的，大大提升了性能。

寫操作：

寫入操作(key不存在)時，會直接在dirty中進行寫入，並將read的amended標記為true，表示read欄位有待更新的數據。

然後再有新的讀取操作到來時，如果amended為true並且miss數量超過dirty長度，則會從dirty中拷貝數據到read，並清除amended標記。

 總結：

在這個設計中，讀操作在大部分情況下是無鎖的，而寫操作(key不存在時)則需要獲取dirty的鎖，從而實現了對於讀多寫少場景的優化。

三、優點

sync.Map在以下兩種情況下表現得特別好：

  • 鍵值對的數量相對穩定，讀操作明顯多於寫操作的場景
  • 多個goroutine併發讀取不重疊的鍵集的場景

這是因為sync.Map的設計將讀取操作優化至極致，同時儘量減少在寫入新鍵值對時的鎖競爭。

四、缺點

然而，sync.Map並不是銀彈，也有一些局限：

  • sync.Map沒有像普通map那樣的直觀語法，必須使用特定的方法來操作鍵值對
  • 對於鍵值對數量快速增長、寫操作頻繁的場景，sync.Map的性能可能不如使用普通map加鎖的方式
  • 讀操作無鎖情況下，可能會出現時間競態問題

五、實現

 sync.Map

type Map struct {
	mu Mutex

	// read contains the portion of the map's contents that are safe for
	// concurrent access (with or without mu held).
	read atomic.Pointer[readOnly]

	// dirty contains the portion of the map's contents that require mu to be
	// held. To ensure that the dirty map can be promoted to the read map quickly,
	// it also includes all of the non-expunged entries in the read map.
	dirty map[any]*entry

	// misses counts the number of loads since the read map was last updated that
	// needed to lock mu to determine whether the key was present.
	misses int
}

readonly

// readOnly is an immutable struct stored atomically in the Map.read field.
type readOnly struct {
	m       map[any]*entry
	amended bool // true if the dirty map contains some key not in m.
}

entry

// An entry is a slot in the map corresponding to a particular key.
type entry struct {
	// p points to the interface{} value stored for the entry.
	p atomic.Pointer[any]
}

expunged

// expunged is an arbitrary pointer that marks entries which have been deleted
// from the dirty map.
var expunged = new(any)

狀態機：

 總結：

  1. 當key從read中刪除時，會先被標記為nil，不會立馬刪除key
  2. 當重新初始化dirty時(將read.m克隆到dirty)，如果key的值為nil，會設置為expunged，並不在dirty中創建這個key。
  3. 如果key為expunged，LoadOrStore/Swap/CompareAndDelete/CompareAndSwap都會不執行寫操作並返回false。

Load

// 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 any) (value any, ok bool) {
	read := m.loadReadOnly()
	e, ok := read.m[key]
	if !ok && read.amended {
		m.mu.Lock()
		// Avoid reporting a spurious miss if m.dirty got promoted while we were
		// blocked on m.mu. (If further loads of the same key will not miss, it's
		// not worth copying the dirty map for this key.)
		read = m.loadReadOnly()
		e, ok = read.m[key]
		if !ok && read.amended {
			e, ok = m.dirty[key]
			// Regardless of whether the entry was present, record a miss: this key
			// will take the slow path until the dirty map is promoted to the read
			// map.
			m.missLocked()
		}
		m.mu.Unlock()
	}
	if !ok {
		return nil, false
	}
	return e.load()
}

func (m *Map) loadReadOnly() readOnly {
	if p := m.read.Load(); p != nil {
		return *p
	}
	return readOnly{}
}

 總結：

  1. 如果查詢的key在read中找到了，返回entry.load()
  2. 如果查詢的key在read中未找到，並且read和dirty一致，返回nil, false
  3. key未找到，並且read與dirty不一致
    1. 加鎖
    2. 重新查詢read，類似上面1、2流程，如果未找到並且read和dirty不一致則繼續
    3. 在dirty中查詢
    4. misses加一
    5. 如果misses數大於dirty長度，將dirty同步到read，重置dirty和misses
    6. 釋放鎖
    7. 返回結果

LoadOrStore

// LoadOrStore returns the existing value for the key if present.
// Otherwise, it stores and returns the given value.
// The loaded result is true if the value was loaded, false if stored.
func (m *Map) LoadOrStore(key, value any) (actual any, loaded bool) {
	// Avoid locking if it's a clean hit.
	read := m.loadReadOnly()
	if e, ok := read.m[key]; ok {
		actual, loaded, ok := e.tryLoadOrStore(value)
		if ok {
			return actual, loaded
		}
	}

	m.mu.Lock()
	read = m.loadReadOnly()
	if e, ok := read.m[key]; ok {
		if e.unexpungeLocked() {
			m.dirty[key] = e
		}
		actual, loaded, _ = e.tryLoadOrStore(value)
	} else if e, ok := m.dirty[key]; ok {
		actual, loaded, _ = e.tryLoadOrStore(value)
		m.missLocked()
	} else {
		if !read.amended {
			// 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.Store(&readOnly{m: read.m, amended: true})
		}
		m.dirty[key] = newEntry(value)
		actual, loaded = value, false
	}
	m.mu.Unlock()

	return actual, loaded
}

// tryLoadOrStore atomically loads or stores a value if the entry is not
// expunged.
//
// If the entry is expunged, tryLoadOrStore leaves the entry unchanged and
// returns with ok==false.
func (e *entry) tryLoadOrStore(i any) (actual any, loaded, ok bool) {
	p := e.p.Load()
	if p == expunged {
		return nil, false, false
	}
	if p != nil {
		return *p, true, true
	}

	// Copy the interface after the first load to make this method more amenable
	// to escape analysis: if we hit the "load" path or the entry is expunged, we
	// shouldn't bother heap-allocating.
	ic := i
	for {
		if e.p.CompareAndSwap(nil, &ic) {
			return i, false, true
		}
		p = e.p.Load()
		if p == expunged {
			return nil, false, false
		}
		if p != nil {
			return *p, true, true
		}
	}
}

 總結：

  1. 如果key在read中找到了，並且不為expunged
    1. 如果為nil，則CAS新的值，並返回value, false
    2. 如果不為nil，則返回*p, true
  2. 如果key在read中不存在，或者為expunged
    1. 加鎖
    2. 再次在read中查找，如果找到了
      1. 如果為expunged，結果為nil, false
      2. 如果為nil，則CAS新的值，結果為value, false
      3. 如果不為nil，結果為*p, true
    3. 如果在dirty中找到了，重覆2的邏輯判斷
    4. 在read和dirty中都沒有，則創建一個新的entry
    5. 釋放鎖
    6. 返回結果

Delete/LoadAndDelete

// Delete deletes the value for a key.
func (m *Map) Delete(key any) {
	m.LoadAndDelete(key)
}
// LoadAndDelete deletes the value for a key, returning the previous value if any.
// The loaded result reports whether the key was present.
func (m *Map) LoadAndDelete(key any) (value any, loaded bool) {
	read := m.loadReadOnly()
	e, ok := read.m[key]
	if !ok && read.amended {
		m.mu.Lock()
		read = m.loadReadOnly()
		e, ok = read.m[key]
		if !ok && read.amended {
			e, ok = m.dirty[key]
			delete(m.dirty, key)
			// Regardless of whether the entry was present, record a miss: this key
			// will take the slow path until the dirty map is promoted to the read
			// map.
			m.missLocked()
		}
		m.mu.Unlock()
	}
	if ok {
		return e.delete()
	}
	return nil, false
}

 總結：

  1. 如果要刪除的key在read中存在，將它置為nil
  2. 如果要刪除的key在read中未找到，並且read和dirty一致，說明key不存在，返回nil, false
  3. key未找到，並且read和dirty不一致
    1. 加鎖
    2. 重新查詢read，類似上面1、2流程，如果key未找到，並且read和dirty不一致繼續
    3. 在dirty中查詢並刪除
    4. misses加一
    5. 如果misses數大於dirty長度，將dirty同步到read，重置dirty和misses
    6. 釋放鎖
    7. 如果key在dirty中也不存在，返回nil, false；反之，將它置為nil

 Store/Swap

// Store sets the value for a key.
func (m *Map) Store(key, value any) {
	_, _ = m.Swap(key, value)
}

// Swap swaps the value for a key and returns the previous value if any.
// The loaded result reports whether the key was present.
func (m *Map) Swap(key, value any) (previous any, loaded bool) {
	read := m.loadReadOnly()
	if e, ok := read.m[key]; ok {
		if v, ok := e.trySwap(&value); ok {
			if v == nil {
				return nil, false
			}
			return *v, true
		}
	}

	m.mu.Lock()
	read = m.loadReadOnly()
	if e, ok := read.m[key]; ok {
		if e.unexpungeLocked() {
			// The entry was previously expunged, which implies that there is a
			// non-nil dirty map and this entry is not in it.
			m.dirty[key] = e
		}
		if v := e.swapLocked(&value); v != nil {
			loaded = true
			previous = *v
		}
	} else if e, ok := m.dirty[key]; ok {
		if v := e.swapLocked(&value); v != nil {
			loaded = true
			previous = *v
		}
	} else {
		if !read.amended {
			// 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.Store(&readOnly{m: read.m, amended: true})
		}
		m.dirty[key] = newEntry(value)
	}
	m.mu.Unlock()
	return previous, loaded
}

// trySwap swaps a value if the entry has not been expunged.
//
// If the entry is expunged, trySwap returns false and leaves the entry
// unchanged.
func (e *entry) trySwap(i *any) (*any, bool) {
	for {
		p := e.p.Load()
		if p == expunged {
			return nil, false
		}
		if e.p.CompareAndSwap(p, i) {
			return p, true
		}
	}
}

總結：

  1. 如果key在read中找到了，並且不為expunged，則試圖CAS並返回結果
  2. key在read中未找到，或者為expunged
    1. 加鎖
    2. 在read中查詢
      1. 如果查到了，試圖unexpunge
        1. 如果需要unexpunge，會將entry置(CAS)為nil，併在dirty中插入key
        2. 執行entry的Swap
    3. 在ditry中查詢
      1. 如果查到了，執行entry的Swap
    4. 都沒查到，則檢查dirty是否存在，初始化dirty，併在dirty增加新的entry
    5. 釋放鎖
    6. 返回結果

CompareAndSwap

// CompareAndSwap swaps the old and new values for key
// if the value stored in the map is equal to old.
// The old value must be of a comparable type.
func (m *Map) CompareAndSwap(key, old, new any) bool {
	read := m.loadReadOnly()
	if e, ok := read.m[key]; ok {
		return e.tryCompareAndSwap(old, new)
	} else if !read.amended {
		return false // No existing value for key.
	}

	m.mu.Lock()
	defer m.mu.Unlock()
	read = m.loadReadOnly()
	swapped := false
	if e, ok := read.m[key]; ok {
		swapped = e.tryCompareAndSwap(old, new)
	} else if e, ok := m.dirty[key]; ok {
		swapped = e.tryCompareAndSwap(old, new)
		// We needed to lock mu in order to load the entry for key,
		// and the operation didn't change the set of keys in the map
		// (so it would be made more efficient by promoting the dirty
		// map to read-only).
		// Count it as a miss so that we will eventually switch to the
		// more efficient steady state.
		m.missLocked()
	}
	return swapped
}

// tryCompareAndSwap compare the entry with the given old value and swaps
// it with a new value if the entry is equal to the old value, and the entry
// has not been expunged.
//
// If the entry is expunged, tryCompareAndSwap returns false and leaves
// the entry unchanged.
func (e *entry) tryCompareAndSwap(old, new any) bool {
	p := e.p.Load()
	if p == nil || p == expunged || *p != old {
		return false
	}

	// Copy the interface after the first load to make this method more amenable
	// to escape analysis: if the comparison fails from the start, we shouldn't
	// bother heap-allocating an interface value to store.
	nc := new
	for {
		if e.p.CompareAndSwap(p, &nc) {
			return true
		}
		p = e.p.Load()
		if p == nil || p == expunged || *p != old {
			return false
		}
	}
}

 總結：

  1. 如果key在read中找到了
    1. 如果為nil/expunged/不等於old，則返回false
    2. 試圖進行entry的CAS，成功返回true，失敗繼續1、2流程
  2. 如果key在read中未找到，並且read與dirty沒有不一致，返回false
  3. 如果key在read中未找到，並且read與dirty不一致
    1. 加鎖
    2. 如果key在read中找到
      1. 如果仍然為nil/expunged/不等於old，結果為false
      2. 試圖進行entry的CAS，CAS成功，則結果為true；否則繼續1、2流程
    3. 如果key在dirty中找到
      1. 如果不等於old，結果為false
      2. 試圖進行entry的CAS，CAS成功，則結果為true；否則繼續1、2流程
      3. misses加一
      4. 如果misses數大於dirty長度，將dirty同步到read，重置dirty和misses
    4. 釋放鎖
    5. 返回結果

CompareAndDelete

// CompareAndDelete deletes the entry for key if its value is equal to old.
// The old value must be of a comparable type.
//
// If there is no current value for key in the map, CompareAndDelete
// returns false (even if the old value is the nil interface value).
func (m *Map) CompareAndDelete(key, old any) (deleted bool) {
	read := m.loadReadOnly()
	e, ok := read.m[key]
	if !ok && read.amended {
		m.mu.Lock()
		read = m.loadReadOnly()
		e, ok = read.m[key]
		if !ok && read.amended {
			e, ok = m.dirty[key]
			// Don't delete key from m.dirty: we still need to do the “compare” part
			// of the operation. The entry will eventually be expunged when the
			// dirty map is promoted to the read map.
			//
			// Regardless of whether the entry was present, record a miss: this key
			// will take the slow path until the dirty map is promoted to the read
			// map.
			m.missLocked()
		}
		m.mu.Unlock()
	}
	for ok {
		p := e.p.Load()
		if p == nil || p == expunged || *p != old {
			return false
		}
		if e.p.CompareAndSwap(p, nil) {
			return true
		}
	}
	return false
}

總結：

  1. 如果key在read中找到了
    1. 如果為nil/expunged/不等於old，則返回false
    2. 試圖進行entry的CAS，成功返回true，失敗繼續1、2流程
  2. 如果key在read中未找到，並且read和dirty沒有不一致，返回false
  3. 如果key在read中未找到，並且read和dirty不一致
    1. 加鎖
    2. 從read中查找
      1. 如果找到key
        1. 為nil/expunged/不等於old，結果為false
        2. 試圖進行CAS，成功結果為true，失敗繼續嘗試
      2. 如果沒找到，並且沒有不一致，結果為false
    3. 如果read和dirty有不一致
      1. 從dirty中查找
      2. 如果找到key
        1. 不等於old，結果為false
        2. 試圖CAS，成功結果為true，失敗繼續嘗試
      3. 沒找到key，結果為false
    4. 釋放鎖
    5. 返回結果

結論

總的來說，sync.Map是Go標準庫提供的一個非常有用的工具，它可以幫助我們簡化併發編程，並且在一些特定的場景下能提供良好的性能。

但在使用的時候，我們需要根據具體的應用場景和需求來選擇使用sync.Map還是其他的併發原語。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Taurus .Net Core 微服務開源框架：Admin 插件【4-2】 - 配置管理-Mvc【含請求日誌列印】
    繼上篇：Taurus .Net Core 微服務開源框架：Admin 插件【4-1】 - 配置管理-Kestrel【含https啟用】，本篇繼續介紹下一個內容：系統配置節點：Mvc 配置界面...... ...
  • Taurus .Net Core 微服務開源框架：Admin 插件【3】 - 指標統計管理 -【API、Redis、MemCache】
    繼上篇：Taurus .Net Core 微服務開源框架：Admin 插件【2】 - 系統環境信息管理，本篇繼續介紹下一個內容：系統指標節點... ...
  • 排查雲主機埠不通（防火牆）
    # 1.背景 在雲主機上寫了一個很簡單的html頁面，預期能通過IP+埠查看下頁面的樣子，但是發現訪問異常，（該主機效期足夠，綁過功能變數名稱，曾經http\s都正常）。 # 2.排查步驟 ## 2.1.安全組已開放埠 ![](https://cdn.yyxyy.top/img/202307012104 ...
  • Spark中RDD的Transformation運算元
    # RDD的Transformation運算元 ## map map運算元的功能為做映射，即將原來的RDD中對應的每一個元素，應用外部傳入的函數進行運算，返回一個新的RDD ```Scala val rdd1: RDD[Int] = sc.parallelize(List(1,2,3,4,5,6,7,8 ...
  • 數據遷移工具，用這8種!
    ETL(是Extract-Transform-Load的縮寫，即數據抽取、轉換、裝載的過程)，對於企業應用來說，我們經常會遇到各種數據的處理、轉換、遷移的場景。 今天特地給大家彙總了一些目前市面上比較常用的ETL數據遷移工具，希望對你會有所幫助。 ...
  • css學習(一)
    本文以 `React`、`Vue` 為例，介紹下主流的渲染模式以及在主流框架中如何實現上述的渲染模式。 ## 前置知識介紹 看渲染模式之前我們先看下幾個主流框架所提供的相關能力，瞭解的可跳到下個章節。 ### 掛載組件到 DOM 節點 這是主流框架最基本的能力，就是將組件渲染到指定的 `DOM` 節 ...
  • vue中封裝伺服器地址/介面與設置請求頭
    1. 設置請求頭 首先創建一個放置伺服器地址的js,如http.js,然後在http.js中引入axios `import axios from "axios";` 如果沒有axios,需要先安裝,npm i axios或者yarn add axois,然後重啟伺服器 ...直接上代碼 點擊查看代碼 ...
  • webman
    不知不覺，《C++面試八股文》已經更新30篇了，這是我第一次寫技術博客，由於個人能力有限，出現了不少紕漏，在此向各位讀者小伙伴們致歉。 為了不誤導更多的小伙伴，以後會不定期的出勘誤文章，請各位小伙伴留意。 在《[C++面試八股文：C++中，設計一個類要註意哪些東西？](https://zhuanla ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類