syncmap

Go standart kütüphanesi tarafından sağlanan sync.Map eşzamanlılık güvenli bir map'tir. Kullanırken kilit kullanmaya gerek yoktur. Uygulaması özellikle karmaşık değildir, yorumlar kaldırıldıktan sonra sadece yaklaşık iki ila üç yüz satır kod vardır.

Yapı

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

Sadece dört alana sahiptir:

read: salt okunur map, dirty için önbellek olarak anlaşılabilir
dirty: normal bir map
misses: read'e erişirken kaçırma sayısı
mu: dirty'nin eşzamanlılık güvenliğini korur

read tipi sync.readonly'dır, içinde hala bir map'tir. amended alanı, dirty'nin read'de olmayan anahtarlara sahip olup olmadığını belirtir.

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

Ayrıca, entry tipi yapısı aşağıdaki gibidir, burada p değere işaretçidir:

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

Bir entry için üç olası durum vardır:

Normal durum: ilgili değeri saklar
p nil olduğunda: anahtar-değer çiftinin silindiğini gösterir. Bu zamanda, dirty boş olabilir veya hala dirty'de var olabilir.
p == expunged: expunged boş bir interface nesnesidir, ayrıca anahtar-değer çiftinin silindiğini ve dirty'de bulunmadığını gösterir.

Standart kütüphane map'in eşzamanlılık güvenliği okuma-yazma ayrımı ile sağlanır. read ve dirty'de saklanan entry işaretçileri aynı değere işaret eder. read salt okunurdur, bu yüzden birden fazla goroutine tarafından erişildiğinde güvenlik sorunu yoktur. dirty değiştirilebilir ve mutex kilidi ile korunur. misses anahtar erişim kaçırma sayısını kaydeder. Sayı belirli bir değere ulaştığında, mevcut dirty, read olur ve misses temizlenir. Bu sync.Map'in genel çalışma mantığıdır. Sonraki bölümler operasyonlarını daha detaylı analiz edecektir.

Okuma

Okuma işlemi Map.Load metoduna karşılık gelir:

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

İlk olarak read'e erişir. Eğer varsa, doğrudan döndürür. Aksi takdirde, mu mutex kilidini almaya çalışır, sonra read'e tekrar erişir. Bu kilit alma sırasında, dirty read'e yükseltilmiş olabilir. Eğer hala bulunamazsa, sonunda dirty'ye erişir, bir kaçırma kaydeder, sonra kilidi açar.

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 metodundan görebileceğimiz gibi, dirty'nin read'e yükseltilmesi için eşik koşulu m.misses >= len(m.dirty)'dir.

Yazma

Yazma işlemi Store metoduna karşılık gelir, ancak aslında Swap metodu tarafından tamamlanır. previous önceki değeri temsil eder ve loaded anahtarın var olup olmadığını gösterir.

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

Yazma işlemi süreci iki bölüme ayrılır. Eğer erişilen anahtar read'de varsa, doğrudan ilgili entry'yi alır, sonra CAS ile entry değerini günceller, süreçte kilit kullanmaz.

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

Dönme sırasında, eğer p == expunged, anahtarın silindiğini gösterir, bu yüzden doğrudan döner.

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

Eğer anahtar read'de yoksa, sonraki operasyonlar için kilidi almaya çalışır. Sonra üç durum vardır. İlk durum: kilit alma sırasında, dirty read'e yükseltildi. Eğer erişilen entry expunged ise, silindiğini ve dirty'de bulunmadığını gösterir. Bu durumda, dirty'ye eklenmesi, sonra ilgili değeri saklaması gerekir.

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

İkinci durum: read'de değil, ancak dirty'de var. Ayrıca doğrudan ilgili değeri saklar:

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

Üçüncü durum: read'de değil ve dirty'de de değil. Burada, eğer read.amended false ise, dirty'nin boş olduğunu gösterir. Sonra m.dirtyLocked kullanarak silinmemiş tüm anahtar-değer çiftlerini read'den dirty'ye kopyalar, read.amended'i true olarak işaretler ve son olarak yeni bir entry oluşturup değeri saklar.

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

Silme

Silme işlemi LoadAndDelete metoduna karşılık gelir. Mantığı neredeyse tamamen okuma işlemi ile aynıdır, sadece ek bir delete fonksiyon çağrısı vardır.

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
}

Bir anahtar-değer çiftini silerken, delete işlemi sadece dirty üzerinde yapılır. Read için, sadece saklanan entry'nin değerini nil olarak değiştirir.

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

Yineleme

Yineleme işlemi Range metoduna karşılık gelir:

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

Yineleme sırasında, sadece read yinelenir. Eğer read.amended true ise, read'de eksik anahtarlar olduğunu gösterir. Bu durumda, dirty doğrudan read'e yükseltilir, sonra for range döngüsü ile yinelenir, her anahtar-değer çifti için callback fonksiyonu çağırır.

Performans

sync.Map eşzamanlılık kontrolü için okuma-yazma ayrımı kullanır. Çoğu durumda bir anahtar-değer çiftine erişim kilit gerektirmediği için çoğunlukla okuma senaryolarına daha uygundur. Ancak, yeni bir eleman eklerken, tüm harita üzerindeki işlemleri engelleyen global bir kilit alması gerekir. Bu yazma performansının kötü olmasına yol açar. Yani sync.Map tüm durumlar için uygun değildir. Çoğunlukla yazma senaryoları için, global olarak engellemekten kaçınmak için bölümlü kilit kullanılabilir. İşte önerilen bir açık kaynak uygulama: orcaman/concurrent-map: a thread-safe concurrent map for go (github.com). Parçalama kullanılarak uygulanmıştır, jenerikleri destekler ve daha iyi performans ve kullanıcı deneyimi sağlar.

syncmap ​

Yapı ​

Okuma ​

Yazma ​

Silme ​

Yineleme ​

Performans ​