- Artigo original: Build a Simple Persistent Key-Value Store in Elixir, using Logs – Part 1
- Tradução: Eric Douglas
- Construindo um Simples Armazenador de Chave-Valor em Elixir, usando Logs - Parte 1 - ⚠ WIP ⚠ - Introdução - What is a log? - O que é um log? - Using a Log to implement a simple KV store - Usando um Log para implementar um simples armazenador CV (chave-valor)
The code in this article is heavily inspired from the concepts amazingly explained in the book Designing Data-Intensive Applications by Martin Kleppmann. O código neste artigo é fortemente inspirado em conceitos incrivelmente explicados no livro Designing Data-Intensive Applications por Martin Kleppmann
Disclaimer, all the code you find in this article, and on the github repo, is written for pure fun and meant just as an experiment. Aviso, todo o código que você encontrar nesse artigo e no repositório do GitHub, foi escrito por pura diversão e criado como um experimento.
Published articles in the series: Artigos publicados nessa série:
- Parte 1 (esse artigo)
- Parte 2
In the last year I’ve got interested in logs and how something so simple can be the solid foundation of databases like Riak, Cassandra and streaming systems like Kafka. No último ano fiquei interessado em logs (registros) e como algo tão simples pode ser a fundação sólida de banco de dados como Riak, Cassandra e sistemas de streaming como Kafka.
In this series of articles we will see the different concepts behind a key-values store (Logs, Segments, Compaction, Memtable, SSTable) implementing a simple engine in Elixir, which is a great language to build highly-concurrent and fault-tolerant architectures. Nesta série de artigos vamos ver os diferentes conceitos por trás de armazenadores chave-valor (Logs, Segmentos, Compactação, Memtable e SSTable) implementando um motor simples em Elixir, a qual é uma grande linguagem para construir arquiteturas altamente concorrentes e tolerantes a falha.
In this first part we will see: Nessa parte vamos ver:
- What is a log?
- O que é um log?
- Making a KV persistent using a log and an index. Using an example we will use along the series, crypto market prices and trades, we are going to see how to store the values in a log using using an index.
- Como fazer um KV (key-value ou chave-valor) persistente usando log e um índice. Com um exemplo que vamos usar ao longo da série, preços e transações do mercado de criptomoedas, iremos ver como armazenar os valores em um log usando um índice.
- LogKV in Elixir. A initial super simple implementation in elixir of a Writer, an Index and a Reader.
- LogKV em Elixir. Uma implementação inicial super simples em Elixir de um Escritor, um Índice e um Leitor.
Let’s think at the most common type of log file, the one we use everyday to debug events and error messages in our applications. This simple file enshrines an interesting property, it’s an append-only file. This means that only sequential writes are allowed and everything we write in the log is immutable.
Vamos pensar no tipo de arquivo de log mais comum, aquele que usamos todos os dias para debugar eventos e mensagens de erro em nossas aplicações. Este arquivo simples consagra uma propriedade interessante, ele é um arquivo append-only (que aceita adições de conteúdo apenas no fim do arquivo). Isso significa que apenas escritas sequenciais são permitidas e tudo que escrevemos no log é imutável.
Why sequential writes could be important for us? Well… speed!
Por que escrita sequencial pode ser importante pra nós? Bom... velocidade!
Acesso Aleatório vs Sequencial - As Patologias do Big Data
We see the huge difference between random and sequential access on both classic magnetic disks, SSD and even memory. So, the idea is to leverage the sequential access speed using an append-only file to save the data of our key-value store.
Pudemos ver a grande diferença entre acesso aleatório e sequencial em ambos discos magnéticos clássicos, SSD e até mesmo a memória. Então, a ideia é potencializar a velocidade do acesso sequencial usando um arquivo apenas de adição para salvar os dados do nosso armazenador chave-valor.
Let’s start with a simple example. Let’s consider a realtime application where we have to store the last price in dollars of the Bitcoin (BTC), Ethereum (ETH) and Litecoin (LTC).
Vamos começar com um simples exemplo. Vamos considerar uma aplicação em tempo real onde nós temos que armazenar o último preço em dólares do Bitcoin (BTC), Ethereum (ETH) e Litecoin (LTC).
| Chave | Valor |
|---|---|
| BTC | 4478.12 |
| ETH | 133.62 |
| LTC | 33.19 |
If we just need to keep this snapshot in memory, in Elixir we can use a Map. But persistence is another story. There are many different ways and technologies we could use to store this map and make it persistent.
Se nós apenas precisássemos manter esse retrato em memória, com Elixir poderíamos usar um Map. Mas persistência é outra história. Existem várias formas diferentes e tecnologias que poderíamos usar para armazenar esse mapa e fazer isso persistente.
If this snapshot would be updated just few times in a day, with just few currencies, then serialising the map into a file would be fine and easy to do, but this is obviously not our case! Our imaginary crypto application needs to keep track of any market’s movement with hundreds of updates per second for hundreds of currencies.
Se esse retrato fosse atualizado apenas algumas vezes por dia, com apenas algumas moedas, então serializar o mapa dentro de um arquivo seria bom e fácil de fazer, mas isso obviamente não é o nosso caso! Nossa aplicação imaginária de criptomoedas precisa acompanhar qualquer movimento do mercado com centenas de atualizações por segundo para centenas de moedas.
But how can we use an append-only file, where data written is immutable by nature, to store the mutable data of a key-value store, to leverage sequential access and to keep our map persistent?
Mas como nós podemos usar um arquivo append-only (apenas anexando informações a ele), onde os dados escritos são imutáveis por natureza, para armazenar dados mutáveis de um armazenador chave-valor, potencializar o acesso sequencial e manter nosso mapa persistente?
The idea is pretty simple:
A ideia é muito simples:
-
append to our log each single price update (value) for any currency (key)
-
use our Map as an index, keeping track of the position and size of the values within our logfile.
-
anexar ao nosso log cada simples atualização de preço (valor) para qualquer moeda (chave)
-
usar nosso
Mapcomo um índice, mantendo o controle da posição e tamanho dos valores dentro do arquivo de log.
Concept of key-value persistence using a log Conceito de persistência chave-valor usando um log
-
17:14:59 – LTC trades at 32.85$. We append the string "32.85" to the log and we update the "LTC" key of our index (implemented with a Map) with value’s offset (0 since it’s the first value in the file) and it’s size (5 bytes, since it’s a string).
-
17:15:00 – ETH trades at 130.98$. We append the string "130.98" to the log and we update the "ETH" key of our index with offset 5 and size 6 bytes.
-
17:15:01 – BTC trades at 4411.99$. We append the string "4411.99" to the log and we update the "BTC" key of our index with offset 11 and size 7 bytes.
-
17:14:59 - LTC comercializado a $32.85. Nós adicionamos a string
"32.85"ao log e atualizamos a chave"LTC"do nosso índice (implementado com um Map) com o valor do offset (deslocamento) (0 já que é o primeiro valor no arquivo) e seu tamanho (5 bytes, pois é uma string). -
17:15:00 - ETC comercializado a $130.98. Nós adicionamos a string
130.98ao log e atualizamos a chave "ETH" ao nosso índice com deslocamento 5 e tamanho 6 bytes. -
17:15:01 - BTC comercializado a $4411.99. Nós adicionamos a string
4411.99ao log e atualizamos a chave "BTC" do nosso índice com deslocamento 11 e tamanho 7 bytes.
What happens if we receive a new price for ETH? How can we overwrite the value in the log since the value we wrote is immutable and we can just append?
O que acontece se nós recebermos um novo preço para ETH? Como podemos sobrescrever o valor no log uma vez que o valor que escrevemos é imutável e só podemos adicionar?
-
17:15:09 – ETH trades at 131.00$.
-
17:15:09 - ETH comercializado a $131.00.
Since to leverage sequential writes we can just append, we then just append the new value updating the index with the new offset and size.
Já que para aumentar a velocidade da escrita sequencial nós só podemos adicionar, nós então apenas adicionamos o novo valor atualizando o índice com o novo deslocamento e tamanho.
The read is efficient too. To retrieve the values from the log, we just use offset and size in the index and with need one seek of the disk to load our value into memory.
A leitura é eficiente também. Para recuperar os valores do log, nós só precisamos usar offset (deslocamento) e size (tamanho) no index (índice) e com uma "olhada" no disco para carregar nossos valores para memória.