A Tiny Transaction Log In Go

A Tiny Transaction Log In Go
Photo by Joel & Jasmin Førestbird / Unsplash

I recently had a technical interview with a really interesting prompt. They presented a simple set of tests and an interface and asked me to write an implementation that would fulfill the tests.

The interface was minimal and looked like this:

set(account, balance)
get(account, height)
increment_height()

The tests were similarly simple, and the interviewer actually didn't even require them to be asserted, just logged for inspection. Basically, they wanted to test that you could retrieve the history of a set of balances. A great problem that can hide a lot of complexity behind a deceptively simple interface.

The Implementation

The bulk of the implementation came down to this

// Set adds a tx to the list at the current height
func (b *chainer) Set(id string, balance uint64) {
	newtx := tx{height: b.height, balance: balance}

	v, ok := b.balances[id]
	if !ok {
		b.balances[id] = []tx{newtx}
		return
	}

	v = append(v, newtx)
	b.balances[id] = v
	b.buffer = append(b.buffer, newtx)
}

// Get returns the balance at the given height.
// If the height is greater than the block height, it uses
// the current block height.
func (b *chainer) Get(id string, height uint64) uint64 {
	var selected int

	txlist, ok := b.balances[id]
	if !ok {
		return 0
	}

	for idx, item := range txlist {
		if item.height <= height {
			selected = idx
		}
		if item.height > height {
			break
		}
	}

	return txlist[selected].balance
}

The buffer holds transactions as they come in for the current height. Upon IncrementHeight being called, we drain the buffer into our list of transactions and create a new item in the log.

Get looks up a user by id  in our balances map and returns the balance of the transaction that has the greatest height less than or equal to the height.

Set is straight forward: it appends a tx to the user's history and adds the transaction to the buffer. If no user is found in the records, it will add the user and return their balance, considering this a deposit.

This code is not meant to operate asynchronously, but honestly it is blazingly fast so it will not be likely to be your bottleneck. Additionally, it would really be easy to set it up in a fan-in/fan-out pattern to wrap it in asynchronous handling, e.g. into a message bus.

A subtle bug

There is a very subtle bug in the Get handling that I discovered when thinking about the Get logic. If there are multiple updates to a user's balance in the same block, the algorithm grab the first matching transaction that has a height number less than or equal to the provided height. But if there exist multiple transactions at that height, any blocks to the right in the slice of that first block will be ignored. This is a sly little bug, but especially pernicious when we're dealing with money.

In one case, this could be used to drain money from an account by tricking the chainer into thinking that there is money in the account and allowing them to withdraw more money than they have in their account until the block is incremented, in which case this would even be a repeatable bug. The stuff of nightmares, let me tell you.

Concurrency concerns

This library, by default, does not use locks. If one wanted to establish multiple writers to this library, but maintain stable and safe reads, they would need to either add a locking mechanism to the struct, an implementation detail, or they would need to control reads and writes manually to ensure they're handled correctly.

If one desired maintaining the lockless writes property of this data structure, perhaps for performance considerations, we could pipeline this into a system that would never need locks and could still offer decent read guarantees.

In Go, this advice is commonly voiced as "share memory by communicating". The typical approach would be to channel-in Set method calls, and then only read Get requests from a shared state that is updated from the responses of those Set requests, maintaining atomic access to the structure without actually needed mutexes or synchronization logic.