Subject: [p2p-sip] Using DNS (was Fwd: [p2p-hackers] designing with back-of-the-envelope estimates)

From: slavitch at gmail.com (Michael Slavitch)
Date: Tue, 21 Nov 2006 16:01:08 -0500

I'm forwarding this to the P2SIP mailing list. It is very interestingreading especially when comparing DNS based systems to systems thatmaintain their own DHT, even large.
DNS in the quad-core age is not needed when 1G of db entries can bere-sorted in 30 seconds.
Regards
M

---------- Forwarded message ----------From: Ryan Barrett <p2p-hackers at ryanb.org>Date: Nov 21, 2006 3:34 PMSubject: [p2p-hackers] designing with back-of-the-envelope estimatesTo: p2p-hackers at lists.zooko.com

i caught a great talk the other day by jeff dean on using back-of-the-envelopecalculations to inform design decisions in large-scale systems. it's relevantto the latency vs. bandwidth thread, and also just good to know in general, soi 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 pointisn't to get them exactly right, just within an order of magnitude or so. :P)

Numbers Everyone Should Know
L1 cache reference                            0.5 nsBranch mispredict                             5 nsL2 cache reference                            7 nsMutex lock/unlock                           100 nsMain memory reference                       100 nsCompress 1K bytes with XXX               10,000 nsSend 2K bytes over 1 Gbps network        20,000 nsRead 1 MB sequentially from memory      250,000 nsRound trip within same datacenter       500,000 nsDisk seek                            10,000,000 nsRead 1 MB sequentially from network  10,000,000 nsRead 1 MB sequentially from disk     30,000,000 nsSend 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/
_______________________________________________p2p-hackers mailing listp2p-hackers at lists.zooko.comhttp://lists.zooko.com/mailman/listinfo/p2p-hackers