syncmap

sync.Map provided by Go standard library is a concurrency-safe map. There's no need to use locks when using it. Its implementation is not particularly complex, with only about two to three hundred lines of code after removing comments.

Structure

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

It has only four fields:

• read: read-only map, can be understood as a cache for dirty
• dirty: a normal map
• misses: count of misses when accessing read
• mu: protects concurrency safety of dirty

read is of type sync.readonly, which internally is still a map. The amended field indicates whether dirty contains keys that read doesn't have.

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

Additionally, the entry type structure is as follows, where p is a pointer to value:

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

For an entry, there are three possible cases:

1. Normal case: stores the corresponding value
2. p is nil: indicates the key-value pair has been deleted. At this time, dirty may be empty, or it may still exist in dirty.
3. p == expunged: expunged is an empty interface object, also indicating the key-value pair has been deleted and doesn't exist in dirty.

The concurrency safety of standard library map is achieved through read-write separation. The entry pointers stored in read and dirty point to the same value. read is read-only, so there's no safety issue when accessed by multiple goroutines. dirty can be modified and is protected by mutex lock. misses records the number of key access misses. When the count accumulates to a certain value, current dirty becomes read, and misses is cleared. This is the general working logic of sync.Map. Subsequent sections will analyze its operations in more detail.

Read

Read operation corresponds to Map.Load method:

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

It first accesses read. If it exists, return directly. Otherwise, try to acquire mu mutex lock, then access read again. This is because during lock acquisition, dirty may have been promoted to read. If still not found, it will eventually access dirty, record a miss, then unlock.

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
}

From the missLocked method, we can see the threshold condition for dirty promotion to read is m.misses >= len(m.dirty).

Write

Write operation corresponds to Store method, but is actually completed by Swap method. previous represents the previous value, and loaded indicates whether the key exists.

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

The write operation process is divided into two parts. If the accessed key exists in read, it directly gets the corresponding entry, then updates the entry value through CAS, without locking during the process.

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

During spinning, if p == expunged, it indicates the key has been deleted, so it returns directly.

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

If the key doesn't exist in read, it tries to acquire the lock for subsequent operations. Next are three cases. First case: during lock acquisition, dirty was promoted to read. If the accessed entry is expunged, it indicates it has been deleted and doesn't exist in dirty. In this case, it needs to be added to dirty, then store the corresponding value.

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

Second case: not in read, but exists in dirty. Also directly stores the corresponding value:

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

Third case: not in read, and not in dirty either. Here, if read.amended is false, it indicates dirty is empty. Then it uses m.dirtyLocked to copy all undeleted key-value pairs from read to dirty, marks read.amended as true, and finally creates a new entry to store the value.

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

Delete

Delete operation corresponds to LoadAndDelete method. Its logic is almost completely consistent with read operation, just with an additional delete function call.

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
}

When deleting a key-value pair, delete operation is only performed on dirty. For read, it only modifies the stored entry's value to 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
    }
  }
}

Iteration

Iteration operation corresponds to Range method:

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

During iteration, only read is iterated. If read.amended is true, it indicates read has missing keys. In this case, dirty is directly promoted to read, then iterated through for range loop, calling callback function for each key-value pair.

Performance

sync.Map adopts read-write separation for concurrency control. It's more suitable for read-mostly scenarios because accessing a key-value pair doesn't require locking in most cases. However, if adding a new element, it needs to acquire a global lock, which blocks all operations on the current map. This leads to poor write performance. So sync.Map is not suitable for all situations. For write-mostly scenarios, segmented lock can be used to avoid blocking globally. Here's a recommended open-source implementation: orcaman/concurrent-map: a thread-safe concurrent map for go (github.com). It's implemented using sharding, supports generics, and provides better performance and user experience.