syncmap

sync.Map được cung cấp bởi thư viện chuẩn go là một map an toàn đồng thời, khi sử dụng nó không cần dùng đến các cách như khóa để kiểm soát, việc triển khai của nó không quá phức tạp, tổng cộng chỉ khoảng hai ba trăm dòng code sau khi bỏ chú thích.

Cấu trúc

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

Nó tổng cộng chỉ có bốn trường, lần lượt như sau

• read, map chỉ đọc, có thể hiểu là bộ đệm của dirty
• dirty, một map bình thường
• misses, số lần không trúng khi truy cập read
• mu, bảo vệ an toàn đồng thời của dirty

read là kiểu sync.readonly, bên trong nó vẫn là một map, trong đó trường amended biểu thị dirty có chứa key mà read không có không.

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

Ngoài ra cấu trúc kiểu entry như sau, p là một con trỏ trỏ đến value.

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

Đối với một entry而言, nó có ba tình huống có thể:

1. Tình huống bình thường, chứa value tương ứng
2. p là nil, biểu thị cặp key-value này đã bị xóa, lúc này dirty có thể là rỗng, hoặc nó vẫn có thể tồn tại trong dirty.
3. p == expunged, expunged là một đối tượng interface rỗng, cũng đại diện cho cặp key-value đã bị xóa và không tồn tại trong dirty.

An toàn đồng thời của map thư viện chuẩn được thực hiện thông qua tách đọc ghi, con trỏ entry mà read và dirty lưu trữ đều trỏ đến cùng một vùng value, read là chỉ đọc nên khi nhiều goroutine truy cập cũng không có vấn đề an toàn, dirty là có thể bị sửa đổi, được bảo vệ bởi khóa tương hỗ, misses ghi lại số lần key truy cập không trúng, khi số lần tích lũy đến một giá trị nhất định, dirty hiện tại sẽ chuyển thành read, misses được đặt lại về 0, đây là logic làm việc đại khái của sync.Map, sau này sẽ phân tích tỉ mỉ hơn các thao tác của nó.

Đọc

Thao tác đọc tương ứng với phương thức Map.Load, code như sau

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

Đầu tiên nó sẽ truy cập read, nếu tồn tại thì trực tiếp trả về, ngược lại sẽ đi thử持有 khóa tương hỗ mu, sau đó lại truy cập read, vì trong thời gian có được khóa dirty có thể đã thăng cấp thành read, nếu vẫn không tìm thấy, cuối cùng sẽ đi truy cập dirty, và ghi lại một lần miss, rồi mở khóa.

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
}

Thông qua phương thức missLocked có thể thấy, ngưỡng dirty thăng cấp thành read là m.misses >= len(m.dirty).

Viết

Thao tác viết tương ứng là phương thức Store, nhưng thực tế cũng do phương thức Swap hoàn thành, previous biểu thị giá trị trước đó, loaded biểu thị key có tồn tại không.

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

Quy trình thao tác viết chia làm hai phần, nếu key truy cập tồn tại trong read, thì sẽ trực tiếp lấy entry tương ứng, sau đó thông qua CAS để cập nhật value của entry, trong thời gian không cần khóa.

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

Trong thời gian tự quay, nếu p == expunged thì biểu thị key này đã bị xóa, sẽ trực tiếp trả về.

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

Nếu key không tồn tại trong read, sẽ thử lấy khóa để thực hiện các thao tác tiếp theo, tiếp theo chia làm ba tình huống. Tình huống đầu tiên, trong thời gian lấy khóa dirty đã thăng cấp thành read, nếu entry truy cập là expunged, thì biểu thị nó đã bị xóa, và không tồn tại trong dirty, lúc này cần thêm nó vào dirty, rồi lưu trữ value tương ứng.

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

Tình huống thứ hai, trong read không có, nhưng trong dirty có, cũng là trực tiếp lưu trữ value tương ứng

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

Tình huống thứ ba, trong read không có, trong dirty cũng không có, ở đây nếu read.amended là false, biểu thị dirty là rỗng, sau đó sẽ sử dụng m.dirtyLocked để sao chép tất cả cặp key-value chưa bị xóa trong read vào dirty, rồi đánh dấu read.amended là true, cuối cùng sẽ trực tiếp tạo mới một entry để lưu trữ value tương ứng.

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

Xóa

Thao tác xóa tương ứng là phương thức LoadAndDelete, ý tưởng của nó gần như hoàn toàn nhất quán với thao tác đọc, chỉ thêm một lời gọi hàm 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
}

Khi xóa cặp key-value thì永远 chỉ thực hiện thao tác delete đối với dirty, đối với read而言, chỉ sẽ sửa đổi value của entry mà nó lưu trữ thành 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
    }
  }
}

Duyệt

Thao tác duyệt tương ứng với phương thức 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
    }
  }
}

Khi duyệt chỉ duyệt read, nếu read.amended là true, biểu thị key trong read có thiếu, lúc này sẽ trực tiếp thăng cấp dirty thành read, sau đó thông qua vòng lặp for range để duyệt, và gọi hàm callback cho mỗi cặp key-value.

Hiệu suất

sync.Map áp dụng cách tách đọc ghi để kiểm soát đồng thời, nó càng thích hợp cho tình huống đọc nhiều viết ít, vì trong đa số tình huống truy cập một cặp key-value không cần khóa. Nhưng nếu muốn thêm một phần tử, thì cần持有 một khóa toàn cục, nó sẽ chặn tất cả các thao tác của map hiện tại, điều này dẫn đến hiệu suất viết thấp, nên sync.Map không thích hợp cho tất cả các tình huống, đối với tình huống đọc ít viết nhiều, có thể áp dụng cách khóa phân đoạn để thực hiện, như vậy có thể tránh chặn toàn cục, ở đây giới thiệu một triển khai nguồn mở orcaman/concurrent-map: a thread-safe concurrent map for go (github.com), áp dụng cách phân mảnh để thực hiện, và hỗ trợ generic, về hiệu suất và trải nghiệm sử dụng đều sẽ tốt hơn một chút.