syncmap

Go 標準ライブラリが提供する sync.Map は並行安全な map で、使用する際にロックなどの方式で制御する必要はありません。その実装はそれほど複雑ではなく、コメントを削除すると合計 200〜300 行程度のコードです。

構造

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

フィールドは合計 4 つだけです。それぞれ以下の通りです。

• read：読み取り専用の map。dirty のキャッシュと理解できます
• dirty：通常の map
• misses：read へのアクセスでヒットしなかった回数
• mu：dirty の並行安全を保護する

read は sync.readOnly 型で、内部はやはり map です。その中の amended フィールドは dirty が read にない key を含んでいるかどうかを表します。

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 而言、3 つの可能性があります。

1. 通常の状況、対応する値が格納されている
2. p が nil、そのキー値対が削除されたことを表す。此时 dirty は空の場合もあれば、依然として dirty 内に存在する場合もある
3. p == expunged、expunged は空のインターフェースオブジェクトで、キー値対が既に削除され、dirty 内に存在しないことも表す

標準ライブラリ map の並行安全は読み書き分離によって実現されています。read と dirty が格納する entry ポインタはすべて同じ value を指しています。read は読み取り専用なので、複数のゴルーチンがアクセスしても安全问题はありません。dirty は変更可能で、相互排他ロックによって保護されています。misses は key アクセスがヒットしなかった回数を記録し、回数が一定値に達すると、現在の 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 を 1 回記録してロック解除します。

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 は key が存在するかどうかを表します。

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

書き込み操作のプロセスは 2 つの部分に分かれます。アクセスした key が 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 の場合、その key が既に削除されたことを表し、直接返します。

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

key が read 内に存在しない場合、ロックを取得して次の操作を試みます。次に 3 つの状況に分かれます。1 つ目の状況、ロック取得期間中に 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
    }
}

2 つ目の状況、read にはなく、dirty 内にある場合、対応する値を直接格納します。

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

3 つ目の状況、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 関数の呼び出しが 1 つ増えただけです。

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 内の key に欠落があることを表します。この時、直接 dirty を read に昇格させ、for range ループを通じて走査し、各キー値対に対してコールバック関数を呼び出します。

パフォーマンス

sync.Map は読み書き分離の方式を採用して並行制御を行っています。読み取りが多く書き込みが少ないシーンに適しています。大部分の状況でキー値対にアクセスする際、ロックは不要です。しかし新しい要素を追加する必要がある場合、グローバルロックを保持する必要があります。現在の map のすべての操作をブロッキングするため、書き込みパフォーマンスの低下につながります。したがって sync.Map はすべての状況に適しているわけではありません。読み取りが少なく書き込みが多い状況では、セグメントロックの方式を採用して実装できます。これによりグローバルなブロッキングを回避できます。ここでオープンソース実装 orcaman/concurrent-map: a thread-safe concurrent map for go (github.com) を推奨します。シャード方式で実装され、ジェネリックもサポートしています。パフォーマンスと使用体験の両面で優れています。