Wednesday, August 1, 2012

Little's Law and IO Performance

Next Tuesday, August 7th, I'll be presenting at the Northern California CMG meeting*. My talk will be about Little's law and its implications for storage IO performance.

As a performance analyst or capacity planner, you already know all about Little's law—it's elementary. Right? Therefore, you completely understand:

  1. How Little's law relates inventory and manufacturing cycle time
  2. John Little (now 84) is not a performance analyst
  3. John Little did not invent Little's law
  4. Little's law was known to A. K. Erlang more than 100 years ago
  5. That there are actually two three versions of Little's law
  6. Little's law is not based on queueing theory
  7. Little's law expresses the fact that response time decreases with increasing throughput
  8. However, on the SPEC website you'll see that response time increases with increasing throughput. WTF !!!?

If you're feeling slightly bewildered about all this, you really should come along to my talk (assuming you're in the area). Otherwise, you can read the slide deck embedded below.

3-dimensional view of Little's law

I'll show you how I discovered the resolution to the apparent contradiction between items 7 and 8 (above) by representing Little's law in 3-dimensions. It's very cool! Even John Little doesn't know about this.

Oh yeah, and I'll also explain how Little's law reveals why it's possible to make your application IOs go 10x to 100x faster. IOPS bandwidth has become irrelevant.

Some of these conclusions are based on recent work I've been doing for Fusion-io. You might've heard of their billion IOPS benchmark, and more recently by association with SSDAlloc software from Princeton University.

* If you're not a ncCMG member, it's a one-time $25 entry fee, which then makes you a life member. See the bottom of their web page for payment and contact details.


gjl said...

I would be very interested in hearing what you have to say on this topic - but I am on the wrong coast. Is there any chance of having the session recorded? Even if audio only?

gjl said...
This comment has been removed by a blog administrator.
Neil Gunther said...

Not only wrong coast, but wrong pond. :) Though rather near my Alma Mater (Soton).

It's been a while since I gave a ncCMG presentation, but last time they certainly did not record the sessions.

Maybe go and bang on UK-CMG to get me over there, once the Olympics mob has cleared out. :)

metasoft said...

Hopefully ncCMG will post the slides after the meeting. I just love the idea of 1B IOPS for a critical OLTP database like trading systems. Do you know if Fusion-io is working on techniques to provide storage-based replication like EMC SRDF for business continuity or disaster recovery?

Neil Gunther said...

I'm doing research, rather than product dev, but this press release from yesterday would seem to be along the lines you're interested in.

PR: Fusion-io's ION software turns its ioMemory into a shared storage target.

Ken said...

That's a pretty interesting plot you included with your post. I assume R(s) means response time in seconds, X(QPS) is throughout expressed in queries per second, and N is number of users.

What do the red and blue dots represent, and what's behind the color change as values increase?

Neil Gunther said...

Thought you'd never ask. All will be revealed on Tuesday. :)

Neil Gunther said...

Just added my presentation slides.

John Goodwin said...

Are you familiar with the Palm Calculus and the result known as 'kitchen sink theorem' proved in the mid 90s, of which Little's law is now known to be a special case, as well as numerous other signal processing results, such as campbell's relation for shot noise? , ch. 7

The fellow at the link uses it to analyze the performance of mobile phone networks in simulations.

The {'time to event' x mean duration of event} relation shows up in other interesting places in the 'big data' world -- specifically, the top level relation of paid search advertising (Revenue per search = Cost per click x click rate) where money takes the place of time. ;)

There is also a relation, much used by actuaries, the Wald Identity, that seems to me to have interesting connection to this topic. Specifically, it relates the time until the first large insurance claim and the time-average cost of claims. I think it works (in the sense of your books) because the first event is special, in the sense of the Commuter's paradox or P-K correction. That is, it encodes details of the CoV of the distribution. Thus if you now the expectation of its occurrence you know quite a bit besides just the average time to the next event.

Anyway, I think a more modern treatment of Little's Law would at least allude to these connections. They come up in practical work, esp. as regards simulation techniques, actuarial work, and 'value at risk' sorts of calculations involving paid search advertising -- more general than computer performance in the narrow sense, but performance analysts get dragged into 'big data' these days, whether we like it or not!

Neil Gunther said...

I wasn't aware of this book or Palm Calculus. I'll have to investigate, when I can find the time. Thanks for the reference.

It's not too surprising that LL would arise as a special case, given its dimensional simplicity.

Matteo said...

Hi Dr. Gunther,
I realised that there is a connection between Little law and warehouse management.
In particular it is known that the mean residence time of materials in a warehouse for a period is
S = mean numer of items in stock for the period / mean number of additional items in that period
mean numer of items in stock = (quantity in stock at period start + quantity in stock at period end)/2 -> (Qs + Qe)/2
mean number of additional items in that period = (number of items arrived + number of items departed)/2 -> (Ia + Id)/2

S =((Qs + Qe)/2) / ((Ia + Id)/2) = (Qs + Qe)/(Ia + Id).

In a steady state as per Little Law case we have Qs = Qe and Ia = Id, which semplify the equation above to
S=Q/I -> Q=I*S

I wouldn't be surprised if Little Law was known by Romans which applied taxes on wheat production :-)