syncmap

go 표준 라이브러리에서 제공하는 sync.Map 은 동시성 안전한 map 으로, 사용할 때 락과 같은 방식으로 제어할 필요가 없습니다. 구현은 그다지 복잡하지 않으며 주석을 제거하면 총 200-300 행 정도의 코드입니다.

구조

type Map struct {
    mu Mutex
    read atomic.Pointer[readOnly]
    dirty map[any]*entry
    misses int
}

총 네 개의 필드가 있으며 각각 다음과 같습니다.

• read, 읽기 전용 map 으로, dirty 에 대한 캐시로 이해할 수 있습니다.
• dirty, 일반 map 입니다.
• misses, read 액세스 시 미스한 횟수입니다.
• mu, dirty 의 동시성 안전을 보호합니다.

read 는 sync.readonly 타입으로, 내부는 여전히 map 이며, 그 중 amended 필드는 dirty 가 read 에 없는 키를 포함하는지 여부를 나타냅니다.

type readOnly struct {
  m       map[any]*entry
  amended bool // true if the dirty map contains some key not in m.
}

또한 entry 타입 구조는 다음과 같으며, p 는 value 를 가리키는 포인터입니다.

type entry struct {
  p atomic.Pointer[any]
}

entry 의 경우 세 가지 가능한 상황이 있습니다.

1. 정상적인 경우, 대응하는 값을 저장합니다.
2. p 가 nil 인 경우, 해당 키 - 값 쌍이 삭제되었음을 나타내며, 이때 dirty 는 비어있을 수 있거나 여전히 dirty 에 있을 수 있습니다.
3. p == expunged, expunged 는 빈 인터페이스 객체로, 키 - 값 쌍이 삭제되었고 dirty 에 존재하지 않음을 나타냅니다.

표준 라이브러리 map 의 동시성 안전은 읽기 - 쓰기 분리를 통해 구현되며, read 와 dirty 가 저장하는 entry 포인터는 모두 동일한 value 메모리를 가리킵니다. read 는 읽기 전용이므로 여러 고루틴이 액세스해도 안전 문제가 없으며, dirty 는 수정 가능하므로 뮤텍스 락의 보호를 받습니다. misses 는 키 액세스 미스 횟수를 기록하며, 이 횟수가 일정 값에 도달하면 현재 dirty 가 read 로 전환되고 misses 가 초기화됩니다. 이것이 sync.Map 의 대략적인 작업 논리이며, 이후에 연산을 더 자세히 분석하겠습니다.

읽기

읽기 연산은 Map.Load 메서드에 해당하며 코드는 다음과 같습니다.

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()
    read = m.loadReadOnly()
    e, ok = read.m[key]
    if !ok && read.amended {
      e, ok = m.dirty[key]
      m.missLocked()
    }
    m.mu.Unlock()
  }
  if !ok {
    return nil, false
  }
  return e.load()
}

먼저 read 를 액세스하며, 존재하면 직접 반환하고, 그렇지 않으면 mu 뮤텍스 락을 획득하려고 시도합니다. 락을 획득하는 동안 dirty 가 read 로 승격될 수 있기 때문입니다. 그래도 찾지 못하면 최종적으로 dirty 를 액세스하고 한 번의 miss 를 기록한 후 락을 해제합니다.

func (m *Map) missLocked() {
  m.misses++
  if m.misses < len(m.dirty) {
    return
  }
  m.read.Store(&readOnly{m: m.dirty})
  m.dirty = nil
  m.misses = 0
}

missLocked 메서드를 통해 dirty 가 read 로 승격되는 임계 조건은 m.misses >= len(m.dirty) 임을 알 수 있습니다.

쓰기

쓰기 연산은 Store 메서드에 해당하지만 실제로는 Swap 메서드가 완료하며, previous 는 이전 값을 나타내고 loaded 는 키 존재 여부를 나타냅니다.

func (m *Map) Swap(key, value any) (previous any, loaded bool)

쓰기 연산의 프로세스는 두 부분으로 나뉩니다. 액세스한 키가 read 에 존재하면 대응하는 entry 를 직접 획득한 후 CAS 를 통해 entry 값을 업데이트하며, 이 기간 동안 락이 필요하지 않습니다.

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
    }
}

스피닝 기간 동안 p == expunged 이면 해당 키가 삭제되었음을 나타내므로 직접 반환합니다.

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
    }
  }
}

키가 read 에 존재하지 않으면 락을 획득하여 다음 연산을 시도합니다. 다음으로 세 가지 상황이 있습니다. 첫 번째 상황, 락을 획득하는 동안 dirty 가 read 로 승격되면 액세스한 entry 가 expunged 이면 삭제되었고 dirty 에 존재하지 않음을 나타내므로, 이때 dirty 에 추가한 후 대응하는 값을 저장해야 합니다.

read = m.loadReadOnly()
if e, ok := read.m[key]; ok {
    if e.unexpungeLocked() {
        m.dirty[key] = e
    }
    if v := e.swapLocked(&value); v != nil {
        loaded = true
        previous = *v
    }
}

두 번째 상황, read 에 없지만 dirty 에 있으면 직접 대응하는 값을 저장합니다.

if e, ok := m.dirty[key]; ok {
    if v := e.swapLocked(&value); v != nil {
        loaded = true
        previous = *v
    }
}

세 번째 상황, read 에 없고 dirty 에도 없습니다. 여기서 read.amended 가 false 이면 dirty 가 비어있음을 나타내므로, m.dirtyLocked 를 사용하여 read 의 모든 미삭제 키 - 값 쌍을 dirty 에 복사한 후 read.amended 를 true 로 표시하고, 마지막으로 새 entry 를 생성하여 대응하는 값을 저장합니다.

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)
}

func (m *Map) dirtyLocked() {
  if m.dirty != nil {
    return
  }

  read := m.loadReadOnly()
  m.dirty = make(map[any]*entry, len(read.m))
  for k, e := range read.m {
    if !e.tryExpungeLocked() {
      m.dirty[k] = e
    }
  }
}

삭제

삭제 연산은 LoadAndDelete 메서드에 해당하며, 그 아이디어는 읽기 연산과 거의 동일하지만 delete 함수 호출이 하나 추가되었습니다.

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)
      m.missLocked()
    }
    m.mu.Unlock()
  }
  if ok {
    return e.delete()
  }
  return nil, false
}

키 - 값 쌍을 삭제할 때 항상 dirty 에 대해서만 delete 연산을 실행하며, read 의 경우 저장한 entry 의 값을 nil 로 수정하기만 합니다.

func (e *entry) delete() (value any, ok bool) {
  for {
    p := e.p.Load()
    if p == nil || p == expunged {
      return nil, false
    }
    if e.p.CompareAndSwap(p, nil) {
      return *p, true
    }
  }
}

순회

순회 연산은 Range 메서드에 해당합니다.

func (m *Map) Range(f func(key, value any) bool) {
  read := m.loadReadOnly()
  if read.amended {
    m.mu.Lock()
    read = m.loadReadOnly()
    if read.amended {
      read = readOnly{m: m.dirty}
      m.read.Store(&read)
      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 만 순회하며, read.amended 가 true 이면 read 의 키가 누락되었음을 나타내므로, 이때 직접 dirty 를 read 로 승격시킨 후 for range 루프로 순회하며 각 키 - 값 쌍에 대해 콜백 함수를 호출합니다.

성능

sync.Map 은 읽기 - 쓰기 분리를 통해 동시성 제어를 구현하며, 읽기가 많고 쓰기가 적은 상황에 더 적합합니다. 대부분의 경우 키 - 값 쌍을 액세스할 때 락이 필요하지 않기 때문입니다. 하지만 새 요소를 추가하려면 전역 락을 획득해야 하며, 이는 현재 map 의 모든 연산을 블로킹하므로 쓰기 성능이 저하됩니다. 따라서 sync.Map 은 모든 상황에 적합하지 않습니다. 읽기가 적고 쓰기가 많은 상황에서는 세그먼트 락 방식을 사용하여 전역 블로킹을 피할 수 있습니다. 여기서는 오픈소스 구현 orcaman/concurrent-map: a thread-safe concurrent map for go (github.com) 을 추천합니다. 샤딩 방식으로 구현되었으며 제네릭을 지원합니다. 성능과 사용 경험 측면에서 더 좋을 것입니다.