sync.Map
O sync.Map fornecido pela biblioteca padrão do Go é um map seguro para concorrência. Não é necessário usar mecanismos como locks ao utilizá-lo. Sua implementação não é muito complexa, com apenas duzentas ou trezentas linhas de código sem comentários.
Estrutura
type Map struct {
mu Mutex
read atomic.Pointer[readOnly]
dirty map[any]*entry
misses int
}Ele tem apenas quatro campos, conforme abaixo:
read, map somente leitura, pode ser entendido como cache dodirtydirty, um map comummisses, número de vezes que o acesso aoreadnão encontrou a chavemu, protege a segurança de concorrência dodirty
read é do tipo sync.readOnly, que internamente também é um map. O campo amended indica se o dirty contém alguma chave que o read não possui.
type readOnly struct {
m map[any]*entry
amended bool // true if the dirty map contains some key not in m.
}Além disso, a estrutura do tipo entry é a seguinte, onde p é um ponteiro para o valor.
type entry struct {
p atomic.Pointer[any]
}Para um entry, há três situações possíveis:
- Situação normal, armazena o valor correspondente
pénil, indica que o par chave-valor foi excluído. Neste momento, o dirty pode estar vazio, ou ainda pode estar presente no dirty.p == expunged, ondeexpungedé um objeto de interface vazio, também representa que o par chave-valor já foi excluído e não existe mais no dirty.
A segurança de concorrência do map da biblioteca padrão é implementada através de separação de leitura e escrita. Os ponteiros entry armazenados em read e dirty apontam para a mesma área de memória de valores. read é somente leitura, então não há problemas de segurança ao acessar por múltiplas goroutines. dirty pode ser modificado e é protegido por mutex. misses registra o número de vezes que o acesso à chave não foi encontrado. Quando este número acumula até um certo valor, o dirty atual se transforma em read, e misses é zerado. Esta é a lógica de funcionamento geral do sync.Map. A seguir, analisaremos suas operações de forma mais detalhada.
Leitura
A operação de leitura corresponde ao método Map.Load, conforme o código abaixo:
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()
}Primeiro acessa o read. Se existir, retorna diretamente. Caso contrário, tenta adquirir o mutex mu. Depois acessa novamente o read, porque durante o período de obtenção do lock, o dirty pode ter sido promovido a read. Se ainda não encontrar, finalmente acessa o dirty e registra um miss, depois desbloqueia.
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
}Pelo método missLocked, podemos ver que o valor limite para o dirty ser promovido a read é m.misses >= len(m.dirty).
Escrita
A operação de escrita corresponde ao método Store, mas na verdade é completada pelo método Swap. previous representa o valor anterior, loaded indica se a chave existe.
func (m *Map) Swap(key, value any) (previous any, loaded bool)O fluxo da operação de escrita é dividido em duas partes. Se a chave acessada existir no read, obtém diretamente o entry correspondente e atualiza o valor do entry através de CAS. Não é necessário bloquear durante o processo.
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
}
}Durante a rotação em loop, se p == expunged, indica que a chave já foi excluída, então retorna diretamente.
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
}
}
}Se a chave não existir no read, tenta adquirir o lock para realizar as próximas operações. Em seguida, há três situações. Primeira situação: durante a obtenção do lock, o dirty foi promovido a read. Se o entry acessado for expunged, indica que já foi excluído e não existe no dirty. Neste caso, é necessário adicioná-lo ao dirty e depois armazenar o valor correspondente.
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
}
}Segunda situação: não está no read, mas está no dirty. Também armazena diretamente o valor correspondente.
if e, ok := m.dirty[key]; ok {
if v := e.swapLocked(&value); v != nil {
loaded = true
previous = *v
}
}Terceira situação: não está no read e também não está no dirty. Aqui, se read.amended for false, indica que o dirty está vazio. Então usa m.dirtyLocked para copiar todos os pares chave-valor não excluídos do read para o dirty. Depois marca read.amended como true. Finalmente, cria diretamente um novo entry para armazenar o valor correspondente.
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
}
}
}Exclusão
A operação de exclusão corresponde ao método LoadAndDelete. Sua lógica é quase completamente consistente com a operação de leitura, apenas adiciona uma chamada à função 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
}Ao excluir um par chave-valor, sempre executa a operação delete apenas no dirty. Para o read, apenas modifica o valor do entry armazenado para 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
}
}
}Iteração
A operação de iteração corresponde ao método 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
}
}
}Durante a iteração, apenas itera sobre o read. Se read.amended for true, indica que há chaves faltando no read. Neste caso, promove diretamente o dirty para read. Depois usa o loop for range para iterar e chama a função de callback para cada par chave-valor.
Desempenho
O sync.Map adota a maneira de separação de leitura e escrita para controle de concorrência. É mais adequado para cenários com muitas leituras e poucas escritas, porque na maioria das situações não é necessário adicionar lock ao acessar um par chave-valor. Mas se for adicionar um novo elemento, é necessário adquirir um lock global, que bloqueia todas as operações do map atual. Isso leva ao baixo desempenho de escrita. Portanto, sync.Map não se aplica a todas as situações. Para situações com poucas leituras e muitas escritas, pode-se implementar usando a maneira de lock segmentado. Aqui recomendamos uma implementação open source orcaman/concurrent-map: a thread-safe concurrent map for go (github.com), implementada usando sharding e com suporte a genéricos. O desempenho e a experiência de uso serão melhores.