Глубокое понимание принципа анализа Go-sync.Map

Go

Map is like a Go map[interface{}]interface{} but is safe for concurrent use

by multiple goroutines without additional locking or coordination.

Loads, stores, and deletes run in amortized constant time.

Вышеупомянутое является официальным правомsync.Mapописание, из описания,sync.Mapиmapтак же, как,sync.MapБазовая реализация также зависит отmap,ноsync.MapотносительноmapЭто одновременно.

1. Обзор структуры

1.1. sync.Map

Структура sync.Map такова.

type Map struct {
	mu Mutex

  // 后面是readOnly结构体，依靠map实现，仅仅只用来读
	read atomic.Value // readOnly

	// 这个map主要用来写的，部分时候也承担读的能力
	dirty map[interface{}]*entry

	// 记录自从上次更新了read之后，从read读取key失败的次数
	misses int
}

1.2. readOnly

Исчезла структура, соответствующая свойству sync.Map.read, я не совсем понимаю, почему свойства структуры readOnly не помещаются напрямую в структуру sync.Map.

type readOnly struct {
  // 读操作所对应的map
	m       map[interface{}]*entry
  // dirty是否包含m中不存在的key
	amended bool // true if the dirty map contains some key not in m.
}

1.3. entry

запись небезопасна. Указатель, который записывает реальный адрес хранилища данных

type entry struct {
	p unsafe.Pointer // *interface{}
}

1.4 Структурная схема

Через приведенную выше структуру мы можем просто нарисовать схематическую диаграмму структуры

2. Процесс анализ

Мы проходим следующую анимацию (вы также можете отлаживать вручную), чтобы увидеть, что происходит, когда мы выполняемStore Load DeleteКогда , какова трансформация этой структуры, давайте сначала добавим немного нашего познания

func main() {
	m := sync.Map{}
	m.Store("test1", "test1")
	m.Store("test2", "test2")
	m.Store("test3", "test3")
	m.Load("test1")
	m.Load("test2")
	m.Load("test3")
	m.Store("test4", "test4")
	m.Delete("test")
	m.Load("test")
}

Взяв приведенный выше код в качестве примера, давайте посмотрим на структурное преобразование m

3. Анализ исходного кода

3.1. Добавить ключ

Добавьте значение ключа,Storeметод достижения

func (m *Map) Store(key, value interface{}) {
	read, _ := m.read.Load().(readOnly)
  // 如果这个key存在，通过tryStore更新
	if e, ok := read.m[key]; ok && e.tryStore(&value) {
		return
	}
  // 走到这里有两种情况，1. key不存在 2. key对应的值被标记为expunged，read中的entry拷贝到dirty时，会将key标记为expunged，需要手动解锁
	m.mu.Lock()
	read, _ = m.read.Load().(readOnly)
	if e, ok := read.m[key]; ok {
    // 第二种情况，先解锁，然后添加到dirty
		if e.unexpungeLocked() {
			// The entry was previously expunged, which implies that there is a
			// non-nil dirty map and this entry is not in it.
			m.dirty[key] = e
		}
		e.storeLocked(&value)
	} else if e, ok := m.dirty[key]; ok {
    // m中没有，但是dirty中存在，更新dirty中的值
		e.storeLocked(&value)
	} else {
    // 如果amend==false，说明dirty和read是一致的，但是我们需要新加key到dirty里面，所以更新read.amended
		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.
      // 这一步会将read中所有的key标记为 expunged
			m.dirtyLocked()
			m.read.Store(readOnly{m: read.m, amended: true})
		}
		m.dirty[key] = newEntry(value)
	}
	m.mu.Unlock()
}

3.1.1. tryLock

func (e *entry) tryStore(i *interface{}) bool {
	p := atomic.LoadPointer(&e.p)
  // 这个entry是key对应的entry，p是key对应的值，如果p被设置为expunged，不能直接更新存储
	if p == expunged {
		return false
	}
	for {
    // 原子更新
		if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
			return true
		}
		p = atomic.LoadPointer(&e.p)
		if p == expunged {
			return false
		}
	}
}

Trylock сделает значение, соответствующее ключу, независимо от того, установлено ли оно на ExpUnged, в этом случае его нельзя обновить напрямую.

3.1.2. dirtyLock

Именно здесь устанавливается флаг expunged, и именно эта функция синхронизирует данные при чтении с грязными.

func (m *Map) dirtyLocked() {
  // dirty != nil 说明dirty在上次read同步dirty数据后，已经有了修改了，这时候read的数据不一定准确，不能同步
	if m.dirty != nil {
		return
	}

	read, _ := m.read.Load().(readOnly)
	m.dirty = make(map[interface{}]*entry, len(read.m))
	for k, e := range read.m {
    // 这里调用tryExpungeLocked 来给entry，即key对应的值 设置标志位
		if !e.tryExpungeLocked() {
			m.dirty[k] = e
		}
	}
}

3.1.3. tryExpungeLocked

С помощью атомарных операций установите флаг expunged на значение, соответствующее записи и ключу.

func (e *entry) tryExpungeLocked() (isExpunged bool) {
	p := atomic.LoadPointer(&e.p)
	for p == nil {
		if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
			return true
		}
		p = atomic.LoadPointer(&e.p)
	}
	return p == expunged
}

3.1.4. unexpungeLocked

func (e *entry) unexpungeLocked() (wasExpunged bool) {
	return atomic.CompareAndSwapPointer(&e.p, expunged, nil)
}

Согласно вышеприведенному анализу мы обнаружили, что при добавлении нового он разделяется на четыре ситуации:

  1. Ключ изначально существовал при чтении, получить адрес памяти, соответствующий ключу, и изменить его атомарно.
  2. Ключ существует, но значение, соответствующее ключу, помечено как удаленное, разблокировать, снять пометку, обновить ключ в грязном, синхронизировать с прочитанным, а затем изменить значение, соответствующее ключу.
  3. Нет ключа в режиме чтения, но ключ существует в грязном, напрямую измените значение ключа в грязном
  4. В read и dirty нет значения. Сначала оцените, было ли изменено грязное содержимое с момента последнего чтения, синхронизировавшего грязное содержимое. Если нет, сначала синхронизируйте прочитанное и грязное значения, а затем добавьте новое значение ключа к грязному.

При возникновении четвертой ситуации легко вызвать недоумение: раз read.amended == false, значит, данные не модифицировались, то зачем считанные данные синхронизировать с грязными?

Ответ вLoadВ функции будет ответ, потому что при чтении синхронизирует грязные данные, она напрямую передает грязный указатель на карту в read.m, а затем устанавливает грязный указатель в nil, поэтому после синхронизации грязный становится nil

Давайте посмотрим на конкретную реализацию

3.2. Читать (нагрузка)

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
	read, _ := m.read.Load().(readOnly)
	e, ok := read.m[key]
  // 如果read的map中没有，且存在修改
	if !ok && read.amended {
		m.mu.Lock()
		// Avoid reporting a spurious miss if m.dirty got promoted while we were
		// blocked on m.mu. (If further loads of the same key will not miss, it's
		// not worth copying the dirty map for this key.)
    // 再查找一次，有可能刚刚将dirty升级为read了
		read, _ = m.read.Load().(readOnly)
		e, ok = read.m[key]
		if !ok && read.amended {
      // 如果amended 还是处于修改状态，则去dirty中查找
			e, ok = m.dirty[key]
			// Regardless of whether the entry was present, record a miss: this key
			// will take the slow path until the dirty map is promoted to the read
			// map.
      // 增加misses的计数，在计数达到一定规则的时候，触发升级dirty为read
			m.missLocked()
		}
		m.mu.Unlock()
	}
  // read dirty中都没有找到
	if !ok {
		return nil, false
	}
  // 找到了，通过load判断具体返回内容
	return e.load()
}

func (e *entry) load() (value interface{}, ok bool) {
	p := atomic.LoadPointer(&e.p)
  // 如果p为nil或者expunged标识，则key不存在
	if p == nil || p == expunged {
		return nil, false
	}
	return *(*interface{})(p), true
}

Почему p найдено, но значение, соответствующее p, равно нулю? Этот ответ анализируется позжеDeleteфункция будет раскрыта

3.2.1. missLocked

func (m *Map) missLocked() {
	m.misses++
	if m.misses < len(m.dirty) {
		return
	}
  // 直接把dirty的指针给read.m，并且设置dirty为nil，这里也就是 Store 函数的最后会调用 m.dirtyLocked的原因
	m.read.Store(readOnly{m: m.dirty})
	m.dirty = nil
	m.misses = 0
}

3.3. Удалить

Удаление здесь не просто удаление ключа с карты

func (m *Map) Delete(key interface{}) {
	read, _ := m.read.Load().(readOnly)
	e, ok := read.m[key]
  // read中没有这个key，但是Map被标识修改了，那么去dirty里面看看
	if !ok && read.amended {
		m.mu.Lock()
		read, _ = m.read.Load().(readOnly)
		e, ok = read.m[key]
		if !ok && read.amended {
      // 调用delete删除dirty的map，delete会判断key是否存在的
			delete(m.dirty, key)
		}
		m.mu.Unlock()
	}
  // 如果read中存在，则假删除
	if ok {
		e.delete()
	}
}

func (e *entry) delete() (hadValue bool) {
	for {
		p := atomic.LoadPointer(&e.p)
    // 已经是被删除了，不需要管了
		if p == nil || p == expunged {
			return false
		}
    // 原子性 将key的值设置为nil
		if atomic.CompareAndSwapPointer(&e.p, p, nil) {
			return true
		}
	}
}

По вышеприведенной логике видно, что при удалении возникают следующие ситуации

  1. Если чтения нет, а Карта модифицируется, попробуйте удалить ключ в карте в грязном
  2. Нет никаких изменений в чтении, и в карте нет модификации, то есть такого ключа нет, операция не требуется
  3. При чтении попробуйте установить значение, соответствующее ключу, равным нулю, и тогда вы будете знать, что оно удалено, когда вы прочитаете его позже, потому что значение карты в dirty и значение в карте чтения указывают на одно и то же. адресное пространство, поэтому модифицируйте Чтение для изменения грязного

3.3. Обход (Диапазон)

Логика обхода относительно проста, карта имеет всего два состояния, модифицированное и немодифицированное.

Изменено: передать грязный указатель для чтения, прочитать последние данные, а затем пройти карту чтения

Без изменений: просто пройдите карту чтения

func (m *Map) Range(f func(key, value interface{}) bool) {
	read, _ := m.read.Load().(readOnly)
	if read.amended {
		m.mu.Lock()
		read, _ = m.read.Load().(readOnly)
		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
		}
	}
}

3.4. Применимые сценарии

Когда официальная презентация, но и на месте, чтобы сделать подходящее объяснение

The Map type is optimized for two common use cases:

(1) when the entry for a given key is only ever written once but read many times, as in caches that only grow,

(2) when multiple goroutines read, write, and overwrite entries for disjoint sets of keys.

In these two cases, use of a Map may significantly reduce lock contention compared to a Go map paired with a separate Mutex or RWMutex.

Анализируя исходный код, понимается, что причина этих двух правил:

Читать больше и меньше писать: В среде больше читать и меньше писать, все читается из карты чтения, и блокировка не требуется. В случае большего количества записи и меньшего чтения требуется блокировка. Во-вторых, есть синхронизация читать данные грязно.Возможность работы, большое количество операций копирования сильно снизит производительность

Чтение и запись разных ключей: sync.Map — это атомарная операция над значением ключа, которая эквивалентна блокировке и загрузке ключа, поэтому чтение и запись нескольких ключей могут выполняться одновременно.

Категории