Como projetar um armazenamento de valor-chave transacional em Go

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:

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:

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

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 🖖