Разбираемся с новым sync.Map в Go 1.926.09.2017 08:18

Одним из нововведений в Go 1.9 было добавление в стандартную библиотеку нового типа sync.Map, и если вы ещё не разобрались что это и для чего он нужен, то эта статья для вас.


Для тех, кому интересен только вывод, TL; DR:


если у вас высоконагруженная (и 100нс решают) система с большим количеством ядер процессора (32+), вы можете захотеть использовать sync.Map вместо стандартного map+sync.RWMutex. В остальных случаях, sync.Map особо не нужен.

fc81799050554f20a7b28314b68afe47.png


Если же интересны подробности, то давайте начнем с основ.


Тип map

Если вы работаете с данными в формате «ключ»-«значение», то всё что вам нужно это встроенный тип map (карта). Хорошее введение, как пользоваться map есть в Effective Go и блог-посте «Go Maps in Action».


map — это generic структура данных, в которой ключом может быть любой тип, кроме слайсов и функций, а значением — вообще любой тип. По сути это хорошо оптимизированная хеш-таблица. Если вам интересно внутреннее устройство map — на прошлом GopherCon был очень хороший доклад на эту тему.


Вспомним как пользоваться map: 


// инициализация
m := make(map[string]int)
// запись
m["habr"] = 42
// чтение
val := m["habr"]
// чтение с comma,ok
val, ok := m["habr"] // ok равен true, если ключ найден
// итерация
for k, v := range m { ... }
// удаление
delete(m, "habr")


Во время итерации значения в map могут изменяться.


Go, как известно, является языком созданным для написания concurrent программ — программ, который эффективно работают на мультипроцессорных системах. Но тип map не безопасен для параллельного доступа. Тоесть для чтения, конечно, безопасен — 1000 горутин могут читать из map без опасений, но вот параллельно в неё ещё и писать — уже нет. До Go 1.8 конкурентный доступ (чтение и запись из разных горутин) могли привести к неопределенности, а после Go 1.8 эта ситуация стала явно выбрасывать панику с сообщением «concurrent map writes».


Почему map не потокобезопасен

Решение делать или нет map потокобезопасным было непростым, но было принято не делать — эта безопасность не даётся бесплатно. Там где она не нужна, дополнительные средства синхронизации вроде мьютексов будут излишне замедлять программу, а там где она нужна — не составляет труда реализовать эту безопасность с помощью sync.Mutex.


В текущей реализации map очень быстр:
4c35b8a25c95465db94ab6a51409efa0.png


Такой компромисс между скоростью и потокобезопасностью, при этом оставляя возможность иметь и первый и второй вариант. Либо у вас сверхбыстрый map безо всяких мьютексов, либо чуть медленнее, но безопасен для параллельного доступа. Важно тут понимать, что в Go использование переменной параллельно несколькими горутинами — это не далеко единственный способ писать concurrent-программы, поэтому кейс этот не такой частый, как может показаться вначале.


Давайте, посмотрим, как это делается.


Map + sync.Mutex

Реализация потокобезопасной map очень проста — создаём новую структуру данных и встраиваем в неё мьютекс. Структуру можно назвать как угодно — хоть MyMap, но есть смысл дать ей осмысленное имя — скорее всего вы решаете какую-то конкретную задачу.


type Counters struct {
    sync.Mutex
    m map[string]int
}


Мьютекс никак инициализировать не нужно, его «нулевое значение» это разлоченный мьютекс, готовый к использованию, а карту таки нужно, поэтому будет удобно (но не обязательно) создать функцию-конструктор: 


func NewCounters() *Counters {
    return &Counters{
        m: make(map[string]int),
    }
}


Теперь у переменной типа Counters будет метод Lock() и Unlock(), но если мы хотим упростить себе жизнь и использовать этот тип из других пакетов, то будет также удобно сделать функции обёртки вроде Load() и Store(). В таком случае мьютекс можно не встраивать, а просто сделать «приватным» полем: 


type Counters struct {
    mx sync.Mutex
    m map[string]int
}

func (c *Counters) Load(key string) (int, bool) {
    c.mx.Lock()
    defer c.mx.Unlock()
    val, ok := c.m[key]
    return val, ok
}

func (c *Counters) Store(key string, value int) {
    c.mx.Lock()
    defer c.mx.Unlock()
    c.m[key] = value
}


Тут нужно обратить внимание на два момента:


  • defer имеет небольшой оверхед (порядка 50–100 наносекунд), поэтому если у вас код для высоконагруженной системы и 100 наносекунд имеют значение, то вам может быть выгодней не использовать defer
  • методы Get() и Store() должны быть определены для указателя на Counters, а не на Counters (тоесть не func (c Counters) Load(key string) int { ... }, потому что в таком случае значение ресивера (c) копируется, вместе с чем скопируется и мьютекс в нашей структуре, что лишает всю затею смысла и приводит к проблемам.


Вы также можете, если нужно, определить методы Delete() и Range(), чтобы защищать мьютексом map во время удаления и итерации по ней.


Кстати, обратите внимание, я намеренно пишу «если нужно», потому что вы всегда решаете конкретную задачу и в каждом конкретном случае у вас могут разные профили использования. Если вам не нужен Range() — не тратьте время на его реализацию. Когда нужно будет — всегда сможете добавить. Keep it simple.


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


counters := NewCounters()
counters.Store("habr", 42)
v, ok := counters.Load("habr")


В зависимости, опять же, от конкретной задачи, можно делать любые удобные вам методы. Например, для счётчиков удобно делать увеличение значения. С обычной map мы бы делали что-то вроде: 


counters["habr"]++


а для нашей структуры можем сделать отдельный метод: 


func (c *Counters) Inc(key string) {
    c.mx.Lock()
    defer c.mx.Unlock()
    c.m[key]++
}
...
counters.Inc("habr")


Но часто у работы с данными в формате «ключ»-«значение», паттерн доступа неравномерный — либо частая запись, и редкое чтение, либо наоборот. Типичный случай — обновление происходит редко, а итерация (range) по всем значениям — часто. Чтение, как мы помним, из map — безопасно, но сейчас мы будем лочиться на каждой операции чтения, теряя без особой выгоды время на ожидание разблокировки.


sync.RWMutex

В стандартной библиотеке для решения этой ситуации есть тип sync.RWMutex. Помимо Lock()/Unlock(), у RWMutex есть отдельные аналогичные методы только для чтения — RLock()/RUnlock(). Если метод нуждается только в чтении — он использует RLock(), который не заблокирует другие операции чтения, но заблокирует операцию записи и наоборот. Давай обновим наш код: 


type Counters struct {
    mx sync.RWMutex
    m  map[string]int
}
...
func (c *Counters) Load(key string) (int, bool) {
    c.mx.RLock()
    defer c.mx.RUnlock()
    val, ok := c.m[key]
    return val, ok
}


Решения map+sync.RWMutex являются почти стандартом для map, которые должны использоваться из разных горутин. Они очень быстрые.


До тех пор, пока у вас не появляется 64 ядра и большое количество одновременных чтений.


Cache contention

Если посмотреть на код sync.RWMutex, то можно увидеть, что при блокировке на чтение, каждая горутина должна обновить поле readerCount — простой счётчик. Это делается атомарно с помощью функции из пакета sync/atomic atomic.AddInt32(). Эти функции оптимизированы под архитектуру конкретного процессора и реализованы на ассемблере.


Когда каждое ядро процессора обновляет счётчик, оно сбрасывает кеш для этого адреса в памяти для всех остальных ядер и объявляет, что владеет актуальным значением для этого адреса. Следующее ядро, прежде чем обновить счётчик, должно сначала вычитать это значение из кеша другого ядра.


На современном железе передача между L2 кешем занимает что-то около 40 наносекунд. Это немного, но когда много ядер одновременно пытаются обновить счётчик, каждое из них становится в очередь и ждёт эту инвалидацию и вычитывание из кеша. Операция, которая должна укладываться в константное время внезапно становится O (N) по количеству ядер. Эта проблема называется cache contention.


В прошлом году в issue-трекере Go была создана issue #17973 на эту проблему RWMutex. Бенчмарк ниже показывает почти 8-кратное увеличение времени на RLock ()/RUnlock () на 64-ядерной машине по мере увеличения количества горутин активно «читающих» (использующих RLock/RUnlock):


1f0f9d89aacb4bfa8866219621f5a996.png


А это бенчмарк на одном и том же количестве горутин (256) по мере увеличения количества ядер:


f677d2e57a1f4949b1f543e0263ca156.png


Как видим, очевидная линейная зависимость от количества задействованных ядер процессора.


В стандартной библиотеке map-ы используются довольно много где, в том числе в таких пакетах как encoding/json, reflect или expvars и описанная проблема может приводить к не очень очевидным замедлениям в более высокоуровневом коде, который и не использует напрямую map+RWMutex, а, например, использует reflect.


Собственно, для решения этой проблемы — cache contention в стандартной библиотеке и был добавлен sync.Map.


sync.Map

Итак, ещё раз сделаю акцент — sync.Map решает совершенно конкретную проблему cache contention в стандартной библиотеке для таких случаев, когда ключи в map стабильны (не обновляются часто) и происходит намного больше чтений, чем записей.


Если вы совершенно чётко не идентифицировали в своей программе узкое место из-за cache contention в map+RWMutex, то, вероятнее всего, никакой выгоды от sync.Map вы не получите, и возможно даже слегка потеряете в скорости.


Ну, а если все таки это ваш случай, то давайте посмотрим, как использовать API sync.Map. И использовать его на удивление просто — практически 1-в-1 наш код раньше: 


    // counters := NewCounters() <-- 
    var counters sync.Map


Запись: 


    counters.Store("habr", 42)


Чтение: 


    v, ok := counters.Load("habr")


Удаление: 


    counters.Delete("habr")


При чтении из sync.Map вам, вероятно также потребуется приведение к нужному типу: 


v, ok := counters.Load("habr")
if ok {
   val = v.(int)
}


Кроме того, есть ещё метод LoadAndStore (), который возвращает существующее значение, и если его нет, то сохраняет новое, и Range (), которое принимает аргументом функцию для каждого шага итерации: 


    v2, ok := counters.LoadOrStore("habr2", 13)


    counters.Range(func(k, v interface{}) bool {
        fmt.Println("key:", k, ", val:", v)
        return true // if false, Range stops
    })


API обусловлен исключительно паттернами использования в стандартной библиотеке. Сейчас sync.Map используется в пакетах encoding/{gob/xml/json}, mime, archive/zip, reflect, expvars, net/rpc.


По производительности sync.Map гарантирует константное время доступа к map вне зависимости от количества одновременных чтений и количества ядер. До 4 ядер, sync.Map при большом количестве параллельных чтений, может быть существенно медленнее, но после начинает выигрывать у map+RWMutex:


fc81799050554f20a7b28314b68afe47.png


Заключение

Резюмируя — sync.Map это не универсальная реализация неблокирующей map-структуры на все случаи жизни. Это реализация для конкретного паттерна использования для, преимущественно, стандартной библиотеки. Если ваш паттерн с этим совпадает и вы совершенно чётко знаете, что узкое место в вашей программе это cache contention на map+sync.RWMutex — смело используйте sync.Map. В противном случае, sync.Map вам вряд ли поможет.


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


Так же для вашего случая могут больше подходить други реализации hash-таблиц, например на lock-free алгоритмах. Подобные пакеты были давно, и единственная причина, почему sync.Map находится в стандартной библиотеке — этого его активное использование другими пакетами из стандратной библиотеки.


Ссылки

  • https://golang.org/pkg/sync/#Map
  • https://github.com/golang/go/issues/17973
  • https://www.youtube.com/watch? v=C1EtfDnsdDs
  • https://www.youtube.com/watch? v=Tl7mi9QmLns
  • https://medium.com/@deckarep/the-new-kid-in-town-gos-sync-map-de24a6bf7c2c

© Habrahabr.ru