Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

Channels ▼


Tough Apps: How Much Hardware Should I Buy?

Dennis Shasha is a professor of Computer Science at New York University. His latest puzzle book Puzzles for Programmers and Pros outlined some general approaches to programmatic puzzle solving. This column challenges you to find the solutions to the puzzles that lie at the core of some cool tough applications. He solicits your help in identifying such cool apps.

Long-time Dr. Dobb's readers may remember "Dr. Ecco's Omniheurist Corner" where Professor Dennis Shasha posed puzzles that required computer solutions. Dennis is returning to Dr. Dobb's, but with a new twist on puzzles. The idea is to take inspiration from the challenging apps that readers have faced and to turn those into puzzles.

If you have written an application that required extensive use of heuristics (because no algorithm would solve it) or that is otherwise algorithmically interesting, please send mail to Dennis at [email protected]. Put "Tough Apps" in the subject line. If Dennis likes it, he will contact you. Then he will try to understand what you've done and create a puzzle explaining the algorithmic core. You will write a little blurb about yourself and the problem if you want.

You work for a successful Internet site. You have severe response-time constraints because users will bolt if they have to wait more than three seconds for a response. Your data is partitionable, so every time-critical task can be processed at any one of many servers.

Your system supports four tasks: search for item, specify properties of the item (e.g. color and size), add to cart, and buy. Each task except buy should be processed within three seconds. The buy transaction depends on external credit card validation, so may take longer. Therefore, we focus on the first three.

Each task has a certain service time and task x may lead to task y based on "transition probabilities" (the likelihood for a given searcher to go from task x to task y). There is also the ever-present probability that the searcher will leave the site altogether. These transition probabilities allow us to compute the number of requests at a given task given an initial traffic rate into the search task.

Figure 1 shows the transition probabilities.

[Click image to view at full size]
Figure 1

 T_search_to_specify = 0.2
 T_search_to_search = 0.4
 T_specify_to_search = 0.2
 T_specify_to_specify = 0.3
 T_specify_to_add = 0.1
 T_add_to_search = 0.6

Next, we compute the net traffic to each task node given that traffic from new visitors comes to the "search" node at a rate T (visits/second).

searchtraffic = T + (0.4 * searchtraffic) + (0.2 * specifytraffic) + (0.6 * addtraffic) 

Let's see if we can reason this out. 40% of the total traffic into search come back to do a new search (the self-loop). The other terms can be explained similarly based on other edges (e.g. 20% of those who start specifying an item come back to search). Now we'll find the net arrival rate into the other tasks.

specifytraffic = (0.2 * searchtraffic) + (0.3 * specifytraffic)
addtraffic = (0.1 * specifytraffic)

Now you have three equations in three unknowns. You know how to solve that.

But we're not done. We need to compute the demand into the tasks. Suppose now that the service time at each task is 100 milliseconds on a single server. If T is say 10,000 requests per second, then we want to determine how many servers we need.

To do this we first turn to queueing theory, which tells us that for a single server having a task arrival rate A and a service time S, the utilization U=A*S. This makes sense because if A tasks come in at the beginning of each second, then they will require A*S time to complete. Thus, the utilization is the fraction (hopefully less than 1 or the queue will grow over time) of a second required to process those A tasks. Queueing theory tells us that the response time R in this case is R=S/(1-U) when U<1.

Suppose however some task receives 5,000 requests per second. Then the utilization of a single server will be 5,000*0.1=500, way too high for a single server. So, how would we figure out how many servers we need if we want R<3 seconds. Well just solve for U in the equation 3=0.1/(1-U). 3-3U=0.1 or 2.9/3=U. If we set the maximum utilization to 2.9/3 at each server, then we can handle an arrival rate at each server to 9, because 9*0.1<2.9/3. So, we could safely have 5,000/9 servers.

Ok, now it's your turn. Given that T is 10,000 requests per second, how many servers do we need for the search, specify, and add tasks assuming a service time of 0.1 seconds per task.

Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.