Taking the Pith Out of Performance

Throughput-Delay Curves

2012-01-22T11:58:00.000-08:00

My colleague Bob Lane at Yahoo.com asked me if I'd ever seen curves like this:

Not only is the answer, yes (it's a throughput-delay plot or XR plot in my notation), but that particular plot comes from my GCaP course notes. There, I use it to analyze the comparative performance of a functional multiprocessor (NS6000) and a symmetric multiprocessor (SC2000). Note how the two curves cross at around 1500 OPS. You can ask yourself why and if you can't come up with an explanation, you should be registering for a Guerrilla class. :)

The above XR plot also serves as a useful reminder that the throughput and response-time metrics are not only dependent on one another, but they are generally dependent in a nonlinear way—despite what some experts may claim:
From xxxx@cisco.com Mon, 16 Sep 2002 08:04:04 +1000 ...in reality, Latency & Throughput are two completely different metrics associated with performance. Latency isn't related to Throughput and vice-versa. ...

What is truly alarming, however, is that I am unable to find this example in any of my books; after a quick and non-exhaustive search. I would have expected it was discussed in The Practical Performance Analyst (since the example is of that vintage), but I don't see it. If you happen to spot it or know which book chapter it is in, please let me know.

Since the throughput-delay product is merely a statement of Little's law, N = X*R, you can use it to trivially calculate the number of thingies (N) at any point on the XR plot. Then, you can plot say, throughput as a function of N, i.e., X = X(N), which you weren't given in the original visual representation. For the above example, N is the number of client generators impressing load on the test rig:

Now you can see clearly that the SC2000 throughput has reached a saturation value of about 2500 OPS by 100 generators. So, there would be no virtue in driving the NFS system with more load generators (even if there is NIC bandwidth available) because the response time will be begin to climb embarrassingly.

Although the above example is dated in terms of the technology, it is timeless in terms of its instruction. With that in mind, you can review more modern XR plots on the SPEC.org website where the current NFS benchmark is called SFS2008. Here are some SPEC throughput-delay plots from 2011:

Packet pushers also regard the bandwidth-delay product as very important because it:

"determines the amount of data that can be in transit in the network"
[is a] "very important concept in a window-based protocol such as TCP, as throughput is bound by" [it]
can be conveniently calculated for TCP packets

Cautionary note: Be careful to distinguish between the (band)width of the network pipe, i.e., X_max, vs. the number of packets per second, i.e., X, being pushed through that pipe.

My Year in Review 2011

2012-01-01T00:13:00.000-08:00

Some days I wonder if I ever actually accomplish anything anymore. Maybe it's time to just pack it in and become a greeter at Walmart. I know a bit about how queues work, so that should put me a few notches ahead of the competition. And I would expect the competition to be fierce because it's a pretty cushy job; but not every day, apparently.

Before taking the big leap, I decided it might be a good idea to note down some of the technical projects I've worked on this year (over and above the daily grind):

Finished editing the manuscript for the 2nd edition of the Perl::PDQ book, which was published in August.
Finalized the invited chapter A Methodology for Optimizing Multithreaded System Scalability on Multicores (co-authored with Shanti Subramanyam and Stefan Parvu) for the edited volume: Programming Multi-core and Many-core Computing Systems (Wiley-Blackwell).
Sommerfeld-Dirac Paradox: In 1916, Arnold Sommerfeld calculated the relativistic corrections to the Bohr atom and found that the associated perihelion precession produced the known fine structure of the hydrogen spectrum. Remarkably, this is the same result as discovered by Dirac more than a decade later in 1928. The paradox is that the Sommerfeld model does not involve electron (fermionic) spin, whereas spin is intimately involved with the Dirac solution. I originally heard about this paradox from my Masters thesis advisor, Prof. Christie Eliezer, who had been one of Dirac's research students. Recently, it has been suggested that the paradox arises from a fortuitous ambiguity in the way certain of the quantum numbers are defined. If this is so, I believe there ought to be a topological proof. I've got the Lie group algebras down, but it's still a work in progress.
My ongoing effort to provide a simple pictorial derivation of the Erlang M/M/m queue has been simplified even further. In case there's any doubt, here's the proof on my whiteboard dated April 13, 2011. :)

I still need to write this up coherently.
Steve Jenkin asked me why the electrical power consumed by a magnetic disk increases as the fifth power of the platter radius. I didn't know it did! So, I decided to see if I could derive the physics from first principles. I was able to do so, but I've yet to find the time to blog about the details. The main point is that the consumed electrical power (Watts) grows as the 5th power of the disk diameter and the 3rd power of the angular speed (RPM). Since these are very fast functions, this relationship is an important result for green datacenter design.
Together with my colleagues at HP Labs, I've been working on a mathematical model of color naming. If you find yourself having trouble even parsing that sentence, now you know how I felt when I was introduced to this subject. Neuroscientists speculate that the left side of the brain, which deals with language, is also involved in processing colors in the right visual field. More colorful background information can be found on the XKCD blog. This is also a work in progress and I can't say more about our results until they are finally published. I can report, however, that quite unexpectedly, it's turned out to be one of the most exiting pieces of science that I've worked on in a long time.
In response to having been challenged both publicly (without any supporting data) and privately (with supporting data that I can't reveal publicly) over the need to model so-called superlinear scaling, I've developed a theorem that states such superlinear modifications to the Universal Scalability Law are unnecessary. More on this later.
I believe I can construct a theorem, which says something like this: The system performance of any computer system, no matter how big or distributed, can always be modeled with just a surprisingly few queueing nodes. How can this be? If you look carefully in my PPDQ book, you'll notice that most (if not all) of the models are relatively simple. Although I've observed this effect many times, over many years, I never put much stock in it. As of March this year, that suddenly changed. I now believe I know why it always works out that way, in general. There will, of course, be some exceptions because you can always add more detail. This theorem also means that it will finally be possible to automatically build your PDQ model directly from collected performance data.
Designed and road-tested the new GDAT training course.
Fixed "string" variables (there are no strings in C) in the PDQ library that were causing the R Console to crash. Still have to export the fix to SourceForge.
Constructed multiple optimization functions for an M/M/m queue to demonstrate that there is no unique way to define optimal load points (ρ*) or "knees" (a misnomer) for response time curves.

For example, for any configuration of m-servers in the above table, which of the functions Y1, Y2 or Y3 represents the correct optimal load (ρ* values in each row)?
Wrote this blog post. OK, that doesn't count but an odd-numbered list might be unlucky in an even year. :P

Since several of these projects are still in a rather untidy state, I probably should spend a bit more time polishing them up before sauntering down to the Walmart employment office. In the meantime,

Happy New Year!

A List of CaP Skills

2011-12-27T12:04:00.000-08:00

This question popped up recently on Linkedin:

"Can someone tell me what skill set should a Performance and Capacity Analyst have and develop throughout his career?"

and I realized that, although I have a kind of list in my head, and I talk about such skills in my classes, I have been too lazy to write them down anywhere; which is pretty dumb. I must try to do something about that (New Year resolution? What are the odds?). In some ways, my fallback is the online Guerrilla Manual. Anyway, here is my (slightly edited) response to the LI question, and let it therefore constitute my first attempt at writing down such a list.

Unlike the usual set of computer-based skills needed for programming or app dev or kernel dev or being a network engineer or a sysadm, CaP (Capacity planning and Performance analysis) is more like a physical science, in my view.
It all starts and ends with the data.

Physical sciences involve such skills as:

Collection and observation of raw data
Controlled experiments in the lab to find clearer relationships in the data
Use of tools to create and analyze data
Development of models to both explain data and predict effects
Publishing/marketing results and budgeting for experimental equipment
Scientists usually don't like to acknowledge (5). "Marketing" is a dirty word, but they do it anyway. :)
It's all marketing!
I'm also including the biological sciences here; the main difference being that bio systems can up and die on you when testing. Rebooting is not an option, and that can really ruin your data.
Translating the above skills list for CaP:

Collection of raw data using monitoring tools
Load testing simulations to determine stimulus-response relationships
Use of Excel, R, visualization, etc., to analyze data
Development of models to both explain and predict
Marketing/publishing your analysis and knowing the financial ramifications
To make each of these skills manifest requires:

understanding the relevant technologies
understanding of good deal of math and statistics (without being a mathematician)
being able to communicate technical concepts to mere mortals (e.g., the CEO)
ability to perform diagnostic experiments
being a generalist vs. a specialist (Get your face out of the bit bucket)
ability to spot patterns and analogies (e.g., UNIX load average acts like an RC electric circuit)
paying attention to the right details (Put that kitchen sink down!)
cross-checking your conclusions (e.g., Therefore: lightweight heavy processes sleep furiously)
constantly watching market trends (to avoid being run over by the technology train)
It's also important to have a clear and unambiguous understanding of performance metrics. But even more important than that, is understanding the relationships between those metrics. Those relationships are typically nonlinear and that's what makes CaP both hard and interesting. And that's what makes all the above skills not only important but vital.
We are data scientists too!
The nonlinear relationships are often best expressed using queue-theoretic paradigms because all complex computer systems can be represented as a network (or circuit) of buffers (queues). QED
The good news here is, you will not be replaced by software or a computer any time soon.
Watson won Jeopardy. Pfft! Big deal.

Models, e.g., queueing models, are not only useful for prediction (the usage most people think of), but they are often more useful for explaining data.
A good model is better than a crystal ball (which is just a piece of glass).
Beyond the technical skills, CaP also requires connecting it all up with financial constraints/budgets in purchasing/procurement cycles, etc. That aspect varies enormously depending on the type of business and its operational requirements.

What did I miss? Comments, corrections, additions, refinements: all welcome.

Season's Greetings 2011

2011-12-19T19:08:00.000-08:00

Best wishes to all my blog readers and Guerrilla class alumni during this 2011 holiday season. I look forward to more of the same next year.

Image: The winter lights of Silicon Valley, California, from Mt. Hamilton webcam courtesy of UC Regents and Lick Observatory.

Webinar: Load Testing Meets Data Analytics

2011-10-24T10:38:00.000-07:00

This Thursday, October 27 at 10 am PDT^*, I'll be participating in a webinar sponsored by SOASTA, Inc. They make a new breed of load-testing product called CloudTest® which, despite its name, is not restricted to load testing cloud-based apps, although it can do that too.

CloudTest facilitates load testing any web-based apps currently being deployed in your data center, at scale, in less time. The "at scale" part refers to the fact that thousands of user-loads can be provisioned dynamically via cloud-based servers, and the "less time" part refers to constructing test scenarios more rapidly than can be achieved with conventional scripting. Therefore, test coverage can approach 100%, which also means a lot of test data might be generated. The potential data torrent caused by such a high degree of coverage necessitates being able to transform all that data into information, thereby exposing performance and scalability issues. Enter CloudTest data visualization and real-time analytics.

In that vein, I'll be presenting three case studies where better test-data analytics would have been very useful:

CASE STUDY: Unseen Error Rates. The inability to visualize RDBMS transaction errors in the SUT meant that the reported throughput data were overly optimistic because they were actually comprised of 70% committed transactions + 30% errors due to failed transactions. None of the performance test engineers were aware of this problem during 18 months of testing (until I pointed it out—over the phone!). Real-time analytics could have avoided a lot of useless testing.
CASE STUDY: Local vs. Global Test Data. Like ships passing in the night, QA and WebOps, being in different organizations, never talked to each other so there was no awareness of the glaring discrepancy between user-latency data (measured by services like Keynote and Gomez) and load-testing SLA targets (measured with LoadRunner, JMeter, etc.) for apps development. CloudTest incorporates both.
CASE STUDY: More Testing is Better. The early releases of memcached were thread-limited, which meant it would still scale out but not scale up on next gen multicore servers; a situation that would be tantamount to considerable wasted capacity—defeating the purpose of cheap K-V caching^†. The ability for CloudTest to resample data via more tests in the same time ensures more accurate statistical analysis. I'll demonstrate how the USL nonlinear regression model can be applied to predicting improved scalability using the memcached load tests.

Because data and information are not the same thing, these examples will also show you how to transform your current test data into more useful information.

* This webinar was recorded. Also check out the online Q&A section.
† See N. Gunther, S. Subramanyam and S. Parvu, "Hidden Scalability Gotchas in Memcached and Friends," Velocity conference 2010.

Kanban Revived in an Agile Kind of Way

2011-10-20T20:32:00.000-07:00

I just returned from a workshop on the latest in web technologies (invitation only) where I was surprised to hear reference made to kanban. Kanban is a card-based system originally developed by Toyota in the 1950s for controlling their manufacturing lines. I have a note about it in the "Brief History of Buffers" section of my Perl::PDQ book because it is a logical precursor to JIT scheduling and compiling. I will also discuss it in the up-coming Guerrilla classes.

Now, it seems kanban has been revived under the "agile" banner for making software development more efficient. Of course, the concept of using cards to capture dev state information is not entirely new, even in the context of software engineering. So-called Snow Cards are another card-based technique used to monitor the software development process.

Visual Illusions: Google vs Facebook vs Yahoo

2011-10-03T00:00:00.000-07:00

The ability to visualize data, enabled by the advent of graphical computer tools, has been a great boon to Cap and Perf. The power derives from the way graphical displays provide an efficient impedance match to the visual system in our brain. The weakness derives from the way graphical displays provide an efficient impedance match to the visual system in our brain. We can get carried away by visual representations alone. Every marketing organization exploits that weakness. Numbers do have poor cognitive impedance, but that doesn't mean numbers should ignored altogether. In fact, we often need a combination of both numerical and visual data representations so that we don't suffer visual miscues and thus jump to the wrong conclusion. The following presents an example of how easily this can happen.

Recently, Guerrilla alumnus, Scott J. pointed me at this Chart of the Day showing how Google revenue growth was outpacing both Facebook and Yahoo, when compared 7 years after launching the respective companies.

Clearly, this chart is intended to be an attention getter for the Silicon Alley Insider website but, it looks about right and normally I might have just accepted the claim without giving it anymore thought. The notion that Google growth is dominating, is also consistent with a lot of other things one sees. No surprises there.

Exponential doubling period

In this particular case, however, I was struck by the shape of the data and curious to find out if the growth of GOOG and FB revenue follows an exponential trend or not. Exponential growth is not unexpected because it's the continuous analog of compound interest. If they are growing exponentially, I can compare their doubling periods numerically and determine by how their growth will look in the future.

The doubling period is an analysis technique that I use in Chapter 8 of my Guerrilla Capacity Planning book to determine the traffic growth of major websites. In section 8.7.5 the doubling time t₂ is defined as:

t₂ = Ln(2) / A

where A is the growth parameter of the fitted exponential curve (the rate at which it bends upward) and Ln(2) is the natural logarithm of 2 (2 for doubling). The only fly in the ointment is that I don't have the actual numeric values used in the histogram chart, but that need not be a showstopper. There are only a half dozen data points for each company, so I can estimate them visually. Then, I can use R to fit the exponential models and calculate the respective doubling times.

Analysis in R

First, we read the data (as eyeballed from the online chart) into R. Since the amount of data is small, I simply use the textConnection trick to write the data in situ, rather than using an external file.


gd <- read.table(textConnection("Year GOOG FB\tYAH
1 0.001 0.002 0.001
2 0.01 0.02 0.01
3 0.1 0.2 0.1
4 0.5 0.45 0.3
5 1.5 0.75 0.6
6 3.2 2.0 1.1
7 6.1 4.0 0.75"), 
header=TRUE,sep="\t")
closeAllConnections()

I can now plot those estimated data points and compare them with the original chart.


plot(gd$Year,gd$GOOG,type="b",col="green",lwd=2,lty="dashed",
main="Annual revenues for GOOG (green), FB (blue), YAH (red)",
xlab="Years after launch", ylab="$ billions")
points(gd$Year,gd$FB,type="b",col="blue",lwd=2,lty="dashed")
points(gd$Year,gd$YAH,type="b",col="red",lwd=2,lty="dashed")

The result looks like this:

The dashed lines simply connect related points together. The two solid lines are produced by performing the corresponding exponential fits to the GOOG and FB data.


# x-values for continuous exp curves
x<-seq(from=1, to=7, by=0.1)

ggfit<-nls(gd$GOOG ~ g0*exp(g1*gd$Year),data=gd,start=list(g0=1,g1=1))
gc<-coef(ggfit)
lines(x,y=gc[1]*exp(gc[2]*x))

fbfit<-nls(gd$FB ~ f0*exp(f1*gd$Year),data=gd,start=list(f0=1,f1=1))
fc<-coef(fbfit)
lines(x,y=fc[1]*exp(fc[2]*x))

# report the doubling periods
text(1,5.0,sprintf("%2s doubling time: %4.2f months", names(gd)[2],12*log(2)/gc[2]),adj=c(0,0))
text(1,4.5,sprintf("%2s doubling time: %4.2f months", names(gd)[3],12*log(2)/fc[2]),adj=c(0,0))

From the R analysis we see that the doubling period for Google (t₂ = 11.39 months) is slightly longer than that for Facebook (t₂ = 10.94 months). Despite the banner claim made by Silicon Alley Insider, based on these estimated data, Google is growing revenue at a slightly slower rate than Facebook. How can that be?

Conclusion

In the original histogram chart, it looks like Google is growing faster than Facebook. Well, looks can be deceiving. Your brain can be fooled (easily) by optical illusions. That's why we need to do analysis in the first place. Viewed uncritically, your brain can easily be led astray.

To resolve this paradox, let's do two things:

Project the growth models out further than the 7 years associated with the data
Plot the projected curves on log-linear axes (for reasons that will become clear shortly)

Here's the result (you might want to click on the image to magnify it).

The left-hand plot shows that the two curves cross somewhere between 7 years out and 40 years out. Whereas green (Google) is currently on top, according to the data, blue (Facebook) eventually ends up on top according to the exponential models; assuming nothing else changes in the future. The right-hand plot uses a log-scaled y-axis to reveal more clearly that the crossover occurs at t = 23.9 years. Once again, if you rely purely on visuals, you might think the crossover doesn't occur until after 30 years (what looks like a "knee" in the left-hand plot), but you'd be misled. It occurs almost 10 years earlier.

If, for example, you were only interested in short-term gains (as Wall St is wont to do), the original visual (histogram) is correct. If, on the other hand, you are in your 20s and investing longer term, e.g., for your retirement, you might get a surprise.

By now, you might be thinking that these projections are not very accurate, and I wouldn't completely disagree with you. But what is accurate here? The original data in the histogram (even the really real actual data) probably aren't very accurate either; we really can't know without deeper investigation. And that's my point: independent of the accuracy of the data, the numerical analysis can cause you to pay attention to, and possibly ask questions about, something you might otherwise have taken for granted on purely visual grounds.

Even wrong expectations are better than no expectations

I'm a big fan of data visualization, but not to the exclusion of numerical analysis. We need both and we need both to be easily accessible.

The art is in the science

Plan for GCaP in November

2011-09-12T11:39:00.000-07:00

Seats are still available for the final Guerrilla Boot Camp (GBoot) and Guerrilla Capacity Planning (GCaP) classes for 2011 at the Early Bird rate. Before registering, you can review the highlights of the May GCaP class. If you came to the August GDAT class, but missed the May classes, this is your chance to complete the set.

As usual, it will be held at our lovely Larkspur Landing location. Click on the image for booking information.

Attendees should bring their laptops, as course materials are provided on CD or flash drive. The venue also offers free wi-fi to the internet.

How Much Wayback for CaP?

2011-09-06T20:59:00.000-07:00

How much data do you need to retain for meaningful capacity planning and performance analysis purposes? Sounds like one of those "how long is a piece of string?" questions and I've never really thought about it in any formal way, but it occurred to me that 5 years is not an unreasonable archival period.

Mister Peabody and Sherman in front of the WABAC machine
My reasoning goes like this:

To make statistically meaningful estimates for models like linear least squares, you need at minimum about half a dozen data points. This is the kind of rule of thumb (RoT) I developed for USL scalability modeling to be meaningful.

Now consider that same RoT from another standpoint. If you are Amazon.com, for example, and you want to estimate your Christmas growth trend, then you need about half a dozen data points. That means 5 or 6 years of data.

That time scale for a historical data repository certainly distinguishes CaP from simple performance monitoring (no storage) and performance analysis (short-term history) where you are looking for diagnostic patterns rather than trends.
How much data is kept during those 5 yrs is a secondary, sampling question. As surely as you throw away arbitrary periods of data those will become the periods you will need at some later time for CaP purposes. In fact, it's probably more work to selectively remove certain data periods than it is to automatically keep the lot. But keeping everything might be overkill. That's typically where data aggregation comes in. The further back in time you go, the less likely you will need events with fine time-granularity.

With this RoT in mind, I decided to google the topic but discovered there is very little that is relevant to CaP since most commentators are typically considering data storage for applications (e.g., an RDMS), not historical data for CaP analysis. FWIW, here's what I found during a relatively quick review:

SMB planning mentions 5 years without any justification

"knowing what your business is doing...in an 18-month time frame, to a three-year time frame, to a five-year time frame. You really need to plan out that far, but if you do, it's fantastic. If you have a five-year plan, it will trickle down more easily into getting your hands around capacity and growth."
Oracle example of 6 weeks

"Suppose, for example, you always want to be able to view hour data for the previous six weeks. ..."
IBM up to 2 months before aggregating ("pruning")

"Capacity planning and predictive alerting: For capacity planning and predictive analytics, you typically perform long term trend analysis. The Performance Analyzer, for example, uses Daily summarization data for the predefined analytic functions. So, in most cases, configure daily summarization. You can define your own analytic functions and use Hourly or Weekly summarization data."

"For the analytic functions to perform well, ensure that you have an appropriate number of data points in the summarized table. If there are too few, the statistical analysis will not be very accurate. You will probably want at least 25 to 50 data points. To achieve 50 data points using Daily summarization, you must keep the data for 50 days before pruning. More data points will make the statistical predictions more accurate, but will affect the performance of your reporting and statistical analysis. Consider having no more than a few hundred data points per resource being evaluated. If you use Hourly summarization, you get 336 data points every 2 weeks."

"Adaptive monitoring (dynamic thresholding): Keep 7 to 30 days of detailed data when comparing all work days. If you compare Monday to Monday, then you need to keep the Detailed data much longer to be able to establish a trend. When comparing a specific day of the week, you will
probably need to have at least 60 days of data.
RRDtool example 2 years for consolidation decisions.

"if now is March 1st, 2009, do you want to look at 2007-03-01 until 2009-03-01 or
do you want to be able to look at 2007-03-01 midnight to next midnight."

"What you need to understand here is consolidation. Say that you will be looking at two years worth of information, and that the available data is in a resolution of 300 seconds per bucket. This means you have more than 200,000 buckets."

"Example: Say you want to be able to display the last 2 years, the last 2 months, the last 2 weeks and the last 2 days. The database uses the default step size of 300
seconds per interval."

Ultimately, I'd like to turn my 5-year RoT into a Guerrilla Mantra. Send me your thoughts and comments to help me get there.

Subjugation to the Sigmas

2011-08-23T00:00:00.000-07:00

No doubt you've heard about the tyranny of the 9s in reference to computer system availability. You're probably also familiar with the phrase six sigma, either in the context of manufacturing process quality control or the improvement of business processes. As we discovered in the recent Guerrilla Data Analysis Techniques class, the two concepts are related.

Nines	Percent	Downtime/Year	σ Level
4	99.99%	52.596 minutes	4σ
5	99.999%	5.2596 minutes	-
6	99.9999%	31.5576 seconds	5σ
7	99.99999%	3.15576 seconds	-
8	99.999999%	315.6 milliseconds	6σ

In this way, people like to talk about achieving "5 nines" availability or a "six sigma" quality level. These phrases are often bandied about without appreciating:

that nines and sigmas refer to similar criteria.
that high nines and high sigmas are very difficult to achieve consistently.

See the appended Comments below for more details and examples.

To arrive at the 3rd column of numbers in the table, you can use the following R function to find out how much shorter downtime per year each additional 9 imposes. Hence, the term tyranny.


downt <- function(nines,tunit=c('s','m','h')) {
	ds <- 10^(-nines) * 365.25*24*60*60
	if(tunit == 's') { ts <- 1; tu <- "seconds" }
	if(tunit == 'm') { ts <- 60; tu <- "minutes" }
	if(tunit == 'h') { ts <- 3600; tu <- "hours" }
	return(sprintf("Downtime per year at %d nines: %g %s", nines, ds/ts,tu))
}

> downt(5,'m')
[1] "Downtime per year at 5 nines: 5.2596 minutes"
> downt(8,'s')
[1] "Downtime per year at 8 nines: 0.315576 seconds"

The associated σ levels correspond to the area under the Normal (Gaussian) or "bell shaped" curve within that 2σ interval centered on the mean (μ). The σ refers to the standard deviation in the usual way.

The corresponding area under the Normal curve can be calculated using the following R function:


library(NORMT3)
sigp <- function(sigma) {
	sigma <- as.integer(sigma)
	apc <- erf(sigma/sqrt(2))
	return(sprintf("%d-sigma bell area: %10.8f%%; Prob(chance): %e", sigma, apc*100, 1-apc))
}

> sigp(2)
[1] "2-sigma bell area: 95.44997361%; Prob(chance): 4.550026e-02"
> sigp(5)
[1] "5-sigma bell area: 99.99994267%; Prob(chance): 5.733031e-07"

So, 5σ corresponds to slightly more than 99.9999% of the area under in the bell curve; the total area being 100%. It also corresponds closely to six 9s availability. The 2nd number computed by sigp is the probability that the achieved availability was a fluke. A reasonable mnemonic for some of these values is:

3σ corresponds roughly to a probability of 1 in 1,000 that four 9s availability occurred by chance.
5σ is roughly a 1 in a million chance, which is like flipping a fair coin and getting 20 heads in a row.
6σ is roughly a 1 in a billion chance that it was a fluke.

Now you see why these goals are easy to covet but hard to achieve.

IBM Introduces the Cognitive Chip

2011-08-17T22:23:00.000-07:00

Last week, in the GDAT class, we were discussing performance visualization tools as requiring a good impedance match between the digital computer under analysis and the cognitive computer of the analyst—AKA the brain.

This week, IBM will announce its first generation cognitive computing chip that they claim mimics the human brain. It is the result of Phase 2 of a grant for DARPA's Systems of Neuromorphic Adaptive Plastic Scalable Electronics (SyNAPSE) project awarded more than 3 years ago to half a dozen IBM labs and 5 major universities.

According to IBM, "BlueMatter, a new algorithm created by IBM researchers in collaboration with Stanford University, exploits the Blue Gene supercomputing architecture in order to noninvasively measure and map the connections between all cortical and sub-cortical locations within the human brain using magnetic resonance diffusion weighted imaging. Mapping the wiring diagram of the brain is crucial to untangling its vast communication network and understanding how it represents and processes information." [Source: CNET]

These so-called cognitive chips have two prototypes that are currently being tested. The semiconductors were created out of standard technology in IBM’s VLSI fab plants. Both cores were fabricated using a 45 nm process and feature 256 neurons. One core contains 262,144 programmable synapses—a social network on a chip, as ZDNet's Larry Dignan describes it—and 65,536 learning synapses. IBM has demonstrated navigation, machine vision, pattern recognition, associative memory and classification with these chips.

So, what does it do for you? Here, IBM hedges somewhat. It wants you to think of it as complementary to conventional von Neumann digital processors. Taken together both types of chips could be used to correlate data, create hypotheses and remember state in a broader sense than a RAM chip. The combinaton of these two types of chips would be a cognitive computer.

No word on GA or price.

GDAT 2011 in Review

2011-08-13T09:34:00.000-07:00

As usual, the Guerrilla Data Analysis Techniques (GDAT) class was a total blast. Motivated students always guarantee that. It would really help our scheduling, however, if people didn't wait until the last nanosecond to register for the class. But given the crazy economic climate, I'm more than happy to do whatever it takes to make GDAT fly.

Guerrillas in the data mist [Photo: P. Newsom]

Some course highlights that you missed:

How to apply PCA tools in R to performance data
An introduction to power-law data modeling. Case studies included: network packet traces, detecting disaster recovery onset, Oracle SQL query-time distributions.
How to use heatmaps and treemaps in R to visualize the performance and capacity of kilo-servers in your data center
The use of animation and video for performance visualization tools
How to apply Machine Learning tools in R to cubic light-years of performance data
How to debug your R scripts
Jim Holtman may have helped me to resolve a bug in PDQ-R that causes the R Console to crash. If so, PDQ-R could soon be ready for CRAN time.

We also had a couple of excellent class dinners. Almost like old times. Maybe we aren't heading for GFC-2 or that "double-dip" recession. :)

Q-Q Plots for Multi-modal Performance Data

2011-08-03T21:30:00.000-07:00

I'm in the process of putting together some slides on how to apply Quantile-Quantile plots to performance data. Q-Q plots are a handy tool for visually inspecting how well your data matches a known probability distribution (prob dsn). If the match is good, the data should line up more or less diagonally in the Q-Q plot. A common usage is to verify normality, i.e. how well the data matches a Normal or Gaussian dsn. In fact, this usage is so common that R even has a separate function called qqnorm() for doing just that.

That's all textbook stuff, so I was wondering if anyone had tried it on computer performance data, e.g., response times. No sooner had I fired up the Google tab than blow me down if I don't see a blog post entitled "Q-Q plots to examine SQL execution time distributions". Not only that, but it's written by my colleague from the Hotsos Symposium, Dave Abercrombie—who has also been beavering away at applying my USL model to Oracle performance data. I recommend you take a look at Dave's post because he has tried to apply Q-Q plots to some tricky SQL performance data that looks benign when plotted as a histogram, but is actually very difficult to tame. This is demonstrated when Dave's attempts to model the underlying prob dsn using Q-Q plots doesn't meet with much success. Nonetheless, his point that it's better to use Q-Q plots than to eyeball histograms, is a good one.

Since I'm a bit of an old hand at constructing models out of data, and Dave was kind enough to provide the data for download from his blog, I decided to see what I could do with it. After a little fooling around, it struck me that there are actually three separate regions in these data. Therefore, it's a lost cause trying to model it with a single prob dsn. The following cluster of 4 plots shows what I came up with.

The top-left plot shows a histogram of the raw data set (some 500 query times), but with one very important difference compared with what Dave did. I ranked the data according to decreasing SQL elapse times. I then partitioned the data into 3 sub-regions (A, B and C). The top-right plot shows a portion of the data (region A) on double-log axes. The near linearity of those data demonstrates rather clearly that they most likely conform to a power law dsn. In fact, this looks like a textbook example. A power law means that the SQL queries are highly correlated in some way.

Both plots on the bottom row (for regions B and C, respectively) also exhibit linear behavior but those data are plotted on log-linear axes, so they cannot be power law. It does suggest, however, that those queries are exponentially distributed. Moreover, since these SQL query times are periods or intervals, that further suggests they belong to Poisson processes with two different rates. It also implies that whatever correlations are present in region A, are not present in regions B and C.

The blue lines in the above plots are the respective regression fits (using R) for each of the proposed models.

Now let's see what the Q-Q plots have to tell us about how well these 3 separate models do.

The top-left plot shows the entire data set compared with a normal dsn and, as Dave observed, it is clearly not normal (in every sense of the word). The top-right plot corresponds to the power law model and, although not a perfect diagonal line, it's better than the normal plot and I know that power laws can be notoriously difficult to model. At the very least, I think it says not to reject the power law on this data alone.

The bottom 2 plots would seem to confirm the validity of the exponential models in their respective regions. I'll be interested to hear if there is any support for this multi-modal approach in the Oracle world.

The M/M/m Numbers Game

2011-07-10T13:42:00.000-07:00

In a previous post, I explained why R_m ~ R₁/m doesn't work as an estimator of the mean residence time in an M/M/m multiserver queue: the residence time with m-servers (R_m) is not m-times smaller than the residence time (R₁) at a single-server (m = 1) queue. The problem is that it grossly underestimates the R_m time, which is precisely the wrong direction for capacity planning scenarios. That's too bad because it would be a handy Guerrilla-style formula if it did work. You could do the calculation in your head and impress everyone on your team and also do party tricks.

M/M/m multiserver queue
Given that R₁/m is a poor estimator, you might wonder if there's a better one, and if you'd been working for Thomas Edison he would have told you: "There is. Find it!" Easy for him to say. But if you did decide to take up Edison's challenge, how would you even begin to search for such a thing?

One way to proceed in situations like this is to play around with numbers and look for any interesting patterns that might emerge. In that vein, we're going to play a kind of multiserver numbers game and see if it reveals anything to us about queueing times. You may be thinking that playing games is a foolish thing to do when it comes to a serious subject like queueing theory, but believe me, even the mathematical heavies like Euler and Gauss were not above playing numbers games just like the one I'm about to show you. And, as you may have heard, they made a lot of important discoveries that way.

A Numbers Game

We know that R₁/m manifestly underestimates the R_m residence time. Another way to say that is: the estimator is too small because the divisor m is too big. Could we design a divisor that is smaller than m? That looks like an idiotic question because m is just a number: the number of servers you intend to apply to service the single queue or waiting line, in order to meet the service level objective, R_m. You can choose any m but it has to be a whole number (an integer). What could it possibly mean to "redesign" that number? Well, this is where thinking like a fool or a child can really work for you.

For example, with childlike innocence I could write m = 2 as m = 1 + 1. Numerically, it's the same thing. But here comes the really cute trick. I know that m = 1 + 1 is too big so, suppose I forget about what m really means in the real world of CaP & Perf, and replace it with something smaller, e.g., m = 1 + 1/2. That expression may look weird but it's certainly smaller than m = 2. Besides, it's just a game. All "adult" evaluating should be turned off. To test out this kind of number play it's important to be systematic, so let's tabulate our results as we go along.

The M/M/2 Game

For simplicity I'll assume R₁ = 2 minutes per customer at a grocery checkout with 1 cashier. The exact Erlang formula for m = 2 cashiers predicts a reduced residence time of R₂ = 1.33 mins. How does our new estimator stack up against the exact calculation? Here's the tabulation.

**Exact** R₂ = 1.33
Series	Ratio	Estimated R₂
1 + 1	2/(1 + 1)	1.00
1 + 1/2	2/(1 + 1/2)	1.33

The 1st column shows the numerical series we are using for m. The 2nd column shows how the series is used in the estimator (both old and new), and the 3rd column shows the numerical value of each type of estimator.

The 2nd row corresponds to the value I used in the previous post. In that case, we would have arrived at R₁/2 = 1 minute, which underestimates the exact value by 0.33 minutes. However, in the 3rd row, with that crazy 1/2, we are spot on. Wow!

The M/M/3 Game

Encouraged by this foolishness, let's consider the m = 3 server case. The next question we have to address is, what to chose for the third number in the series for m? If 1/2 worked as the second term for the m-series in the m = 2 case, that suggests 1/3 might be a good choice for the third term of this m-series. See 1st column, 3rd row. In that case, the rule that seems to be emerging is: count the term in the m-series and invert that count. Since the new term is a 3rd term in the series, add 1/3. Choosing 1/3 for the third term certainly moves things in the right direction (see 3rd column, 3rd row) when compared with just using m = 3, but there's still a significant gap. Can we make the gap smaller?

**Exact** R₃ = 1.16
Series	Ratio	Estimated R₃
1 + 1 + 1	2/(1 + 1 + 1)	0.67
1 + 1/2 + 1/3	2/(1 + 1/2 + 1/3)	1.09
1 + 1/2 + 1/4	2/(1 + 1/2 + 1/4)	1.14

If, instead of using the inverse of the term, we halve each successive term then we get (1/2)/2 = 1/4 for the third term. Certainly, 1/4 is smaller than 1/3. Using 1/4 in the 4th row of the above table shows a vast improvement, although it's not spot on, like the m = 2 case. But that's fine. Let's not lose our heads in all the excitement. We are only seeking a better estimator, not a wholesale replacement for the very complex Erlang formula. If things were that simple it would have been done 100 years ago (or earlier) and we would never have heard of Agner Erlang.

The M/M/4 Game

Let's check one more time with m = 4 servers.

**Exact** R₄ = 1.09
Series	Ratio	Estimated R₄
1 + 1 + 1 + 1	2/(1 + 1 + 1 + 1)	0.50
1 + 1/2 + 1/3 + 1/4	2/(1 + 1/2 + 1/3 + 1/4)	0.96
1 + 1/2 + 1/4 + 1/8	2/(1 + 1/2 + 1/4 + 1/8)	1.07

Once again, we see in the 4th row that the halving rule seems to work best. In fact, it will work for any arbitrary value of m.

What about other R₁ values besides 2 minutes—the numerator in the middle column? Unfortunately, the answer there is negatory. The halving rule only works for R₁ = 2 minutes. Any other value and the ratio will give incorrect results. Oh oh!

The General Game

What's gone wrong? Nothing has gone wrong, I just chose a special case for the M/M/1 residence time in order to reveal particular number patterns. If we played around with other values of R₁, we'd eventually find the general rule, but it helps to know what you're doing. Since I've already done all that, I'll just tell you the result. Or, feel free to keep playing the game and come back later to read the rest of this post.

In the above tables I used R₁ = 2 minutes, and that choice contains two assumptions which I deliberately didn't tell you about. I assumed something about the service time (S) and the arrival rate (λ). The server utilization is given by ρ = λS from Little's law. The halving rule has emerged because I have been assuming a server utilization of ρ = 0.5 or, written as a fraction, ρ = 1/2. That's where the 1/2 came from and it made the fractional series progressions more intuitive but, at the same time, more restricted in applicability.

If I had chosen some arbitrary utilization value, then the corresponding fractions in the series would have looked ugly and their progression would have been obscured. Not to worry because I can already see how to generalize those nice simple number patterns to form a general rule. But before I explain that, a few remarks.

I didn't choose R₁ = 2 minutes or ρ = 1/2 to trick you. It's actually the sanest thing to do when you're fooling around and not sure of the outcome. Always choose numbers where the patterns will be most obvious and can also be checked in some way. When acting the fool, there's plenty of room to screw up.
Because this is often a point of confusion, I should clarify that I'm comparing all M/M/m servers operating at the same ρ value. That means the arriving traffic has already been adjusted in each configuration to make ρ the same. Even though this may not be how things are done in practice, it is the appropriate assumption for the comparisons being made here. Looking at the diagram of the M/M/m queue (top) you can see that the traffic gets split m-ways. If nothing else is done, then the utilization of the servers will fall with each additional server. Therefore, in order to keep things fair and balanced for comparison, the total traffic arriving into the system has to be increased in proportion to the number of m servers. Since we're not using λ explicitly in the tables, this step is hidden in the value of ρ.
Moreover, for M/M/1, I have the rule-of-thumb that if the server utilization is 50%, then the residence time will be 2 service periods or R₁ = 2, no matter the actual service time or the actual arrival rate.

Returning to the business of generalizing the halving rule, the series in the first column has to be expressed in terms of the utilization ρ (whatever that value happens to be), not a fixed value like 1/2. The generalization of the series in the above tables now becomes:

1 + ρ + ρ² + ρ³ + ... + ρ^m

and the corresponding estimator (second column) becomes

R₁ / (1 + ρ + ρ² + ρ³ + ... + ρ^m)

So, instead of multiplying by 1/2 to get each successive term in the series, we multiply each successive term by the utilization ρ to produce: 1 + ρ + (ρ × ρ) + (ρ × ρ) × ρ + ... and so on, up to m terms. The series always starts with a zeroth term of 1 because ρ⁰ = 1. I deliberately chose ρ = 1/2 in the above tables to make the numeric patterns obvious. If you substitute that special value into this general rule, you'll see that it is consistent with the tabulated results.

This generalized estimator will always be superior to the naive estimator R₁/m. Try it, you'll like it.

Finally, I should note that although I started out looking for a way to express a reduced m-divisor, e.g., I wrote m = 1 + 1/2 + 1/4, the ultimate series in ρ does not represent m, per se. It's formally some other function—I call it the "morphing function" but that's whole 'nother story. However, if all m servers are running full tilt at 100% busy (and ignoring unbounded queueing effects), the ρ-series above becomes 1 + 1 + ... + 1, up to m terms because 1 raised to any power is still 1. In that way we do get back to my starting point, which was to "foolishly" write: m = 1 + 1 + ... + 1.

What's interesting for me is that although I already knew this result (see Section 2.7 of my Perl::PDQ book), I derived it using calculus techniques and the finite geometric series rather than numerically, as I've done here. This numerical approach arose out of some very interesting student remarks and questions during the May 2011 Guerrilla classes.

Your next opportunity to help me learn new things will be the upcoming GDAT class in August.

Little's Lore

2011-07-02T17:40:00.000-07:00

Guerrilla alumnus Paul P. has a penchant for sending me interesting things, and recently he sent me a piece on Little's law. Remarkably, it wasn't just another proof of L = λW, but a brief retrospective written by none other than John Little himself. I quote it here because it not only provides some unusual insight into how these things get done, but it is written in a charming and self-effacing style.

How did a sensible young PhD like me get involved in a crazy field like this? From 1957-1962, I taught operations research at the Case Institute of Technology in Cleveland (now Case Western Reserve University). I was asked to teach a course on queuing. OK. Initially I used my own notes, but when Morse (1958) came out, I used his book extensively. Queuing was taken by most of the OR graduate students and, indeed, one of these, Ron Wolff, went on to become a first class queuing theorist (Wolff 1989). One year we were at the point when we had done the basic Poisson-exponential queue and moved through multi-server queues, and some other general cases. I remarked, as many before and after me probably have (and Morse does), that the often reappearing formula L = λW ^†seemed very general. In addition I gave the heuristic proof.^‡ After class I was talking to a number of students and one of them (Sid Hess) asked, "How hard would it be to prove it in general?" On the spur of the moment, I obligingly said, "I guess it shouldn't be too hard." Famous last words. Sid replied, "Then you should do it!"

The remark stuck in my mind and I started to think about the question from time to time. Clearly there was something fundamental going on, since, when you draw the picture you do not really seem to need any detailed assumptions about interarrival times, service times, number of servers, order of service, and all the other ingredients that go into the panoply of queuing models. You only seemed to need a process that goes up and down in unit amounts and some guarantee of steady state and conservation of items. In addition, because I could see there were end effects in the picture, there needed to be a way to get rid of them in the limit. It seemed to me I was in the general arena of stationary stochastic processes. I am not a mathematician by training, and so I bought copies of measure theoretic stochastic process books like Doob (1953), which mentioned stationary processes and ergodic theorems.

My family's habit at the time was to go to Nantucket in the summer where my wife's family had a small summer house. We would load our children in a station wagon, drive to Woods Hole, take the ferry, and spend a couple months away from the world. Since the beach was the baby-sitter, I was able to split off solid blocks of time to work on research as a good assistant professor should. (I wish I could do that today!) I always brought a pile of books and projects with me. L = λW was one of them. I soon ran into problems that required more than looking up theorems in my new books, but I worked out approaches to the road blocks and eventually wrote everything up, giving it my best shot. I sent the paper off to Operations Research. It was accepted on the first round.

[Source: D. Chhajed and T. J. Lowe (eds.) Building Intuition: Insights From Basic Operations Management Models and Principles. © Springer, 2008]

† In my usual notation, I write Q = λR where Q is the queue length (including requests in service) and R is the residence time: R = W + S, the sum of the time spent waiting for service and the service time. In the above, W is also the waiting time and therefore L is the waiting-line length or the queue length that doesn't include requests in service.
‡ Same as the visual proof in Chapter 2 of Perl::PDQ.

The Backstory on Time-Share Computing

2011-06-28T10:11:00.000-07:00

In chapter 4 of my Perl::PDQ book, "Linux Load Average—Take a Load Off" and Appendix B "A Short History of Buffers," I briefly refer to the history of Unix and ultimately Linux via Multics, starting with the original MIT project called CTSS (Compatible Time-sharing System). My purpose there was to point out that the load average metric is the earliest example of O/S performance instrumentation. Naturally then, the following 5-part series in the NYT on the development of time-share computers caught my attention:

These accounts are noteworthy because they are written by the brother of one of the developers (of early email—depending on how you define email) and the author is a journalist, so he interviewed some of the personalities (who are now getting on a bit).

There are also lots of fascinating photos.

A Winking Pink Elephant

2011-06-27T00:01:00.000-07:00

The title of chapter 5 in my Guerrilla Capacity Planning book is, "Evaluating Scalability Parameters," and underneath it you'll see this quote:

"With four parameters I can fit an elephant. With five I can make his trunk wiggle. —John von Nemann

In that vein, Guerrilla alumnus Stephen O'C. pointed me at a recent blog post and paper (PDF) that draws an elephantine curve using just 4 fitting coefficients or parameters. Stephen also sent me his translation of the Python code into R. Previous efforts apparently had required some 30 parameters. The secret to the success of this latest example is plotting the elephant in the complex plane by summing certain Fourier modes. That's all very cool but I was surprised to see that the output was static (no wiggles), even though 5 parameters are defined. That shortcoming, however, provided me with the impetus to try out R's animation package and here's the result.

Notice that my elephant not only wiggles his trunk but he also winks—a wiggling winking pink elephant. Actually, I think he looks more like a winking woolly mammoth. :)

Since I also know a thing or two about complex numbers and Fourier transforms, I found the Python code a bit obtuse but I didn't want to spend a lot of time rewriting it. Instead, I just looked for opportunities to:

use the R animation package
reorganize the code
use R constructs such as lapply or sapply instead of loops
use the fft (fast fourier transform) function in R

and that's what I discuss in the remainder of this post. First, let's consider a little bit about how this thing works.

The resulting shape (and wiggling) of this elephant is controlled by a set of 5 (complex) parameters and their rotated complement. That's actually 20 numbers, but who's counting?


require(MASS)
library(animation)

mkmovie = TRUE  #guarantees some form of output

param <- c(50-30i,18+8i,12-10i,-14-60i,1+20i)
parar <- param * exp(1i*pi/2)  #rotate by 90 degrees

If we apply each of the first 4 parameters in succession, the results look like this.

The first parameter produces an ellipse, the second makes a dent in the ellipse, while all 4 parameters together produce the base elephant shape. Roughly speaking, each parameter (p) produces p + 1 lobes in the 2D figure ... or are they limbs? The following R function assigns the parameters to the Fourier coefficients (Cx and Cy) to draw "pinky" the elephant.


pinky <- function() {
 Cx <- as.complex(rep(0,length(param)))
 Cy <- as.complex(rep(0,length(param))) 
 tv <- seq(0,2*pi,length=1000)

 for (i in 1:2) { #movie frames
  Cx[1] <- parar[1] + Im(param[1])
  Cx[2] <- parar[2] + Im(param[2])
  Cx[3] <- Re(param[3])
  Cx[4] <- Re(param[5]) - (i-1)
  Cx[5] <- Re(param[4])
  
  Cy[1] <- param[1] - Re(param[1]) + Im(param[4])
  Cy[2] <- param[2] - Re(param[2])
  Cy[3] <- param[3] - Re(param[3])
  
  x <- c(fourier(tv, Cx))
  y <- c(fourier(tv, Cy))
  
  plot(y, -x, type="l", col='red', lwd=10, axes=FALSE, ylab='', xlab='')
  lines(y, -x, type="l", col='pink', lwd=4)
  if (i > 1) points(Im(param[5]), Im(param[5]), col='black', pch=126, cex=2)
     else points(Im(param[5]), Im(param[5]), col='black', pch=20, cex=2)
  }
}

Other combinations of these parameters can produce such things as Lissajous figures, just like I used to make on my father's oscilloscope (when he wasn't using it to fix our TV). I also grew up seeing another Lissajous figure: the logo of the Australian Broadcasting Corporation.

The vectors Cx and Cy are used in the Fourier summation, which I've written as a recursive function.


fourier <- function(tt,cc) {
 wt <- rep(0, length(tt)) 
 fsum <- function(n) {
   if (n > 0) wt <- wt + fsum(n-1) + Re(cc[n]) * cos(n*tt) + Im(cc[n]) * sin(n*tt)
   return(wt)
 }
 fsum(length(cc))
}

This tells me immediately that there's no point using fft in R because there, the purpose is to determine the parameter values (as outputs) that produce a given periodic function. Here, the parameter values are being chosen deliberately as inputs to draw a function that resembles an elephant. That's also antithetical to von Neumann's statement but let's not get too pedentic.

I also tried to find a way to use lapply directly but I ran into a conflict between the size of the tt (time) vector versus the number of summation terms. In any event, I was quickly facing the prospect of writing some additional functions for lapply and it all started to feel like I was overloading its intent. Worse yet, I would also have ended up with more code than the original for-loop. Ultimately, I just replaced it with the recursive routine above and declared victory.

Finally, the two frames from the pinky function can be output optionally as an animated GIF, such as I've used here, or as two static plots in the standard R graphics window.


if (mkmovie) {
 aopt = ani.options(interval = 0, nmax = 2)
 saveMovie(pinky(), interval = 0.25, outdir = getwd(), width = 400, height = 400)
 ani.options(aopt)
} else pinky()

Who knew that elephants could be so mathematically interesting. Animation is also a powerful tool for performance data visualization and I'll say more about that in the upcoming GDAT class.

Thanks, Stephen!

Bit.ly Kung Fooz Itself

2011-06-22T22:09:00.000-07:00

You know Bit Ly? Bruce Lee's distant cousin.

I love Twitter, but it's not for everybody and I can understand why some people don't get it or don't like it. One of the things I like is how the 140 char limit forces you to compose your tweet more carefully than you would in email or a blog. Tweeted URL links are counted as chars, so they can become a problem. Whether you use Twitter or not, there are occasions when you would like to replace some cosmologically long URL, like this http://maps.google.com/maps?q=27%C2%B09%E2%80%B236.73%E2%80%B3S+70%C2%B029%E2%80%B248.4%E2%80%B3W+&hl=en&ie=UTF8&ll=-27.268058,-70.423737&spn=0.330804,0.558929&sll=37.0625,-95.677068&sspn=37.819897,72.158203&t=h&z=11 with this http://j.mp/dmYEHy. That's where URL shorteners come in and there are many shortening services out there.

Until very recently, I had settled on using j.mp exclusively for Twitter because it was the first service I became aware of that produced the shortest URLs without going to unicode. j.mp is owned by bit.ly. With the recent advent of Twitter auto-shortening, bit.ly seems to be scrambling to keep users and in that process I suddenly noticed j.mp was now being redirected to bit.ly, which is not as short.

Moreover, j.mp was taking much more time to process a URL due to the growing JS eye-candy on their web page, not to mention "processing" your data. I can really see this with my web client bloat-detector: a 1 GHz Power Mac G4.

Finally, I decided to give bit.ly the chop in favor of goo.gl. Here's why:

Not as short as j.mp but generally shorter than Tweeter's auto-shortner
Tweeter auto-shortner can leave fairly explicit URL fragments
Sometimes I don't want to divert attention with the longer Twitter URL string
It has much lower JS overhead (Goog KISSes it) which makes for faster translation
Goog doesn't need to riffle my wallet for this service
Goog was tracking my data anyway :/

So, 再见 (zàijiàn) bit.ly ... fast as lightning.

Bye Bye Mr. Bar Code

2011-06-20T09:10:00.000-07:00

Last week, there was a New York Times obituary for Alan Haberman, he being the person who ushered in the barcode. Notice that's usher and not invent. That distinction goes to Norman Woodland and Bernard Silver, two graduate students at the Drexel Institute of Technology (now Drexel University), and was based—perhaps not surprisingly—on Morse code, which is now defunct.

Queueing at a grocery checkout [Source: Perl PDQ 2nd edn]
The bar code was an effort to modernize the grocery industry, which dates back to the 1940s. Woodland and Silver received a patent in 1952, but because scanning technology was rather poor at that time, their invention went largely unused. And that's where Alan Haberman comes in because he championed its adoption in actual retail stores. The first product to be purchased using a barcode, chewing gum no less, took place in 1974 at Marsh Supermarket in Troy, Ohio,

All of which brings me to the point of this post. Not only do I tend to use the grocery store as a familiar example of queueing effects, both in my Guerrilla CaP classes and my Perl::PDQ book, but Jim Holtman, one of our GDAT instructors, is currently doing data analysis and simulations for Kroger Supermarket in Cincinnati, Ohio. What is it with Ohio and grocery stores?

What started with barcodes, continues today with the application of RFID, motion capture, shelf optimization and so forth. And all these performance improvements rely on analyzing big data sets. No doubt, Jim will recount some of this in the upcoming GDAT class. You could do worse than be there for that. You can even bring your own data to be scanned and we'll check it out for you. :)

Two Heads Are Better Than One ... And m

2011-06-14T00:01:00.000-07:00

In the GCaP class, one of the homework exercises refers to a grocery store checkout where the customer arrival rate is 1 customer every 2 minutes and the mean service time for the cashier to ring up groceries is 1.5 minutes. The first question is: What is the mean residence time for each customer?

From Little's law, the utilization of the cashier is ρ = λ S = 0.5 × 1.5 = 0.75 or 75%. The residence time is given by R₁ = S/(1 − ρ) = 6.0 minutes.

A later question asks what happens if another cashier is employed to service the same aisle under the condition that the amount of traffic in the store is also doubled? In other words, the same waiting line now has 2 servers but the arrival rate into that waiting line has also increased by a factor of 2. The result is R₂ = S/(1 − ρ²) = 3.4286 minutes.

This result is surprising on several levels:

You'd expect that adding more capacity (2 servers) with the same arrival rate would produce a better residence time than for a single server. And it does. In that case, R₂ = 1.7455 minutes, which is smaller by better than a factor of 3.
Even with double the store traffic, the residence time per customer is better than the single cashier time (R₁) by almost a factor of 2. That is remarkable and unintuitive.
Is there a rule of thumb (RoT) here? Something like R₂ ≈ R₁/2.
And if that's true, can we generalize it to arbitrary m servers: R_m ≈ R₁/m?

These questions came up in the most recent GCaP class.

The answer to (3) is a qualified yes. It's like the old adage: two heads are better than one or, in this case, two cashiers. The answer to (4), however, is an unqualified no. The same RoT with m heads (or cashiers) is rot and does not produce a valid estimate. The following plot shows why.

The y-axis shows the residence time (R) normalized by the service time (S) plotted against the server load or utilization (ρ). Normalizing the residence time is a convenient way to compare across different server configurations without getting tied up in knots about the actual service time (Here, it's the same S = 1.5 minutes, anyway).

The blue curve toward the upper left is the single cashier case (aka M/M/1 in queueing parlance). The middle pair of curves (solid and dashed) pertain to the 2-cashier case (M/M/2). The third pair of curves are for 10-cashiers (M/M/10); chosen arbitrarily to represent more than 2 cashiers.

Notice first that all three solid curves approach R/S = 1 on the left side of the plot, i.e., at low cashier loads. That's because at low loads, the traffic in the store is so light that there are hardly any arrivals at the cashier, so no waiting line forms.

The dashed curve in the middle corresponds to half the M/M/1 residence time. You can see that although it's close to the actual M/M/2 residence time, it gets even closer for loads above 60% or 70%. We were considering 75% in the GCaP homework exercise above.

The dashed curve for M/M/10, however, is way off unless we are considering loads very close 100%, which is not much use for CaP predictions. Let's check that the curve itself is correct and we didn't make a mistake in calculating it. At ρ = 0.8, R/S = 5 for the M/M/1 curve and 1/10th of that value is R/S = 0.5, which is precisely on the dashed line for M/M/10. So, the dashed curve is correct.

The RoT R_m = R₁/m fails because it pushes the estimated residence time (the dashed curve) closer and closer to the x-axis as the number of cashiers (m) is increased. In other words, the estimated R/S ratio gets closer and closer to zero. Something like 100th of R₁ is going to be indistinguishable from the x-axis, for example. In reality, however, as the number of m servers is increased, the actual R/S ratio remains close to 1.0 (not zero) at higher and higher loads. That's the whole point of using a multiserver M/M/m queue.

Go Guerrill-R on Your Data

2011-05-31T09:20:00.000-07:00

The Guerrilla Data Analysis Techniques training course (GDAT) will be held during the week of August 8-12 this year. As usual, the focus will be on applying R to your performance and capacity planning data, as well as how to use the PDQ-R modeling tool.

(Click on the image for details)
Classes are held at our Larkspur Landing location in Pleasanton, California; a 45-minute BART ride to downtown San Francisco. For those of you coming from international locations, here is a table of currency EXCHANGE rates. We look forward to seeing all of you in August!

Quantifying Scalability FTW (The Movie)

2011-05-26T09:39:00.000-07:00

The video of my presentation at the Surge 2010 conference on scalability and performance has finally been posted. Since it doesn't seem to be a streaming server, it may take several minutes to download the video (depending on the speed of your pipe). Also, the audio is suboptimal because it seems to have been recorded from the ambient loudspeakers rather than a direct mic. I was too busy giving the talk to remember the setup they used.

Here's the abstract:

You probably already collect performance data, but data ain't information. Successfull scalability requires transforming your data so that you can quantify the cost-benefit of any architectural decisions. In other words:

measurement + models == information
So, measurement alone is only half the story; you need a method to transform your data. In this presentation I will show you a method that I have developed and applied successfully to large-scale web sites and stack applications to quantify the benefits of proposed scaling strategies. To the degree that you don't quantify your scalability, you run the risk of ending up with WTF rather than FTW.

May 2011 Guerrilla Classes: Light Bulb Moments

2011-05-23T09:05:00.000-07:00

It's impossible to know what will constitute a light bulb moment for someone else. In the recent Guerrilla classes (GBoot and GCaP), we seemed to be having many more than our usual quota of such moments. So much so, that I decided to keep a list.

The first was mine. Asa H. was having trouble setting up PDQ under cygwin on his work-provided Windows laptop. I suddenly realized that it would have been more helpful if I had provided an example .bashrc file in the PDQ distribution. I will do that but, in the meantime, I've now included a copy in the PDQ download notes.
Another problem is using PDQ-R under cygwin because R is not part of the official cygwin distro. A quick search on the web uncovered cygwinports, which provides R separately.
For people new to using PDQ functions in R, explicit name-dependency can be very helpful. Gary L. asked if this could be done in R. The answer is, yes. Instead of just writing say, CreateNode(name, CEN, FCFS) to define a queueing resource in PDQ, you can write pdq::CreateNode(name, CEN, FCFS) in R. A more detailed example is presented in my blog post "Applying PDQ in R to Load Testing".
John McG. pointed out that my grocery store "price check" service-time stretching analogy for coherency delays in the USL model (i.e., the point-to-point β term), doesn't scale with N customers in checkout lane.
My organizing principle of defining Inputs and Outputs for queueing theory calculations, was a big hit with some students. As a trivial example, if you wanted to apply Little's law, Q = λ R, to some performance data, it is important to know what variables you have and which one you want to solve for. If want to solve for the mean queue length Q, then you need both the arrival rate λ and the mean residence time R. Supposing you do indeed have data for λ and R, then they constitute your inputs and Q is the output. More generally, after you rearrange the equation appropriately, whatever is on the right side of the equal sign are the inputs and the left side is the output. The scheme can be (should be) applied to the construction of PDQ models.
When presenting Erlang's famous queueing formulae, I always apply the mnemonic device that the B stands for a "blocked call" (an engaged signal), and C stands for "call waiting' (a very modern concept). However, the Danish telephone system in the early 1900s did not offer call waiting, so what did Erlang mean in his 1917 paper when he uses the term "waiting room" (the waiting line) to define the difference between his B and C formulae? The image of a doctor's clinic comes to mind, but this could not have been implemented in telephone switches at that time. Gary L. provided us with a new insight. Telephones were still a rare resource in those days, and one can imagine that Danes who wanted to place a call did not have their own phone at home. Instead, they probably had to visit a shop or the post office to use a communal phone and it's in that room that they probably had to wait.
In reviewing one of the questions in the homework exercises, Gary L. observed that the response time R₂ for an M/M/2 queue is very close to one half R₁ for an M/M/1 queue if each server has the same load. We can test this in R. First we create a function to compute the response time (R) for an M/M/m queue
```
mmmR <- function(m,a,S) {
   R <- S/(1-(a*S)^m)
   return(R)
}
```
where the respective arguments are: m the number of servers, a the mean arrival rate into the queue, and S the mean service time at the queue. Note that this is a Guerrilla approximation to the exact Erlang C formula. Now, test it out. We know that R₁ should be 2S at ρ = a S = 0.5. Assuming S = 1:
```
> mmmR(1,0.5,1)
[1] 2
```
And R₁ should be 4S at ρ = a S = 0.75:
```
> mmmR(1,0.75,1)
[1] 4
```
In the class exercise, we first simply added another cashier to an existing check-out lane, where the original cashier was 75% busy. So, the load is now split in two:
```
> mmmR(2,0.75/2,1)
[1] 1.163636
```
A clear win compared with R₁ = 4. The next part of the exercise added another cashier, but make them both as busy as the original lone cashier:
```
> mmmR(2,0.75,1)
[1] 2.285714
```
Also a win when compared with R₁ = 4, even though both cashiers are as busy as the M/M/1 case. That result is not obvious. What about the observation that R₂ ≅ R₁/2? The following R code will generate a table:
```
r <- 0.0
cat(sprintf("%4s\t%6s\t%6s\t%6s\n", "load","M/M/1", "M/M/2", "M/M/20"))
for (i in 1:10) {
 cat(sprintf("%4.2f\t%6.2f\t%6.2f\t%6.2f\n", r, mmmR(1,r,1), mmmR(2,r,1), mmmR(20,r,1)))
 r <- r + 0.1
}
```
which allows us to compare both M/M/2 and M/M/20 for ρ > 0.5 (heavy traffic condition):
```
load  M/M/1  M/M/2 M/M/20
0.00   1.00   1.00   1.00
0.10   1.11   1.01   1.00
0.20   1.25   1.04   1.00
0.30   1.43   1.10   1.00
0.40   1.67   1.19   1.00
0.50   2.00   1.33   1.00
0.60   2.50   1.56   1.00
0.70   3.33   1.96   1.00
0.80   5.00   2.78   1.01
0.90  10.00   5.26   1.14
```
It looks like it holds for M/M/2 under heavy traffic, but it doesn't do so well as the number of servers is increased, e.g., m = 20 servers. Clearly, R₂₀ ≠ R₁/20, even at very high loads. See this blog post for an explanation.
The concept of iteratively tuning load-test measurements to try and match the theoretical USL curve, was a eureka moment for Asa H.

As you can see, a good time was had by all.

Applying PDQ in R to Load Testing

2011-05-19T00:28:00.000-07:00

PDQ is a library of functions that helps you to express and solve performance questions about computer systems using the abstraction of queues. The queueing paradigm is a natural choice because, whether big (a web site) or small (a laptop), all computer systems can be represented as a network or circuit of buffers and a buffer is a type of queue.

As a performance analyst, there are several things I really like about using PDQ in R; as opposed to the other programming languages: C, Perl, Python, etc. It enables you to:

easily import (large) data with a variety formats
perform sophisticated statistical analysis
extract input parameters for a PDQ model
construct and execute the PDQ model within R
plot the PDQ output and compare it with the original data
test your ideas in the R console and save the best into a script

In applying this approach, you could find yourself using a number of R library packages. To improve clarity in your modeling script, you might like to identify clearly which routines belong to PDQ; especially if you're new to PDQ and not familiar with all the functions.

R syntax for naming function dependency is the same as Perl. The :: operator is used for explicitly exported names. It also avoids conflict between packages the export different functions with the same name. The ::: operator is used for access to functions that are not exported in the package namespace.

Let's look at the above steps in the context of an example based on load testing data. A key point to observe here is how the performance data and the performance model play together to provide validation of the measurements.

Performance data

We begin by importing the load test data from measurements of an application intended for a three-tier architecture.


library(ineq)
library(pdq)

# Read in the performance measurements
gdat <- read.csv("/Users/njg/.../gcap.dat",header=TRUE)

Even though the ineq package is part of base R functionality, I've loaded it explicitly so as to name its functions explicitly. This will also provide a contrast with explicitly named functions from the PDQ package.


> gdat
  Vusr Xgps   Rms Uweb Uapp Udbm
1    1   24  26.0 0.21 0.08 0.04
2    2   48  26.0 0.41 0.13 0.05
3    4   85  29.3 0.74 0.20 0.05
4    7  100  44.7 0.95 0.23 0.05
5   10  115  66.0 0.96 0.22 0.06
6   20  112 140.0 0.97 0.22 0.06

The columns are respectively the client load, measured throughput, response time (in milliseconds), and system utilization on each of the three tiers.

Statistical analysis

We can now perform various kinds of statistical analysis on these data.


> summary(gdat)
      Vusr             Xgps             Rms              Uweb             Uapp       
 Min.   : 1.000   Min.   : 24.00   Min.   : 26.00   Min.   :0.2100   Min.   :0.0800  
 1st Qu.: 2.500   1st Qu.: 57.25   1st Qu.: 26.82   1st Qu.:0.4925   1st Qu.:0.1475  
 Median : 5.500   Median : 92.50   Median : 37.00   Median :0.8450   Median :0.2100  
 Mean   : 7.333   Mean   : 80.67   Mean   : 55.33   Mean   :0.7067   Mean   :0.1800  
 3rd Qu.: 9.250   3rd Qu.:109.00   3rd Qu.: 60.67   3rd Qu.:0.9575   3rd Qu.:0.2200  
 Max.   :20.000   Max.   :115.00   Max.   :140.00   Max.   :0.9700   Max.   :0.2300  
      Udbm        
 Min.   :0.04000  
 1st Qu.:0.05000  
 Median :0.05000  
 Mean   :0.05167  
 3rd Qu.:0.05750  
 Max.   :0.06000

More significantly, we can use R statistical functions to derive appropriate parameters for a PDQ model.


# Apply Little's law to get mean service times + CoVs
Sweb <- mean(gdat$Uweb/gdat$Xgps)
Sapp <- mean(gdat$Uapp/gdat$Xgps)
Sdbm <- mean(gdat$Udbm/gdat$Xgps)

Csw <- ineq::var.coeff(gdat$Uweb/gdat$Xgps)
Csa <- ineq::var.coeff(gdat$Uapp/gdat$Xgps)
Csd <- ineq::var.coeff(gdat$Udbm/gdat$Xgps)

s1 <- sprintf("System: %6s %6s %6s\n", "Web","App","DBMS")
s2 <- sprintf("Mean S: %6.4f %6.4f %6.4f\n", Sweb, Sapp, Sdbm)
s3 <- sprintf("CoV  S: %6.4f %6.4f %6.4f\n", Csw, Csa, Csd)
cat("\n",s1,s2,s3)

In particular, we calculate the average service times on each tier (second row) by applying Little's law.


 System:    Web    App   DBMS
 Mean S: 0.0088 0.0024 0.0008
 CoV  S: 0.0411 0.1989 0.5271

PDQ model

As shown in Figure 1, the service times for each of the three tiers in the load-test platform can be represented as queueing resources in PDQ.

Fig. 1 PDQ model of load test configuration

There is a finite number of requests allowed in the system corresponding to the load clients or virtual users that range between N = 1 and N = 20 Vusers, represented by the octagonal box in Figure 1. Using the diagram, we set up the following PDQ model. Note the use of explicitly named functions from the PDQ library


# Plotting variables
xc <- 0  # Vuser loads
yc <- 0  # PDQ throughputs
rc <- 0  # PDQ response times

# Define and solve the PDQ model
for(n in 1:max(gdat$Vusr)) {
 pdq::Init("Three-Tier Model")
 
 pdq::CreateClosed("httpGETs", TERM, as.numeric(n), 0.028)
 
 pdq::CreateNode("WebServer", CEN, FCFS)
 pdq::CreateNode("AppServer", CEN, FCFS)
 pdq::CreateNode("DBMServer", CEN, FCFS)
 
 pdq::SetDemand("WebServer", "httpGETs", Sweb)
 pdq::SetDemand("AppServer", "httpGETs", Sapp)
 pdq::SetDemand("DBMServer", "httpGETs", Sdbm)

 pdq::Solve(EXACT)
 
 xc[n] <- n
 yc[n] <- pdq::GetThruput(TERM, "httpGETs")
 rc[n] <- pdq::GetResponse(TERM, "httpGETs") * 10^3
}

In the above PDQ model, we've selected the predicted throughput and the predicted response times to compare with the original load-test data.

Plot PDQ results


# Plot throughput and response time models
par(mfrow=c(2,1))
plot(xc, yc, type="l", lwd=1, col="blue", ylim=c(0,120), main="PDQ Throughput Model", xlab="Vusers (N)", ylab="Gets/s X(N)")
points(gdat$Vusr, gdat$Xgps)
plot(xc, rc, type="l", lwd=1, col="blue", ylim=c(0,220), main="PDQ Response Time Model", xlab="Vusers (N)", ylab="ms R(N)")
points(gdat$Vusr, gdat$Rms)

The above R code produces the following plot array:

/>Fig. 2 Throughput and response time data and predicted PDQ curves

We see that the data and PDQ model are in good agreement with the throughput saturating above N = 5 vusers with the corresponding response time rising up the proverbial "hockey stick" handle.

PDQ report

Optionally, we can produce a formal PDQ report to examine the performance of each of the three tiers, even if we don't have any corresponding performance measurements from the load-test platform. This is one way by which bottlenecks can be predicted and checked before deploying into production.


> pdq::Report()
                ***************************************
                ****** Pretty Damn Quick REPORT *******
                ***************************************
                ***  of : Sun May 15 18:26:21 2011  ***
                ***  for: Three-Tier Model          ***
                ***  Ver: PDQ Analyzer v5.0 030211  ***
                ***************************************
                ***************************************

                =======================================
                ******    PDQ Model INPUTS      *******
                =======================================

Node Sched Resource   Workload   Class     Demand
---- ----- --------   --------   -----     ------
CEN  FCFS  WebServer  httpGETs   TERML     0.0088
CEN  FCFS  AppServer  httpGETs   TERML     0.0024
CEN  FCFS  DBMServer  httpGETs   TERML     0.0008

Queueing Circuit Totals:
        Streams:      1
        Nodes:        3

WORKLOAD Parameters:
httpGETs      20.00        0.0120     0.03


                =======================================
                ******   PDQ Model OUTPUTS      *******
                =======================================

Solution Method: EXACT

                ******   SYSTEM Performance     *******

Metric                     Value    Unit
------                     -----    ----
Workload: "httpGETs"
Mean concurrency         16.8004    Users
Mean throughput         114.2725    Users/Sec
Response time             0.1470    Sec
Round trip time           0.1750    Sec
Stretch factor           12.2633

Bounds Analysis:
Max throughput          114.2725    Users/Sec
Min response              0.0120    Sec
Max Demand                0.0088    Sec
Tot demand                0.0120    Sec
Think time                0.0280    Sec
Optimal clients           4.5696    Clients


                ******   RESOURCE Performance   *******

Metric          Resource     Work              Value   Unit
------          --------     ----              -----   ----
Throughput      WebServer    httpGETs       114.2725   Users/Sec
Utilization     WebServer    httpGETs       100.0000   Percent
Queue length    WebServer    httpGETs        16.3144   Users
Waiting line    WebServer    httpGETs        15.3144   Users
Waiting time    WebServer    httpGETs         0.1340   Sec
Residence time  WebServer    httpGETs         0.1428   Sec

Throughput      AppServer    httpGETs       114.2725   Users/Sec
Utilization     AppServer    httpGETs        27.7529   Percent
Queue length    AppServer    httpGETs         0.3841   Users
Waiting line    AppServer    httpGETs         0.1066   Users
Waiting time    AppServer    httpGETs         0.0009   Sec
Residence time  AppServer    httpGETs         0.0034   Sec

Throughput      DBMServer    httpGETs       114.2725   Users/Sec
Utilization     DBMServer    httpGETs         9.2447   Percent
Queue length    DBMServer    httpGETs         0.1019   Users
Waiting line    DBMServer    httpGETs         0.0094   Users
Waiting time    DBMServer    httpGETs         0.0001   Sec
Residence time  DBMServer    httpGETs         0.0009   Sec

Fundamental Performance Metrics

2011-05-01T12:34:00.000-07:00

Baron Schwartz invited me to comment on his latest blog post entitled "The four fundamental performance metrics," which I did. Coincidentally, I happened to address this same topic in my presentation at CMG Atlanta last week. I claim there are really only 3 fundamental performance metrics (actually 2, if you want to get truly fundamental about it).

Here are the relevant slides from that talk, which I hope you will be able to compare with Baron's perspective.

Baron seems to be getting his cue from certain Linux kernel metrics. However, I would strongly caution against using metrics defined by Linux kernel hackers (or any other hackers, for that matter). I've seen too many examples of bastardized nomenclature, not to mention broken code that incorrectly computes said metrics. Moreover, I see no virtue in reinventing the wheel only to end up with an irregular polygon.

With that in mind, what I think Baron is trying to elucidate is that just a small number of simple performance metrics (4?) is all that is required to parameterize certain performance models, such as the USL scalability model. In other words, performance modeling may not be as far away from your already collected performance data as you might think, and therefore there is little excuse not to do it. Amen to that!

I'll be discussing this topic again in my Guerrilla Boot Camp class, later this week.