Multiple waiter synchronization in Go

waiter-sync.md

Multiple-Waiter Synchronization in Go

Often you have an object that is waiting for some result, e.g., an error to be delivered (once) by some goroutine. Multiple goroutines would like to wait for that to happen.

A traditional solution uses a condition variable, e.g.,

var result value
var ready bool
var mu sync.Mutex
cond := sync.NewCond(&mu)

func deliver(v value) {
  mu.Lock()
  defer mu.Unlock()
  result = v
  ready = true
  cond.Broadcast()
}

func wait() value {
  mu.Lock()
  defer mu.Unlock()
  for !ready {
    cond.Wait()
  }
  return result
}

This works, but it's messy, and it means all the waiters wind up contending on the lock once the delivery occurs. This solution also makes it tricky to handle cancellation: You could start a separate goroutine to wake the condition variable when the context ends, but then you have to add another select to the retry loop to distinguish readiness.

It would be nice to have a solution that integrates cleanly with contexts, avoids contention among waiters, and does not require so many pieces of state just to deliver a pending value.

Tactic: First Past the Post

One tactic I have found that works well this scenario is to use a buffered sentinel channel. The basic idea is to create a buffered sentinel channel, and instead of closing it to signal completion, send one value on the channel.

Now, goroutines wanting to check for completion have an additional responsibility: The first goroutine to receive a value is now responsible for closing the sentinel, after doing any other work necessary for admission control. This is the cooperative strategy used in many lock-free algorithms, and it looks something like this:

var result value
done := make(chan value, 1) // N.B. buffered

// Waiter
func wait(ctx context.Context) value {
  select {
  case <-ctx.Done():
    return errIGiveUp
  case v, ok := <-done:
    if ok {
      // I am the first recipient! No others will get a value until I, who
      // thereby am responsible for doing so, have closed the channel.
      //
      // Thus protected, I can update state, and all is well. Just make
      // sure not to close the channel until I'm completely done.
      result = v
      close(done)
    }
    return result  // everyone gets here eventually
  }
}

This tactic feels little subtle at first, but in many ways it's a lot more elegant than using an explicit lock and condition variable, or polling.