Como projetar um armazenamento de valor-chave transacional em Go

Como projetar um armazenamento de valor-chave transacional em Go

9 de September, 2020 0 By António César de Andrade
Click to rate this post!
[Total: 0 Average: 0]


Se você deseja projetar um shell interativo que permita o acesso a um armazenamento de chave / valor transacional na memória, você está no lugar certo.

Vamos juntos e projetar um agora.

História

As questões de design de sistema sempre me interessaram porque permitem que você seja criativo.

Recentemente li De Uduak blog onde ele compartilhou sua experiência em uma maratona de entrevistas de 30 dias, o que foi muito emocionante. Eu recomendo a leitura.

Enfim, fiquei sabendo desse interessante projeto de sistema pergunta que foi feita durante a entrevista.

O desafio

A questão é a seguinte:

Construir um shell interativo que permite o acesso a um “armazenamento de chave / valor transacional na memória”.

Nota: A pergunta é reformulada para melhor compreensão. Foi dado como um projeto “para levar para casa” durante a entrevista do autor acima mencionado.

O shell deve aceitar os seguintes comandos:

Comando Descrição
SET Define a chave fornecida com o valor especificado. Uma chave também pode ser atualizada.
GET Imprime o valor atual da chave especificada.
DELETE Exclui a chave fornecida. Se a chave não foi definida, ignore.
COUNT Retorna o número de chaves que foram definidas para o valor especificado. Se nenhuma chave tiver sido definida com esse valor, imprime 0.
BEGIN Inicia uma transação. Essas transações permitem que você modifique o estado do sistema e confirme ou reverta suas alterações.
END Termina uma transação. Tudo feito na transação “ativa” é perdido.
ROLLBACK Descarta as alterações feitas no contexto da transação ativa. Se nenhuma transação estiver ativa, imprime “Nenhuma transação ativa”.
COMMIT Confirma as alterações feitas no contexto da transação ativa e termina a transação ativa.

Estamos na arena 🛡

Antes de começar, podemos fazer algumas perguntas adicionais, como:

T1. Os dados persistem após o término da sessão de shell interativo?

2º trimestre. As operações nos dados refletem no shell global?

3º trimestre. As mudanças de COMMITing em uma transação aninhada também refletem nos avós?

Suas perguntas podem ser diferentes, o que é perfeito. Quanto mais perguntas você fizer, melhor compreenderá o problema.

Resolver o problema vai depender muito das perguntas feitas, então vamos definir o que vamos assumir ao construir nosso armazenamento de valor-chave:

  1. Os dados não são persistentes (ou seja, assim que a sessão do shell termina, os dados são perdidos).
  2. Os valores-chave só podem ser strings (podemos implementar interfaces para tipos de dados personalizados, mas isso está fora do escopo deste tutorial).

Agora, vamos tentar entender a parte complicada do nosso problema.

Compreendendo uma “Transação”

Uma transação é criada com o BEGIN comando e cria um contexto para as outras operações acontecerem. Por exemplo:

> BEGIN // Creates a new transaction
> SET X 200
> SET Y 14
> GET Y
14

Esta é a transação ativa atual e todas as operações funcionam apenas dentro dela.

Até que a transação ativa seja confirmada usando o COMMIT comando, essas operações não persistem. E a ROLLBACK comando descarta quaisquer alterações feitas por essas operações no contexto da transação ativa. Para ser mais preciso, ele exclui todos os pares de valores-chave do mapa.

Por exemplo:

> BEGIN //Creates a new transaction which is currently active
> SET Y 2020
> GET Y
2020
> ROLLBACK //Throws away any changes made
> GET Y
Y not set // Changes made by SET Y have been discarded

Uma transação também pode ser aninhada, ou seja, ter transações filhas também:

Hierarquia pai-filho nas transações

A transação recém-gerada herda as variáveis ​​de sua transação pai e as alterações feitas no contexto de uma transação filha também serão refletidas na transação pai.

Por exemplo:

> BEGIN //Creates a new active transaction
> SET X 5
> SET Y 19
> BEGIN //Spawns a new transaction in the context of the previous transaction and now this is currently active
> GET Y
Y = 19 //The new transaction inherits the context of its parent transaction**
> SET Y 23
> COMMIT //Y's new value has been persisted to the key-value store**
> GET Y
Y = 23 // Changes made by SET Y 19 have been discarded**

Tentei logo depois de ler o blog. Vamos ver como podemos resolver isso.

Vamos projetar

Discutimos que as transações também podem ter transações filhas, podemos usar o pilha estrutura de dados para generalizar isso:

Visualizando nossa pilha de transações

  • Cada elemento da pilha é um transação.
  • O topo da pilha armazena nossa transação “ativa” atual.
  • Cada elemento de transação tem seu próprio mapa. Vamos chamá-lo de “loja local”, que atua como um cache local – sempre que SET uma variável dentro de uma transação que esta loja é atualizada.
  • Uma vez que as mudanças são COMMITed dentro de uma transação, os valores neste armazenamento “local” são gravados em nosso objeto de mapa global.

Estaremos usando um Lista vinculada implementação de pilha. Também podemos conseguir isso usando matrizes dinâmicas, mas isso é tarefa para o leitor:

package main

import (
	"fmt"
	"os"
	"bufio"
	"strings"
)

/*GlobalStore holds the (global) variables*/
var GlobalStore = make(map[string]string)

/*Transaction points to a key:value store*/
type Transaction struct {
	store map[string]string // every transaction has its own local store
	next  *Transaction
}

/*TransactionStack maintains a list of active/suspended transactions */
type TransactionStack struct {
	top  *Transaction
	size int 			// more meta data can be saved like Stack limit etc.
}

  • Nossa pilha é representada por uma estrutura, TransactionStack que apenas armazena um ponteiro para o top da pilha.size é uma variável de estrutura que pode ser usada para determinar o tamanho de nossa pilha, ou seja, para encontrar o número de transações suspensas e ativas (completamente opcional – você pode omitir a declaração).
  • o Transaction struct tem um armazenamento que definimos anteriormente como um mapa e um ponteiro para a próxima transação na memória.
  • GlobalStore é um mapa que é compartilhado por todas as transações na pilha. É assim que alcançamos um relacionamento pai-filho, mas mais sobre isso depois.

Agora vamos escrever os métodos push e pop para nossos TransactionStack.


/*PushTransaction creates a new active transaction*/
func (ts *TransactionStack) PushTransaction() {
	// Push a new Transaction, this is the current active transaction
	temp := Transaction{store : make(map[string]string)}
	temp.next = ts.top
	ts.top = &temp
	ts.size++
}

/*PopTransaction deletes a transaction from stack*/
func (ts *TransactionStack) PopTransaction() {
	// Pop the Transaction from stack, no longer active
	if ts.top == nil {
		// basically stack underflow
		fmt.Printf("ERROR: No Active Transactionsn")
	} else {
		node := &Transaction{}
		ts.top = ts.top.next
		node.next = nil
		ts.size--
	}
}

  • Com todos BEGIN operação, um novo elemento de pilha é empurrado para o TransactionStack e atualizações top a este valor.
  • Para cada COMMIT ou END operação, a transação ativa é estourou da pilha e o próximo elemento da pilha é atribuído a top. Portanto, a transação pai agora é nossa transação ativa atual.

Se você é novo no Go, observe que PushTransaction() e PopTransaction() estão métodos e não funções do tipo receptor (*TransactionStack)

Em linguagens como JavaScript e Python, a invocação do método receptor é alcançada pelas palavras-chave this e self, respectivamente.

No entanto, em Go, esse não é o caso. Você pode nomeá-lo como quiser. Para facilitar a compreensão, escolhemos ts para se referir à pilha de transações.

Agora criamos um Peek método para nos devolver o top elemento da pilha:

/*Peek returns the active transaction*/
func (ts *TransactionStack) Peek() *Transaction {
	return ts.top
}

Observe que estamos retornando uma variável de ponteiro do tipo Transaction.

O COMPROMISSO com uma transação envolverá “copiar” todos os valores novos e / ou atualizados da loja local da transação para o nosso GlobalStore:

/*Commit write(SET) changes to the store with TranscationStack scope
Also write changes to disk/file, if data needs to persist after the shell closes
*/
func (ts *TransactionStack) Commit() {
	ActiveTransaction := ts.Peek()
	if ActiveTransaction != nil {
		for key, value := range ActiveTransaction.store {
			GlobalStore[key] = value
			if ActiveTransaction.next != nil {
				// update the parent transaction
				ActiveTransaction.next.store[key] = value
			}
		}
	} else {
		fmt.Printf("INFO: Nothing to commitn")
	}
	// write data to file to make it persist to disk
	// Tip: serialize map data to JSON
}

Reverter uma transação é muito fácil. Basta excluir todas as chaves do mapa (o mapa local de uma transação):

/*RollBackTransaction clears all keys SET within a transaction*/
func (ts *TransactionStack) RollBackTransaction() {
	if ts.top == nil {
		fmt.Printf("ERROR: No Active Transactionn")
	} else {
		for key := range ts.top.store {
			delete(ts.top.store, key)
		}
	}
}

E, finalmente, aqui estão os GET e SET funções:

/*Get value of key from Store*/
func Get(key string, T *TransactionStack) {
	ActiveTransaction := T.Peek()
	if ActiveTransaction == nil {
		if val, ok := GlobalStore[key]; ok {
		    fmt.Printf("%sn", val)
		} else {
			fmt.Printf("%s not setn", key)
		}
	} else {
		if val, ok := ActiveTransaction.store[key]; ok {
		    fmt.Printf("%sn", val)
		} else {
			fmt.Printf("%s not setn", key)
		}
	}
}

Ao definir uma variável, também devemos considerar o caso em que o usuário pode não executar nenhuma transação. Isso significa que nossa pilha ficará vazia, ou seja, o usuário está configurando variáveis ​​no próprio shell global.

> SET F 55
> GET F
55

Neste caso, podemos atualizar diretamente nosso GlobalStore:

/*Set key to value */
func Set(key string, value string, T *TransactionStack) {
	// Get key:value store from active transaction
	ActiveTransaction := T.Peek()
	if ActiveTransaction == nil {
		GlobalStore[key] = value
	} else {
		ActiveTransaction.store[key] = value
	}
}

Você ainda está comigo? Não vá!

estamos no final do jogo agora

Já concluímos nosso armazenamento de valor-chave, então vamos escrever o código do driver:


func main(){
	reader := bufio.NewReader(os.Stdin)
	items := &TransactionStack{}
	for {
		fmt.Printf("> ")
		text, _ := reader.ReadString('n')
		// split the text into operation strings
		operation := strings.Fields(text)
		switch operation[0] {
		case "BEGIN": 		items.PushTransaction()
		case "ROLLBACK": 	items.RollBackTransaction()
		case "COMMIT": 		items.Commit(); items.PopTransaction()
		case "END": 		items.PopTransaction()
		case "SET": 		Set(operation[1], operation[2], items)
		case "GET": 		Get(operation[1], items)
        case "DELETE": 		Delete(operation[1], items)
		case "COUNT": 		Count(operation[1], items)
		case "STOP": 		os.Exit(0)
		default:
			fmt.Printf("ERROR: Unrecognised Operation %sn", operation[0])
		}
	}
}

o COUNT e DELETE as operações são bastante fáceis de implementar, se você ficou comigo até agora.

Eu encorajo você a fazer isso como lição de casa, mas eu forneci minha implementação abaixo se você ficar preso em algum lugar.

É hora de testar ⚔.

zoe-demo

E deixe-me deixá-los com meu código-fonte:

zoe-key-value-store-in-go
Dê um ⭐ para apoiar o meu trabalho

Se você gostou deste tutorial, você pode ler mais de minhas coisas em meu blog.

Alguma dúvida, algo está errado ou você tem algum feedback? Conecte-se comigo no Twitter ou o email eles para mim diretamente.

Gophers por MariaLetta / free-gophers-pack

Feliz Aprendizagem 🖖





Fonte