So entwerfen Sie einen Transaktionsschlüsselwertspeicher in Go

Wenn Sie eine interaktive Shell entwerfen möchten, die den Zugriff auf einen speicherinternen Schlüssel- / Wertspeicher für Transaktionen ermöglicht, sind Sie hier richtig.

Lass uns zusammen gehen und jetzt eines entwerfen.

Hintergrundgeschichte

Fragen zum Systemdesign haben mich immer interessiert, weil Sie kreativ sein können.

Kürzlich habe ich Uduaks Blog gelesen, in dem er seine Erfahrungen bei einem 30-tägigen Interviewmarathon mitteilte, was ziemlich aufregend war. Ich kann es nur empfehlen.

Wie auch immer, ich habe von dieser interessanten Frage zum Systemdesign erfahren, die ihm während des Interviews gestellt wurde.

Die Herausforderung

Die Frage lautet wie folgt:

Erstellen Sie eine interaktive Shell, die den Zugriff auf einen "Transaktions-Schlüssel- / Wertspeicher im Speicher" ermöglicht.

Hinweis : Die Frage wurde zum besseren Verständnis neu formuliert. Es wurde während des oben genannten Autoreninterviews als "Take-Home" -Projekt gegeben.

Die Shell sollte die folgenden Befehle akzeptieren:

BefehlBeschreibung
SETSetzt den angegebenen Schlüssel auf den angegebenen Wert. Ein Schlüssel kann auch aktualisiert werden.
GETDruckt den aktuellen Wert des angegebenen Schlüssels aus.
DELETELöscht den angegebenen Schlüssel. Wenn der Schlüssel nicht gesetzt wurde, ignorieren Sie.
COUNTGibt die Anzahl der Schlüssel zurück, die auf den angegebenen Wert gesetzt wurden. Wenn für diesen Wert keine Schlüssel festgelegt wurden, wird 0 ausgegeben.
BEGINStartet eine Transaktion. Mit diesen Transaktionen können Sie den Status des Systems ändern und Ihre Änderungen festschreiben oder zurücksetzen.
ENDBeendet eine Transaktion. Alles, was innerhalb der "aktiven" Transaktion getan wird, geht verloren.
ROLLBACKWirft Änderungen weg, die im Kontext der aktiven Transaktion vorgenommen wurden. Wenn keine Transaktion aktiv ist, wird "Keine aktive Transaktion" gedruckt.
COMMITÜbernimmt die im Kontext der aktiven Transaktion vorgenommenen Änderungen und beendet die aktive Transaktion.

Wir sind in der Arena?

Bevor wir beginnen, können wir einige zusätzliche Fragen stellen wie:

Q1. Bleiben die Daten nach dem Ende der interaktiven Shell-Sitzung bestehen?

Q2. Spiegeln Operationen an den Daten die globale Shell wider?

Q3. Entspricht das Festschreiben von Änderungen in einer verschachtelten Transaktion auch den Großeltern?

Ihre Fragen können unterschiedlich sein, was perfekt ist. Je mehr Fragen Sie stellen, desto besser verstehen Sie das Problem.

Die Lösung des Problems hängt weitgehend von den gestellten Fragen ab. Definieren wir also, was wir beim Aufbau unseres Schlüsselwertspeichers annehmen werden:

  1. Daten sind nicht persistent (dh sobald die Shell-Sitzung endet, gehen Daten verloren).
  2. Schlüsselwerte können nur Zeichenfolgen sein (wir können Schnittstellen für benutzerdefinierte Datentypen implementieren, dies ist jedoch für dieses Lernprogramm nicht zulässig).

Versuchen wir nun, den schwierigen Teil unseres Problems zu verstehen.

Eine "Transaktion" verstehen

Mit dem BEGINBefehl wird eine Transaktion erstellt und ein Kontext für die anderen Vorgänge erstellt. Zum Beispiel:

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

Dies ist die aktuell aktive Transaktion, und alle Vorgänge funktionieren nur darin.

Bis die aktive Transaktion mit dem COMMITBefehl festgeschrieben wird, bleiben diese Vorgänge nicht bestehen. Der ROLLBACKBefehl wirft alle Änderungen weg, die von diesen Vorgängen im Kontext der aktiven Transaktion vorgenommen wurden. Genauer gesagt werden alle Schlüssel-Wert-Paare aus der Karte gelöscht.

Zum Beispiel:

> 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 

Eine Transaktion kann auch verschachtelt sein, dh auch untergeordnete Transaktionen haben:

Die neu erzeugte Transaktion erbt die Variablen von ihrer übergeordneten Transaktion, und Änderungen, die im Kontext einer untergeordneten Transaktion vorgenommen wurden, werden auch in der übergeordneten Transaktion berücksichtigt.

Zum Beispiel:

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

Ich habe es versucht, kurz nachdem ich den Blog gelesen hatte. Mal sehen, wie wir das lösen können.

Lassen Sie uns entwerfen

Wir haben diskutiert, dass Transaktionen auch untergeordnete Transaktionen haben können. Wir können die Stack-Datenstruktur verwenden, um dies zu verallgemeinern:

  • Jedes Stapelelement ist eine Transaktion .
  • Oben im Stapel wird unsere aktuelle "Aktive" Transaktion gespeichert.
  • Jedes Transaktionselement hat eine eigene Zuordnung. Wir werden es "lokaler Speicher" nennen, der sich wie ein lokaler Cache verhält - jedes Mal, wenn wir SETeine Variable in einer Transaktion haben, wird dieser Speicher aktualisiert.
  • Sobald die Änderungen innerhalb einer Transaktion festgeschrieben sind, werden die Werte in diesem "lokalen" Speicher in unser globales Kartenobjekt geschrieben.

Wir werden eine Linked-List-Implementierung von Stack verwenden. Wir können dies auch mit dynamischen Arrays erreichen, aber das sind Hausaufgaben für den Leser:

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. } 
  • Unser Stapel wird durch eine Struktur dargestellt, TransactionStackdie nur einen Zeiger auf topden Stapel speichert . sizeist eine Strukturvariable, mit der die Größe unseres Stapels bestimmt werden kann, dh um die Anzahl der angehaltenen und aktiven Transaktionen zu ermitteln (völlig optional - Sie können die Deklaration weglassen).
  • Die TransactionStruktur hat einen Speicher, den wir zuvor als Map definiert haben, und einen Zeiger auf die nächste Transaktion im Speicher.
  • GlobalStoreist eine Karte, die von allen Transaktionen im Stapel gemeinsam genutzt wird. Auf diese Weise erreichen wir eine Eltern-Kind-Beziehung, aber dazu später mehr.

Schreiben wir nun die Push- und Pop-Methoden für unsere 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-- } } 
  • Bei jeder BEGINOperation wird ein neues Stapelelement in das TransactionStackverschoben und topauf diesen Wert aktualisiert .
  • Für jeden COMMIToder ENDBetrieb wird die aktive Transaktion aufgetaucht aus dem Stapel und dem nächsten Element des Stapels zugeordnet ist top. Daher ist die übergeordnete Transaktion jetzt unsere aktuell aktive Transaktion.

Wenn Sie neu zu gehen, beachten Sie, dass PushTransaction()und PopTransaction()Methoden sind und nicht die Funktionen des Empfängertypen ( *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 ?