DEV Community

Igor Melo
Igor Melo

Posted on

Go: Criando um cache em memória com map, mutex e generics

1. Introdução

Nesse artigo vamos desenvolver um cache chave-valor na memória do processo para aprender sobre data races, Mutex, RWMutex e generics no Go.
No final vamos fazer comparações de performance para vermos qual é a solução mais eficiente.

2. Por que não usar simplesmente um map?

Podemos usar um map de cache da seguinte forma:

var cache = map[string]string{}

...

// tentando pegar o valor do  cache
val, ok := cache["api_lenta/info"]

// valor nao esta no cache, tenho que pegar da API
if !ok {
    val = consultarAPILenta()

    // guardando o valor no cache para o proximo uso
    cache["api_lenta/info"] = val
}

// usando o valor, vindo do cache ou da api
usarValor(val)
Enter fullscreen mode Exit fullscreen mode

A princípio não tem problema nessa abordagem, porque o cache está sendo usado por uma só goroutine.
O problema começa quando adicionamos múltiplas goroutines...
Vamos falar de data races.

3. O que são data races?

Um data race ocorre quando duas ou mais goroutines tentam concorrentemente ler e/ou alterar um dado.

count := 0
for i := 0; i < 1000; i++ {
    go func() {
        count = count + 1
    }()
}

time.Sleep(time.Second)
fmt.Println(count)
Enter fullscreen mode Exit fullscreen mode

No exemplo acima eu crio mil goroutines para incrementar o valor de count.
Só que eventualmente algumas goroutines vão rodar em paralelo e vão ler e alterar o valor de count ao mesmo tempo.

E mesmo que não rodem em paralelo, o scheduler pode interromper a goroutine no meio da execução dela, antes dela atualizar o valor na memória, e resumir tempo depois, fazendo com que o count que ela calculou esteja desatualizado.

Quando isso acontece, não há como determinar qual vai ser o resultado da operação. Tanto que se eu rodar esse programa múltiplas vezes, vou ter resultados diferentes:

$ go run main.go 
904
$ go run main.go
903
$ go run main.go
958
$ go run main.go
926
$ go run main.go
975
Enter fullscreen mode Exit fullscreen mode

Regra geral sobre data races

Basicamente podemos pensar da seguinte forma:

Acontece data race quando

  • Duas ou mais goroutines estão alterando um mesmo valor
  • Uma ou mais goroutines estão lendo um valor, enquanto uma goroutine está alterando

Não acontece data race quando

  • Só há uma goroutine lidando com um dado (lendo ou escrevendo)
  • Há múltiplas goroutines lendo um dado (e nenhuma escrevendo)

Em tipos mais complexos, como é o caso do map, um data race bagunçaria totalmente a estrutura interna dele, então quando ele detecta um data race ele dá um panic com uma das seguintes mensagens:

fatal error: concurrent map writes
Enter fullscreen mode Exit fullscreen mode

ou

fatal error: concurrent map read and map write
Enter fullscreen mode Exit fullscreen mode

Race detector

Felizmente o Go vem com uma ferramenta chamada data race detector que, como o nome sugere, detecta data races de forma geral e nos diz exatamente as linhas que estão causando o race.

Para usar o race detector, basta utilizar -race nos principais comandos do Go:

go test -race ./...
go run -race arquivo.go
go build -race .
Enter fullscreen mode Exit fullscreen mode

Se usarmos o race detector no programa que deveria contar até 1000, ele vai detectar o race e mostrar a seguinte mensagem:

$ go run -race main.go 
==================
WARNING: DATA RACE
Read at 0x00c000026178 by goroutine 11:
  main.main.func1()
      /projeto/main.go:7 +0x30

Previous write at 0x00c000026178 by goroutine 7:
  main.main.func1()
      /projeto/main.go:7 +0x44
...
Enter fullscreen mode Exit fullscreen mode

Apesar de parecer intimidadora essa saída, a informação relevante é que tivemos um read na linha 7 por uma goroutine e um write na mesma linha 7 por outra goroutine, então nos diz exatamente onde ocorreu o race.

Sugestões de leitura:

Data Race Detector - The Go Programming Language

4. Cache com sync.Mutex

Como vimos anteriormente, precisamos de alguma forma de evitar data race no map do nosso cache. Para esse tipo de problema existe o conceito de mutex.

Mutex é um mecanismo para garantirmos que somente uma goroutine tem acesso exclusivo a algo do momento que ela adquire o lock até o momento que ela libera o lock.

Uma analogia para ficar mais claro:
Pensa em um banheiro. Se não tem nenhuma forma de sincronização, pode acontecer de duas ou mais pessoas usarem o banheiro ao mesmo tempo, o que daria resultados bem desagradáveis.

A mutex é como se fosse a chave para o banheiro, e quem adquire essa chave se tranca no banheiro e tem acesso exclusivo a ele, enquanto as outras pessoas esperam do lado de fora até que a pessoa termine de usar o banheiro.

A mutex dá problema quando, ainda na analogia, uma pessoa se tranca no banheiro e não quer mais sair, que é o cenário de deadlock.

Criando um tipo para o Cache e utilizando uma mutex

Para começar vamos criar uma struct para o Cache com o método Get, Set e Delete, que por enquanto só executa as operações normais do map, sem ser concurrent-safe.

type Cache struct {
    data map[string]string
}

func NewCache() Cache {
    return Cache{
        data: map[string]string{},
    }
}

func (c Cache) Set(key string, val string) {
    c.data[key] = val
}

func (c Cache) Get(key string) (val string, ok bool) {
    val, ok = c.data[key]
    return
}

func (c Cache) Delete(key string) {
    delete(c.data, key)
}
Enter fullscreen mode Exit fullscreen mode

Agora vamos adicionar a mutex a struct e ao construtor:

type Cache struct {
    data    map[string]string
    dataMut *sync.Mutex
}

func NewCache() Cache {
    return Cache{
        data:    map[string]string{},
        dataMut: &sync.Mutex{},
    }
}
Enter fullscreen mode Exit fullscreen mode

Agora antes de lermos ou escrevermos no map, precisamos fazer um Lock para garantirmos que só uma goroutine está lendo/escrevendo, e quando terminarmos, precisamos fazer um Unlock para permitir que outra goroutine possa fazer o mesmo.

func (c Cache) Set(key string, val string) {
    c.dataMut.Lock()
    c.data[key] = val
    c.dataMut.Unlock()
}

func (c Cache) Get(key string) (val string, ok bool) {
    c.dataMut.Lock()
    val, ok = c.data[key]
    c.dataMut.Unlock()
    return
}

func (c Cache) Delete(key string) {
    c.dataMut.Lock()
    delete(c.data, key)
    c.dataMut.Unlock()
}
Enter fullscreen mode Exit fullscreen mode

E para utilizar o cache:

cache := NewCache()
cache.Get("key") // "", false
cache.Set("key", "somevalue")
cache.Get("key") // "somevalue", true
cache.Delete("key")
cache.Get("key") // "", false
Enter fullscreen mode Exit fullscreen mode

Sugestões de leitura:

Mutual exclusion - Wikipedia
Documentação da sync.Mutex - Go Packages

5. Introduzindo a sync.RWMutex

Como falamos antes, podemos ter múltiplas goroutines lendo o mesmo dado sem problemas, desde que não tenha nenhuma escrevendo ao mesmo tempo, porém com a sync.Mutex só permitimos uma goroutine ler por vez.

Para permitirmos leituras concorrentes, existe a sync.RWMutex, onde o "RW" é uma sigla para "read-write".
A RWMutex nos permite fazer dois tipos de lock e unlock:

  • write lock com Lock, write unlock com Unlock
  • read lock com RLock. read unlock com RUnlock

Quando precisamos alterar um dado, temos que fazer fazer um Lock e no fim Unlock.
Quando só queremos ler um dado sem fazer modificações, podemos fazer um RLock e no fim um RUnlock.

Atualizando métodos para usar sync.RWMutex

type Cache struct {
    data    map[string]string
    dataMut *sync.RWMutex
}

func NewCache() Cache {
    return Cache{
        data:    map[string]string{},
        dataMut: &sync.RWMutex{},
    }
}

func (c Cache) Set(key string, val string) {
    // write lock
    c.dataMut.Lock()
    c.data[key] = val
    c.dataMut.Unlock()
}

func (c Cache) Get(key string) (val string, ok bool) {
    // read lock
    c.dataMut.RLock()
    val, ok = c.data[key]
    c.dataMut.RUnlock()
    return
}

func (c Cache) Delete(key string) {
    // write lock
    c.dataMut.Lock()
    delete(c.data, key)
    c.dataMut.Unlock()
}
Enter fullscreen mode Exit fullscreen mode

Sugestões de leitura:

Readers-writers lock
Documentação da sync.RWMutex

6. Utilizando generics

Até o momento, nosso cache só aceita chaves e valores do tipo string, mas agora vamos deixar nosso cache mais flexível, aceitando qualquer tipo de chave e valor.

Introduzindo a sintaxe de generics

Alguns exemplos de structs genéricas:

type List[T any] struct {
    slice []T
}

// a chave do map precisa ser um tipo comparável
type Map[K comparable, V any] struct {
    m map[K]V
}
Enter fullscreen mode Exit fullscreen mode

Agora um exemplo de função genérica:

func max[T int | float64](a, b T) T {
    if a > b {
        return b
    }
    return a
}
Enter fullscreen mode Exit fullscreen mode

Agora um exemplo de "método" genérico:

type List[T any] struct {
    slice []T
}

func (l *List[T]) Append(v T) {
    l.slice = append(l.slice, v)
}
Enter fullscreen mode Exit fullscreen mode

Aplicando generics no tipo Cache

type Cache[K comparable, V any] struct {
    data    map[K]V
    dataMut *sync.RWMutex
}

func NewCache[K comparable, V any]() Cache[K, V] {
    return Cache[K, V]{
        data:    map[K]V{},
        dataMut: &sync.RWMutex{},
    }
}

func (c Cache[K, V]) Set(key K, val V) {
    c.dataMut.Lock()
    c.data[key] = val
    c.dataMut.Unlock()
}

func (c Cache[K, V]) Get(key K) (val V, ok bool) {
    c.dataMut.RLock()
    val, ok = c.data[key]
    c.dataMut.RUnlock()
    return
}

func (c Cache[K, V]) Delete(key K) {
    c.dataMut.Lock()
    delete(c.data, key)
    c.dataMut.Unlock()
}
Enter fullscreen mode Exit fullscreen mode

E agora para usarmos nosso cache genérico:

func main() {
    cache := NewCache[string, bool]()
    cache.Set("valid", true)
    valid, _ := cache.Get("valid")
    log.Println(valid) // true
}
Enter fullscreen mode Exit fullscreen mode

7. Comparações de performance

Comparei o cache utilizando sync.Mutex, sync.RWMutex, e um outro tipo que não falei aqui ainda: o sync.Map.
E para a minha surpresa, a sync.Mutex performou quase igual a sync.RWMutex, e até melhor em algumas operações.

O sync.Map é um tipo que funciona similar a um map, mas é concurrent-safe.
Pela documentação, o sync.Map é otimizado para leituras concorrentes e leituras e escritas em valores distintos.

O Resultado do benchmark foi:

# 1000 gets e sets na mesma chave
sync.Mutex      86908 ns/op
sync.RWMutex   111462 ns/op
sync.Map       239797 ns/op

# 1000 gets e sets em chaves diferentes
sync.Mutex      90000 ns/op
sync.RWMutex   115520 ns/op
sync.Map       299608 ns/op

# 1000 gets e sets concorrentes em chaves diferentes
sync.Mutex     2238245 ns/op
sync.RWMutex   2856618 ns/op
sync.Map       1884196 ns/op

# 1000 get concorrentes em chaves diferentes
sync.Mutex    1074670 ns/op
sync.RWMutex   935320 ns/op
sync.Map       876155 ns/op
Enter fullscreen mode Exit fullscreen mode

Quanto maior o tempo, pior.

Então podemos concluir que nesses benchmarks:

  • A sync.Mutex foi mais rápida em gets e sets sequenciais na mesma chave
  • A sync.Mutex foi mais rápida em gets e sets sequenciais em chaves diferentes
  • O sync.Map foi mais rápido em gets e sets concorrentes em chaves distintas
  • o sync.Map foi mais rápido em gets concorrentes (sem sets) em chaves distintas

Sugestões de leitura:

Documentação do sync.Map

Top comments (0)