Fizz Buzz but better - distributed Fizz Buzz!

A distributed approach to a much loved interview question.
5 minute read Published:

What is Fizz Buzz? If you aren’t already aware, a common entry-level programming challenge is to write this simple program. Here are the rules:

  • Print each integer from say 1-100.
  • When the number is divisible by 3, don’t print the number but print “Fizz” instead.
  • When the number is divisible by 5, don’t print the number but print “Buzz” instead.
  • When the number is divisible by both 3 and 5, print “FizzBuzz”.

This particular challenge has also become something of a joke and is used to represent all that is wrong when using a programming challenge to determine skill level.

Background

My colleagues and I were talking one day about the challenges of assessing skill during interviewing. I joked that we should ask our senior python developers to write a distributed Fizz Buzz application. After all, adding the word “distributed” to anything makes it hard or worse.

Shortly after this conversation I had some time on my hands and decided to actually write some code to solve this problem.

The problem

There are a number of ways to interpret “distributed Fizz Buzz”. I decided that the distributed application should run so that only one process prints a line for each number. If the output of the processes were concatenated in real time, they should produce the same output as the original.

It should be able to tolerate failure of any of the nodes.

An alternative implementation could use a lock to choose a master node and have it print all results until it fails and another node picks up the lock to become the new master. I chose to share the Fizz Buzz task among the nodes.

What are the options?

I didn’t really want to build the distributed logic from scratch. Was there some existing tool or library that I could build upon?

We need a distributed lock and to share an integer between processes.

  • Redis - ways to create a distributed lock and can store values.
  • etcd - has a lock primitive and can store values.
  • Raft - consensus algorithm for maintaining membership, electing a leader and replicating a journal. etcd is built upon this.
  • SWIM - this is a membership protocol and doesn’t really help. It does provide a way to share state but has no lock primitive. Consul is build upon this.
  • Scuttlebutt - provides a mechanism to gossip state changes. Potentially useful but has no lock primitive.

There are various other options that I have not included in this list to keep it brief. Some people I have talked to since suggested SWIM and Scuttlebutt but neither of these are immediately useful as they are protocols and do not provide distributed locking. We could also roll our own.

Since this project has its roots as an interview question, how would you feel about a candidate that presented a solution rolling their own? I may be impressed but would have concerns about not invented here syndrome and deploying a custom consensus algorithm in production without some comprehensive Jepsen tests.

I selected etcd as it has all of the primitives I need and I am already somewhat familiar with it.

Show me the code

Here is a short version with error handling omitted. The full version is on GitHub.

package main

import (
	"context"
	"fmt"
	"strconv"
	"time"

	"github.com/coreos/etcd/clientv3"
	"github.com/coreos/etcd/clientv3/concurrency"
)

func main() {
	cli, _ := clientv3.New(clientv3.Config{
		DialTimeout: 10 * time.Second,
		Endpoints:   []string{"127.0.0.1:2379"},
	})
	kv := clientv3.NewKV(cli)
	session, _ := concurrency.NewSession(cli)
	m := concurrency.NewMutex(session, "/counter/lock")
	backgroundCtx := context.Background()
	for {
		time.Sleep(time.Second)
		ctx, cancel := context.WithTimeout(backgroundCtx, 1 * time.Second)
		m.Lock(ctx)
		gr, _ := kv.Get(ctx, "/counter/current")
		var value int
		var modRevision int64
		if len(gr.Kvs) > 0 {
			value, _ = strconv.Atoi(string(gr.Kvs[0].Value))
			modRevision = gr.Kvs[0].ModRevision
		}
		value++
		printFizzBuzz(value)
		kv.Txn(ctx).
			If(clientv3.Compare(clientv3.ModRevision("/counter/current"), "=", modRevision)).
			Then(clientv3.OpPut("/counter/current", strconv.Itoa(value))).
			Commit()
		m.Unlock(ctx)
		cancel()
	}
}

func printFizzBuzz(num int) {
	fizz := num%3 == 0
	buzz := num%5 == 0

	if fizz && buzz {
		fmt.Println("FizzBuzz")
	} else if fizz {
		fmt.Println("Fizz")
	} else if buzz {
		fmt.Println("Buzz")
	} else {
		fmt.Println(num)
	}
}

Breaking it down

First, connect to etcd with the client. I have omitted error handling and proper use of context for brevity.

cli, _ := clientv3.New(clientv3.Config{
	DialTimeout: 10 * time.Second,
	Endpoints:   []string{"127.0.0.1:2379"},
})

Create a reference to a key and initialise a session. If the process dies, the lock will automatically expire due to the session.

kv := clientv3.NewKV(cli)
session, _ := concurrency.NewSession(cli)

We need two keys, one for the lock /counter/lock and one for the current value /counter/current.

Create a mutex locally. This doesn’t change server state.

m := concurrency.NewMutex(session, "/counter/lock")

In a loop, try to acquire the lock from the server. A sensible timeout is recommended.

for {
	m.Lock(ctx)

Read the current value. gr is a GetResponse and gr.Kvs is a slice of the requested keys. We only requested one key so we just take its value if it exists.

	gr, _ := kv.Get(ctx, "/counter/current")
	value := 0
	if len(gr.Kvs) > 0 {
		value, err = strconv.Atoi(string(gr.Kvs[0].Value))
		modRevision = gr.Kvs[0].ModRevision
	}

Increment the counter, print the value and store the counter in etcd again.

	value++
	printFizzBuzz(value)
	kv.Txn(ctx).
		If(clientv3.Compare(clientv3.ModRevision("/counter/current"), "=", modRevision)).
		Then(clientv3.OpPut("/counter/current", strconv.Itoa(value))).
		Commit()

We could use the following, simpler code in place of the kv.Txn:

	kv.Put(ctx, "/counter/current", strconv.Itoa(value))

Unfortunately in unusual circumstances this could be received and processed by the etcd server after the lock has timed out and another Fizz Buzz node has already incremented the counter. This would result in the same value being printed again. While that could happen anyway (see below) this will improve correctness.

The transaction ensures (atomically) that the counter is still at the same revision as when we fetched it before updating the value.

Finally we release the lock.

	m.Unlock(ctx)
}

We have a distributed program that will print out a line like the traditional Fizz Buzz every second. If a process dies, the others will compete for the lock and continue counting. There is a small risk of printing duplicate values if there is an issue saving the updated counter but I chose this option so that it will not skip a number.

Fizz Buzz can be fun after all.