Анализ исходного кода Golang sync.Map, который вы должны знать

задний план

Как мы все знаем, обычная карта go не поддерживает параллелизм, другими словами, она не является потокобезопасной (горутинной). Блогер начал использовать golang 1.4, в то время параллельное чтение карты не поддерживалось, а параллельная запись приводила к грязным данным. После golang 1.6 одновременные операции чтения и записи будут вызывать панику напрямую:

fatal error: concurrent map read and map write

package main
func main() {
	m := make(map[int]int)
	go func() {
		for {
			_ = m[1]
		}
	}()
	go func() {
		for {
			m[2] = 2
		}
	}()
	select {}
}

Поэтому, когда необходимо поддерживать параллельное чтение и запись карт, блогеры используют два метода:

Сторонняя библиотека классовconcurrent-map.
map плюс sync.RWMutex для обеспечения безопасности потоков (горутин).

После версии golang 1.9 в пакете синхронизации появилась карта, безопасная для параллелизма, а также был предоставлен третий метод для блоггеров. Фокус этой статьи также здесь.Ради своевременности, эта статья основана на исходном коде golang 1.10 для анализа.

sync.Map

структура

Map

type Map struct {
	mu Mutex    //互斥锁，用于锁定dirty map

	read atomic.Value //优先读map,支持原子操作，注释中有readOnly不是说read是只读，而是它的结构体。read实际上有写的操作

	dirty map[interface{}]*entry // dirty是一个当前最新的map，允许读写

	misses int // 主要记录read读取不到数据加锁读取read map以及dirty map的次数，当misses等于dirty的长度时，会将dirty复制到read
}

readOnly

Readonly в основном используется для хранения, сохраненного в map.read посредством атомарных операций.

type readOnly struct {
	m       map[interface{}]*entry
	amended bool // 如果数据在dirty中但没有在read中，该值为true,作为修改标识
}

entry

type entry struct {
	// nil: 表示为被删除，调用Delete()可以将read map中的元素置为nil
	// expunged: 也是表示被删除，但是该键只在read而没有在dirty中，这种情况出现在将read复制到dirty中，即复制的过程会先将nil标记为expunged，然后不将其复制到dirty
	//  其他: 表示存着真正的数据
	p unsafe.Pointer // *interface{}
}

принцип

Если у вас есть доступ к большой Java, вы должны использовать CocurrentHashMapТехнология сегментации блокировкиКоличество блокировок увеличено, чтобы хорошо запоминался принцип управления количеством потоков, конкурирующих за одну и ту же блокировку.
Так использует ли sync.Map Голанга тот же принцип? Принцип sync.Map очень прост, используяПространство для времениСтратегия с помощью двух избыточных структур данных (чтение, загрязнение) для достижения влияния блокировки на производительность. Чтение и запись разделены на разные карты путем введения двух карт, где карта чтения обеспечивает одновременное чтение и атомарную запись существующих элементов, а грязная карта отвечает за чтение и запись. Таким образом, карта чтения может выполнять одновременное чтение без блокировки.Когда в карте чтения не считывается значение, оно будет заблокировано для последующего чтения, и количество промахов будет накапливаться.Когда количество промахов больше или равно длине грязной карты, поднимите грязную карту, чтобы прочитать карту. Из определения предыдущей структуры можно обнаружить, что хотя введены две карты, базовые данные хранят указатели, указывающие на одно и то же значение.

В начале sync.Map записывает данные

X=1
Y=2
Z=3

Грязная карта в основном принимает запросы на запись, а карта чтения не имеет данных.В настоящее время данные карты чтения и грязной карты показаны ниже.

При чтении данных читать из карты чтения. В это время карта чтения не имеет данных. Промах записывает количество неудачных операций чтения из карты чтения. Когда промахивается>=len(грязная карта), грязная карта напрямую обновляется до прочитанная карта. , Здесь адрес грязной карты копируется напрямую, а грязная карта очищается, а промахи устанавливаются в 0. В настоящее время данные прочитанной карты и измененной карты показаны ниже.

Теперь необходимо модифицировать Z-элемент Z=4, sync.Map напрямую модифицирует элементы прочитанной карты.

Если вновь добавленный элемент K = 5, вновь добавленный элемент должен управлять грязной картой.Если грязная карта напрямую обновляется до карты чтения после того, как количество промахов достигает порога, а грязная карта является пустой картой (исправлено чтение = =false), грязная карта должна быть Копировать данные из прочитанной карты.

Эффект после обновления следующий.

Если вам нужно удалить Z, вам нужно разделить его на несколько ситуаций:
Карта чтения существует с этим элементом, и чтение изменено == false: прямо устанавливает элемент в чтении на ноль.

Другой заключается в том, что элемент только что был записан в грязную карту и не был обновлен до карты чтения: напрямую вызовите встроенную функцию golang delete, чтобы удалить элемент грязной карты;

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

точка оптимизации

пространство для времени. За счет избыточных двух структур данных (чтение, загрязнение) реализуется влияние блокировки на производительность.
Используйте данные только для чтения (чтение), чтобы избежать конфликтов записи с чтением.
Динамическая регулировка, после того, как количество промахов велико, грязные данные обновлены для чтения.
двойная проверка.
Отложить удаление. Удаление значения ключа только помечается, а удаленные данные очищаются только при поднятии грязного.
Чтение, обновление, удаление из чтения предпочтительнее, потому что чтение при чтении не требует блокировки.

Анализ исходного кода метода

Load

Load возвращает значение ключа, сохраненное в карте, или nil, если значение отсутствует. Результат ok указывает, было ли найдено значение на карте.

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
	// 第一次检测元素是否存在
	read, _ := m.read.Load().(readOnly)
	e, ok := read.m[key]
	if !ok && read.amended {
		// 为dirty map 加锁
		m.mu.Lock()
		// 第二次检测元素是否存在，主要防止在加锁的过程中,dirty map转换成read map,从而导致读取不到数据
		read, _ = m.read.Load().(readOnly)
		e, ok = read.m[key]
		if !ok && read.amended {
			// 从dirty map中获取是为了应对read map中不存在的新元素
			e, ok = m.dirty[key]
			// 不论元素是否存在，均需要记录miss数，以便dirty map升级为read map
			m.missLocked()
		}
		// 解锁
		m.mu.Unlock()
	}
	// 元素不存在直接返回
	if !ok {
		return nil, false
	}
	return e.load()
}

грязная карта обновлена до чтения карты

func (m *Map) missLocked() {
	// misses自增1
	m.misses++
	// 判断dirty map是否可以升级为read map
	if m.misses < len(m.dirty) {
		return
	}
	// dirty map升级为read map
	m.read.Store(readOnly{m: m.dirty})
	// dirty map 清空
	m.dirty = nil
	// misses重置为0
	m.misses = 0
}

Значения элементов

func (e *entry) load() (value interface{}, ok bool) {
	p := atomic.LoadPointer(&e.p)
	// 元素不存在或者被删除，则直接返回
	if p == nil || p == expunged {
		return nil, false
	}
	return *(*interface{})(p), true
}

Карта чтения в основном используется для чтения.Каждая загрузка сначала считывает чтение.Когда чтение не существует, а измененное значение равно true, данные считываются из грязного. Вне зависимости от того, существует ли элемент в грязной карте, будет выполнена функция missLocked, которая пропустит+1, когдаm.misses < len(m.dirty), грязный будет скопирован для чтения, а затем грязный будет установлен в ноль, промахи = 0.

storage

Установите ключ => значение.

func (m *Map) Store(key, value interface{}) {
	// 如果read存在这个键，并且这个entry没有被标记删除，尝试直接写入,写入成功，则结束
	// 第一次检测
	read, _ := m.read.Load().(readOnly)
	if e, ok := read.m[key]; ok && e.tryStore(&value) {
		return
	}
	// dirty map锁
	m.mu.Lock()
	// 第二次检测
	read, _ = m.read.Load().(readOnly)
	if e, ok := read.m[key]; ok {
		// unexpungelocc确保元素没有被标记为删除
		// 判断元素被标识为删除
		if e.unexpungeLocked() {
			// 这个元素之前被删除了，这意味着有一个非nil的dirty，这个元素不在里面.
			m.dirty[key] = e
		}
		// 更新read map 元素值
		e.storeLocked(&value)
	} else if e, ok := m.dirty[key]; ok {
		// 此时read map没有该元素，但是dirty map有该元素，并需修改dirty map元素值为最新值
		e.storeLocked(&value)
	} else {
		// read.amended==false,说明dirty map为空，需要将read map 复制一份到dirty map
		if !read.amended {
			m.dirtyLocked()
			// 设置read.amended==true，说明dirty map有数据
			m.read.Store(readOnly{m: read.m, amended: true})
		}
		// 设置元素进入dirty map，此时dirty map拥有read map和最新设置的元素
		m.dirty[key] = newEntry(value)
	}
	// 解锁，有人认为锁的范围有点大，假设read map数据很大，那么执行m.dirtyLocked()会耗费花时间较多，完全可以在操作dirty map时才加锁，这样的想法是不对的，因为m.dirtyLocked()中有写入操作
	m.mu.Unlock()
}

Попробуйте сохранить элемент.

func (e *entry) tryStore(i *interface{}) bool {
	// 获取对应Key的元素，判断是否标识为删除
	p := atomic.LoadPointer(&e.p)
	if p == expunged {
		return false
	}
	for {
		// cas尝试写入新元素值
		if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
			return true
		}
		// 判断是否标识为删除
		p = atomic.LoadPointer(&e.p)
		if p == expunged {
			return false
		}
	}
}

UNEXPUNGELOCC гарантирует, что элементы не будут помечены как удаляемые. Если этот элемент удален, его необходимо добавить на Грязную карту перед разблокировкой.

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

Скопируйте из карты чтения на грязную карту.

func (m *Map) dirtyLocked() {
	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 {
		// 如果标记为nil或者expunged，则不复制到dirty map
		if !e.tryExpungeLocked() {
			m.dirty[k] = e
		}
	}
}

LoadOrStore

Если соответствующий элемент существует, вернуть значение элемента, если нет, записать элемент в sync.Map. Результат загрузки равен true, если значение было загружено, и false, если оно было сохранено.

func (m *Map) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool) {
	// 不加锁的情况下读取read map
	// 第一次检测
	read, _ := m.read.Load().(readOnly)
	if e, ok := read.m[key]; ok {
		// 如果元素存在（是否标识为删除由tryLoadOrStore执行处理），尝试获取该元素已存在的值或者将元素写入
		actual, loaded, ok := e.tryLoadOrStore(value)
		if ok {
			return actual, loaded
		}
	}

	m.mu.Lock()
	// 第二次检测
	// 以下逻辑参看Store
	read, _ = m.read.Load().(readOnly)
	if e, ok := read.m[key]; ok {
		if e.unexpungeLocked() {
			m.dirty[key] = e
		}
		actual, loaded, _ = e.tryLoadOrStore(value)
	} else if e, ok := m.dirty[key]; ok {
		actual, loaded, _ = e.tryLoadOrStore(value)
		m.missLocked()
	} else {
		if !read.amended {
			m.dirtyLocked()
			m.read.Store(readOnly{m: read.m, amended: true})
		}
		m.dirty[key] = newEntry(value)
		actual, loaded = value, false
	}
	m.mu.Unlock()

	return actual, loaded
}

Если ни один элемент не удален, tryLoadOrStore автоматически загрузит или сохранит значение. Если элемент удален, tryLoadOrStore оставляет запись без изменений и возвращает ok=false.

func (e *entry) tryLoadOrStore(i interface{}) (actual interface{}, loaded, ok bool) {
	p := atomic.LoadPointer(&e.p)
	// 元素标识删除，直接返回
	if p == expunged {
		return nil, false, false
	}
	// 存在该元素真实值，则直接返回原来的元素值
	if p != nil {
		return *(*interface{})(p), true, true
	}

	// 如果p为nil(此处的nil，并是不是指元素的值为nil，而是atomic.LoadPointer(&e.p)为nil，元素的nil在unsafe.Pointer是有值的)，则更新该元素值
	ic := i
	for {
		if atomic.CompareAndSwapPointer(&e.p, nil, unsafe.Pointer(&ic)) {
			return i, false, true
		}
		p = atomic.LoadPointer(&e.p)
		if p == expunged {
			return nil, false, false
		}
		if p != nil {
			return *(*interface{})(p), true, true
		}
	}
}

Delete

Чтобы удалить элемент, используйте отложенное удаление. Когда в карте чтения есть элемент, установите элемент равным nil. Количество удалений очищается только при поднятии грязного. Отложенное удаление позволяет избежать необходимости блокировки при последующем получении удаленные элементы. Когда в прочитанной карте нет элемента, удалите элемент в грязной карте напрямую

func (m *Map) Delete(key interface{}) {
	// 第一次检测
	read, _ := m.read.Load().(readOnly)
	e, ok := read.m[key]
	if !ok && read.amended {
		m.mu.Lock()
		// 第二次检测
		read, _ = m.read.Load().(readOnly)
		e, ok = read.m[key]
		if !ok && read.amended {
			// 不论dirty map是否存在该元素，都会执行删除
			delete(m.dirty, key)
		}
		m.mu.Unlock()
	}
	if ok {
		// 如果在read中，则将其标记为删除（nil）
		e.delete()
	}
}

Значение элемента установлено равным нулю

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

Range

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

func (m *Map) Range(f func(key, value interface{}) bool) {
	// 第一检测
	read, _ := m.read.Load().(readOnly)
	// read.amended=true,说明dirty map包含所有有效的元素（含新加，不含被删除的），使用dirty map
	if read.amended {
		// 第二检测
		m.mu.Lock()
		read, _ = m.read.Load().(readOnly)
		if read.amended {
			// 使用dirty map并且升级为read map
			read = readOnly{m: m.dirty}
			m.read.Store(read)
			m.dirty = nil
			m.misses = 0
		}
		m.mu.Unlock()
	}
	// 一贯原则，使用read map作为读
	for k, e := range read.m {
		v, ok := e.load()
		// 被删除的不计入
		if !ok {
			continue
		}
		// 函数返回false，终止
		if !f(k, v) {
			break
		}
	}
}

Суммировать

После приведенного выше анализа видно, что sync.Map не подходит для сценариев, в которых одновременно происходит большое количество операций чтения и записи.Большое количество операций записи приведет к тому, что карта чтения не сможет прочитать данные. данные и, таким образом, блокируются для дальнейшего чтения.В то же время грязная карта постоянно обновляется до карты чтения. В результате общая производительность низка, особенно для сценариев кэширования.Для операций только добавления и большого количества операций чтения относительно удобно использовать sync.Map для небольшого количества сценариев записи.

Sync.map не обеспечивает доступ к количеству метода элементов len (), но может быть () достигается диапазоном.

func Len(sm sync.Map) int {
	lengh := 0
	f := func(key, value interface{}) bool {
		lengh++
		return true
	}
	one:=lengh
	lengh=0
	sm.Range(f)
	if one != lengh {
	    one = lengh
		lengh=0
		sm.Range(f)
		if one <lengh {
			return lengh
		}
		
	}
	return one
}

Ссылаться на

Go sync.Map
Синхронизация Go 1.9. Демистификация карты