Πώς να σχεδιάσετε ένα κατάστημα συναλλαγής κλειδιού-τιμής στο Go

Εάν θέλετε να σχεδιάσετε ένα διαδραστικό κέλυφος που επιτρέπει την πρόσβαση σε ένα κλειδί / τιμή αποθήκευσης συναλλαγών στη μνήμη, τότε βρίσκεστε στο σωστό μέρος.

Ας πάμε μαζί και σχεδιάστε ένα τώρα.

Backstory

Οι ερωτήσεις σχεδιασμού συστήματος με ενδιέφεραν πάντα γιατί σας επιτρέπουν να είστε δημιουργικοί.

Πρόσφατα διάβασα το blog του Uduak, όπου μοιράστηκε την εμπειρία του να κάνει έναν μαραθώνιο συνέντευξης 30 ημερών, ο οποίος ήταν πολύ συναρπαστικός. Συνιστώ ανεπιφύλακτα να το διαβάσετε.

Τέλος πάντων, γνώρισα για αυτήν την ενδιαφέρουσα ερώτηση σχεδιασμού συστήματος που του ρωτήθηκε κατά τη διάρκεια της συνέντευξης.

Η πρόκληση

Το ερώτημα έχει ως εξής:

Δημιουργήστε ένα διαδραστικό κέλυφος που επιτρέπει την πρόσβαση σε ένα "κλειδί συναλλαγών / μνήμης συναλλαγών".

Σημείωση : Η ερώτηση επαναδιατυπώνεται για καλύτερη κατανόηση. Δόθηκε ως έργο "take home" κατά τη διάρκεια της συνέντευξης του συγγραφέα που αναφέρεται παραπάνω.

Το κέλυφος πρέπει να δέχεται τις ακόλουθες εντολές:

Εντολή Περιγραφή
SET Ορίζει το δεδομένο κλειδί στην καθορισμένη τιμή. Ένα κλειδί μπορεί επίσης να ενημερωθεί.
GET Εκτυπώνει την τρέχουσα τιμή του καθορισμένου κλειδιού.
DELETE Διαγράφει το δεδομένο κλειδί. Εάν το κλειδί δεν έχει οριστεί, αγνοήστε.
COUNT Επιστρέφει τον αριθμό των κλειδιών που έχουν οριστεί στην καθορισμένη τιμή. Εάν δεν έχουν οριστεί κλειδιά σε αυτήν την τιμή, εκτυπώνεται 0.
BEGIN Ξεκινά μια συναλλαγή. Αυτές οι συναλλαγές σάς επιτρέπουν να τροποποιήσετε την κατάσταση του συστήματος και να πραγματοποιήσετε ή να επαναφέρετε τις αλλαγές σας.
END Τερματίζει μια συναλλαγή. Όλα όσα γίνονται στην "ενεργή" συναλλαγή χάνονται.
ROLLBACK Απορρίπτει τις αλλαγές που έγιναν στο πλαίσιο της ενεργής συναλλαγής. Εάν δεν υπάρχει ενεργή συναλλαγή, εκτυπώνεται "Χωρίς ενεργή συναλλαγή".
COMMIT Δεσμεύει τις αλλαγές που έγιναν στο πλαίσιο της ενεργής συναλλαγής και τερματίζει την ενεργή συναλλαγή.

Είμαστε στην αρένα;

Πριν ξεκινήσουμε, μπορούμε να κάνουμε μερικές επιπλέον ερωτήσεις όπως:

Ε1. Τα δεδομένα παραμένουν μετά τη λήξη της διαδραστικής περιόδου κελύφους;

Ε2. Οι λειτουργίες των δεδομένων αντικατοπτρίζουν το παγκόσμιο κέλυφος;

Ε3. Αντικατοπτρίζει και οι αλλαγές ΕΠΙΒΟΛΗΣ σε μια ένθετη συναλλαγή για τους παππούδες;

Οι ερωτήσεις σας μπορεί να διαφέρουν, κάτι που είναι τέλειο. Όσο περισσότερες ερωτήσεις κάνετε τόσο καλύτερα κατανοείτε το πρόβλημα.

Η επίλυση του προβλήματος εξαρτάται σε μεγάλο βαθμό από τις ερωτήσεις που τίθενται, οπότε ας καθορίσουμε τι πρόκειται να υποθέσουμε κατά τη δημιουργία του καταστήματος κλειδιών-τιμών μας:

  1. Τα δεδομένα δεν είναι μόνιμα (δηλαδή, μόλις τελειώσει η περίοδος κελύφους, τα δεδομένα χάνονται).
  2. Οι τιμές-κλειδιά μπορούν να είναι μόνο συμβολοσειρές (μπορούμε να εφαρμόσουμε διεπαφές για προσαρμοσμένους τύπους δεδομένων, αλλά αυτό είναι εκτός πεδίου για αυτό το σεμινάριο).

Τώρα ας προσπαθήσουμε να κατανοήσουμε το δύσκολο μέρος του προβλήματός μας.

Κατανόηση "συναλλαγής"

Μια συναλλαγή δημιουργείται με την BEGINεντολή και δημιουργεί ένα πλαίσιο για να πραγματοποιηθούν οι άλλες λειτουργίες. Για παράδειγμα:

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

Αυτή είναι η τρέχουσα ενεργή συναλλαγή και όλες οι λειτουργίες λειτουργούν μόνο μέσα σε αυτήν.

Μέχρι να γίνει η ενεργή συναλλαγή χρησιμοποιώντας την COMMITεντολή, αυτές οι λειτουργίες δεν συνεχίζονται. Και, η ROLLBACKεντολή απορρίπτει τυχόν αλλαγές που γίνονται από αυτές τις λειτουργίες στο πλαίσιο της ενεργής συναλλαγής. Για να είμαστε πιο ακριβείς, διαγράφει όλα τα ζεύγη τιμών-κλειδιών από το χάρτη.

Για παράδειγμα:

> 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 

Μια συναλλαγή μπορεί επίσης να τοποθετηθεί, δηλαδή να έχει και θυγατρικές συναλλαγές:

Η πρόσφατα αναπαραχθείσα συναλλαγή κληρονομεί τις μεταβλητές από τη μητρική συναλλαγή της και οι αλλαγές που πραγματοποιούνται στο πλαίσιο μιας θυγατρικής συναλλαγής θα αντικατοπτρίζονται και στη μητρική συναλλαγή.

Για παράδειγμα:

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

Το έδωσα αμέσως μόλις διάβασα το blog. Ας δούμε πώς μπορούμε να το λύσουμε.

Ας σχεδιάσουμε

Συζητήσαμε ότι οι συναλλαγές μπορεί επίσης να έχουν θυγατρικές συναλλαγές, μπορούμε να χρησιμοποιήσουμε τη δομή δεδομένων στοίβας για να το γενικεύσουμε:

  • Κάθε στοιχείο στοίβας είναι μια συναλλαγή .
  • Η κορυφή της στοίβας αποθηκεύει την τρέχουσα "Ενεργή" συναλλαγή μας
  • Κάθε στοιχείο συναλλαγής έχει το δικό του χάρτη. Θα το ονομάσουμε "τοπικό κατάστημα" που λειτουργεί σαν τοπική προσωρινή μνήμη - κάθε φορά που SETμια μεταβλητή μέσα σε μια συναλλαγή ενημερώνεται αυτό το κατάστημα.
  • Μόλις δεσμευτούν οι αλλαγές μέσα σε μια συναλλαγή, οι τιμές σε αυτό το "τοπικό" κατάστημα γράφονται στο παγκόσμιο αντικείμενο χαρτών.

Θα χρησιμοποιήσουμε μια υλοποίηση συνδεδεμένης λίστας στοίβας. Μπορούμε επίσης να το επιτύχουμε χρησιμοποιώντας δυναμικές συστοιχίες, αλλά αυτό είναι το σπίτι για τον αναγνώστη:

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. } 
  • Η στοίβα μας αντιπροσωπεύεται από μια δομή, η TransactionStackοποία αποθηκεύει μόνο ένα δείκτη στη topστοίβα. sizeείναι μια μεταβλητή δομή που μπορεί να χρησιμοποιηθεί για τον προσδιορισμό του μεγέθους της στοίβας μας, δηλαδή για τον εντοπισμό του αριθμού των ανασταλμένων και ενεργών συναλλαγών (εντελώς προαιρετικό - μπορείτε να παραλείψετε να το δηλώσετε).
  • Η Transactionδομή έχει ένα κατάστημα που ορίσαμε νωρίτερα ως χάρτη και δείκτη της επόμενης συναλλαγής στη μνήμη.
  • GlobalStoreείναι ένας χάρτης που μοιράζεται όλες οι συναλλαγές στη στοίβα. Έτσι επιτυγχάνουμε μια σχέση γονέα-παιδιού, αλλά περισσότερο σε αυτό αργότερα.

Τώρα ας γράψουμε τις μεθόδους push και pop για μας 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-- } } 
  • Με κάθε BEGINλειτουργία, ένα νέο στοιχείο στοίβας ωθείται TransactionStackκαι ενημερώνεται topσε αυτήν την τιμή.
  • Για κάθε COMMITή ENDλειτουργίας, το ενεργό συναλλαγή έσκασε από τη στοίβα και το επόμενο στοιχείο της στοίβας έχει ανατεθεί top. Εξ ου και η γονική συναλλαγή είναι τώρα η τρέχουσα ενεργή συναλλαγή μας.

Εάν είστε νέοι στο Go, σημειώστε ότι PushTransaction()και PopTransaction()είναι μέθοδοι και όχι λειτουργίες του τύπου δέκτη ( *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 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.

Έχετε αμφιβολίες, κάτι δεν πάει καλά ή έχετε σχόλια; Συνδεθείτε μαζί μου στο Twitter ή στείλτε μου απευθείας μέσω email.

Gophers από τη MariaLetta / free-gophers-pack

Καλή μάθηση;