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.
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.