syncmap

sync.Map yang disediakan oleh pustaka standar go adalah map yang aman secara konkuren, tidak perlu menggunakan cara seperti lock saat menggunakannya, implementasinya tidak terlalu kompleks, hanya sekitar dua atau tiga ratus baris kode setelah menghapus komentar.

Struktur

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

Ia hanya memiliki empat field, masing-masing sebagai berikut

• read, map yang hanya dapat dibaca, dapat dipahami sebagai cache untuk dirty
• dirty, map biasa
• misses, jumlah kali akses ke read tidak命中
• mu, melindungi keamanan konkuren dirty

read adalah tipe sync.readonly, internalnya juga merupakan map, field amended di dalamnya menunjukkan apakah dirty berisi key yang tidak ada di read.

type readOnly struct {
  m       map[any]*entry
  amended bool // true jika dirty map berisi beberapa key yang tidak ada di m.
}

Selain itu struktur tipe entry adalah sebagai berikut, p adalah pointer yang menunjuk ke value.

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

Untuk sebuah entry, ia memiliki tiga kemungkinan situasi

1. Situasi normal, menyimpan value yang sesuai
2. p adalah nil, menunjukkan pasangan key-value telah dihapus, saat ini dirty mungkin kosong, atau mungkin masih ada di dirty
3. p == expunged, expunged adalah objek interface kosong, juga mewakili bahwa pasangan key-value telah dihapus dan tidak ada di dirty

Keamanan konkuren map pustaka standar dicapai melalui pemisahan baca-tulis, pointer entry yang disimpan oleh read dan dirty menunjuk ke value yang sama, read hanya dapat dibaca sehingga tidak akan ada masalah keamanan saat beberapa goroutine mengaksesnya, dirty dapat dimodifikasi dan dilindungi oleh mutex, misses mencatat jumlah kali key tidak命中, ketika jumlah ini terakumulasi ke nilai tertentu, dirty saat ini akan berubah menjadi read, misses direset, ini adalah logika kerja大致 sync.Map, selanjutnya akan menganalisis operasinya dengan lebih detail.

Baca

Operasi baca sesuai dengan metode Map.Load, kodenya adalah sebagai berikut

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

Pertama-tama ia akan mengakses read, jika ada langsung return, jika tidak akan mencoba memegang mutex mu, kemudian mengakses read lagi, karena selama periode memegang lock dirty mungkin telah dipromosikan menjadi read, jika masih tidak ditemukan, akhirnya akan mengakses dirty, dan mencatat satu miss, kemudian 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
}

Dari metode missLocked dapat dilihat, ambang batas dirty dipromosikan menjadi read adalah m.misses >= len(m.dirty).

Tulis

Operasi tulis sesuai dengan metode Store, tetapi sebenarnya diselesaikan oleh metode Swap, previous mewakili nilai sebelumnya, loaded menunjukkan apakah key ada.

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

Proses operasi tulis dibagi menjadi dua bagian, jika key yang diakses ada di read, maka akan langsung mendapatkan entry yang sesuai, kemudian memperbarui nilai entry melalui CAS, tidak perlu lock selama periode.

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

Selama periode spinning, jika p == expunged menunjukkan bahwa key telah dihapus, akan langsung return.

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

Jika key tidak ada di read, akan mencoba mendapatkan lock untuk melakukan operasi selanjutnya, selanjutnya dibagi menjadi tiga situasi. Situasi pertama, selama periode mendapatkan lock dirty dipromosikan menjadi read, jika entry yang diakses adalah expunged, menunjukkan bahwa ia telah dihapus dan tidak ada di dirty, saat ini perlu menambahkannya ke dirty, kemudian menyimpan value yang sesuai.

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

Situasi kedua, tidak ada di read, tetapi ada di dirty, juga langsung menyimpan value yang sesuai

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

Situasi ketiga, tidak ada di read, juga tidak ada di dirty, di sini jika read.amended adalah false, menunjukkan bahwa dirty kosong, kemudian akan menggunakan m.dirtyLocked untuk menyalin semua pasangan key-value yang belum dihapus di read ke dirty, kemudian menandai read.amended sebagai true, terakhir akan langsung membuat entry baru untuk menyimpan value yang sesuai.

else {
    if !read.amended {
        // Kami menambahkan key baru pertama ke dirty map.
        // Pastikan dialokasikan dan tandai read-only map sebagai tidak lengkap.
        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
    }
  }
}

Hapus

Operasi hapus sesuai dengan metode LoadAndDelete, idenya hampir sama persis dengan operasi baca, hanya menambahkan pemanggilan fungsi 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
}

Saat menghapus pasangan key-value, hanya akan mengeksekusi operasi delete pada dirty, untuk read而言，hanya akan memodifikasi nilai entry yang disimpannya menjadi 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
    }
  }
}

Traversing

Operasi traversing sesuai dengan metode 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
    }
  }
}

Saat traversing hanya akan traversing read, jika read.amended adalah true, menunjukkan bahwa key di read tidak lengkap, saat ini akan langsung mempromosikan dirty menjadi read, kemudian traversing melalui loop for range, dan memanggil fungsi callback untuk setiap pasangan key-value.

Performa

sync.Map mengadopsi cara pemisahan baca-tulis untuk kontrol konkuren, lebih cocok untuk skenario baca banyak tulis sedikit, karena dalam sebagian besar kasus saat mengakses pasangan key-value tidak perlu lock. Tetapi jika ingin menambahkan elemen baru, perlu memegang lock global, yang akan memblokir semua operasi map saat ini, ini menyebabkan performa tulis yang rendah, jadi sync.Map tidak cocok untuk semua situasi, untuk situasi baca sedikit tulis banyak, dapat mengadopsi cara segmented lock, dapat menghindari blocking global, di sini merekomendasikan implementasi open source orcaman/concurrent-map: a thread-safe concurrent map for go (github.com), diimplementasikan dengan cara sharding, dan mendukung generik, dalam performa dan pengalaman penggunaan akan lebih baik.