golang 비동기. synchronization primitive(1) sync.Map구현에서 적용해보는 sync.RWMutex

July 15, 2024 8 minute read

해당 아티클은 다음 수준의 지식을 요구합니다.

goroutine을 사용해본 경험

다음 실행환경에서 동작합니다.

wsl2 Ubuntu-22.04
go1.22.2 linux/amd64

golang 비동기 프로그래밍에서는 다양한 동기화 프리미티브를 활용합니다. 이번에는 동기화에 가장 기본적으로 사용되는 sync.RWMutex를 이용하여 고루틴에 안전한 generic map을 구현해보겠습니다. sync.Map과 유사한 인터페이스를 제공하는 방향으로 구현합니다.

sync.Map & sync.RWMutex 소개

sync.Map은 golang에서 map 자료 구조를 여러 고루틴에 대하여 안전하게 읽기/쓰기를 할 수 있도록 구현한 구조체입니다. 해당 자료구조는 다음과 같은 메서드를 여러 고루틴에 대하여 안전하게 실행할 수 있도록 제공하고 있습니다.

func (m *sync.Map) Load(key any) (value any, ok bool)                   // key에 대한 값을 불러옵니다. 없을 경우 ok가 false입니다.
func (m *sync.Map) Store(key any, value any)                            // key와 value를 저장합니다.
func (m *sync.Map) Delete(key any)                                      // key를 삭제합니다.
func (m *sync.Map) Swap(key any, value any) (previous any, loaded bool) // key의 value를 upsert하고 이전값을 가져옵니다. 이전값이 존재하면 loaded가 true입니다.

func (m *sync.Map) CompareAndDelete(key any, old any) (deleted bool)         // key에 대한 value를 old와 비교해서 같으면 삭제하고 deleted를 true로 리턴합니다.
func (m *sync.Map) CompareAndSwap(key any, old any, new any) bool            // key에 대한 value를 old와 비교해서 같으면 new로 바꾸고 true를 리턴합니다.
func (m *sync.Map) LoadAndDelete(key any) (value any, loaded bool)           // key에 대한 value를 가져오고 map에서 해당 key를 삭제합니다. key가 존재했었다면 loaded가 true입니다.
func (m *sync.Map) LoadOrStore(key any, value any) (actual any, loaded bool) // key가 있으면 actual에 값을 가져오고 없으면 value를 저장하고 값을 가져옵니다.
func (m *sync.Map) Range(f func(key any, value any) bool)                    // 모든 key에 대하여 컬백 f를 실행합니다. bool을 false로 리턴하면 루프가 종료됩니다.

이번에는 sync.RWMutex입니다. RWMutex는 여러 고루틴의 동시 읽기를 허용하면서도, 쓰기 고루틴은 항상 단독으로 동작하여 모든 읽기와 쓰기를 차단하도록 구현되어 있습니다. sync.RWMutex는 크게 다음의 네 가지 메서드를 사용합니다.

func (rw *sync.RWMutex) Lock()    // 쓰기에 대하여 락을 획득합니다.
func (rw *sync.RWMutex) Unlock()  // 쓰기에 대하여 락을 해제합니다.
func (rw *sync.RWMutex) RLock()   // 읽기에 대하여 락을 획득합니다.
func (rw *sync.RWMutex) RUnlock() // 읽기에 대하여 락을 해제합니다.

그럼 이제 generic map을 RWMutex를 이용하여 굉장히 단순하게 동시성에 대하여 안전하도록 구현해봅시다. 프로젝트 구성은 다음과 같이 세팅했습니다.

$ go mod init syncgo

.
├── ds
│   ├── map.go
│   └── map_test.go
└── go.mod

아래 구조체를 기반으로, Value 타입이 comparable이어야 사용 가능한 compare 메서드를 제외한 나머지 메서드를 구현합니다.

// ds/map.go
type Map[F comparable, T any] struct {
	mu sync.RWMutex
	m  map[F]T
}

func NewMap[F comparable, T any](initSize int) *Map[F, T] {
	r := new(Map[F, T])
	r.m = make(map[F]T, initSize)
	return r
}

generic map 구현

동시성에 안전한 구현을 위해 golang에서 sync.RWMutex를 활용할 때는 일반적으로 다음과 같이 처리합니다.

func() {
	mu.Lock()          // 쓰기 또는 읽기 락 획득
	defer mu.Unlock()  // 쓰기 또는 읽기 락 해제
	
	// 아래에서 비즈니스 로직 처리
}

보다시피 락 사용 자체는 간단합니다. defer를 이용하여 함수 탈출 시 자동으로 락이 해제되도록 하고, 이후에 비즈니스 로직을 작성합니다.

먼저 RLock을 사용하는 Load 메서드입니다. 읽기 락을 획득하고 맵에서 데이터를 가져와 리턴합니다.

// ds/map.go
func (m *Map[F, T]) Load(k F) (v T, ok bool) {
	m.mu.RLock()
	defer m.mu.RUnlock()
	v, ok = m.m[k]
	return v, ok
}

Store, Delete, Swap 메서드는 다음과 같이 구현합니다. 각각 쓰기 락을 획득하고 이외 로직을 처리합니다.

// ds/map.go
func (m *Map[F, T]) Store(k F, v T) {
	m.mu.Lock()
	defer m.mu.Unlock()
	m.m[k] = v
}

func (m *Map[F, T]) Delete(k F) {
	m.mu.Lock()
	defer m.mu.Unlock()
	delete(m.m, k)
}

func (m *Map[F, T]) Swap(k F, v T) (p T, loaded bool) {
	m.mu.Lock()
	defer m.mu.Unlock()
	p, loaded = m.m[k]
	m.m[k] = v
	return p, loaded
}

나머지 메서드는 다음과 같이 구현했습니다. 여기도 위의 Store, Delete, Swap 메서드처럼 락을 획득하고 로직을 진행합니다.

// ds/map.go
func (m *Map[F, T]) LoadAndDelete(k F) (v T, loaded bool) {
	m.mu.Lock()
	defer m.mu.Unlock()
	v, loaded = m.m[k]
	delete(m.m, k)
	return v, loaded
}

func (m *Map[F, T]) LoadOrStore(k F, v T) (T, bool) {
	m.mu.Lock()
	defer m.mu.Unlock()
	if existing, loaded := m.m[k]; loaded {
		return existing, true
	}
	m.m[k] = v
	return v, false
}

func (m *Map[F, T]) Range(f func(F, T) bool) {
	m.mu.RLock()
	defer m.mu.RUnlock()
	for k, v := range m.m {
		if !f(k, v) {
			break
		}
	}
}

이런 방식으로 RWMutex를 이용하면 간단하게 동시성에 안전한 generic map을 구현할 수 있습니다. 하지만 실제로는 안전하지 않은 부분이 한 가지 있습니다. 어떤 문제인지 살펴봅시다.

컬백에서 발생할 수 있는 데드락

위에서 작성한 코드로 데드락이 발생할 수 있는 시나리오를 가정해봅시다. 예를 들어, 웹소켓 채팅 서버에서 위에서 구현한 ds/Map으로 브로드캐스팅을 구현한다면 데드락이 발생할 수 있습니다. 코드 예시는 다음과 같으며, 해설은 주석으로 추가했습니다.

type Username string
type User interface {
	write(data []byte) error
}

// 메세지를 userMap에 속한 모든 user에게 전달합니다.
func WriteMessage(message []byte, userMap *ds.Map[Username, User]) {

	// some code ...

	// userMap의 모든 user에 대해 컬백함수 동작
	userMap.Range(func(username Username, user User) bool {
		// 데이터를 전달하고 에러 발생 시 유저 삭제
		if err := user.write(message); err != nil {
			// some log ...
			userMap.Delete(username)
		}
		return true
	})

	// some code ...
}

위의 경우가 바로 데드락이 호출될 수 있는 코드입니다. 데드락이 발생하는 시나리오는 다음과 같습니다.

먼저 userMap의 Range 메서드가 호출되고 해당 메서드는 읽기 락을 획득하고 컬백함수를 모든 map의 원소에 대해 순차적으로 실행합니다.
만약 user.write 메서드가 동작하다가 에러가 발생했다고 합시다.
에러 발생 시 userMap의 Delete 메서드가 호출되며 쓰기 락을 획득하려고 합니다.
쓰기 락은 모든 읽기 락이 해제될 때까지 대기합니다.
그러나 읽기 락은 앞에서 먼저 호출된 Range 메서드로 인해 잠겨있는 상태이고 Range 메서드의 컬백으로 호출된 Delete 메서드로 인해 쓰기 락이 무한히 대기하게 됩니다.
따라서 데드락이 발생합니다.

위의 코드를 예시가 아닌 발생할 수 있는 코드로 당장 테스트해보면 이렇게 되는 것을 확인할 수 있습니다.

// main.go
package main

import (
	"fmt"
	"syncgo/ds"
)

func main() {
	m := ds.NewMap[int, int](8)
	m.Store(1, 101)
	m.Store(2, 202)
	m.Store(3, 303)
	m.Store(4, 404)
	m.Store(5, 505)
	m.Store(6, 606)
	m.Store(7, 707)
	m.Store(8, 808)

	m.Range(func(key, value int) bool {
		if key == 2 {
			m.Delete(2)
		}
		fmt.Println(key, value)
		return true
	})
}

$ go run .
1 101
fatal error: all goroutines are asleep - deadlock!

이번에는 sync.Map에서도 비슷한 이슈가 발생하는지 살펴봅시다.

// main.go
package main

import (
	"fmt"
	"sync"
)

func main() {
	m := sync.Map{}
	m.Store(1, 101)
	m.Store(2, 202)
	m.Store(3, 303)
	m.Store(4, 404)
	m.Store(5, 505)
	m.Store(6, 606)
	m.Store(7, 707)
	m.Store(8, 808)

	m.Range(func(key, value any) bool {
		if key == 2 {
			m.Delete(2)
		}
		fmt.Println(key, value)
		return true
	})
}

실행해보면 재미있게도 데드락이 발생하지 않고 동작합니다. 이는 어떻게 구현한 걸까요? 코드 내부를 살펴봅시다.

약한 일관성과 sync.Map의 Range 내부

sync.Map내부에서는 그럼 어떻게 동작하기에 동시성 문제를 회피할 수 있었던 걸까요? 먼저 golang/go의 sync/map.go 내부에서 Map의 Range 코드 내부를 살펴봅시다.

func (m *Map) Range(f func(key, value any) bool) {
	// loadReadOnly로 현재 map을 읽기 전용으로 불러옵니다.
	read := m.loadReadOnly()
	// amended 플래그가 참이면
	if read.amended {
		// 락을 획득하고 한 번 더 읽기를 시도하여 갱신합니다.
		m.mu.Lock()
		read = m.loadReadOnly()
		// 또 플래그가 참이면 m.dirty로 readOnly를 갱신하고
		// dirty를 초기화하고 락을 해제합니다.
		if read.amended {
			read = readOnly{m: m.dirty}
			copyRead := read
			m.read.Store(&copyRead)
			m.dirty = nil
			m.misses = 0
		}
		m.mu.Unlock()
	}
	
	// 모든 키를 순회합니다.
	for k, e := range read.m {
		v, ok := e.load()
		if !ok {
			continue
		}
		if !f(k, v) {
			break
		}
	}
}

해당 부분을 확인해보면 read := m.loadReadOnly() 를 통해 read를 가져오고 if read.amended 를 호출합니다. sync.Map은 내부에 read와 dirty 필드를 가지는데 이 둘은 map의 역할을 수행합니다. read는 동시에 접근하여 읽기가 가능하고 dirty는 락을 획득해야만 접근 가능한 필드입니다. 이렇게 sync.Map내부에서 read를 캐시와 유사하게 활용하여 읽기 성능을 개선하는 방향으로 구현되어 있습니다. 몇 가지 메서드의 구현에서 read와 dirty를 어떻게 사용하고 있는지 간단하게 살펴봅시다.

Map.Load메서드는 호출 시 다음과 같이 동작합니다.

https://github.com/golang/go/blob/a10e42f219abb9c5b/src/sync/map.go#L120

Map의 read를 가져오고 read에서 key를 조회합니다.
존재하지 않으면 misses를 증가시킵니다.
일정 횟수 이상 misses값이 커지면, dirty를 read로 덮어씁니다.

한편 Swap(Store도 Swap 메서드를 호출합니다)는 다음과 같이 동작합니다.

https://github.com/golang/go/blob/a10e42f219abb9c5b/src/sync/map.go#L330

Map의 read를 가져오고 read에서 key에 대한 값을 조회합니다.
만약 조회되면 read의 key에 대하여 스왑을 시도합니다.
만약 조회되지 않으면 락 획득 후 다시 read를 불러옵니다.
key를 조회하고 존재하는 경우, read에 존재하는 값을 갱신합니다. (또한 key에 대한 값의 상태에 따라(expunged: sync.Map에서 해당 키가 유효하지 않음) dirty에 추가합니다)
key가 read에 없고 dirty에만 존재하는 경우, dirty의 값을 갱신합니다.
둘 다 존재하지 않는 경우, dirty를 초기화하고(dirtyLocked) 새로운 key를 dirty에 추가합니다.

중요한 것은 sync.Map은 read와 dirty를 분리하고 read에서 읽기 전용으로 빠르게 읽고, 락이 걸려야 하는 작업은 dirty에 적절히 분산하여 해결하는 것입니다. 다시 sync.Map의 Range 연산을 살펴보면, 락을 획득하는 부분은 하나의 지점인 것을 알 수 있습니다. 바로 read.amended 가 참이 되어 m.read.Store(&copyRead) 로 read를 갱신하는 부분입니다. 그 뒤에 read.m을 순회하며 모든 k, v에 대하여 f를 실행하고 있는 것을 확인할 수 있습니다. 따라서 f에서 sync.Map을 변경하려고 하면, 즉 락을 획득하고 데이터에 create, update, delete와 관련된 연산을 진행된다면, 반영되지 않은 상태로 read가 복제된 시점의 스냅샷을 이용하여 동작한다는 것을 알 수 있습니다. 이렇게 약한 일관성을 가져 Range를 순회하는 read의 포인터에 대하여 해당 시점에 일어난 sync.Map에 대한 변화를 반영하지 않습니다. 그러나 다른 연산에 대해서는 강한 일관성을 보장합니다.

따라서 락을 이중으로 획득하게 만들지 않으려면 Range가 호출됐을 때 map을 복사해야 합니다. 따라서 다음과 같은 방향으로 단순하게 구현하여 동작하게 할 수 있습니다. 락을 먼저 획득하고 key와 value를 모두 복사하여 루프로 함수를 호출하는 방식입니다. 이 경우에 Map이 변경되어도 무시하고 코드에서 락을 획득한 시점에 대한 Map을 기반으로 실행됩니다. 그 이후의 맵의 변화는 무시됩니다. 복사에 대한 오버헤드를 감수하고 데드락을 방지하는 방식입니다.

// ds/map.go
func (m *Map[F, T]) Range(f func(F, T) bool) {
	m.mu.RLock()
	length := len(m.m)
	ks := make([]F, 0, length)
	vs := make([]T, 0, length)
	for k, v := range m.m {
		ks = append(ks, k)
		vs = append(vs, v)
	}
	m.mu.RUnlock()
	for i := range length {
		if !f(ks[i], vs[i]) {
			break
		}
	}
}

코드입니다.

https://github.com/atgane/syncgo/blob/bed56a7069307ea39935af6720cd026440d74a1a/ds/map.go

결론

이렇게 컨테이너 형식의 자료구조에서 컬백함수로 여러 개의 대상을 실행시키는 코드가 존재하는 경우, 컬백함수 내부에서 락을 획득하여 실행하게 되면 컬백함수 내부에서 자료구조의 create/update/delete를 호출할 때 데드락이 발생할 수 있다는 것을 알게 되었습니다. 이런 경우, 회피하는 방법으로 약한 일관성을 이용하여 컨테이너의 일부 또는 전체를 복사하여 문제를 회피할 수 있었습니다. 실제로 golang의 sync.Map은 해당 방식으로 동작하고 있고, read와 dirty를 분리하여 읽기 성능을 가속화하고 있다는 점도 확인했습니다. 생각보다 golang의 내부는 분산 시스템의 구조가 보이는 것 같습니다.

다음은 채널과 이벤트 루프의 구현에 대해서 다뤄보겠습니다.

Share on

X Facebook LinkedIn Bluesky

atgane

golang 비동기. synchronization primitive(1) sync.Map구현에서 적용해보는 sync.RWMutex

sync.Map & sync.RWMutex 소개

generic map 구현

컬백에서 발생할 수 있는 데드락

약한 일관성과 sync.Map의 Range 내부

결론

Share on

Leave a comment

You may also enjoy

kubernetes data plane: containerd는 언제 결정하는가

kubernetes data plane: containerd CreateContainer & StartContainer

kubernetes data plane: containerd sandbox 생성 과정 추적

kubernetes data plane: containerd 플러그인 시스템과 gRPC 서버 초기화