RE: designing with back-of-the-envelope estimates

On Tuesday, November 21, 2006 Ryan Barrett wrote:
> Design 2: Issue reads in parallel:
>     10 ms/seek + 256K read / 30 MB/s = 18 ms
>     (Ignores variance, so really more like 30-60 ms, probably)

        Wonderful table. But keep in mind that this thingie above 
is true only if you have [at least] 30 disks, and all your images 
are evenly spread over these disks - the case of the big server 
farm, more or less. Certainly true for Google, but try this on 
a single machine, and you'll be back to 560 ms from Design 1.

        Best wishes -
        S.Osokine.
        21 Nov 2006.


-----Original Message-----
From: p2p-hackers-bounces@xxxxxxxxxxxxxxx
[mailto:p2p-hackers-bounces@xxxxxxxxxxxxxxx]On Behalf Of Ryan Barrett
Sent: Tuesday, November 21, 2006 12:34 PM
To: p2p-hackers@xxxxxxxxxxxxxxx
Subject: [p2p-hackers] designing with back-of-the-envelope estimates


i caught a great talk the other day by jeff dean on using
back-of-the-envelope 
calculations to inform design decisions in large-scale systems. it's relevant

to the latency vs. bandwidth thread, and also just good to know in general,
so 
i figured i'd share a few of the more interesting slides.

no link for the talk, but jeff is http://labs.google.com/people/jeff/ .

(i'm sure we can dispute all of the numbers to varying degrees. the point 
isn't to get them exactly right, just within an order of magnitude or so. :P)


Numbers Everyone Should Know

L1 cache reference                            0.5 ns 
Branch mispredict                             5 ns 
L2 cache reference                            7 ns 
Mutex lock/unlock                           100 ns 
Main memory reference                       100 ns 
Compress 1K bytes with XXX               10,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 network  10,000,000 ns 
Read 1 MB sequentially from disk     30,000,000 ns 
Send packet CA->Netherlands->CA     150,000,000 ns


Back of the Envelope Calculations

How long to generate image results page (30 thumbnails)?

Design 1: Read serially, thumbnail 256K images on the fly
     30 seeks * 10 ms/seek + 30 * 256K / 30 MB/s = 560 ms

Design 2: Issue reads in parallel:
     10 ms/seek + 256K read / 30 MB/s = 18 ms
     (Ignores variance, so really more like 30-60 ms, probably)

Lots of variations:
     ­ caching (single images? whole sets of thumbnails?)
     ­ pre-computing thumbnails
     ­...

Back of the envelope helps identify most promising...


How long to quicksort 1 GB of 4 byte numbers?

Comparisons: lots of unpredictable branches
     log(2^28) passes over 2^28 numbers = ~2^33 comparisons
     ~1/2 will mispredict, so 2^32 mispredicts * 5 ns/mispredict = 21 secs

Memory bandwidth: mostly sequential streaming
     2^30 bytes * 28 passes = 28 GB. Memory BW is ~4 GB/s, so ~7 secs

So, it should take ~30 seconds to sort 1 GB on one CPU

Estimate only! Ignores initial read from disk, parallelism, etc...

-Ryan

--
http://snarfed.org/