syncmap

sync.Map ที่จัดเตรียมโดยไลบรารีมาตรฐานของ go เป็น map ที่ปลอดภัยต่อการทำงานพร้อมกัน ไม่จำเป็นต้องใช้ล็อกหรือวิธีอื่นเพื่อควบคุมเมื่อนำไปใช้ การใช้งานไม่ซับซ้อนมาก ลบความคิดเห็นออกแล้วมีโค้ดเพียงสองสามร้อยบรรทัด

โครงสร้าง

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

มีฟิลด์ทั้งหมดเพียงสี่ฟิลด์ ดังนี้

• read map แบบอ่านอย่างเดียว สามารถเข้าใจได้ว่าเป็นแคชของ dirty
• dirty map ธรรมดา
• misses จำนวนครั้งที่访问ไม่命中เมื่อ访问 read
• mu ปกป้องความปลอดภัยของการทำงานพร้อมกันของ dirty

read เป็นประเภท sync.readonly ภายในยังคงเป็น map ฟิลด์ amended แสดงว่า dirty มี key ที่ read ไม่มีหรือไม่

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 หนึ่งตัว มีสามกรณีที่เป็นไปได้

1. กรณีปกติ เก็บค่าที่ตรงกัน
2. p เป็น nil แสดงว่าคู่ key-value ถูกลบแล้ว ในขณะนี้ dirty อาจเป็นว่าง หรืออาจยังคงอยู่ใน dirty
3. p == expunged expunged เป็นอ็อบเจ็กต์อินเตอร์เฟซว่าง เช่นกันแสดงว่าคู่ key-value ถูกลบแล้วและไม่อยู่ใน dirty

ความปลอดภัยของการทำงานพร้อมกันของ map มาตรฐานใช้การแยก read/write เพื่อ實現 read และ dirty ที่เก็บตัวชี้ entry ชี้ไปยังพื้นที่ value เดียวกัน read เป็นแบบอ่านอย่างเดียว ดังนั้นเมื่อหลาย goroutine เข้าถึงก็ไม่มีปัญหาความปลอดภัย dirty สามารถถูกแก้ไขได้ อยู่ภายใต้การปกป้องของ mutex 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 หากมีอยู่จะคืนค่าโดยตรง มิฉะนั้นจะลองถือ mutex mu แล้ว访问 read เพราะในช่วงที่ได้รับ lock dirty อาจเลื่อนขั้นเป็น read หากยังไม่พบ สุดท้ายจะ访问 dirty และบันทึก miss หนึ่งครั้ง แล้วปลดล็อก

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)

ขั้นตอนการเขียนแบ่งเป็นสองส่วน หาก 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
    }
}

ในช่วง spin หาก 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 จะลองรับ lock เพื่อดำเนินการต่อไป ต่อไปแบ่งเป็นสามกรณี กรณีแรก ในช่วงที่ได้รับ lock 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
    }
}

กรณีที่สอง read ไม่มี แต่ dirty มี ก็เก็บค่าที่ตรงกันโดยตรง

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

กรณีที่สาม read ไม่มี dirty ก็ไม่มี ที่นี่หาก read.amended เป็น false แสดงว่า dirty ว่าง แล้วใช้ m.dirtyLocked คัดลอกคู่ key-value ที่ยังไม่ถูกลบทั้งหมดใน read ไปยัง ditry แล้ว标记 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

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
}

เมื่อลบคู่ key-value จะดำเนินการ delete กับ ditry เท่านั้น สำหรับ 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 แสดงว่า key ใน read ขาดหาย这时จะ直接将 ditry เลื่อนขั้นเป็น read แล้วใช้ลูป for range遍历 และเรียกฟังก์ชัน callback สำหรับแต่ละคู่ key-value

ประสิทธิภาพ

sync.Map ใช้วิธีแยก read/write เพื่อควบคุมการทำงานพร้อมกัน เหมาะกับสถานการณ์ที่อ่านมากเขียนน้อย เพราะในกรณีส่วนใหญ่การ访问คู่ key-value ไม่จำเป็นต้องล็อก แต่หากต้องการเพิ่มองค์ประกอบใหม่ จำเป็นต้องถือ lock ส่วนกลาง มันจะบล็อกการดำเนินการทั้งหมดของ map ปัจจุบัน ส่งผลให้ประสิทธิภาพการเขียนต่ำ ดังนั้น sync.Map ไม่เหมาะกับทุกสถานการณ์ สำหรับสถานการณ์ที่อ่านน้อยเขียนมาก สามารถใช้วิธี分段锁เพื่อ實現 ที่นี่ขอแนะนำการ开源实现 orcaman/concurrent-map: a thread-safe concurrent map for go (github.com) ใช้วิธี分片เพื่อ實現 และรองรับ generic ประสิทธิภาพและประสบการณ์การใช้งานจะดีกว่า