Wednesday, November 17, 2010

Numbers everyone should know

Jeffrey Dean recently gave a talk "Building Software Systems at Google and Lessons Learned" at Stanford (video). One of his slides was the following list of numbers:

L1 cache reference0.5ns
Branch mispredict 5 ns
L2 cache reference 7 ns
Mutex lock/unlock 25 ns
Main memory reference 100 ns
Compress 1K bytes w/ cheap algorithm 3,000 ns
Send 2K bytes over 1 Gbps network 20,000 ns
Read 1 MB sequentially from memory 250,000 ns
Round trip within same datacenter 500,000 ns
Disk seek 10,000,000 ns
Read 1 MB sequentially from disk 20,000,000 ns
Send packet CA->Netherlands->CA150,000,000 ns

Everyone who wants to design high-performance, scalable systems should memorize these numbers. There are many, many lessons to be learned.


Volodymyr Obrizan said...

There are many questions to this table. The data depends on clock frequency, a microarchitecture, number of cores, system bus frequency, RAM type, system bus saturation, HDD type, number of processes in OS, internet traffic and so on.

So, these numbers are not constant. And they will be different for any reader.

Julian Hyde said...

Of course. These numbers are only correct within a factor of two at best, sometimes a factor of ten. (In an earlier version of Dean's talk, some of the numbers were indeed different.)

But engineering decisions -- such as whether to store a particular piece of data in memory, on disk, or in the memory of a neighboring machine -- are usually not very sensitive to these parameters. (If they were sensitive, you would be building a system that would only work well in certain circumstances. No one wants such a finicky system, so you should throw away your design.)

The wrong conclusion to draw from these numbers is to say, "We don't have the exact numbers. Let's ignore the numbers and just build the system that we think will work best." In other words, go by intuition. Well, my intuition is just not capable of understanding the factor of 10 million difference between referencing a byte in L1 cache versus disk.

Great engineers know when to use informed intuition, otherwise known as the back-of-the-envelope calculation. They use results of those calculations to challenge their assumptions, and when the results of those calculations produce surprises, they change their own intuition.

Actually, there are two problems with this set of numbers. As I've said, I'm not concerned with the accuracy, because an order of magnitude is good enough. But the numbers don't take into account cost, and they don't take into account how the performance and cost are trending over time.

For instance, the cost of storing a byte on disk gets much cheaper every year; the time to access that byte also reduces every year, but not by anywhere as much. Flash memory is reducing in cost much faster than either disk or RAM, and its access times are lower than disk reducing. As a result, a new tier is appearing in the memory/storage hierarchy: registers, L1 cache, L2 cache, RAM, flash, disk, offline storage.

Another current trend is the rise of cache-efficient algorithms and data structures; driven by the widening gap between RAM speed and L1/L2 cache access times. (Interestingly, some of those algorithms and data structures look similar to those we used 20 years ago for organizing data on disk.)

I recommend that you read The 5 minute rule by Jim Gray and Gianfranco Putzolu, and its sequels "The 5 minute rule ten years later" by Jim Gray and Goetz Graefe, and "The 5 minute rule twenty years later", by Goetz Graefe. These papers are truly a masterclass in back-of-the-envelope calculations, how cost is as important as speed in engineering practical systems, and how those calculations change over time.

Dodgy_Coder said...

An excellent post - I'm sure google engineers working on their main product (search) must know these back to front.