Learn Concurrency by Making a Countdown Latch in Ruby

A Countdown Latch is a concurrency abstraction that allows one or more threads to wait until all other threads are done with what they are doing. Therefore, a countdown latch is often referred to as a thread synchronization primitive.

How are Countdown Latches Useful?

Let say you have a bunch of threads that are fetching, say, Chuck Norris jokes. You create ten threads and you want to ensure that they all complete before you proceed on with the next step.

In this instance, you can create a countdown latch with a counter of ten. Then, right before your next step in the code, you can wait for your threads to complete. Until then, your code cannot proceed until all the threads are done.

When each thread fetches a joke, it will decrement the counter. Eventually as all ten threads are done fetching jokes, the counter in the countdown latch will eventually hit zero. That’s when the code is allowed to proceed.

Implementing Your Own Countdown Latch: Test First!

In a previous article, we went though how to implement Futures in Ruby. In this article, we are going test-drive an implementation of a Countdown Latch. Let’s get started!

Setting Up

Let’s bootstrap a new Ruby project. My favorite way is to create a Ruby gem:

% bundle gem countdown_latch -t
Creating gem 'countdown_latch'...
MIT License enabled in config
      create  countdown_latch/Gemfile
      create  countdown_latch/.gitignore
      create  countdown_latch/lib/countdown_latch.rb
      create  countdown_latch/lib/countdown_latch/version.rb
      create  countdown_latch/countdown_latch.gemspec
      create  countdown_latch/Rakefile
      create  countdown_latch/README.md
      create  countdown_latch/bin/console
      create  countdown_latch/bin/setup
      create  countdown_latch/LICENSE.txt
      create  countdown_latch/.travis.yml
      create  countdown_latch/.rspec
      create  countdown_latch/spec/spec_helper.rb
      create  countdown_latch/spec/countdown_latch_spec.rb
Initializing git repo in /Users/benjamintan/workspace/countdown_latch

Did you notice the -t flat appended? This flag adds RSpec as a development dependency.

Next, go into the project directory:

% cd countdown_latch

Run bin/setup to install the dependencies:

% bin/setup
Resolving dependencies...
Using rake 10.4.2
Using bundler 1.10.6
Using countdown_latch 0.1.0 from source at .
Using diff-lcs 1.2.5
Using rspec-support 3.3.0
Using rspec-core 3.3.2
Using rspec-expectations 3.3.1
Using rspec-mocks 3.3.2
Using rspec 3.3.0
Bundle complete! 4 Gemfile dependencies, 9 gems now installed.
Use `bundle show [gemname]` to see where a bundled gem is installed.

Creating the Countdown Latch

Now, on to the fun stuff! Since we are doing this test-first. The tests will help us drive towards the implementation that we will flesh out in order to get the tests to pass.

As a sanity check, we can quickly make sure everything is hooked up as expected:

% rspec                                                                        
CountdownLatch
  has a version number
  does something useful (FAILED - 1)

Failures:

  1) CountdownLatch does something useful
     Failure/Error: expect(false).to eq(true)

       expected: true
            got: false

       (compared using ==)
     # ./spec/countdown_latch_spec.rb:9:in `block (2 levels) in <top (required)>'

Finished in 0.01957 seconds (files took 0.07757 seconds to load)
2 examples, 1 failure

Failed examples:

rspec ./spec/countdown_latch_spec.rb:8 # CountdownLatch does something useful

Excellent! RSpec is working fine! Now, open up the test file located at spec/countdownlatchspec.rb. We are going to write the first test.

A Countdown Latch Requires a Non-negative Integer as an Argument

You should delete everything in spec/countdownlatchspec.rb and replace it with this skeleton:

module CountdownLatch

  describe CountdownLatch do

  end
end

The first test is to make sure that the argument passed into the constructor of the countdown latch is a non-negative integer:

module CountdownLatch
  describe CountdownLatch do
    it "requires a non-negative integer as an argument" do
      latch = CountdownLatch.new(3)
      expect(latch.count).to eq(3)
    end
  end
end

In order to get this to pass, we need a constructor that accepts a non-negative integer as an argument. Getting this test to pass is simple:

module CountdownLatch
  class CountdownLatch

    def initialize(count)
      if count.is_a?(Fixnum) && count > 0
        @count = count
      end
    end

  end
end

At this point, the test will pass. Let’s also make sure that 0 is accepted:

module CountdownLatch
  describe CountdownLatch do

    it "zero is a valid argument" do
      latch = CountdownLatch.new(0)
      expect(latch.count).to eq(0)
    end
  end
end

Whoops! Our test caught something:

Failures:

  1) CountdownLatch::CountdownLatch zero is a valid argument
     Failure/Error: expect(latch.count).to eq(0)

       expected: 0
            got: nil

       (compared using ==)

Turns out, we have an off by one error when comparing count and zero:

module CountdownLatch
  class CountdownLatch

    def initialize(count)
      if count.is_a?(Fixnum) && count >= 0
        @count = count
      end
    end

  end
end

The countdown latch cannot be initialized with a negative number, or a Float, for example, since those two cases do not make sense. Let’s add the tests:

module CountdownLatch
  describe CountdownLatch do

    it "throws ArgumentError for negative numbers" do
      expect { CountdownLatch.new(-1) }.to raise_error(ArgumentError)
    end

    it "throws ArgumentError for non-integers" do
      expect { CountdownLatch.new(1.0) }.to raise_error(ArgumentError)
    end
  end
end

Now the tests will fail:

Failures:

  1) CountdownLatch::CountdownLatch throws ArgumentError for negative numbers
     Failure/Error: expect { CountdownLatch.new(-1) }.to raise_error(ArgumentError)
       expected ArgumentError but nothing was raised
     # ./spec/countdown_latch_spec.rb:17:in `block (2 levels) in <module:CountdownLatch>'

  2) CountdownLatch::CountdownLatch throws ArgumentError for non-integers
     Failure/Error: expect { CountdownLatch.new(1.0) }.to raise_error(ArgumentError)
       expected ArgumentError but nothing was raised
     # ./spec/countdown_latch_spec.rb:21:in `block (2 levels) in <module:CountdownLatch>'

Thankfully, this too is an easy fix. We just have to get the initializer to raise an ArgumentError for well, errors in the argument. In lib/countdownlatch/countdownlatch.rb:

module CountdownLatch
  class CountdownLatch

    def initialize(count)
      if count.is_a?(Fixnum) && count >= 0
        @count = count
        @mutex = Mutex.new
        @condition = ConditionVariable.new
      else
        raise ArgumentError
      end
    end

  end
end

Now the tests should all pass.

Counting Down

A countdown latch has to know how to count down its own internal counter.

module CountdownLatch
  describe CountdownLatch do

    it "#count decreases when #count_down is called" do
      latch = CountdownLatch.new(3)
      latch.count_down
      expect(latch.count).to eq(2)
    end

  end
end

Now we need have access to the @count field. That is easy enough:

module CountdownLatch
  class CountdownLatch

    def initialize(count)
      # ...
    end

    def count
      @count
    end

  end
end

The count_down method looks almost simplistic:

module CountdownLatch
  class CountdownLatch

    def count_down
      @count -= 1
    end

  end
end

Resist the temptation to add more behavior and “smarter” logic until the tests are forcing you to do something about it. In this case, the tests should be all green now.

However, our tests are not complete. The countdown latch should only count down to zero and nothing less. Let’s add a test for that:

module CountdownLatch
  describe CountdownLatch do

    it "#count never reaches below zero" do
      latch = CountdownLatch.new(0)
      latch.count_down
      expect(latch.count).to eq(0)
    end

  end
end

The above test fails:

  1) CountdownLatch::CountdownLatch #count never reaches below zero
     Failure/Error: expect(latch.count).to eq(0)

       expected: 0
            got: -1

       (compared using ==)

We just need to check if @count is zero:

module CountdownLatch
  class CountdownLatch

    def count_down
      unless @count.zero?
        @count -= 1
      end
    end

  end
end

Everything should be green!

Awaiting for Threads

Till now, we simply have a glorified countdown object. It is not even thread-safe! This is because count_down can be called by multiple threads and since @count is not synchronized in anyway, race conditions can occur.

This is the first test that will drive us to implement the concurrency features in our countdown latch:

module CountdownLatch
  describe CountdownLatch do

    it "#await will wait for a thread to finish its work" do
      latch = CountdownLatch.new(1)

      Thread.new do
        latch.count_down
      end

      latch.await
      expect(latch.count).to eq(0)
    end

  end
end

The test creates a countdown latch initialized to 1. We then create a thread that decrements the latch. Outside of the thread, we call latch.await.

This is basically saying that the program will wait for the thread to finish its work. Again, once the thread is done with its work, it will call latch.count_down. Therefore, we expect that the count of the latch to be zero.

In order to see the test fail correctly, we need an empty implementation of await:

module CountdownLatch
  class CountdownLatch

    def await
    end

  end
end

When you run the tests, the following will fail:

Failures:

  1) CountdownLatch::CountdownLatch #await will wait for a thread to finish its work
     Failure/Error: expect(latch.count).to eq(0)

       expected: 0
            got: 1

       (compared using ==)

Since await does nothing, the program doesn’t wait for the thread to tell the countdown latch that it’s OK to proceed. Instead, the program simply runs straight through. In order to get this test to pass, you need to know about condition variables.

Condition Variables

A condition variable is essentially a synchronization primitive (recall that a countdown latch is also a synchronization primitive) that allows threads to wait until some condition occurs. In the case of a countdown latch, that condition is when @count hits zero.

When that happens, the broadcast method has to be called on the condition variable to tell all the waiting threads that they can stop waiting and proceed.

First, we’ll add the condition variable to the implementation and tell it to broadcast to all waiting threads when the condition has been met. Do not forget to include require "thread" too:

require "thread"  # <----

module CountdownLatch
  class CountdownLatch

    def initialize(count)
      if count.is_a?(Fixnum) && count >= 0
        @count = count
        @condition = ConditionVariable.new # <----
      else
        raise ArgumentError
      end
    end

    def count_down
      unless @count.zero?
        @count -= 1
      else
        @condition.broadcast # <----
      end
    end

  end
end

Now, to deal with the other side of the equation: Making threads suspend execution and wait till the condition is met. Here’s the first attempt. ConditionVariable has a method called wait:

module CountdownLatch
  class CountdownLatch

    def await
      @condition.wait
    end

  end
end

However, this doesn’t work because ConditionVariable#wait requires an argument that takes in a Mutex object. A mutex is essentially a lock that protects a section of code from being entered by more than one thread. Recall that I mentioned @count is , until now, not thread-safe. We are going to fix this.

In this case, we need to supply a mutex to the condition variable, so that only one thread can read/write to the condition variable at any one time.

First, we will create a mutex for the countdown latch:

module CountdownLatch
  class CountdownLatch

    def initialize(count)
      if count.is_a?(Fixnum) && count >= 0
        @count = count
        @condition = ConditionVariable.new
        @mutex = Mutex.new <----
      else
        raise ArgumentError
      end
    end

  end
end

Next, we will use @mutex.synchronize to demarcate a critical section. A critical section is an area of code where only one thread can enter. First, let’s handle the count_down method:

module CountdownLatch
  class CountdownLatch

    def count_down
      @mutex.synchronize {
        unless @count.zero?
          @count -= 1
        else
          @condition.broadcast
        end
      }
    end

  end
end

We finally have a mutex to pass into @condition.wait :

module CountdownLatch
  class CountdownLatch

    def await
      @condition.wait(@mutex)
    end

  end
end

However, just like the count_down method, you need a critical section. Here it is:

module CountdownLatch
  class CountdownLatch

    def await
      @mutex.synchronize {
        @condition.wait(@mutex)
      }
    end

  end
end

While we are add it, let’s wrap the @count in the count method with a mutex too:

module CountdownLatch
  class CountdownLatch

    def count
      @mutex.synchronize { 
        @count
      }
    end

  end
end

Run the test again and we should be green! Woot!

A Sample Run

Create a folder under lib called sample. In that folder, I create a file called chucky.rb with the following contents:

require 'open-uri'
require 'json'

module CountdownLatch

  class Chucky
    URL = 'http://api.icndb.com/jokes/random'

    def get_fact
      open(URL) do |f|
        f.each_line { |line| puts JSON.parse(line)['value']['joke'] }
      end
    end

    def get_facts(num)
      latch = CountdownLatch.new(num) # <---- Latch

      facts = []
      (1..num).each do |x|
        Thread.new do
          facts << get_fact
          latch.count_down
        end
      end

      latch.await

      facts
    end

  end
end

This class fetches jokes from a third-party API, parses the JSON response and returns the joke as a String. We can use a test to drive Chucky and get us some facts:

require 'spec_helper'
require 'sample/chucky' # <---- Remember to add this!

module CountdownLatch
  describe CountdownLatch do

    it "sample run", :speed => 'slow' do
      chucky = Chucky.new
      facts = chucky.get_facts(5)

      expect(facts.size).to eq(5)
    end

  end
end

As expected, the tests will pass. Try removing the latch and see what happens.

Limitations, Acknowledgments, and Where to Learn More

This implementation doesn’t handle spurious wakeups, an interesting phenomenon where threads can wake up even though the condition variable hasn’t signaled/broadcasted yet.

If you want a more solid and refined implementation of a countdown latch, take a look at the fantastic Ruby Concurrency GitHub repository.

Thanks for Reading!

I hope you have learned something new about condition variables, mutexes, and, of course, creating your own countdown latch! More importantly, I hope you had lots of fun following along. You can grab the full source here. Thanks for reading!

Frequently Asked Questions (FAQs) about Concurrency and Countdown Latch in Ruby