Go: Criando um cache em memória com map, mutex e generics
Tags: go, tutorial, programming, beginners
Published: 2023-12-03 19:17:53

## 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:

```go
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)
```

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.

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

time.Sleep(time.Second)
fmt.Println(count)
```

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:

```sh
$ 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
```

### 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
```
ou
```
fatal error: concurrent map read and map write
```

### 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:
```sh
go test -race ./...
go run -race arquivo.go
go build -race .
```

Se usarmos o race detector no programa que deveria contar até 1000, ele vai detectar o race e mostrar a seguinte mensagem:
```sh
$ 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
...
```

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](https://go.dev/doc/articles/race_detector)

## 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_.

```go
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)
}
```

Agora vamos adicionar a mutex a `struct` e ao construtor:
```go
type Cache struct {
	data    map[string]string
	dataMut *sync.Mutex
}

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

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.

```go
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()
}
```

E para utilizar o cache:
```go
cache := NewCache()
cache.Get("key") // "", false
cache.Set("key", "somevalue")
cache.Get("key") // "somevalue", true
cache.Delete("key")
cache.Get("key") // "", false
```

Sugestões de leitura:

> [Mutual exclusion - Wikipedia](https://en.wikipedia.org/wiki/Mutual_exclusion)
> [Documentação da `sync.Mutex` - Go Packages](https://pkg.go.dev/sync#Mutex)

## 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`

```go
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()
}
```

Sugestões de leitura:
> [Readers-writers lock](https://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock)
> [Documentação da `sync.RWMutex`](https://pkg.go.dev/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:
```go
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
}
```

Agora um exemplo de função genérica:
```go
func max[T int | float64](a, b T) T {
	if a > b {
		return b
	}
	return a
}
```

Agora um exemplo de "método" genérico:
```go
type List[T any] struct {
	slice []T
}

func (l *List[T]) Append(v T) {
	l.slice = append(l.slice, v)
}
```

### Aplicando generics no tipo Cache

```go
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()
}
```

E agora para usarmos nosso cache genérico:
```go
func main() {
	cache := NewCache[string, bool]()
	cache.Set("valid", true)
	valid, _ := cache.Get("valid")
	log.Println(valid) // true
}
```

## 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:
```sh
# 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
```

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`](https://pkg.go.dev/sync#Map)