Richard Layte

Modelling Starbucks Concurrency in Go

I’ve been using go a lot lately for my own projects and have so far found the learning curve to be pretty straight forward. Most of the concepts feel very familiar if you’ve come from any imperative, c based language. However, one new concept, and one of go’s major selling points, is its support for concurrency using CSP, or in go terms: go routines and channels.

CSP, or communicating sequential processes, is a concept developed by Tony Hoare to model concurrent actions within applications — i.e. actions that may happen at the same time rather than strictly sequentially. Go implements these ideas by allowing you to execute code in a go routine, which essentially creates a new thread to execute the code. Crucially, go doesn’t use real OS threads, but rather green threads so this ends up being really cheap and allows for thousands of concurrent processes to be created. The other half of go’s CSP implementation are channels, which are queues that can be used to pass data between go routines and the main thread.

To get a better grip on how all this works I wanted to implement some basic concurrency patterns found in the real world. One obvious example is the sometimes confusing experience of ordering coffee at Starbucks. In case, like me, you haven’t been to a Starbucks in a while lets review the process:

  • Customer places order with a Barista
  • Customer gives Barista their name
  • Customer waits for order
  • Barista takes order from a list
  • Barista makes the drink
  • Barista shouts an approximation of a Customer’s name
  • Customer collects drink

There are a few details I’m skipping over here like having a separate person serve the customers from the baristas, but this should model the main ordering process well enough.

Simple example

We’ll start with a simplified example: a small independent coffee shop that has one employee performing all tasks.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

type Barista struct {
  name   string
  orders chan string
  drinks chan string
}

func (b Barista) makeDrink(name string) {
  fmt.Println(b.name, "making", name)
  time.Sleep(time.Second)
}

func (b Barista) waitForOrders() {
  for {
    fmt.Println(b.name, "waiting for orders")
    drink := <-b.orders
    b.makeDrink(drink)
    b.drinks <- drink
  }
}

func NewBarista(orders chan string, drinks chan string) Barista {
  b := Barista{name, orders, drinks}
  go b.waitForOrders()
  return b
}

First, we define a Barista type, which takes two channels orders and drinks, which represent the incoming customer orders and completed drinks respectively.

There are also two methods defined on the Barista type. makeDrink represents the act of making a coffee by simply printing the order and waiting for a short period of time. I’ve selected one second here to make running the code faster than real life. waitForOrders starts an infinite loop that continuously takes drink requests from the orders channel, makes the required drink using makeDrink, and then finally puts the completed order on the drinks channel for the customer to take. Because makeDrink waits for one second this has the effect of completing a new order every second.

One final point to note is Barista’s constructor function. It takes the two required channels and creates a new Barista type, but also calls the waitForOrders method in a go routine. This is important because if it was called on the main thread the program would block and never return the new Barista due to the infinite loop in waitForOrders. By running this function in a go routine we “park” the execution of this method in a new thread and return immediately.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

type Customer struct {
  name   string
  orders chan string
  drinks chan string
}

func (c Customer) collectDrink() {
  fmt.Println(c.name, "waiting to collect drink")
  drink := <-c.drinks
  fmt.Println(c.name, "collected", drink)
}

func (c Customer) order(drink string) {
  fmt.Println(c.name, "ordered a", drink)
  c.orders <- drink
  c.collectDrink()
}

func NewCustomer(name string, orders chan string, drinks chan string) Customer {
  c := Customer{name, orders, drinks}
  return c
}

Next up we need to define a Customer type to consume the drinks Barista is producing. The set up for this is pretty similar to Barista: we pass in two channels to represent orders and drinks and then define methods to request an order and take a completed drink.

I won’t go through each line here because it should feel quite familiar from the last example, but one important point to note is that the infinite loop to collect a drink is only triggered once an order has been placed - i.e. in the order method instead of when the Customer is initialised. Again, this is called in a go routine to prevent the loop from blocking the main thread.

1
2
3
4
5
6
7
8
9
10
11
12
13

func main() {
  orders := make(chan string)
  drinks := make(chan string)

  NewBarista("Rob", orders, drinks)
  c1 := NewCustomer("Rachid", orders, drinks)
  c2 := NewCustomer("Rich", orders, drinks)

  c1.order("Filter")
  c2.order("Flat white")

  time.Sleep(time.Second * 10)
}

Finally, we kick all of this off in the main function by creating a couple of channels and passing these to a Barista and two Customers. Once the type have been created we can call the order method on each customer to request a drink from the Barista.

This should output the following to stdout:

1
2
3
4
5
6
7
8
9
10
11

Rachid ordered a Filter
Rob waiting for orders
Rob making Filter
Rich ordered a Flat white
Rachid waiting to collect drink
Rob waiting for orders
Rob making Flat white
Rachid collected a Filter
Rich waiting to collect drink
Rob waiting for orders
Rich collected a Flat white

Parellising with Multiple Baristas

So this works well for a small coffee shop, but in the case of a busy Starbucks branch we’ll clearly need to improve things. The obvious way to do this is to add multiple Baristas so that more than one drink can be made at a time. In other words, we want to parallelise the task. It’s important to make the distinction between concurrent and parallel, but as we’ve already made the simple version correctly concurrent adding parallelism is trivial.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

func main() {
  orders := make(chan string)
  drinks := make(chan string)

  NewBarista("Rob", orders, drinks)
  NewBarista("Pete", orders, drinks)
  c1 := NewCustomer("Rachid", orders, drinks)
  c2 := NewCustomer("Rich", orders, drinks)

  c1.order("Filter")
  c2.order("Flat white")

  time.Sleep(time.Second * 10)
}

The only change we’ve made here is to create two Baristas to handle the workload. If we now run this it should produce the same output, but the ordering of the two drink orders will now be interleaved because they are happening at the same time. For example:

1
2
3
4
5
6
7
8
9
10
11
12

Rachid ordered a Filter
Rob waiting for orders
Rob making Filter
Pete waiting for orders
Rich ordered a Flat white
Rachid waiting to collect drink
Pete making Flat white
Rich waiting to collect drink
Rob waiting for orders
Pete waiting for orders
Rachid collected a Filter
Rich collected a Flat white

However, a problem arises if we add some more real world complexity. A Flat White takes about 2 minutes to prepare whereas a filter should take up to 4 minutes to correctly brew. In our current application, Rachid would collect the wrong drink because we rely on an implicit ordering of the drinks channel.

First, we need to add variable wait times depending on what drink is being made.

1
2
3
4
5
6
7
8
9

var drinks = map[string]int{
  "Flat white": 2,
  "Filter":     4,
}

func (b Barista) makeDrink(name string) {
  fmt.Println(b.name, "making", name)
  time.Sleep(time.Second * time.Duration(drinks[name]))
}

If we now run this code without any further changes we can clearly see the problem on line 10: “Rachid collected a Flat white”.

1
2
3
4
5
6
7
8
9
10
11
12

Rachid ordered a Filter
Rob waiting for orders
Rob making Filter
Pete waiting for orders
Rich ordered a Flat white
Rachid waiting to collect drink
Pete making Flat white
Rich waiting to collect drink
Pete waiting for orders
Rachid collected a Flat white
Rob waiting for orders
Rich collected a Filter

Synchronizing orders

Starbucks solve this problem by taking a customer’s name when they order so lets try to take a similar approach.

First, we need to define a new type Drink, which holds the name of the drink ordered and a channel that we’ll put a value on once the order is complete. This represents the action of a barista shouting a customer’s name.

1
2
3
4

type Drink struct {
  name     string
  complete chan string
}

Next, we need to modify the Customer order methods to pass a Drink instance and use this new channel rather than the global drinks channel we previously blocked on. Note that we’re creating a single channel and passing that to both the collectDrinks method and passing it to the orders channel. This allows us to synchronize our actions between the separate Barista and Customer go routines.

1
2
3
4
5
6
7
8
9
10
11
12
13

func (c Customer) collectDrink(complete chan string) {
  fmt.Println(c.name, "waiting to collect drink")
  drink := <-complete
  fmt.Println(c.name, "collected a", drink)
}

func (c Customer) order(name string) {
  fmt.Println(c.name, "ordered a", name)
  complete := make(chan string)
  drink := Drink{name, complete}
  c.orders <- drink
  go c.collectDrink(complete)
}

Finally, we need to update Barista.waitForOrders to use the Drink type correctly and pass completed orders to the current drink channel.

1
2
3
4
5
6
7
8

func (b Barista) waitForOrders() {
  for {
    fmt.Println(b.name, "waiting for orders")
    drink := <-b.orders
    b.makeDrink(drink.name)
    drink.complete <- drink.name
  }
}

If we run the code again we should now see both customers receiving the correct orders.

1
2
3
4
5
6
7
8
9
10
11
12

Rachid ordered a Filter
Rob waiting for orders
Rob making Filter
Pete waiting for orders
Rich ordered a Flat white
Rachid waiting to collect drink
Pete making Flat white
Rich waiting to collect drink
Pete waiting for orders
Rich collected a Flat white
Rob waiting for orders
Rachid collected a Filter

Conclusion

There are a few other improvements we could make to more correctly model the real world, like adding a Cashier abstraction to handle taking orders from Customers, or adding some kind of bandwidth restrictions on how many drinks can be made on the available espresso machines. However, hopefully this demonstrates the basics of CSP and how to use them in go.

Thanks to Rob Berry, Rachid Belaid, Janosch Oppermann, and Ryan Slade for reviewing this.