14. Concurrency

Two people ask for the last table at eight o’clock at the same moment. In chapter 4 it took two Java threads and two carefully chosen sleeps to show what goes wrong. With IO the same race is a five-line method.

14.1. Two requests at once

As it stands, reserve decides what to book and saves it in one method. Later in this chapter the deciding has to happen without the saving, so replace reserve in availability.scala with these two:

def decide(
    bookings: List[Booking],
    party: Party,
    time: LocalTime
): Either[BookingError, Booking] =
  if party.size > Booking.largestParty then Left(BookingError.PartyTooLarge(party.size))
  else
    bestTable(party, time, bookings)
      .toRight(BookingError.NothingFree(party.size, time))
      .map(table => Booking(party, table, time, Status.Confirmed))

def reserve(store: BookingStore, party: Party, time: LocalTime): Either[BookingError, Booking] =
  decide(store.all, party, time).map: booking =>
    store.add(booking)
    booking

The new function, decide, works only from the list of bookings it’s given. It has no side effects, so it can be called any number of times from anywhere and tested without a store.

Delete the lastTable method from main.scala, threads and all. Then create concurrency.scala:

package fullybooked

import cats.effect.{Deferred, IO, IOApp, Ref}
import cats.effect.std.{Queue, Semaphore}
import cats.syntax.all.*
import java.time.LocalTime
import scala.concurrent.duration.*

val eight = LocalTime.of(20, 0)
val ibrahim = Party("Ibrahim", 7)
val castellanos = Party("Castellanos", 8)

val regulars: List[Booking] =
  Table.all
    .filter(_.number != 6)
    .map(table => Booking.walkIn(Party("Regular", table.seats), table, eight))

def lastTableRace(store: BookingStore): IO[(String, String)] =
  val first = reserveIO(store, ibrahim, eight).map(result => reply(ibrahim.name, result))
  val second = IO.sleep(100.millis) >>
    reserveIO(store, castellanos, eight).map(result => reply(castellanos.name, result))
  (first, second).parTupled

object LastTable extends IOApp.Simple:
  def slowStore: IO[BookingStore] =
    IO.blocking:
      val store = SlowStore(300)
      regulars.foreach(store.add)
      store

  def show(title: String, answers: (String, String)): IO[Unit] =
    IO.println(s"$title\n  ${answers(0)}\n  ${answers(1)}")

  def run: IO[Unit] =
    for
      raced <- slowStore.flatMap(lastTableRace)
      _ <- show("Two requests at once:", raced)
    yield ()

Several of those imports are for code still to come. As in chapter 4 the restaurant is nearly full: regulars puts a party at every table but number 6. In LastTable, slowStore makes a slow store with those bookings already in it.

In lastTableRace the Ibrahims’ reservation is first and the Castellanos party’s is second, held back a tenth of a second by IO.sleep. We can write that length of time as 100.millis because of the import of scala.concurrent.duration.*. The >> after the sleep means “then”: it runs the program on its left and after it the one on its right. On the last line, parTupled turns the tuple of two programs into a single program that runs both at the same time and gives back a tuple of their results. show prints that pair under a title. Its answers(0) is the first element of the tuple, another way of writing answers._1.

$ scala run . --main-class fullybooked.LastTable
Two requests at once:
  Ibrahim: table 6 at 20:00
  Castellanos: table 6 at 20:00

Both parties have table 6, the double booking from chapter 4. The Castellanos request read the store a tenth of a second in, while the slow store was still saving the Ibrahims’ booking.

14.2. Fibers

Each of the two programs handed to parTupled ran on a fiber. A fiber is Cats Effect’s version of a thread: a sequence of steps that runs independently of the others. It’s an object in memory and far lighter than a thread. A program can have hundreds of thousands of fibers, taking turns on the pool of real threads that chapter 13 described. A fiber that’s waiting, in IO.sleep for instance, isn’t using a thread at all.

To start and stop a fiber by hand, add this to the end of concurrency.scala and run Waiting:

object Waiting extends IOApp.Simple:
  def run: IO[Unit] =
    for
      freed <- Deferred[IO, Table]
      silva <- freed.get.map(table => s"Silva: table ${table.number} is yours").start
      moreau <- IO.sleep(1.hour).onCancel(IO.println("Moreau: gave up waiting")).start
      _ <- IO.println("Two parties are waiting")
      _ <- IO.sleep(100.millis)
      _ <- moreau.cancel
      _ <- freed.complete(Table(2, 2))
      message <- silva.joinWithNever
      _ <- IO.println(message)
    yield ()
$ scala run . --main-class fullybooked.Waiting
Two parties are waiting
Moreau: gave up waiting
Silva: table 2 is yours

Each party waits on a fiber of its own: start begins a program on a new fiber and returns at once with a handle to it. The Silvas’ fiber is waiting on freed, a Deferred made on the first line: a box that starts empty and can be filled exactly once. Its get doesn’t return until the box is full. The Moreaus’ fiber would sleep for an hour, but cancel stops it after a tenth of a second and the onCancel we attached runs on the way out. Then complete fills the box with a table, which lets the Silvas’ get return. Their message reaches us through joinWithNever, which waits for a fiber and hands back what it produced. Had that fiber been cancelled, joinWithNever would wait for ever.

The tenth of a second before the cancel is there to let both fibers get going. A fiber that’s cancelled before it has run a single step never reaches its onCancel, and on a machine with one core that happened in about half my runs without the pause.

Java has no good counterpart to cancel: interrupting a thread is a request that the code on it may or may not notice. A fiber can be cancelled between any two steps of its IO, or while it’s waiting in a step such as IO.sleep. When it is, every Resource it has open is released and every onCancel it has reached runs.

I rarely call start myself. parTupled and its relatives start the fibers, wait for them and tidy up: if one side fails, the other is cancelled and the failure is passed on. A hand-started fiber that nobody joins or cancels just keeps running, which is an easy leak to write.

14.3. State that fibers share

Part of chapter 4’s bug was a var updated by two threads at once. For a value that several fibers change, Cats Effect has Ref. Create concurrency.test.scala:

package fullybooked

import cats.effect.IO
import cats.effect.unsafe.implicits.global
import cats.syntax.all.*

class ConcurrencyTests extends munit.FunSuite:
  test("a Ref counts correctly from many fibers"):
    val program =
      for
        counter <- IO.ref(0)
        _ <- List.fill(1000)(counter.update(_ + 1)).parSequence_
        total <- counter.get
      yield total
    assertEquals(program.unsafeRunSync(), 1000)

The test makes a Ref holding 0 with IO.ref(0), and counter.update(_ + 1) is a program that adds one to it. List.fill(1000) makes a list of a thousand copies of that program for parSequence_ to run all at once, each on a fiber of its own. In Cats and Cats Effect, methods whose names end in an underscore, such as parSequence_ here and traverse_ further on, run the effects and throw away the results. Run the tests as often as you like and the answer is a thousand. Underneath, a Ref is Java’s AtomicReference with methods that return IO. When two updates collide, one of them is tried again with the new value. That means the function passed to update can run more than once, so it has to be free of side effects.

In chapter 4, checking for a table and saving the booking were two separate steps, with room for another thread in between. A Ref can make them one step with modify. Add these to the end of concurrency.scala:

class Bookings(ref: Ref[IO, List[Booking]]):
  def all: IO[List[Booking]] = ref.get

  def reserve(party: Party, time: LocalTime): IO[Either[BookingError, Booking]] =
    ref.modify: bookings =>
      decide(bookings, party, time) match
        case Right(booking) => (bookings :+ booking, Right(booking))
        case Left(error)    => (bookings, Left(error))

object Bookings:
  def starting(bookings: List[Booking]): IO[Bookings] =
    Ref.of[IO, List[Booking]](bookings).map(ref => Bookings(ref))

def lastTableFixed(bookings: Bookings): IO[(String, String)] =
  val first = bookings.reserve(ibrahim, eight).map(result => reply(ibrahim.name, result))
  val second = IO.sleep(100.millis) >>
    bookings.reserve(castellanos, eight).map(result => reply(castellanos.name, result))
  (first, second).parTupled

A Bookings keeps its list of bookings in a Ref. Bookings.starting makes that Ref with Ref.of, which is IO.ref with the types written out. The reserve method of Bookings uses modify, which is like update except that it also gives the caller an answer. The function passed to modify receives the current list and returns a pair: the new list to store, and a result for the caller. In reserve that function runs decide, then either adds the booking to the list and answers Right, or leaves the list as it was and answers with the error. The check and the save are now a single step that no other fiber can get between, which is only possible because decide needs nothing except the list.

14.4. A lock, when the state lives elsewhere

The slow store stands for a database, and the bookings in a database can’t be moved into a Ref. The traditional way to protect state like that is a lock, so that only one reservation is in progress at a time. Add this to concurrency.scala as well:

def lastTableLocked(store: BookingStore): IO[(String, String)] =
  Semaphore[IO](1).flatMap: lock =>
    val first = lock.permit.use: _ =>
      reserveIO(store, ibrahim, eight).map(result => reply(ibrahim.name, result))
    val second = IO.sleep(100.millis) >> lock.permit.use: _ =>
      reserveIO(store, castellanos, eight).map(result => reply(castellanos.name, result))
    (first, second).parTupled

A Semaphore hands out a fixed number of permits, here one. lock.permit is a Resource, so use takes the permit, runs the reservation and gives the permit back whatever happens. The _ => is there because the reservation has no use for the value a permit hands over. While the Ibrahims’ request holds the permit, the Castellanos request waits, and by the time its turn comes the Ibrahims’ booking is in the store.

Replace the LastTable object with one that runs all three versions:

object LastTable extends IOApp.Simple:
  def slowStore: IO[BookingStore] =
    IO.blocking:
      val store = SlowStore(300)
      regulars.foreach(store.add)
      store

  def show(title: String, answers: (String, String)): IO[Unit] =
    IO.println(s"$title\n  ${answers(0)}\n  ${answers(1)}")

  def run: IO[Unit] =
    for
      raced <- slowStore.flatMap(lastTableRace)
      _ <- show("Two requests at once:", raced)
      bookings <- Bookings.starting(regulars)
      fixed <- lastTableFixed(bookings)
      _ <- show("With the bookings in a Ref:", fixed)
      locked <- slowStore.flatMap(lastTableLocked)
      _ <- show("With a lock around the slow store:", locked)
    yield ()
$ scala run . --main-class fullybooked.LastTable
Two requests at once:
  Ibrahim: table 6 at 20:00
  Castellanos: table 6 at 20:00
With the bookings in a Ref:
  Ibrahim: table 6 at 20:00
  Castellanos: sorry, no table for 8 is free at 20:00
With a lock around the slow store:
  Ibrahim: table 6 at 20:00
  Castellanos: sorry, no table for 8 is free at 20:00

Both fixes give the table to the Ibrahims and tell the Castellanos party that nothing is free. The lock does it by making every reservation queue behind the one before, even when the two have nothing to do with each other. Neither fix works once there’s more than one copy of the program running, since the lock and the Ref both live in one program’s memory. Chapter 20 has the database do the job.

Add a stronger test, with twenty parties at once, to the end of ConcurrencyTests:

  test("a Ref never gives the last table to two parties"):
    val program =
      for
        bookings <- Bookings.starting(regulars)
        parties = List.tabulate(20)(n => Party(s"Party $n", 7))
        results <- parties.parTraverse(party => bookings.reserve(party, eight))
        stored <- bookings.all
      yield (results.count(_.isRight), stored.count(_.table.number == 6))
    assertEquals(program.unsafeRunSync(), (1, 1))

A line like parties = ... inside a for gives a name to an ordinary value, with = in place of the arrow. Here the value is a list of twenty parties, built by List.tabulate(20) calling its function with the numbers 0 to 19. parTraverse is traverse from chapter 11 with every element handled on its own fiber. Twenty parties of seven go for table 6 together and exactly one gets it.

14.5. A queue between fibers

When a booking is confirmed the restaurant sends a message. The code that takes the booking shouldn’t have to wait while the message goes. It can put the message on a Queue and leave another fiber to send it. Add one more object to concurrency.scala:

object Confirmations extends IOApp.Simple:
  def sender(queue: Queue[IO, String]): IO[Unit] =
    queue.take.flatMap(message => IO.println(s"Sent: $message")).replicateA_(3)

  def run: IO[Unit] =
    for
      queue <- Queue.bounded[IO, String](10)
      worker <- sender(queue).start
      _ <- List("Okonkwo", "Lindqvist", "Moreau").traverse_(name => queue.offer(s"$name, see you tonight"))
      _ <- worker.join
      _ <- IO.println("All confirmations sent")
    yield ()
$ scala run . --main-class fullybooked.Confirmations
Sent: Okonkwo, see you tonight
Sent: Lindqvist, see you tonight
Sent: Moreau, see you tonight
All confirmations sent

The queue comes from Queue.bounded and holds at most ten messages. sender runs on its own fiber, taking messages off the queue one at a time and waiting in take whenever the queue is empty. This sender stops after three messages so that the program ends: replicateA_(3) repeats a program three times. worker.join waits for the sender’s fiber to finish and returns a value saying how it ended, which the program ignores. On the other side of the queue, offer waits when the queue is full. With a bound of ten, code that fills the queue faster than the sender empties it is slowed to the sender’s speed.

14.6. Exercises

Solutions are in the book’s downloadable code, under ch14/exercises.

  1. Write lookUpAll(names: List[String]): IO[List[String]], in which each lookup sleeps for 200 milliseconds and all of them run at once. Test that three take well under 600. IO.monotonic reads a clock, and the difference between two readings is a FiniteDuration.

  2. IO.race(a, b) runs two programs, returns whichever finishes first as a Left or a Right, and cancels the other. Use it to write firstToAnswer(a: IO[String], b: IO[String]): IO[String]. merge turns an Either[String, String] into a String.

  3. Write cancel(ref: Ref[IO, List[Booking]], name: String): IO[Boolean], which removes a party’s booking in one atomic step and says whether there was one to remove.

  4. A restaurant with two greeters can show two parties to their tables at the same time. Start ten parties together, use a Semaphore with two permits to hold them to that, and report the largest number that were being seated at any moment. A pair of Refs will do for the counting, and updateAndGet on a Ref returns the new value.

  5. Write openKitchen(waiters: Int): IO[List[String]], in which every waiter’s fiber waits on one Deferred[IO, Unit] and all of them carry on when it’s completed.