Cómo diseñar una tienda transaccional de valor-clave en Go

Si desea diseñar un shell interactivo que permita el acceso a un almacén transaccional de claves / valores en memoria, entonces está en el lugar correcto.

Vayamos juntos y diseñemos uno ahora.

Trasfondo

Las preguntas sobre el diseño de sistemas siempre me han interesado porque te permiten ser creativo.

Recientemente leí el blog de Uduak donde compartió su experiencia haciendo un maratón de entrevistas de 30 días, lo cual fue bastante emocionante. Recomiendo fuertemente leer esto.

De todos modos, me enteré de esta interesante pregunta sobre el diseño del sistema que le hicieron durante la entrevista.

El reto

La pregunta es la siguiente:

Construya un shell interactivo que permita el acceso a un "almacén transaccional de clave / valor en memoria".

Nota : La pregunta se reformula para una mejor comprensión. Se presentó como un proyecto "para llevar a casa" durante la entrevista del autor mencionado anteriormente.

El shell debe aceptar los siguientes comandos:

Mando Descripción
SET Establece la clave dada en el valor especificado. También se puede actualizar una clave.
GET Imprime el valor actual de la clave especificada.
DELETE Elimina la clave dada. Si no se ha configurado la clave, ignórela.
COUNT Devuelve el número de claves que se han establecido en el valor especificado. Si no se han configurado claves para ese valor, imprime 0.
BEGIN Inicia una transacción. Estas transacciones le permiten modificar el estado del sistema y confirmar o deshacer sus cambios.
END Finaliza una transacción. Todo lo realizado dentro de la transacción "activa" se pierde.
ROLLBACK Elimina los cambios realizados en el contexto de la transacción activa. Si no hay ninguna transacción activa, imprime "Ninguna transacción activa".
COMMIT Confirma los cambios realizados en el contexto de la transacción activa y finaliza la transacción activa.

¿Estamos en la arena?

Antes de comenzar, podemos hacer algunas preguntas adicionales como:

Q1. ¿Los datos persisten después de que finaliza la sesión de shell interactiva?

Q2. ¿Las operaciones sobre los datos se reflejan en el caparazón global?

Q3. ¿COMPROMETER los cambios en una transacción anidada también se refleja en los abuelos?

Tus preguntas pueden diferir, lo cual es perfecto. Cuantas más preguntas haga, mejor comprenderá el problema.

Resolver el problema dependerá en gran medida de las preguntas que se hagan, así que definamos lo que vamos a asumir mientras construimos nuestra tienda de valor clave:

  1. Los datos no son persistentes (es decir, tan pronto como finaliza la sesión de shell, se pierden los datos).
  2. Los valores clave solo pueden ser cadenas (podemos implementar interfaces para tipos de datos personalizados, pero eso está fuera del alcance de este tutorial).

Ahora intentemos comprender la parte complicada de nuestro problema.

Comprensión de una "transacción"

Se crea una transacción con el BEGINcomando y crea un contexto para que ocurran las otras operaciones. Por ejemplo:

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

Esta es la transacción activa actual y todas las operaciones solo funcionan dentro de ella.

Hasta que la transacción activa se confirme mediante el COMMITcomando, esas operaciones no persisten. Y el ROLLBACKcomando descarta cualquier cambio realizado por esas operaciones en el contexto de la transacción activa. Para ser más precisos, elimina todos los pares clave-valor del mapa.

Por ejemplo:

> 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 

Una transacción también se puede anidar, es decir, tener transacciones secundarias también:

La transacción recién generada hereda las variables de su transacción principal y los cambios realizados en el contexto de una transacción secundaria también se reflejarán en la transacción principal.

Por ejemplo:

> 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** 

Lo intenté justo después de leer el blog. Veamos cómo podemos solucionar esto.

Vamos a diseñar

Discutimos que las transacciones también pueden tener transacciones secundarias, podemos usar la estructura de datos de la pila para generalizar esto:

  • Cada elemento de la pila es una transacción .
  • La parte superior de la pila almacena nuestra transacción "Activa" actual.
  • Cada elemento de transacción tiene su propio mapa. Lo llamaremos "tienda local", que actúa como una caché local: cada vez que SETse actualiza una variable dentro de una transacción, esta tienda.
  • Once the changes are COMMITed inside a transaction the values in this "local" store are written to our global map object.

We will be using a Linked-list implementation of stack. We can also achieve this using dynamic arrays as well, but that's homework for the reader:

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. } 
  • Our stack is represented by a structure, TransactionStack which only stores a pointer to the top of the stack.size is a struct variable which can be used to determine the size of our stack i.e to find number of suspended & active transactions (completely optional – you can omit declaring this).
  • The Transaction struct has a store which we defined earlier as a map and a pointer to the next transaction in memory.
  • GlobalStore is a map which is shared by all the transactions in the stack. This is how we achieve a parent-child relationship, but more on this later.

Now let's write the push and pop methods for our 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 Transactions\n") } else { node := &Transaction{} ts.top = ts.top.next node.next = nil ts.size-- } } 
  • With every BEGIN operation, a new stack element is pushed into the TransactionStack and updates top to this value.
  • For every COMMIT or END operation, the active transaction is popped from the stack and the next element of the stack is assigned to top. Hence the parent transaction is now our current active transaction.

If you are new to Go, note that PushTransaction() and PopTransaction() are methods and not functions of receiver type (*TransactionStack).

In languages like JavaScript and Python, the receiver method invocation is achieved by the keywords this and self, respectively.

However in Go this is not the case. You can name it anything you want. To make it easier to understand we choose ts to refer to the transaction stack.

Now we create a Peek method to return us the top element from the stack:

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

Note that we are returning a pointer variable of type Transaction.

COMMITing a transaction will involve "copying" all the new and/or updated values from the transaction local store to our 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 commit\n") } // write data to file to make it persist to disk // Tip: serialize map data to JSON } 

Rolling back a transaction is pretty easy. Just delete all the keys from the map (the local map of a transaction):

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

And finally, here are the GET and SET functions:

/*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("%s\n", val) } else { fmt.Printf("%s not set\n", key) } } else { if val, ok := ActiveTransaction.store[key]; ok { fmt.Printf("%s\n", val) } else { fmt.Printf("%s not set\n", key) } } } 

While SETing a variable, we also have to consider the case when the user might not run any transactions at all. This means that our stack will be empty, that is, the user is SETing variables in the global shell itself.

> SET F 55 > GET F 55 

In this case we can directly update our 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 } } 

Are you still with me? Don't go!

we are in the endgame now

We are pretty much done with our key-value store, so let's write the driver code:

 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 %s\n", operation[0]) } } } 

The COUNT and DELETE operations are fairly easy to implement if you stuck with me until now.

I encourage you to do this as homework, but I have provided my implementation below if you get stuck somewhere.

Time for testing ⚔.

zoe-demo

And let me leave you with my source code - you can give the repo a star if you want to support my work.

If you liked this tutorial, you can read more of my stuff at my blog.

Any doubts, something's wrong, or you have feedback? Connect with me on Twitter or e-mail them to me directly.

Gophers by MariaLetta/free-gophers-pack

Happy Learning ?