Implementando árvores em Elixir
Tags: elixir, ingresse, ptbr, datastructures
Published: 2020-04-16 14:48:33

# Problema
Com o aumento na demanda de requisições feitas para a API da [Ingresse] (https://ingresse.com) alguns processos se tornaram um tipo de *gargalo*. O exemplo que usarei durante este artigo será o nosso processo de definir se a sessão (data/hora) de um evento está disponível para venda ou não.

Cada requisição feita pelo usuário a nossa API faz uma grande quantidade de buscas no nosso banco de dados e no Redis. São operações simples e que não deveriam ser muito custosas, porém são muitos dados que temos que buscar, e isso em grande escala de requests se torna bastante custoso.

---

# Prova de conceito
Desde o início dos estudos para completar esta tarefa de refatoração nós optamos por dividi-la em duas partes, sendo elas:

---

**Construir a árvore completa de um evento**

A ideia nesta etapa é fazer todo o processo de buscas necessárias nos bancos de dados, percorrer esses dados e construir a árvore que será consumida por outros processos.

Aqui foram criados os dois principais *módulos* (ou classes para quem estiver mais habituado com linguagens OOP) que são os que representam os nós e a árvore em si. Esses dois módulos são uma implementação simples de uma árvore e com eles nós conseguimos criá-la a partir de uma estrutura de **evento** que é a entidade carregada do banco de dados com suas respectivas associações como sessões, grupo de ingressos e ingressos.

###### node.ex
{% gist https://gist.github.com/viniciuslcpereira97/d62eb04760650efd5131cfb1b86d65f0 %}

###### tree.ex
{% gist https://gist.github.com/viniciuslcpereira97/aae1c0bff9ea566a039480d1550d4f7b %}

---

**Calcular os status de sessões a partir de uma árvore já construída**

Esta etapa é a responsável por consumir uma árvore já criada e percorrer sobre os nós dela para calcular o status de cada um. Neste ponto nós usaremos a árvore criada pela etapa anterior a esta, assim, conseguiremos percorrer por todos os nós dentro da árvore utilizando o algoritmo [Postorder Traversal](https://www.programiz.com/dsa/tree-traversal).

Para fazer os cálculos dos status nós decidimos utilizar pesos neles, o que significa que, cada status terá um peso de acordo com o tipo de status que ele é, com o intuito de podermos definir qual status é mais relevante comparado com outros.

É importante deixar claro que nós temos dois grupos de status que são: Disponível e Indisponível.
Dentro do grupo Indisponível nós temos outros tipos de status, que podem ser: sem estoque, vendas não iniciadas, encerrado, etc, e esses sim tem o peso mencionado acima.

Nesta estapa também decidimos usar uma tabela [ETS] (https://elixirschool.com/en/lessons/specifics/ets/) para guardar o status de cada nó e dar como resposta para nosso cliente.


---


###### Recursive Traversal
{% gist https://gist.github.com/viniciuslcpereira97/8384c5a58d292e51a4b4579c0aefe310 %}

Depois de termos concluido essas duas etapas, começamos a pesquisar qual seria a melhor forma de construirmos a árvore e evitar ter que construí-la toda vez que alguém fizesse algum request para nosso serviço. Diante disto, pensamos em cachea-la no Redis como JSON, porém algumas árvores seriam muito grandes e parsear o JSON sempre seria algo custoso, depois de algumas pesquisas, achamos algo que poderia funcionar para a gente, em **Elixir** podemos facilmente transformar uma struct em um binário usando a função `term_to_binary` do **Erlang**, e tendo esse binário podemos usar um algoritmo de hash, assim teremos a hash de uma estrutura válida para guardarmos em algum tipo de cache e então reconstruir a árvore sem executar muitos processos usando a função `binary_to_term` do **Erlang**.


```elixir

# iex

iex(1)> tree = Tree.build(event)
%Tree.Node{
  childs: [
    %Tree.Node{
      childs: [
        %Tree.Node{
          childs: nil,
          name: 55089
        }
      ],
      name:26190
     },
     %Tree.Node{
       childs: [],
       name: 26230
     }
  ],
  name: "Teste arena alterado"
}

iex(2)> binary = tree |> :erlang.term_to_binary()
<<131, 116, 0, 0, 0, 3, 100, 0, 10, 95, 95, 115, 116, 114, 117, 99, 116, 95, 95, 100, 0, 16, 69, 108, 105, 120, 105, 114, 46, 84, 114, 101, 101, 46, 78, 111, 100, 101, 100, 0, 6, 99, 104, 105, 108, 100, 115, 108, 0, 0, ...>>


iex(3)> hash = binary |> Base.encode64()
"g3QAAAADZAAKX19zdHJ1Y3RfX2QAEEVsaXhpci5UcmVlLk5vZGVkAAZjaGlsZHNsAAAAAnQAAAADZAAKX19zdHJ1Y3RfX2QAEEVsaXhpci5UcmVlLk5vZGVkAAZjaGlsZHNsAAAAAXQAAAADZAAKX19zdHJ1Y3RfX2QAEEVsaXhpci5UcmVlLk5vZGVkAAZjaGlsZHNkAANuaWxkAARuYW1lYgAA1zFqZAAEbmFtZWIAAGZOdAAAAANkAApfX3N0cnVjdF9fZAAQRWxpeGlyLlRyZWUuTm9kZWQABmNoaWxkc2pkAARuYW1lYgAAZnZqZAAEbmFtZW0AAAAUVGVzdGUgYXJlbmEgYWx0ZXJhZG8="
```

Tendo esta hash, podemos voltar à estrutura usando o caminho inverso.

```elixir
hash = "g3QAAAADZAAKX19zdHJ1Y3RfX2QAEEVsaXhpci5UcmVlLk5vZGVkAAZjaGlsZHNsAAAAAnQAAAADZAAKX19zdHJ1Y3RfX2QAEEVsaXhpci5UcmVlLk5vZGVkAAZjaGlsZHNsAAAAAXQAAAADZAAKX19zdHJ1Y3RfX2QAEEVsaXhpci5UcmVlLk5vZGVkAAZjaGlsZHNkAANuaWxkAARuYW1lYgAA1zFqZAAEbmFtZWIAAGZOdAAAAANkAApfX3N0cnVjdF9fZAAQRWxpeGlyLlRyZWUuTm9kZWQABmNoaWxkc2pkAARuYW1lYgAAZnZqZAAEbmFtZW0AAAAUVGVzdGUgYXJlbmEgYWx0ZXJhZG8="

decoded_hash = Base.decode64!(hash)
<<131, 116, 0, 0, 0, 3, 100, 0, 10, 95, 95, 115, 116, 114, 117, 99, 116, 95, 95, 100, 0, 16, 69, 108, 105, 120, 105, 114, 46, 84, 114, 101, 101, 46, 78, 111, 100, 101, 100, 0, 6, 99, 104, 105, 108, 100, 115, 108, 0, 0, ...>>

structure = :erlang.binary_to_term(decoded_hash)
%Tree.Node{
  childs: [
    %Tree.Node{
      childs: [
        %Tree.Node{
          childs: nil,
          name: 55089
        }
      ],
      name:26190
     },
     %Tree.Node{
       childs: [],
       name: 26230
     }
  ],
  name: "Teste arena alterado"
}
```
---


# Resultados Obtidos

Aqui devemos considerar os seguintes atributos

**ips - iterations per second:** a quantidade de iterações que podemos executar a cada segundo.
**median:** a mediana dos tempos de execução calculada no benchmark


### Events

|Id|Session Qty.|Groups Qty.|Tickets Qty.|
|--|------------|-----------|------------|
|34392|1|3|12|
|31627|11|11|746|
|34477|2020|349|361|715|

### Queries

#### Performance Statistics

|Name|ips|average|deviation|median|99th %|
|----|---|-------|---------|------|------|
|repo.by_id.34392|1.54|648.62 ms|±6.75%|631.75 ms|756.44 ms|
|repo.by_id.31627|1.20|833.57 ms|±9.18%|826.11 ms|930.56 ms|
|repo.by_id.34477|1.09|913.59 ms|±0.41%|913.63 ms|919.02 ms|

#### Memory Usage Statistics

|Name|average|deviation|median|99th %|
|----|-------|---------|------|------|
|repo.by_id.34392|0.111 MB|±0.09%|0.111 MB|0.111 MB|
|repo.by_id.31627|1.08 MB|±0.30%|1.08 MB|1.08 MB|
|repo.by_id.34477|3.76 MB|±0.13%|3.76 MB|3.77 MB|


### Builds

#### Performance Statistics

|Name|ips|average|deviation|median|99th %|
|----|---|-------|---------|------|------|
|tree.build.34392|215.20 K|4.65 μs|±425.27%|3.46 μs|19.62 μs|
|tree.build.31627|5.94 K|168.23 μs|±60.08%|137.62 μs|654.07 μs|
|tree.build.34477|1.98 K|506.14 μs|±59.40%|392.54 μs|1864.66 μs|

#### Memory Usage Statistics

|Name|Memory usage|
|----|------------|
|tree.build.34392|4.66 KB|
|tree.build.31627|188.73 KB - 40.53x memory usage +184.08 KB|
|tree.build.34477|429.12 KB - 92.16x memory usage +424.46 KB|

### Recursive Traversal

#### Performance Statistics

|Name|ips|average|deviation|median|99th %|
|----|---|-------|---------|------|------|
|recursive.traversal.tree.34392|101.38 K|9.86 μs|±101.58%|9.18 μs|21.58 μs|
|recursive.traversal.tree.31627|10.18 K|98.19 μs|±51.78%|86.70 μs|264.75 μs|
|recursive.traversal.tree.34477|0.84 K|1188.36 μs|±3.93%|1183.79 μs|1387.74 μs|

#### Memory Usage Statistics

|Name|Memory usage|
|----|------------|
|recursive.traversal.tree.34392|6.18 KB|
|recursive.traversal.tree.31627|43.16 KB - 6.98x memory usage +36.98 KB|
|recursive.traversal.tree.34477|1010.42 KB - 163.51x memory usage +1004.24 KB|

### Tree to binary

#### Performance Statistics

|Name|ips|average|deviation|median|99th %|
|----|---|-------|---------|------|------|
|tree.to.binary.34392|177.49 K|5.63 μs|±470.90%|4.18 μs|23.35 μs|
|tree.to.binary.31627|5.89 K|169.79 μs|±32.19%|152.80 μs|411.31 μs|
|tree.to.binary.34477|2.21 K|451.81 μs|±60.66%|344.38 μs|1628.34 μs|

#### Memory Usage Statistics

|Name|Memory usage|
|----|------------|
|tree.to.binary.34392|48 B|
|tree.to.binary.31627|48 B - 1.00x memory usage +0 B|
|tree.to.binary.34477|48 B - 1.00x memory usage +0 B|


### Binary to Hash

#### Performance Statistics

|Name|ips|average|deviation|median|99th %|
|----|---|-------|---------|------|------|
|binary.to.hash.34392|22191.97|0.0451 ms|±53.24%|0.0379 ms|0.132 ms|
|binary.to.hash.31627|475.17|2.10 ms|±34.34%|1.83 ms|4.86 ms|
|binary.to.hash.34477|298.97|3.34 ms|±27.40%|3.02 ms|6.71 ms|

#### Memory Usage Statistics

|Name|Memory usage|
|----|------------|
|binary.to.hash.34392|304 B|
|binary.to.hash.31627|376 B - 1.24x memory usage +72 B|
|binary.to.hash.34477|376 B - 1.24x memory usage +72 B|

### Serialize

#### Performance Statistics

|Name|ips|average|deviation|median|99th %|
|----|---|-------|---------|------|------|
|tree.serialize.34392|21510.67|0.0465 ms|±78.93%|0.0374 ms|0.149 ms|
|tree.serialize.31627|520.52|1.92 ms|±33.44%|1.69 ms|4.42 ms|
|tree.serialize.34477|280.24|3.57 ms|±30.92%|3.13 ms|7.16 ms|

#### Memory Usage Statistics

|Name|Memory usage|
|----|------------|
|tree.serialize.34392|424 B|
|tree.serialize.31627|424 B - 1.00x memory usage +0 B|
|tree.serialize.34477|424 B - 1.00x memory usage +0 B|

Com esses resultados temos apenas uma preocupação no momento que é a quantidade de memória utilizada no algoritmo `recursive traversal`, por ser uma função recursiva nós já tinhamos em mente que ela usaria bastante memória e isso pode nos trazer problemas em um cenário de um evento gigante, o evento exemplo `34477` já é um evento considerado grande para nós devido a quantidade de ingressos e sessões que ele possui. Talvez iremos procurar resoluções para esse possível problema e acredito que se conseguirmos achar algo iremos trazer em um futuro post.

---


# Conclusão

No final dessa POC conseguimos comprovar que nós conseguimos ter o mesmo cálculo que temos hoje, porém utilizando a estrutura de árvore que montamos para esse caso que se provou muito mais eficiente que o que temos hoje, pois os resultados que tivemos se provaram muito eficientes para diversos casos que temos hoje em nosso sistema.

---

Agradecimentos especiais ao [Arthur](https://github.com/arthurmartins) por me orientar e acompanhar durante o processo de desenvolvimento! 

Espero que gostem do post.

Até uma próxima!