Implementing a Stack That Supports Nested Transactions

Kyle mentioned that in one of his recent technical interviews he was asked to implement a stack that supports nested transactions. Since I've been trying to brush up on my data structures and algorithms skills and prepare myself for such interviews I thought this would be a fun exercise to tackle. Fortunately I went on vacation shortly after he mentioned this so I had some time to think about it. Not sure how well I would fare in an interview environment but I suppose that's for a different post.

Not So Basic Operations

Of course this data structure should support the basic stack operations of Push(), Pop() and even Peek(), an operation that returns the next value that would be popped without actually popping it off the stack. Implementing these operations are relatively straight forward. The interesting part however is when you start thinking about handling nested transactions. What happens if you begin a new transaction, push a few values on the stack but decide to rollback? One option would be to track these values in a temporary location and only apply them to the stack once a commit or rollback takes place. But how do you actually handle these temporary values?

The Structure

I decided to use Go to write this implementation so all methods will be written on the txstack.Stack type.

Here's what the struct looks like:

type Stack struct {
    Storage    [][]int
    InTx       bool
    Pointer    int
    TxCommitted int
}

The most interesting field in this struct is the Storage slice. More precisely, it's a slice of slices of type int. This is where the so-called magic happens. The other three fields will become apparent after I describe the nested transaction functionality.

Transactions and Nesting

Transactions occur after a Begin() call. This is when the InTx field is set to true. Basic operations can still take place before a transaction begins but all operations afterwards are in a temporary state. What this means is that the operations won't be applied to the stack until a Commit() takes place, or, if a Rollback() happens, all operations after the Begin() will be discarded. A transaction ends when either a rollback takes place or when the number of commits match the number of begins.

That last sentence could use a bit of unpacking. Essentially what it means is that when a Begin() takes place both the Pointer and Committed fields are incremented. The pointer keeps track of the current transaction state (operations are done on the storage at index Pointer) and when a Commit() takes place the Committed int is decremented. When this field reaches 0 all nested commits have taken place so all temporary stacks can be flushed and the latest stack gets copied into Storage at index 0.

Example:

s := txstack.New()
s.Push(3)
s.Push(2)
s.Push(1)

State:

+ - +
| 1 |
+ - +
| 2 |
+ - +
| 3 |
+ - +

No transactions have taken place. That is the stack as it stands.

s.Begin()
s.Pop()

Temporary State:

+ - +
| 2 |
+ - +
| 3 |
+ - +

A new transaction has begun creating a temporary state of the stack.

s.Rollback()

State:

+ - +
| 1 |
+ - +
| 2 |
+ - +
| 3 |
+ - +

The stack looks the same before the Begin() took place because of the call to Rollback(). If a call to Commit() happened instead then obviously the temporary state would have become the permanent state.

Handling State

Each time a new transaction begins a new temporary stack is created. This is where the Storage and Pointer fields comes in. A new slice is created, the contents of the previous slice are copied into it and the pointer is incremented. Now, all methods are done on the stack that the pointer points to.

Given the same example from above the internal state of the data structure would look like the following:

s := txstack.New()
s.Push(3)
s.Push(2)
s.Push(1)

Internal State:

Stack {
    Storage: [[3,2,1]],
    InTx: false,
    Pointer: 0,
    Committed: 0,
}
s.Begin()
s.Pop()

Internal State:

Stack {
    Storage: [[3,2,1],[3,2]],
    InTx: true,
    Pointer: 1,
    Committed: 1,
}
s.Rollback()

Internal State:

Stack {
    Storage: [[3,2,1]],
    InTx: false,
    Pointer: 0,
    Committed: 0,
}

If Commit() was called instead of Rollback() then the Committed field would be set to 0. When this happens the last slice gets copied into index 0 and the other slices are removed.

Putting the whole txstack package together:

package txstack

type Stack struct {
    Storage     [][]int
    InTx        bool
    Pointer     int
    TxCommitted int
}

// flushTxStacks will flush all temp storage stacks while only
// retaining the stack at storage location p by copying it into
// storage location 0.
func (s *Stack) flushTxStacks(p int) {
    keepStack := s.Storage[p]

    storage := make([][]int, 1)
    for _, val := range keepStack {
        storage[0] = append(storage[0], val)
    }
    s.Storage = storage
}

func (s *Stack) inTx() bool {
    return s.InTx
}

func (s *Stack) Empty() bool {
    p := s.Pointer
    if len(s.Storage[p]) != 0 {
        return false
    }

    return true
}

func (s *Stack) Size() int {
    p := s.Pointer
    return len(s.Storage[p])
}

func (s *Stack) Push(val int) {
    p := s.Pointer
    s.Storage[p] = append(s.Storage[p], val)
}

func (s *Stack) Pop() int {
    p := s.Pointer
    val := s.Storage[p][s.Size()-1]
    s.Storage[p] = s.Storage[p][:s.Size()-1]

    return val
}

func (s *Stack) Peek() int {
    p := s.Pointer
    return s.Storage[p][s.Size()-1]
}

// Begin creates a new transaction by making a new temporary slice and
// copying the last storage into it. Only when a full commit or
// rollback takes place will the temporary stacks be flushed.
func (s *Stack) Begin() {
    s.InTx = true
    newStack := make([]int, s.Size())

    p := s.Pointer
    copy(newStack, s.Storage[p])

    s.Storage = append(s.Storage, newStack)

    s.Pointer++
    s.TxCommitted++
}

// Commit decrements the internal TxCommitted counter and when a full
// commit takes place (when the counter reaches 0) it flushes all
// stacks while only retaining the latest.
func (s *Stack) Commit() {
    s.TxCommitted--
    if s.TxCommitted == 0 {
        s.flushTxStacks(s.Pointer)
        s.Pointer = 0
    }
}

func (s *Stack) Rollback() {
    s.flushTxStacks(0)
    s.Pointer = 0
    s.TxCommitted = 0
    s.InTx = false
}

func New() Stack {
    storage := make([][]int, 1)
    return Stack{
        Storage:     storage,
        InTx:        false,
        Pointer:     0,
        TxCommitted: 0,
    }
}

It could certainly use some more work like implementing error handling and watching for underflows and overflows but it works and I'm pretty happy with the outcome. Interestingly there isn't much on the web about writing a stack like this. Actually, I couldn't find anything but information about SQL transactions. This made it even more satisfying when all the tests passed.