Analysis of a Multithreading Test Task for Senior Software Engineer at Global Bank

This is one of the most interesting Java test tasks I have encountered. It is not an abstract problem from a curriculum but rather a scenario that closely resembles real-life use cases. In this article, I'm going to analyze the task, provide a breakdown of the requirements, and justify my decisions. You can find a link to the source code at the end of the article.

Disclaimer

I received this task almost two years ago. The bank should have already changed the assignment; therefore, I believe it is fair to discuss this task openly.

Task Statement

Implementation of a test task with the following requirements:

You have to write a PriceThrottler class that will implement the following requirements:

1) Implement the PriceProcessor interface.

2) Distribute updates to its listeners, which are added through subscribe() and removed through unsubscribe().

3) Some subscribers are very fast (i.e., onPrice() for them will only take a microsecond), and some are very slow (onPrice() might take 30 minutes). Imagine that some subscribers might be showing a price on a screen, and some might be printing it on paper.

4) Some currency pairs (ccyPairs) change rates 100 times a second, and some only once or two times a day.

5) ONLY LAST PRICE for each ccyPair matters for subscribers. I.e., if a slow subscriber is not coping with updates for EURUSD, it is only important to deliver the latest rate.

6) It is important not to miss the rarely changing prices. I.e., it is important to deliver USDAED if it ticks once every several hours, but you may skip some EURUSD ticking every millisecond.

7) You don't know in advance which ccyPair are frequent and which are rare. Some might become more frequent at different times of the day.

8) You don't know in advance which of the subscribers are slow and which are fast.

9) Slow subscribers should not impact fast subscribers.

In short, the purpose of PriceThrottler is to solve slow consumers

The Statement Explained

The API

In the task, you are expected to implement an interface called PriceProcessor, which includes three methods: onPrice, subscribe, and unsubscribe. There is another interface that is not explicitly mentioned: the subscriber, which acts as a parameter of the subscribe and unsubscribe methods.

The onPrice method takes two parameters: a currency pair and the exchange price. The currency pair is represented as a string, such as EURUSD, which signifies the conversion from USD to EUR. In this case, the price reflects the value of EUR against the dollar, or, in other words, how many euros one can purchase for a single dollar.

We can begin by defining these interfaces. I've decided to rename the main interface to PriceDistributor, as it more accurately reflects its function of distributing the price updates to the subscribers. The PriceProcessor interface will be retained but will only include the onPrice method and will be used as the subscriber.

public interface PriceProcessor {
   void onPrice(String ccyPair, double rate);
}

public interface PriceDistributor {
   void onPrice(String ccyPair, double rate);
   void subscribe(PriceProcessor priceProcessor);
   void unsubscribe(PriceProcessor priceProcessor);
}

By defining the interfaces, we’ve wrapped up 1st and 2nd points of the statement.

Slow Consumers

The 3rd point states the problem of slow consumers; the example is pretty self-explanatory. But in combination with the 8th and 9th points, it states additionally that execution by the consumers should be separated into different threads. And as soon as we can’t determine whether a particular consumer is fast or slow, we need to execute each consumer in a separate thread. One can come up with some optimizations, but it’s premature at this point.

The simplest way to implement such a solution is to create a queue with a handler in a separate thread.

We need broadcast distribution. From the top of my head, there are two ways to implement it: 

1. A single array for all subscribers, with each subscriber having its own offset.
2. Each subscriber has its own queue.

There is no need to make a decision so far. We’ll most probably have the answer when all the points are checked.

Dropping Outdated Price

We need to keep in mind that there can be a consumer, which is slower than a producer. It means that the queue will always be growing. In general, the only way to keep the queue size under control is to drop the items.

You need to determine the existence of this problem and try to avoid uncontrollable queue growth, even when there is no business justification for dropping items. But the authors of this task have already solved this problem for you. Point 5 of the statement tells us at which point we can start dropping the queued updates.

We can drop duplicate currency pairs. Wikipedia says that there are 130 independent currencies in the world, so the physical maximum of unique pairs is (130 - 1) * 130 / 2 = 8385 (formula). Despite the fact that, in reality, the number of currency pairs is way smaller, we need to achieve O(1) time complexity for adding a price update and pulling the next element with the most up-to-date price from the queue.

Implementing the Price Updates Queue

We need to drop the old price. But how exactly? Let's discuss the implementation because it's the most crucial part of the task.

Removal of old items from the queue and pushing the latest update to the end of the queue is not an option because the most frequently updated pairs may never be processed.

We can make a mutable state of the queued item and update it, but it’s quite inefficient as it requires iteration over the queue, which is supposed to be thread-safe and high-throughput, so it's not an option either.

Would LinkedHashMap Work?

One of the possible solutions could be LinkedHashMap, because (docs):

Note that insertion order is not affected if a key is re-inserted into the map.

So if a pair exists in the map, the next map.put(existingCcPair, newPrice) will update the price and keep the order of the previously inserted pairs. So you could get the head entry, take its key, and get the value using map.remove(key). The only problem with LinkedHashMap is that it’s not thread-safe. You can’t get the head element without calling iterator().next(), which will cause a ConcurrentModificationException if there is an update between iterator() and next().

Yes, we can use synchronized blocks; so did I at first, but then I came up with a little nicer way.

A Solution With BlockingQueue

We can use BlockingQueue to keep the updates ordered and have the most recent price in HashMap. HashMap has constant time access to check if a pair is already there, so we can queue the pair only if it’s not in the HashMap. Synchronized blocks are still required to avoid the test-and-set problem, but now we have handy features of, for instance, the blocking method BlockingQueue#take, which is very convenient when you need to wait for something to appear in the queue and don't want to implement the synchronization yourself.

So we have just chosen option two: each subscriber has its own queue. And we can finally check all the points of the task.

Implicit Requirements

We’ve done with the list, but is it all we need to care about?

In the previous section, we decided to have a queue and price map for each consumer. The number of currencies is finite, so we don’t need to worry about the queue size. But what if there are millions of consumers? Will the solution work for it? Most likely not, but it actually depends on the hardware capacity.

One of the most crucial things on a production server is capacity planning. You also need to keep the utilization within the boundaries; therefore, we need to define the maximum number of subscribers and reject new subscriptions if the limit is reached.

Conclusion

We thoroughly examined and analyzed the task, breaking it down into functional requirements, and chose implementation considering non-functional requirements. We defined the API and extensively discussed the most crucial aspect of the implementation. There is no universally perfect solution, and in some cases, the solution may even be considered excessive. But it demonstrates your capabilities within the context of the test task.

The source code of the implementation is available on GitHub: https://github.com/timurnav/price-throttler