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 و dirty يخزنان مؤشرات entry التي تشير لنفس قيمة value، read للقراءة فقط، لذا لا توجد مشاكل أمنية عند وصول عدة كوروتينات، dirty يمكن تعديله ومحمي بقفل استبعاد متبادل، 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، إذا وُجد تُرجع مباشرة، وإلا ستحاول الحصول على قفل mu الاستبعادي، ثم تصل لـ read مرة أخرى، لأنه خلال فترة الحصول على القفل قد يترقى 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 المقابل، ثم تُحدِّث قيمة entry عبر CAS، دون الحاجة للقفل خلال هذه الفترة.

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

خلال الدوران، إذا كان 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، ستحاول الحصول على القفل لإجراء العمليات التالية، ثم تنقسم لثلاث حالات. الحالة الأولى، خلال فترة الحصول على القفل ترقى 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 لـ dirty، ثم يُعلَّم 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 على dirty فقط، أما بالنسبة لـ 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، وفي هذه الحالة يُرقَّى dirty مباشرة لـ read، ثم يُجتاز عبر حلقة for range، ويُستدعى دالة الاستدعاء الرجعي لكل زوج key-value.

الأداء

يستخدم sync.Map طريقة فصل القراءة والكتابة للتحكم في التزامن، وهو أنسب للحالات التي يكون فيها القراءة أكثر من الكتابة، لأنه في معظم الحالات لا يحتاج للقفل عند الوصول لزوج key-value. لكن إذا أُضيف عنصر جديد، يجب امتلاك قفل عام، وهذا سيحجب جميع عمليات map الحالي، مما يؤدي لضعف أداء الكتابة، لذا sync.Map ليس مناسبًا لجميع الحالات، للحالات التي يكون فيها القراءة أقل من الكتابة، يمكن استخدام طريقة الأقفال المجزأة للتنفيذ، وهذا يمكن أن يتجنب حجب الموقف العام، هنا نوصي بتنفيذ مفتوح المصدر orcaman/concurrent-map: a thread-safe concurrent map for go (github.com)، يُنفَّذ بطريقة التقسيم، ويدعم الوراثة، وسيكون أفضل في الأداء وتجربة الاستخدام.