sync.Map

02.05.2020 sync.map map конкуррентность


sync.Map

Рассмотрим особенности типа sync.Map.

Давным давно, в 2016 году, когда мир еще не знал о существовании короновируса, в GO 1.9 появился тип данных sync.Map.

Интерфейс

При работе с sync.Map нам доступны следующие методы:

  • Load(key interface{}) (value interface{}, ok bool)
  • Store(key, value interface{})
  • Delete(key interface{})
  • Range(f func(key, value interface{}) bool)
  • LoadOrStore(key, value interface{}) (actual interface{}, loaded bool)

Методы покрывают все случаи использования мапы — вставка, чтение, удаление, итерирование. Также существует бонусный метод LoadOrStore, позволяющий установить значение по ключу в случае если оно еще не установлено.

Для итерирования есть функция Range, принимающая анонимную функцию, вызываемую для каждого элемента мапы. Если функция возвращает false, итерирование прекращается.

Название пакета sync наводит на мысли о том, что sync.Map — это стандартный map с мьютексом sync.RWMutex. Однако внутреннее устройство sync.Map намного сложнее. Давайте посмотрим в исходники и разберемся, как он работает.

Исходники

Структура sync.Map выглядит так:

type Map struct {
	mu sync.Mutex

	read atomic.Value // указатель на структуру readOnly
	dirty map[interface{}]*entry
	misses int
}

type readOnly struct {
	m       map[interface{}]*entry
	amended bool 
}

read — указатель на структуру readOnly, в данной структуре хранится часть данных sync.Map, используемая для проверки наличия ключа, либо же чтения. Поэтому при доступе к read мьютексы не нужны (параллельное чтение мапы не является проблемой).

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

Таким образом, sync.Map имеет две внутренние мапы (read и dirty) и благодаря этому пытается избежать использования мьютексов при чтении. Далее рассмотрим, как изнутри происходят различные операции с sync.Map.

Чтение

В первую очередь пытаемся найти данные в read. Если нашли — возвращаем. Это самый эффективный сценарий — возврат данных из read.

Во вторую очередь смотрим в dirty — под мьютексом mu. Увеличиваем misses — счетчик чтений dirty. Важный момент — если данный счетчик превышает текущее кол-во элементов dirty, то элементы из dirty будут скопированы в read, а счетчик обнулен. Копирование произойдет синхронно сразу после чтения из dirty — в этот момент мьютекс mu активирован.

Для того, чтобы впустую не смотеть в dirty, в структуре readOnly есть поле amended, которое собственно и говорит нам о существовании непустого dirty.

Таким образом чтение из sync.Map наиболее оптимально из данных в read. В этом случае скорость доступа равна чтению из обычной map без использования mutex. Если ваш кейс заключается в длительном конкурентном сохранении данных в мапу, а затем только в чтении из нее, то на этапе чтения sync.Map определенно эффективен.

Запись

При записи сначала пытаемся считать ключ из read. Если ключ есть в read, то обновляем с помощью atomic.CompareAndSwap. Данный метод позволяет атомарно изменить значение.

Если ключа в read не было, делаем аналогичные действия с dirty. Если dirty был не инициализирован, то инициализируем.

Таким образом, обновление уже существующего ключа является простым случаем. Сложнейшим случаем является добавление нового ключа, ранее не существовавшего.

Итерирование

При итерировании интересным является то, что перед ним все элементы из dirty копируются в read, если dirty содержит какие-либо элементы. Делается это под локом mu.

Далее происходит итерирование по read — обычное итерирование по map.

Итог

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

Другие статьи