Internals of a Thread Pool

In order to perform an asynchronous task, a Thread is required. If you have to perform a large number of tasks then you might need to initialize multiple threads. As there is a limit to the number of threads which can be executed in parallel, you will need to create and destroy these threads again and again. This is suboptimal because of following reasons:

1. There will be a lot of overhead of creating and destroying multiple thread objects.
2. Also, management of the number of threads which can be initialized or the number of tasks which can be executed in parallel becomes very difficult.

A Thread Pool overcomes both of these issues. It has a pre-defined pool of pre-initialized long running threads. Whenever a task needs to be executed, it is assigned to one of these threads. Once the task is done, that thread again becomes available for the next task.

Thus, it provides improved performance by reducing the overhead of thread creation and destruction. Also, it provides a means of bounding and managing resources. For obvious reasons, this performance gain is huge when a large number of short tasks need to be executed.

Initialization

When a thread pool is initialized, its core pool size, maximum pool size, keep alive time and work queue are defined. After initialization, based on the requirement, either

1. one thread can be initialized which can idly wait for a task to be submitted or,
2. all the threads equal to core pool size can be initialized which can all idly wait for tasks to be submitted or,
3. threads can be initialized on demand whenever a new task is submitted

After initialization, a thread pool is ready to accept requests for task execution.

Source code for basic and advanced implementations for a Thread Pool based on below mentioned concepts is available here.

Important Components

A Thread Pool Executor has three major components:

1. Work Queue (e.g. BlockingQueue)
2. Workers (e.g. Set)
3. Thread Factory

Work Queue

Maintains a list of all the tasks which need to be performed. A work queue can be bounded (e.g. ArrayBlockingQueue) or unbounded (e.g. LinkedBlockingQueue).

Workers

As the name implies, a Worker (implements Runnable) is the one who picks the task from Work Queue and executes it. Once done, it waits for more tasks to be available in the Work Queue. The moment a task is available in the queue, it fetches it and starts executing it. This cycle/loop keeps on going until an exceptional termination condition has been met or no more tasks are available based on one of the two conditions (in the given order):

1. till keep alive time if either idle thread timeout has been defined or worker count is more than core pool size
2. until a new task is available in the queue

The maximum number of workers allowed can be Integer.MAX_VALUE.

Note: ThreadPoolExecutor in Java has limited this to 29 bits, (2^29)–1 as it uses the last 3 bits of the same integer field to keep track of its own state.

Thread Factory

A Thread Factory is used to create new threads which are required to run the workers. Each Worker runs in a different thread. Basically, when a thread’s start method is called, it calls run method overridden by the Worker which takes the Worker in a task execution loop as mentioned above.

Important Attributes

A Thread Pool Executor has some important properties which affect the Worker management:

1. core pool size, the minimum number of workers that need to be maintained. If the worker count ever goes below this, a new worker is created when a new task is submitted to the executor instead of storing it in the queue. If workers count is more this number then idle workers are killed.
2. maximum pool size, the maximum number of workers which can be running at a particular moment. If worker count reaches this limit, no new workers are created in the executor and newly submitted tasks are stored in the queue. So, whenever any worker is free, it picks up an available task from the queue.
3. keep alive time, the time after which an idle worker would be killed.

4. allow core thread timeout, a boolean which tells the system if idle core workers should be killed.

Shutdown

When asked to shut down, the thread pool executor will change its state to SHUTDOWN and will interrupt all the workers. If asked for immediate shutdown then it will interrupt all the workers which have started and drain the task queue else it will interrupt only idle workers and wait for running workers to complete tasks from the task queue. Once the shutdown is triggered, no new tasks are accepted.

Source code for basic and advanced implementations for a Thread Pool based on above mentioned concepts is available here.

Internals of Java Future<V>

Future<V> is one of the most interesting Interfaces of Java. This is a concurrency abstraction also know as Promise which promises to return the result of an asynchronous computation in future without blocking the code execution. This is helpful when the job to be executed is going to take a while and you have some more computation to be done before you need the results of this job. Once the executor executes the job, it stores the results of the job in outcome member variable of the Future object which is returned to you when the job is submitted to the executor.

Following is the usage of Future:

interface ImageDownloader {
  Object download(String imageUrl);
}

class App {
  ExecutorService executor = ...
  ImageDownloader downloader = ...

  Object getImage(final String imageUrl) throws InterruptedException {
    Future<Object> future
      = executor.submit(new Callable<Object>() {
        public String call() {
          return downloader.download(imageUrl);
        }});
    Object metadata = getImageMetadata(); // do other things while downloading
    try {
      Object image = prepareImage(future.get()); // use future
      return prepareImageResult();
    } catch (ExecutionException ex) {
      cleanup();
      return;
    }
  }
}

Here, the system has submitted a Job (Callable<T>) to the scheduler whose work is the download the image for the given URL. Upon submission, executor returned an instance of Future. By the time the image is downloaded, the system has to fetch other metadata related to the image (let’s say from the internal database).

Once, the system is ready to use the image object, it calls get method on the Future instance and gets the image object. If the image is not downloaded till the time get was called, Future will block the call and wait till the time image is not downloaded. In order to prevent infinite wait, you can pass a timeout as input, after which get will throw a TimeoutExecption.

How does Future do this?

Now, the interesting question is, how does the system know which Future instance is linked to which (Callable or Runnable) Job? Does the Executor maintain some kind of internal Map to keep track of it or is there a better way of handling it?

It’s actually very simple but a clever design. Following class-diagram shows the type hierarchy of Future interface. This is where things get interesting.

Future<V> type hierarchy

Here, we can see that the instance of Future is actually an instance of its subclass FutureTask which stores Callable reference as its member variable. This is how a Future instance is linked to the submitted job.

Following are the steps which are performed when a Job is submitted to an executor:

1. The client creates a Callable instance callable by providing a definition of call method.
2. The callable is submitted to an Executor.
3. The Executor creates a FutureTask instance future by passing this callable to its constructor. This means future has a reference to the Callable which needs to be executed.
4. This future is returned to the client by the Executor.
5. When it’s time, Executor calls run method on the future which in turn calls a call method on callable.
6. When callable is executed successfully, its result is stored in the future and is returned to the client when get method is called on the future.

Future<V> Usage Sequence diagram

Important Features

1. Future wraps Callable or Runnable object and submits it to the task executor for asynchronous execution.
2. Future provides a get method which is a blocking method and blocks the flow until the result is available.
3. Future provides isDone as a non-blocking method to check if the job has completed and the result is available. Also, isCancelled method is provided which tells if the job has been canceled before completion.
4. Future also provides a cancel method to cancel the execution of a job.
5. There is a sub-interface of Future which is ScheduledFuture. This is useful to get results of a scheduled task.

This is how the Future<V> is handled internally by Java. Knowing about Future interface is very important for building an asynchronous system.

Ruby general purpose Execution Hooks / Filters

Rails provides a fantastic framework for execution hooks/Filters. Using this, we can define hooks which can be executed before or after the execution of required methods. The problem is that this functionality is not present by default in Ruby. This is available only in Rails controllers and models.

Recently as part of one of the requirements, I needed to implement something similar but outside controllers/models. The requirement was something like, “set a parameter before making an HTTP call to external systems” or “send an event after the response from external system is received”. This was needed to be done for all the existing code blocks.

Though there are frameworks available in Ruby, but we didn’t want to use big frameworks to handle this small requirement. So, we built our own Filters framework which can be used anywhere to provide this functionality, even outside the context of Rails.

Here, we will discuss about the concept on which Rails Filters work and how to build a part of this functionality on our own.

Introduction

We always try to keep our classes decoupled and make them follow Single Responsibility Principle. But there are parts of our applications like authorization, logging, persistence, notification etc which are scattered throughout our code creating strong dependencies in the code.

This is where the concept of Aspect Oriented Programming (AOP) comes to rescue. With AOP, we treat all the cross cutting concerns as aspects of the various components which we are building. Here we try to remove explicit calls to the code related to these concerns, about which a class doesn’t need to be worried, into separate methods. These methods are then executed automatically before or after the execution of intended components.

Usually, before filter is used to check for authentication, authorization or preparing data for the method call. A before filter can stop the execution of method and has access to request for the method. Similarly, after filter is executed once the method call is done. Obviously, after filter hook can’t stop the execution of the method but it has access to the response of the method. Another type of filter is around filter which can execute a logic before as well as after the method call. Generally after and around filters are used for logging purpose.

So, what if a developer needs to use these kind of execution hooks outside the context of Rails. Let’s see how we can create filters of our own.

Execution Hooks/Filters

In order to add a hook before or after execution of an intended method, we can simply use the concept of meta programming.

Full source code for the framework is available here.

We can take the method definition and redefine it by adding execution of a hook method before or after the execution of the method. Following is how it can be done:

def before_action(hook, method_names)
  method_names.each do |method_name|
    if instance_methods.include? method_name
      enhance_instance_method(hook, method_name)
    end
  end
end

def enhance_instance_method(hook, method_name)
  # Take reference to the original method
  original_method = instance_method(method_name)
  
  # Redefine the method to add the required hook
  define_method(method_name) do |*args, &block|
    # Make a call to the hook
    method(hook).call(*args)
  
    # Make a call to the original method
    original_method.bind(self).(*args, &block)
  end
end

Above, we are redefining the original method and in first line of new definition, we are adding a call to hook method and then we are calling original method. This is an example of before filter. Similarly, we can create an after filter by adding hook execution after the original method call.

Above specified method needs to be added to a module so that other modules or classes can use it by using include keyword.

Use cases

We will discuss following two use cases where we will need to use Execution Hooks:

1. Existing classes
2. New classes

Existing classes

Let’s say, we have some classes which includes HTTParty module in order make calls to external services. Also, there are classes which are directly using HTTParty module’s get and post methods. Now, the requirement is to add a global timeout before making HTTP calls. One way is to go to every piece of code where we are making HTTP calls and pass timeout parameter explicitly. A better way is to override HTTParty’s get and post methods and add a before filter which will take care of setting the timeout.

module HTTParty
  module ClassMethods
    include Hooks

    before_action :set_timeout, :get, :post 

    def set_timeout(*args)
      args << { timeout: 20 }
    end
  end
end

With above code, wherever we are using HTTParty to make a get or post call, a specified timeout will get added to the request. (Based on the parameters being sent in get/post call, internals of set_timeout method may need to be changed.)

Now, if we need to specify a client specific timeout too, we can abstract the part to fetch timeout into a different method which clients can override in order to provide required timeouts.

New classes

Let’s say, we need to implement a service class which provides CRUD operations on a resource. For operations like show, update and delete, we need to access resource based on provided ID. This logic can be extracted out into a separate method and a before filter (just like Rails controller) can be applied here. This can be specified in the following way:

class BooksService
  include Hooks
  def set_book(id)
    @book = Book.find(id)
  end

  def show(id)
  end

  def update(id)
    @book.update
  end

  def delete(id)
    @book.destroy
  end

  before_action :set_book, :show, :update, :delete
end

In this way, Execution Hooks can be added as a way of implementing Aspects in a program similar to what Rails Filters do. I understand there might be better ways to design this kind of framework but this was good enough for the requirement we had.

Eames Lounge Chair and Ottoman – Icon of Modern Design

Eames Lounge Chair and Ottoman was design by Charles and Ray Eames. It’s production started in 1956 and immediately it became an icon of modern design. It was the first chair that the Eames couple designed for a luxury market. 1956 rosewood Eames Lounge Chair and Ottoman are in the permanent collection of the Museum of Modern Art in New York City. Apart from a few famous museums, it can also be seen in designer homes, television series and movies as part of stylish interiors.

Hierarchical data in SQL

Few year before, I came across a requirement where I needed to build a dynamic hierarchy for organization structure with employee and subordinate relationship. Based on the general idea, I initially thought of implementing it according to one-to-many relationship based on a foreign key. But, soon I realized that this approach is not going to work because the SLA to fetch the data from the database was very tight and this approach incorporated a lot of joins and doesn’t handle large and dynamic hierarchies very well. Then, I came to know about the concept of Nested Set approach which absolutely fit my requirement. Here, we will be discussing about both the approaches in details with their pros and cons.

Introduction

Most of the projects use Relational Databases to persist the data. And many times, they get a requirement where they need to store hierarchical data in the database. The most intuitive way of storing this kind of data is to have a one-to-many relationship within the same table. In this case, there will be a foreign key column which would be pointing to another row in the same table. But is this a very good approach?

Lets take an example of an E-commerce firm. This firm sells furnitures and wants to create a hierarchy of categories in order to represent different types of furnitures. Based on this requirement, the tree structure would consists of several top level categories where each category can contain one or more second level categories and so on. Following is a sample hierarchy of categories:

There are two approaches to handle this scenario.

1. Adjacency list
2. Nested set

Both of these approaches have pros and cons. Lets discuss about them in detail.

Saboteur

From the back of the box:

“You are dwarves digging for gold in the depths of a mine. Suddenly, a pick-axe breaks and the light from the lantern goes out. The saboteur has struck again – but which of your fellow players is a saboteur? Will you find the gold first, or will the saboteur ‘s sinister actions be successful? After three rounds, the player with the most gold nuggets wins the game!”

Introduction

Saboteur is a hidden identity card game by Frederic Moyersoen. In this game, players assume the role of dwarf miners who are trying to find the gold by digging tunnels. They support each other in order to create a path to the treasure and get rewarded with gold nuggets. Each dwarf carries a pick-axe, a lantern and a cart. Sounds too easy, eh?

On the way to the gold, while digging, sometimes bad things happen. When bad things start happening that means a Saboteur has entered the game. A saboteur is just like other dwarves (gold diggers) but his ultimate goal is to prevent other dwarves from reaching the gold. He tries to put a lot of obstacles into their path. He can break pick-axe, lantern or cart of another dwarf can simply divert the tunnel into a wrong direction, can try to mislead gold diggers in the wrong direction or can even create a strong mistrust among them. Due to this confusion, dwarves start blocking each other and sometimes they end up paralysing their fellow dwarf.

Now, with a saboteur in the game, gold diggers have to use their wits, observation and tools in hand to keep digging towards the gold and claim it.

Having a Saboteur in the game makes it very interesting. It becomes difficult to trust fellow dwarves. Each action of others starts to look suspicious. You’ll hear questions or accusations like, “Why are you going there?”, “Why have you broken my pick-axe?”, “He has blocked that way, he must be a Saboteur!” and on the other hand, replies will be like, “I am just trying to take us to the gold.”, “I am on your side.”, “Just trust me, I have no other choice”.

Spring context sharing between different modules in a web application

Let’s consider a scenario of a web application which contains multiple modules. Each module represents a different Spring context as each module works almost independent of other modules. With this model, the web application is working properly. So far so good.

Now, as per requirement, we need to implement another module which provides security related functionality which is required by each and every module. So, we go ahead and create a new module say “security” which has its own Spring context. Now, if we want to use services of this module into other modules, we either need to make an HTTP call to the exposed “security” services which is expensive or we need to specify beans of “security” module into context files of other modules too. But this can lead to a serious problem which is the creation of multiple instances of “security” beans, which is not acceptable.

So, we need a way to make these “security” beans, Singleton and make them available globally in the web application. In order to achieve that, Spring provides “Parent Context” feature. As per this feature, we can declare our beans inside parent context which will be available to all the modules declared under that web application at run-time.

Legalization of Prenatal Sex Determination

Finally a book has arrived which talks openly about this topic!!

Introduction

Prenatal sex determination is the prenatal testing for finding out the sex of a fetus before birth. Prenatal sex determination was banned in India in 1994, under the Pre-conception and Prenatal Diagnostic Techniques (Prohibition of Sex Selection) Act. The Act aims to prevent sex-selective abortions, which, according to the Indian Ministry of Health and Family Welfare, “has its roots in India’s long history of strong patriarchal influence in all spheres of life”, and will adversely effect the sex ratio.

The law requires all genetic clinics to register with the government to conduct prenatal diagnostic tests. These tests can only be used for detecting fetal abnormalities. This law makes it illegal for the Doctors to inform the women or her relatives of sex of the fetus. If they do so, they may be fined and put in jail upto 5 years. Parents who request sex determination services can also be fined and put in jail. Doctors in government hospitals already claim that they do not use sex determination practices and do not conduct abortions based on sex preference. Private clinics who practice sex determination tests and selective abortions do so clandestinely.

Dominion – A deck building game

From the back of the box:

“You are a monarch, like your parents before you, a ruler of a small pleasant kingdom of rivers and evergreens. Unlike your parents, however, you have hopes and dreams! You want a bigger and more pleasant kingdom, with more rivers and a wider variety of trees. You want a Dominion! In all directions lie fiefs, freeholds, and feodums. All are small bits of land, controlled by petty lords and verging on anarchy. You will bring civilization to these people, uniting them under your banner.

But wait! It must be something in the air; several other monarchs have had the exact same idea. You must race to get as much of the unclaimed land as possible, fending them off along the way. To do this you will hire minions, construct buildings, spruce up your castle, and fill the coffers of your treasury. Your parents wouldn’t be proud, but your grandparents, on your mother’s side, would be delighted.”

Introduction

Dominion is a deck building game created by Donald X. Vaccarino. This game brought the concept of building play deck during the game. This is considered to be a grand daddy for all the deck building games present now. This game has won many awards and is one of the most popular deck building games. It has a light medieval theme which is very well depicted by the theme of the cards and story behind the game.

This is a good gateway game for the players new to board gaming. Though the deck building concept, at first, can be very strange and bewildering, but once a new player will complete initial 4-5 turns, he/she will start to hang of the mechanics behind it. I have seen people losing this game very badly at first but by the next few games, they become very good at it.

In this game, players assume the role of monarch who wants to expand his/her kingdom. They start with a small treasure and a small kingdom. Each player’s goal is to expand his/her kingdom by hiring different workers, building various structures and finally acquiring territories which will give them victory points. A player with highest number of victory points wins the game.

The Settlers of Catan – A Board Game

This is my first board game review ever. I am starting with this game because I love playing it. It’s an easy but really good strategy game.

Introduction

The Settlers of Catan is a multiplayer strategy game which was designed by Klaus Teuber and it was first published in 1995 in Germany. This game has won many awards and is one of the most popular games due to its amazing ability to appeal to experienced gamers as well as those new to board gaming.

This game is easy to understand. All it takes is one round of complete gameplay to understand the mechanics behind it, which also makes it a very good gateway game to the players who are new to board games. It is also very interesting to play as it involves tons of interaction among the players.

In this game, players assume the role of settlers on an island of Catan. Each player’s goal is to build and expand his/her colony while acquiring and trading resources. Players get victory points as their settlements grow and first one to reach a certain number of victory points wins the game.