Como projetar um armazenamento de valor-chave transacional em Go

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 Y14

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 Y2020> ROLLBACK //Throws away any changes made> GET YY 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:

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 YY = 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 YY = 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:

• 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 mainimport (	"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 scopeAlso 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 F55

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á!

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 ⚔.

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

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 🖖