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.
-
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.monotonicreads a clock, and the difference between two readings is aFiniteDuration. -
IO.race(a, b)runs two programs, returns whichever finishes first as aLeftor aRight, and cancels the other. Use it to writefirstToAnswer(a: IO[String], b: IO[String]): IO[String].mergeturns anEither[String, String]into aString. -
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. -
A restaurant with two greeters can show two parties to their tables at the same time. Start ten parties together, use a
Semaphorewith two permits to hold them to that, and report the largest number that were being seated at any moment. A pair ofRefs will do for the counting, andupdateAndGeton aRefreturns the new value. -
Write
openKitchen(waiters: Int): IO[List[String]], in which every waiter’s fiber waits on oneDeferred[IO, Unit]and all of them carry on when it’s completed.