|
RE: designing with back-of-the-envelope estimates: msg#00072network.peer-to-peer.p2p-hackers
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/ |
|
| <Prev in Thread] | Current Thread | [Next in Thread> |
|---|---|---|
| Previous by Date: | designing with back-of-the-envelope estimates: 00072, Ryan Barrett |
|---|---|
| Next by Date: | WiredReach Platform re-released: 00072, Ash Maurya |
| Previous by Thread: | designing with back-of-the-envelope estimatesi: 00072, Ryan Barrett |
| Next by Thread: | WiredReach Platform re-released: 00072, Ash Maurya |
| Indexes: | [Date] [Thread] [Top] [All Lists] |
| News | FAQ | advertise |