The ultimate guide to Ruby concurrency interviews. Developed by FAANG engineers, this course covers Monitors, Deferred Callbacks and problem-solving strategies for Reader-Writer and Dining Philosopher Problems.

Concurrency in Ruby is one of the most complex and advanced topics brought up during senior engineering interviews. Knowledge of concurrency and multithreading can put interviewees at a considerable advantage. This course lays the foundations of advanced concurrency and multithreading and explains concepts such as Monitors and Deferred Callbacks in depth. It also builds simple and complete solutions to popular concurrency problems that can be asked about in interviews like the Reader-Writer Problem and the Dining Philosopher Problem. While prior knowledge of concurrency is not required to follow through with this course, familiarity with the basics of Ruby would be helpful.

Ruby Concurrency for Senior Engineering Interviews

<div class="card">
   # Rate Limiting Using Token Bucket Filter
    <div class="ans">
<p><i>This is an actual interview question asked at Uber and Oracle.</i></p>
<p>Imagine you have a bucket that gets filled with tokens at the rate of 1 token per second. The bucket can hold a maximum of N tokens. Implement a thread-safe class that lets threads get a token when one is available. If no token is available, then the token-requesting threads should block.</p>
<p> The class should expose an API called <code>getToken</code> that various threads can call to get a token.</p>
    </div>
</div>


<div class="card">

# Solution
<div class="ans">

<p>This problem is a naive form of a class of algorithms called the "token bucket" algorithms. A complimentary set of algorithms is called "leaky bucket" algorithms. One application of these algorithms is shaping network traffic flows. This particular problem is interesting because the majority of candidates incorrectly start with a multithreaded approach when taking a stab at the problem. One is tempted to create a background thread to fill the bucket with tokens at regular intervals but there is a far simpler solution devoid of threads and a lesson in making judicious use of threads. This question tests a candidate's comprehension prowess as well as concurrency knowledge.</p>

<p>The key to the problem is to find a way to track the number of available tokens when a consumer requests for a token. Note the rate at which the tokens are being generated is constant. So <span class="hi-yl">if we know when the token bucket was instantiated and when a consumer called <code class="mthd">getToken()</code> we can take the difference of the two instants and know the number of possible tokens we would have collected so far.</span> However, we'll need to tweak our solution to account for the max number of tokens the bucket can hold.
Let's start with the skeleton of our class:</p>


```ruby
class TokenBucketFilter

  def initialize(maxTokens)
    @maxTokens = maxTokens
    @lastRequestTime = DateTime.now.strftime('%s').to_f
    @possibleTokens = 0.0
    @mutex = Mutex.new
  end

  def getToken
  end
```


<p>The class <code class="clazz">TokenBucketFilter</code> contains a constructor method <code class="mthd">initialize()</code> and the <code class="mthd">getToken()</code> method. The bucket can hold N number of tokens at a given time represented by the <code class="mthd">maxTokens</code> variable. There are two more variables, <code class="mthd">lastRequestTime</code> and the current number of tokens represented by the variable <code class="mthd">possibleTokens</code> in the bucket.</p>
<b>

```ruby
class TokenBucketFilter

  def initialize(maxTokens) 
    @max_tokens = maxTokens
    @lastRequestTime = DateTime.now.strftime('%Q').to_f
    @possibleTokens = 0.0
    @mutex = Mutex.new
  end

  def getToken

  end

end
```
</b>  

<p>Note how <code class="mthd">getToken()</code> doesn't return any token type! The fact that a thread can return from the <code class="mthd">getToken()</code> call would imply that the thread <i>has the token</i>, which is nothing more than a permission to undertake some action.</p>

<p>We can envelope the logic of the <code class="mthd">getToken()</code> with the mutex we define in the <code class="mthd">initialize()</code> method. Since we'll be manipulating the token count, we must ensure that only a single thread is inside the <code class="mthd">getToken()</code> method at any given time. Given the GIL restriction in Ruby, we may erroneously reason that we don't need to use a lock since only one thread can be active within the <code class="mthd">getToken()</code> method. However, not using a lock can wreak havoc as the thread can be context switched at any time, allowing mutation of shared state in a thread-unsafe manner.</p>

<p>Moving on, we need to think about the following three cases to roll out our algorithm. Let's assume that the maximum allowed tokens our bucket can hold are 5.</p>

<ul>
<li><p>The last request for token was more than 5 seconds ago: In this scenario, each elapsed second would have generated one token which may total more than five tokens since the last request was more than 5 seconds ago. We need to set the maximum tokens available to 5 since that is the most the bucket will hold and return one token out of those 5.</p>
 </li>

  <li><p>The last request for token was within a window of 5 seconds: In this scenario, we need to calculate the new tokens generated since the last request and add them to the unused tokens we already have. We then return 1 token from the count.</p></li>

 <li><p>The last request was within a 5-second window and all the tokens are used up: In this scenario, there's no option but to sleep for a whole second to guarantee that a token would become available and then let the thread return. While we <code class="mthd">sleep()</code>, the mutex would still be held by the token-requesting thread and any new threads (processes) invoking <code class="mthd">getToken()</code> would get blocked.</p></li>
</ul>

<p>The above logic is translated into code below:</p>

```ruby
class TokenBucketFilter

  # initializing the bucket with maximum number of tokens
  def initialize(maxTokens)
    @maxTokens = maxTokens
    @lastRequestTime = DateTime.now.strftime('%s').to_f
    @possibleTokens = 0.0
    @mutex = Mutex.new
  end

  # the method where token is granted and the bucket is updated accordingly
  def getToken
    @mutex.synchronize do
      @possibleTokens += ((DateTime.now.strftime('%s').to_f) - @lastRequestTime)
      if (@possibleTokens > @maxTokens)
        @possibleTokens = @maxTokens
      end
      if (@possibleTokens == 0)
        sleep 1
      else
        @possibleTokens = @possibleTokens - 1
      end
      @lastRequestTime = DateTime.now.strftime('%s').to_f
      puts "Granting " + (Thread.current[:name]).to_s + " token at " + (DateTime.now.strftime('%s')).to_s
    end
  end
```

<p>You can see the final solution comes out to be very trivial without the requirement for creating a bucket-filling thread of sorts that runs perpetually and increments a counter every second to reflect the addition of a token to the bucket. Many candidates initially get off-track by taking this approach. Though you might be able to solve this problem using the mentioned approach, the code would unnecessarily be complex and unwieldy.</p>

<p>If you execute the code below, you'll see we create a token bucket with max tokens set to 1 and have ten threads request for a token. The threads are shown being granted tokens at exactly 1-second intervals instead of all at once. The program output displays the timestamps at which each thread gets the token and we can verify the timestamps are 1 second apart.</p>

</div>
</div>

<div>
   # Rate Limiting Using Token Bucket Filter
    <div>
<p><i>This is an actual interview question asked at Uber and Oracle.</i></p>
<p>Imagine you have a bucket that gets filled with tokens at the rate of 1 token per second. The bucket can hold a maximum of N tokens. Implement a thread-safe class that lets threads get a token when one is available. If no token is available, then the token-requesting threads should block.</p>
<p> The class should expose an API called <code>getToken</code> that various threads can call to get a token.</p>
    </div>
</div>


<div>

# Solution
<div>

<p>This problem is a naive form of a class of algorithms called the "token bucket" algorithms. A complimentary set of algorithms is called "leaky bucket" algorithms. One application of these algorithms is shaping network traffic flows. This particular problem is interesting because the majority of candidates incorrectly start with a multithreaded approach when taking a stab at the problem. One is tempted to create a background thread to fill the bucket with tokens at regular intervals but there is a far simpler solution devoid of threads and a lesson in making judicious use of threads. This question tests a candidate's comprehension prowess as well as concurrency knowledge.</p>

<p>The key to the problem is to find a way to track the number of available tokens when a consumer requests for a token. Note the rate at which the tokens are being generated is constant. So <span>if we know when the token bucket was instantiated and when a consumer called <code>getToken()</code> we can take the difference of the two instants and know the number of possible tokens we would have collected so far.</span> However, we'll need to tweak our solution to account for the max number of tokens the bucket can hold.
Let's start with the skeleton of our class:</p>


```ruby
class TokenBucketFilter

  def initialize(maxTokens)
    @maxTokens = maxTokens
    @lastRequestTime = DateTime.now.strftime('%s').to_f
    @possibleTokens = 0.0
    @mutex = Mutex.new
  end

  def getToken
  end
```


<p>The class <code>TokenBucketFilter</code> contains a constructor method <code>initialize()</code> and the <code>getToken()</code> method. The bucket can hold N number of tokens at a given time represented by the <code>maxTokens</code> variable. There are two more variables, <code>lastRequestTime</code> and the current number of tokens represented by the variable <code>possibleTokens</code> in the bucket.</p>
<b>

```ruby
class TokenBucketFilter

  def initialize(maxTokens) 
    @max_tokens = maxTokens
    @lastRequestTime = DateTime.now.strftime('%Q').to_f
    @possibleTokens = 0.0
    @mutex = Mutex.new
  end

  def getToken

  end

end
```
</b>  

<p>Note how <code>getToken()</code> doesn't return any token type! The fact that a thread can return from the <code>getToken()</code> call would imply that the thread <i>has the token</i>, which is nothing more than a permission to undertake some action.</p>

<p>We can envelope the logic of the <code>getToken()</code> with the mutex we define in the <code>initialize()</code> method. Since we'll be manipulating the token count, we must ensure that only a single thread is inside the <code>getToken()</code> method at any given time. Given the GIL restriction in Ruby, we may erroneously reason that we don't need to use a lock since only one thread can be active within the <code>getToken()</code> method. However, not using a lock can wreak havoc as the thread can be context switched at any time, allowing mutation of shared state in a thread-unsafe manner.</p>

<p>Moving on, we need to think about the following three cases to roll out our algorithm. Let's assume that the maximum allowed tokens our bucket can hold are 5.</p>

<ul>
<li><p>The last request for token was more than 5 seconds ago: In this scenario, each elapsed second would have generated one token which may total more than five tokens since the last request was more than 5 seconds ago. We need to set the maximum tokens available to 5 since that is the most the bucket will hold and return one token out of those 5.</p>
 </li>

  <li><p>The last request for token was within a window of 5 seconds: In this scenario, we need to calculate the new tokens generated since the last request and add them to the unused tokens we already have. We then return 1 token from the count.</p></li>

 <li><p>The last request was within a 5-second window and all the tokens are used up: In this scenario, there's no option but to sleep for a whole second to guarantee that a token would become available and then let the thread return. While we <code>sleep()</code>, the mutex would still be held by the token-requesting thread and any new threads (processes) invoking <code>getToken()</code> would get blocked.</p></li>
</ul>

<p>The above logic is translated into code below:</p>

```ruby
class TokenBucketFilter

  # initializing the bucket with maximum number of tokens
  def initialize(maxTokens)
    @maxTokens = maxTokens
    @lastRequestTime = DateTime.now.strftime('%s').to_f
    @possibleTokens = 0.0
    @mutex = Mutex.new
  end

  # the method where token is granted and the bucket is updated accordingly
  def getToken
    @mutex.synchronize do
      @possibleTokens += ((DateTime.now.strftime('%s').to_f) - @lastRequestTime)
      if (@possibleTokens > @maxTokens)
        @possibleTokens = @maxTokens
      end
      if (@possibleTokens == 0)
        sleep 1
      else
        @possibleTokens = @possibleTokens - 1
      end
      @lastRequestTime = DateTime.now.strftime('%s').to_f
      puts "Granting " + (Thread.current[:name]).to_s + " token at " + (DateTime.now.strftime('%s')).to_s
    end
  end
```

<p>You can see the final solution comes out to be very trivial without the requirement for creating a bucket-filling thread of sorts that runs perpetually and increments a counter every second to reflect the addition of a token to the bucket. Many candidates initially get off-track by taking this approach. Though you might be able to solve this problem using the mentioned approach, the code would unnecessarily be complex and unwieldy.</p>

<p>If you execute the code below, you'll see we create a token bucket with max tokens set to 1 and have ten threads request for a token. The threads are shown being granted tokens at exactly 1-second intervals instead of all at once. The program output displays the timestamps at which each thread gets the token and we can verify the timestamps are 1 second apart.</p>

</div>
</div>

In this lesson, we will be ​ implementing rate limiting using a naive token bucket filter algorithm.

The Basics

API Overview

Brief Intro to Asynchronous Programming

Interview Practice Problems

Bonus Questions

Epilogue

Rate Limiting Using Token Bucket Filter

Rate Limiting Using Token Bucket Filter