Zenn
🐥

Golang: sync.MapのLoadOrStore()やLoadAndDelete()はなぜ必要か

2024/12/26に公開
Go
goroutine
tech

あまり並行処理は書いたことが無かったんですが、最近は書く機会が増えてきました。
そんな中で並行処理について調べる事も多く、先日sync.MapのLoadOrStore()やLoadAndDelete()が必要な理由が解説されてるdev.toの記事を読んだのですが、また分からなくなった時に英語の記事を読み直すのもしんどいので、将来の自分のためにまとめる事にしました。

Go: sync.Map's LoadAndDelete and LoadOrStore. Why are they needed? - DEV Community https://dev.to/sreramk/go-loadanddelete-and-loadorstore-in-sync-map-why-are-they-needed-30f7
読んだ記事はこちらです。

なお、こうして調べたことはMisskey.ioに長文ノートで放流する事がほとんどだったんですが、今回は長くなりすぎて流石のMisskeyも文字数オーバーで投稿できなかったので、久しぶりにブログにしています。
雑に書いたものを手直ししたので、文体など不自然な箇所が多々あると思います。

まとめ

sync.MapのLoadOrStore()やLoadAndDelete()は、"Loadして無ければStore"と"Loadして有ればDelete"までをアトミックに行うので、2個以上のgoroutineが並行実行される場合に、2個以上が同時に無いからStoreする事や、有るからDeleteするというrace conditionを避けられます。
ただし、アトミックなのはそれだけなので、StoreやDeleteが出来た後の処理でrace conditionにならない様にする事までは、めんどうを見てはくれません。

例えばchannelを入れてる場合なんかは、Load()する並行処理とLoadAndDelete()してDeleteしたらcloseする並行処理が同時に走る事で、Load()は出来たけど直後にcloseされてしまう、みたいな事はsync.Mapは何も出来ないので自分で対処する必要があります。
記事中でatomic.AddInt32()を使っているのも、enterCount = enterCount + 1だと"読み込み->加算->書き込み"の途中を他のgoroutineに割り込まれる可能性があるためです。

LoadOrStore()が必要な理由

func enterRoomUnsafe(roomId string, timestamp time.Time) bool {
	if _, ok := m.Load(roomId); !ok {
		m.Store(roomId, timestamp)      // 競合リスク: タイムスタンプの上書き
		atomic.AddInt32(&enterCount, 1) // 競合リスク: 冪等性のない処理
		return true                     // 入室成功
	}
	return false // 使用中の為、入室失敗
}
  1. Goroutine A: m.Load("room123")で部屋が空いてると確認 (ok == false)
  2. Goroutine B: m.Load("room123")で部屋が空いてると確認 (ok == false)
  3. Goroutine A: m.Store("room123", timestampA)で入室成功
  4. Goroutine B: m.Store("room123", timestampB)で重複して入室
  5. Goroutine A: atomic.AddInt32(&enterCount, 1)でカウントが+1
  6. Goroutine B: atomic.AddInt32(&enterCount, 1)でカウントがさらに+1

先に入室成功したtimestampAだった入室日時が、timestampBに上書きされます。
さらにsync.Mapに格納出来た事をトリガーにカウントを上げるなど、冪等性の無い処理があれば2回実行してしまいます。

これはLoad()の後のStore()が実行される前に、他のgoroutineでもLoad()が実行されてしまう事でrace conditionになった事になります。

func enterRoom(roomId string, timestamp time.Time) bool {
	if _, loaded := m.LoadOrStore(roomId, timestamp); !loaded {
		atomic.AddInt32(&enterCount, 1)
		return true
	}
	return false
}

LoadOrStore()ならLoad()とStore()がアトミックな操作になり、race conditionを回避できます。

race condition発生確認コード

package main

import (
	"fmt"
	"sync"
	"sync/atomic"
	"time"
)

var (
	m          sync.Map
	enterCount int32
)

// race conditionの可能性がある入室処理
func enterRoomUnsafe(roomId string, timestamp time.Time) bool {
	if _, ok := m.Load(roomId); !ok {
		m.Store(roomId, timestamp)      // 競合リスク: タイムスタンプの上書き
		atomic.AddInt32(&enterCount, 1) // 競合リスク: 冪等性のない処理
		return true                     // 入室成功
	}
	return false // 使用中の為、入室失敗
}

// 何度か実行すると、下記の様に入室成功が2回出てしまうrace conditionが確認できる。
//
// 入室成功: 2009-11-10 23:00:04 +0000 UTC m=+4.000000001
// 入室成功: 2009-11-10 23:00:15 +0000 UTC m=+15.000000001
// mapに記録された入室時刻: 2009-11-10 23:00:15 +0000 UTC m=+15.000000001
// 入室回数: 2
func main() {
	const goroutineCount = 500
	var wg sync.WaitGroup
	roomId := "room123"

	baseTime := time.Now()

	// 複数のゴルーチンを起動しrace conditionの発生を確認する
	for i := 0; i < goroutineCount; i++ {
		wg.Add(1)
		go func(i int) {
			defer wg.Done()
			// 入室時刻をi秒加算して擬似的な個別時刻を生成
			timestamp := baseTime.Add(time.Duration(i) * time.Second)
			ok := enterRoomUnsafe(roomId, timestamp)
			if ok {
				fmt.Printf("入室成功: %v\n", timestamp)
			}
		}(i)
	}
	wg.Wait()

	val, _ := m.Load(roomId)
	fmt.Printf("mapに記録された入室時刻: %v\n", val)
	fmt.Printf("入室回数: %d\n", atomic.LoadInt32(&enterCount))
}

https://go.dev/play/p/Ih7k1XMEzKb

LoadAndDelete()が必要な理由

func leaveRoomUnsafe(roomId string) bool {
	if _, ok := m.Load(roomId); ok {
		m.Delete(roomId)               // 競合リスク: ただし冪等性あり
		atomic.AddInt32(&exitCount, 1) // 競合リスク: 冪等性のない処理
		return true                    // 退室成功
	}
	return false // 部屋が存在しない
}
  1. Goroutine A: m.Load("room123")で部屋が存在すると確認 (ok == true)
  2. Goroutine B: m.Load("room123")で部屋が存在すると確認 (ok == true)
  3. Goroutine A: m.Delete("room123")で部屋を削除
  4. Goroutine B: m.Delete("room123")で部屋を削除するが、削除済みなので何も起こらない
  5. Goroutine A: atomic.AddInt32(&exitCount, 1)でカウントが+1
  6. Goroutine B: atomic.AddInt32(&exitCount, 1)でカウントがさらに+1

削除自体は冪等性があり、重複しても上書きされるものもないし、実質問題は無いと言えます。
ただしこちらも、削除できた事をトリガーにカウントを上げるなど、冪等性の無い処理があれば2回実行してしまいます。
退室でカウントアップは例として良くなかったけど、複数ユーザーが入る部屋の場合に、在室人数を増減させる場合なんかは、実際の人数との差が生まれてしまうでしょう。

こっちも、Load()の後のDelete()が実行される前に、他のgoroutineでもLoad()が実行されてしまう事でrace conditionとなります。

func leaveRoom(roomId string) bool {
	if val, deleted := m.LoadAndDelete(roomId); deleted {
		atomic.AddInt32(&exitCount, 1)
		return true
	}
	return false
}

LoadAndDelete()ならLoad()とDelete()がアトミックな操作になり、race conditionを回避できます。

race condition発生確認コード

package main

import (
	"fmt"
	"sync"
	"sync/atomic"
	"time"
)

var (
	m         sync.Map
	exitCount int32
)

// race conditionの可能性がある退室処理
func leaveRoomUnsafe(roomId string) bool {
	if _, ok := m.Load(roomId); ok {
		m.Delete(roomId)               // 競合リスク: ただし冪等性あり
		atomic.AddInt32(&exitCount, 1) // 競合リスク: 冪等性のない処理
		return true                    // 退室成功
	}
	return false // 部屋が存在しない
}

// 何度か実行すると、下記の様に退室成功が2回出てしまうrace conditionが確認できる。
// `Delete()`は冪等性があるのでrace conditionになり2回実行しても問題ないが、削除に追加で非冪等な処理をすると、問題のあるrace conditionになる。
//
// 退室成功: room123
// 退室成功: room123
// 退室回数: 2
func main() {
	const goroutineCount = 500
	var wg sync.WaitGroup
	roomId := "room123"

	// 部屋の初期登録
	m.Store(roomId, time.Now())

	// 複数のゴルーチンを起動しrace conditionの発生を確認する
	for i := 0; i < goroutineCount; i++ {
		wg.Add(1)
		go func(i int) {
			defer wg.Done()
			ok := leaveRoomUnsafe(roomId)
			if ok {
				fmt.Printf("退室成功: %s\n", roomId)
			}
		}(i)
	}
	wg.Wait()

	fmt.Printf("退室回数: %d\n", atomic.LoadInt32(&exitCount))
}

https://go.dev/play/p/G3vWiy2OzVz

Delete()は冪等性があるが、Store()が絡んで結局race conditionの可能性がある

前述のコードでatomic.AddInt32(&exitCount, 1)の様な冪等性がない処理を含まなければ、Delete()は複数回実行しても結果は変わらず問題ないとしました。
しかし、2個のgoroutineがDelete()を、1個のgoroutineがStore()を行うと、稀にrace conditionになる可能性があります。

  1. room123は入室状態とする
  2. Goroutine A: m.Load("room123")で部屋が存在すると確認 (ok == true)
  3. Goroutine B: m.Load("room123")で部屋が存在すると確認 (ok == true)
  4. Goroutine A: m.Delete("room123")で部屋を削除
  5. Goroutine C: m.Load("room123")で部屋が空いてると確認 (ok == false)
  6. Goroutine C: m.Store("room123", timestamp)で入室成功
  7. Goroutine B: m.Delete("room123")で部屋を削除

3個のgoroutineの各行の実行順がうまく重なるとrace conditionとなる感じですが、下記の確認コードで実行を繰り返すと、手動でも10分程で確認できる位には発生します。

race condition発生確認コード

package main

import (
	"fmt"
	"sync"
	"time"
)

var m sync.Map

func leaveRoomUnsafe(roomId string) bool {
	if _, ok := m.Load(roomId); ok {
		m.Delete(roomId) // 競合リスク
		return true      // 退室成功
	}
	return false // 部屋が存在しなかった
}

func enterRoomUnsafe(roomId string, timestamp time.Time) bool {
	if _, ok := m.Load(roomId); !ok {
		m.Store(roomId, timestamp) // 競合リスク
		return true                // 入室成功
	}
	return false // 使用中の為、入室失敗
}

// 何度も実行すると、稀に入室したのに部屋が存在しないrace conditionが確認できる。
// 数百回の試行ができるコードになってないので、根気よく何度も試して稀にだけど。
// ゴルーチンCが`Store()`して`return`する間に、AかBが`Delete()`したと思われる。
// 
// ゴルーチンA: room123 を削除しました。
// ゴルーチンB: room123 を削除しました。
// ゴルーチンC: room123 に入室しました。
// 最終確認: 部屋 room123 は存在しません。
func main() {
	roomId := "room123"
	baseTime := time.Now()
	m.Store(roomId, baseTime) // 初期登録

	var wg sync.WaitGroup

	// ゴルーチンA: 退室
	wg.Add(1)
	go func() {
		defer wg.Done()
		time.Sleep(1 * time.Millisecond) // Sleep挟まないとGoroutineの実行順が毎回ほぼ同じだったので追加
		if leaveRoomUnsafe(roomId) {
			fmt.Printf("ゴルーチンA: %s を削除しました。\n", roomId)
		}
	}()

	// ゴルーチンB: 退室
	wg.Add(1)
	go func() {
		defer wg.Done()
		time.Sleep(1 * time.Millisecond) // Sleep挟まないとGoroutineの実行順が毎回ほぼ同じだったので追加
		if leaveRoomUnsafe(roomId) {
			fmt.Printf("ゴルーチンB: %s を削除しました。\n", roomId)
		}
	}()

	// ゴルーチンC: 入室
	wg.Add(1)
	go func() {
		defer wg.Done()
		time.Sleep(1 * time.Millisecond) // Sleep挟まないとGoroutineの実行順が毎回ほぼ同じだったので追加
		if enterRoomUnsafe(roomId, baseTime.Add(33*time.Second)) {
			fmt.Printf("ゴルーチンC: %s に入室しました。\n", roomId)
		}
	}()

	wg.Wait()

	// 最終確認
	val, exists := m.Load(roomId)
	if exists {
		fmt.Printf("最終確認: 部屋 %s の入室時刻は %v です。\n", roomId, val)
	} else {
		fmt.Printf("最終確認: 部屋 %s は存在しません。\n", roomId)
	}
}

https://go.dev/play/p/QoBGImiJiAt

Discussion