Rules of Thumb in Data Engineering

Jim Gray, Prashant Shenoy

Microsoft Research, U. Mass, Amherst.
Gray@Microsoft.com, shenoy@cs.umass.edu

Abstract disk capacity has been improving by leaps and bounds; it

This paper reexamines the rules of thumb for the design has improved 100 fold over the last decade. The
of data storage systems. Briefly, it looks at storage, magnetic aerial density has gone from 20 Mbpsi
processing, and networking costs, ratios, and trends with (megabits per square inch in 1985), to 35 Gbpsi. Disks
a particular focus on performance and spin three times faster now, but they are also 5 times
price/performance. Amdahl’s ratio laws for system smaller than they were 15 years ago, so the data rate has
design need only slight revision after 35 years—the major only improved only 30 fold (see Figure 1). Today, disks
change being the increased use of RAM. An analysis also can store over 70 GB, have access times of about 10
indicates storage should be used to cache both database milliseconds (~ 120 kaps kilobyte accesses per second),
and web data to save disk bandwidth, network bandwidth, and transfer rates of about 25MBps (~ 20 maps (megabyte
and people’s time. Surprisingly, the 5-minute rule for accesses per second)) and a scan time of 45 minutes [1].
disk caching becomes a cache-everything rule for web These disks cost approximately 42 k$/TB today (15
caching. k$/TB for lower-performance IDE drives packaged,
powered, and network served) [2]. Within 5 years, the
1. Introduction same form-factor should be storing nearly ½ terabyte,
support 150 kaps, and a transfer rate of 75 MBps. At that
rate, it will take nearly 2 hours to scan the disk. By then,
We engineer data using intuition and rules of thumb.
Many of these rules are folklore. Given the rapid changes the prices should be nearing 1 k$/TB.
in technology, these rules need to be constantly re-
The ratio between disk capacity and disk accesses per
evaluated.
second is increasing more than 10x per decade. Also, the
This article is our attempt to document some of the main capacity/bandwidth ratio is increasing by 10x per decade.
These changes have two implications: (1) disk accesses
rules we use in engineering database systems. Since we
have to design for the future, the article also assesses become more and more precious; and (2) disk data
technology trends and predicts the sizes of future systems. becomes cooler with time [3].

We reduce disk accesses by (1) using a few large

2. Storage performance and price
Magnetic Disk Parameters vs Time
Many rules of thumb are a consequence of Moore’s 1000000
Law, which posits that circuit densities increase 4x each 100000
three years. That means that memories get 4 times larger
10000
each three years, or about 100x per decade. It also means
that in-memory data grows at this rate: creating the need 1000
for an extra bit of addressing every 18 months. In 1970 100
we were comfortable with 16-bit address spaces: it was
10
rare to find a machine with a megaword of memory.
Thirty years later we need 20 extra address bits to address 1 tpi
kbpi
the 64 GB memories (36 bit addresses) found in the larger 0.1 MBps
computers on the market. Today most computer Gbpsi
0.01
architectures give 64-bit logical addressing (e.g. MIPS, 84 88 92 96 00 04
Alpha, PowerPC, SPARC, Itanium) or 96-bit (e.g. year
AS400) addressing. Physical addressing is 36-bits to 40-
Figure 1: Disk capacity has improved 1,000 fold in the
bits, and growing a bit per 18 months. These extra 30 bits
last 15 years, consistent with Moore’s law, but the
should hold us for many years to come. transfer rate MBps has improved only 40x in the same
time. The metrics are tracks per inch (tpi), thousands of
Moore’s Law originally applied only to random
bits per linear inch of track (kbpi), megabits per second
access memory (RAM). It has been generalized to apply as the media spins (MBps), and gigabits per square inch
to microprocessors and to disk storage capacity. Indeed,
transfers rather than many small ones, (2) favoring 100x more expensive than disk. Indeed, today one can
sequential transfers, and (3) using mirroring rather than buy a 40 GB tape cartridge for 80$, a 36 GB disk for
RAID5. A random access costs a seek time, half a 1200$ (DELL and SCSI are not the least expensive), and
rotation time, and then the transfer time. If the transfer is 1 GB of memory for about 2400$ [4]. These ratios
sequential, there is no seek time, and if the transfer is an translate to 2$/GB, 32 $/GB and 2.4k$/GB giving a ratio
entire track, there is no rotation time. So track-sized of 1:16:1200 for storage.
sequential transfers maximize disk bandwidth and arm
utilization. Over the decade, disk pages have grown from But when the offline tapes are put in a nearline tape
2KB to 8KB and are poised to grow again. In ten years, robot, the price per tape rises to 10K$/TB while packaged
the typical small transfer unit will probably be 64KB, and disks are 30K$/TB. This brings the ratios back to
large transfer units will be a megabyte or more. The 1:3:240. It is fair to say that the storage cost ratios are
argument in favor of mirrors is that they double the read about 1:3:300.
bandwidth to each data item, and they cost only one extra
access for a write. RAID5 uses up to 4 disk accesses to The cost/MB of RAM declines with time: about 100x
do a write, and improves read bandwidth only if the data a decade. Since disk and RAM have a 1:100 price ratio,
requests go to different disks. what is economical to put on disk today will be
economical to put in RAM in about 10 years.
The move to sequential IO is well underway.
Transaction logging and log-structured file systems A striking thing about these storage cost calculations
convert random writes into sequential writes. This has is that disk prices are approaching nearline tape prices.
already had large benefits for database systems and By using RAID (mirroring or parity), administrators
operating systems. Buffering and caching of database sacrifice disk storage capacity to protect against disk
pages also converts many random operations into media failures. Increasingly, sites that need to be online
sequential operations. These techniques will continue to all the time are replicating their entire state at a remote
yield benefits as disk accesses become more precious. site, so that they have two online copies of the data. If
one site fails, the other offers access to the data, and the
Ten years ago, disks offered 30 kaps (kilobyte failed site can recover from the data stored at the second
accesses per second) to 1GB of data, and 5 minute scan site. In essence, disks are replacing tapes as backup
times. Current disks offer 120 kaps to 80 GB of data with devices. Tapes continue to be used for data interchange,
a 45 minute scan times. This is 250 kaps per GB vs. 1.5 but if Gilders’ Law holds (see below), then someday all
kaps per GB. So, modern disk data needs to be at least data interchange will go over the Internet rather than over
100x colder than data of 15 years ago. In fact, all the sneaker net.
“hot” data of 1990 has migrated to RAM: disk cost
10$/MB in that era, five times what RAM costs today. So Storage prices have dropped so low that the storage
1990s disk data can easily afford to be in RAM today. management costs now exceed storage costs (similarly,
The use of large main memories is one way to cool the PC management costs exceed the cost of the hardware).
data on disk. Another way is to store the data multiple In 1980, there was a rule of thumb that one needed a data
times and spread the reads among the copies: again administrator for 1GB of storage. At that time a GB of
suggesting mirroring. disk cost about a million dollars, and so it made sense to
have someone optimizing it and monitoring the use of
Meanwhile, there has been great progress in tape disk space. Today, a million dollars can buy 1 TB to 100
storage: tapes now store up to 40 GB. A drive with a 15 TB of disk storage (if you shop carefully). So, today, the
tape cartridges costs about 6 k$ and stores about 600GB rule of thumb is that a person can manage 1 TB to 100 TB
nearline. These drives provide 6 MBps data rates so the of storage – with 10 TB being typical. The storage
scan time for one cartridge is about 1.2 days, and management tools are struggling to keep up with the
approximately zero kaps and maps per second. This tape relentless growth of storage. If you are designing for the
store is ½ the cost per terabyte of disk storage, but tape next decade, you need build systems that allow one
does not provide easy access to the data. In five years, person to manage a 10 PB store.
this situation should be even more dramatic. The tape
capacities are expected to improve by 5x, making the Summarizing the Storage rules of thumb:
access problem even more dramatic: several days to scan 1. Moore’s Law: Things get 4x better every three years.
the archive. 2. You need an extra bit of addressing every 18 months.
3. Storage capacities are increasing 100x per decade.
Historically, tape, disk, and RAM have maintained a 4. Storage device throughput is increasing 10x per
price ratio of about 1:10:1000. That is, disk storage has decade.
been 10x more expensive than tape, and RAM has been 5. Disk data cools 10x per decade.
6. Disk page sizes increase 5x per decade.
7. NearlineTape:OnlineDisk:RAM storage cost ratios Amdahl’s balanced system law becomes mo re
are approximately 1:3:300. complex to interpret in the new world of quad-issue
8. In ten years DRAM will cost what disk costs today. pipelined processors. Table 2 summarizes the following
9. A person can administer a million dollars of disk analysis. In theory, the current 550 MHz Intel processors
storage: that is 10TB of storage today are able to execute 2 billion instructions per second, so
And two observations: Amdahl’s IO law suggests that each 550 MHz processors
• Disks are replacing tapes as backup devices. needs 160 MBps of disk bandwidth (all numbers
• Mirroring rather than Parity to save disk arms rounded). However, on real benchmarks, these
processors demonstrate 1.2 clocks per instruction on
3. Amdahl’s system balance rules sequential workloads (TPC-D,H,R) and 2.2 clocks per
instruction on random IO workloads (TPC-C, W) [7,8].
Gene Amdahl is famous for many rules of thumb. These larger CPIs translate to 450 MIPS on sequential
For data engineering, there are four famous ones [6]: and 260 MIPS on random workloads. In turn, Amdahl’s
10. Amdahl’s parallelism law: If a computation has a law says these processors need 60 MBps sequential IO
serial part S and a parallel component P, then the bandwidth (~450/8) and 30 MBps random of IO
maximum speedup is S/(S+P). bandwidth (~260/8) per cpu respectively (for tpcH and
11. Amdahl’s balanced system law: A system needs a bit tpcC). A recent tpcH benchmark by Compaq [5] used
of IO per second per instruction per second: about 8 eight 550 MHz processors with 176 disks. This translates
MIPS per MBps. to 22 disks per cpu, or about 70 MBps of raw disk
12. Amdahl’s memory law: α=1: that is the MB/MIPS bandwidth per cpu and 120 MBps of controller bandwidth
per cpu (consistent with Amdahl’s prediction of
ratio (called alpha ( α)), in a balanced system is 1.
60MBps). Amdahl’s law predicts that system needs
13. Amdahl’s IO law: Programs do one IO per 50,000
30MBps of IO bandwidth. Using 8KB pages and 100
instructions.
IOps per disk implies 38 disks per processor – a number
comparable to the 50 disks Dell actually used [4].
How have Amdahl’s law changed in the last 35 years?
The parallelism law is algebra, and so remains true and
Both TPC results mentioned here use approximately
very relevant to this day. The thing that is surprising is
½ gigabyte per processor. Based on the MIPS column of
that these 35-year-old laws have survived while speeds
Table 2, approximately 1 to 2 MB per MIPS. These are
and sizes have grown by orders of magnitude and while
Intel IA32 processors that are limited to 4 GB of memory.
ratios have changed by factors of 10 and 100.
When one considers HP and Sun systems that do not have
the 4GB limit, there is between 1GB/cpu and 2GB/cpu
To re-evaluate Amdahl’s IO laws, one can look at the
(12 to 32 GB overall). This roughly translates to 2
Transaction Processing Performance Council benchmark
MB/MIPS to 4 MB/MIPS. As argued by many people
systems [4]. These systems are carefully tuned to have
working in main memory databases (for example [9]), as
the appropriate hardware for the benchmark. For
disk IOs become more precious, we are moving towards
example, the OLTP systems tend to use small disks
relatively larger main memories. Alpha, the MB to MIPS
because the benchmarks are arm limited, and they tend to
ratio is rising from 1 to 4.
use the appropriate number of controllers. The following
paragraphs evaluate Amdahl’s balanced system law:
What about the execution interval? How many
concluding that with current technology it should be
instructions are executed per IO? In essence, if there are
amended to say:
8 instructions per byte, and 50 K instructions/IO, then IOs
10. Amdahl’s revised balanced system law: A system Table 2: Amdahl’s balanced system law and the parameters
needs 8 MIPS/MbpsIO, but the instruction rate and of two recent TPC benchmarks (www.tpc.org). The CPI
IO rate must be measured on the relevant workload. varies among the workloads, and the IO sizes also vary,
(Sequential workloads tend to have low CP (clocks still, the instructions/byte are similar to Amdahl’s prediction
per instruction), random workloads tend to have of eight instructions per byte (a bit of IO per instruction).
higher CPI.) IO/s Ins/
12. Alpha (the MB/MIPS ratio) is rising from 1 to 4. This MHz/ mip KB/ /dis Dis Disks/ MB/s/ IO
cpu CPI s IO k ks cpu cpu Byte
trend will likely continue.
13. Random IO’s happen about once each 50,000 Amdahl 1 1 1 6 8
TPC-C
instructions. Based on rule 10, sequential IOs are = random 550 2.1 262 8 100 397 50 40 7
much larger and so the instructions per IO are much TPC-H
higher for sequential workloads. = sequential 550 1.2 458 64 100 176 22 141 3
are about 6 KB (~50/8). Again, there is a dichotomy bytes on 100 Mbps Ethernet is less than a millisecond –
between sequential and random workloads: On TPC-C so the LAN was cpu limited, not transmit time limited.
benchmarks which do a lot of random IO, there are about
60 k instructions between 8 KB IOs (~7*8) and on A rule of thumb for traditional message systems has been
sequential workloads there are 200 k instructions between 16. A network message costs
64 KB IOs (~3*64). 10,000 instructions and 10 instructions per byte.
17. A disk IO costs
In summary, Amdahl’s laws are still good rules of 5,000 instructions and 0.1 instructions per byte.
thumb in sizing the IO and memory systems. The major
changes are that (1) the MIPS rate must be measured, Why are disk IOs so efficient when compared to
rather than assuming a CPI of 1 or less, (2) sequential IOs network IO? After all, disk IOs are just messages to the
are much larger than random IOs and hence the disk controller. There have been substantial strides in
instructions per IO are much higher for sequential understanding that simple question. The networking
workloads, (3) Alpha (the MB/MIPS ratio) is rising from community has offloaded much of the protocol to the
1 to 2 or 4, this trend will likely continue. Given the 100x NICs (much as SCISI and IDE do), and use memory more
and 1,000x changes in speeds and capacities, it is striking aggressively to buffer requests and correct errors.
that Amdahl’s ratios continue to hold. Checksuming, fragmentation/assembly, and DMA have
all been added to high-speed NICs. Much of this work
4. Networking: Gilder’s Law has gone on under the banner of System Area Networking
(SAN) and the Virtual Interface Architecture [11]. The
George Gilder predicted in 1995 that network current revision to rule of thumb is:
bandwidth would triple every year for the next 25 years 18. The cpu cost of a SAN network message is
[12]. So far his prediction seems to be approximately 3,000 clocks and 1 clock per byte.
correct. Individual wavelength channels run at 40 Gbps.
Wave-division multiplexing gives 10 or 20 channels per In particular, it is now possible to do an RPC in less
fiber. Multi-terabit links are operating in the laboratory. than 10 microseconds, and to move a Gbps from node to
Several companies are deploying thousands of miles of node while the processor is only half busy doing network
fiber optic networks. We are on the verge of having very (tcp/ip) tasks. The network carries 100,000 packets per
high-speed (Gbps) wide-area networks. When telecom second (300 M clocks) and 128 M bytes per second (128
deregulation or competition works, these links will be M clocks) so on a 650 MHz machine, there are 200 M
very inexpensive. clocks to spare for useful work.
14. Gilder’s law: Deployed bandwidth triples every year.
15. Link bandwidth improves 4x every 3 years. Currently, it costs a more than a dollar to send
100MB via a WAN (see Table 7 of Odlysko [13]), while
Paradoxically, the fastest link on the Microsoft local disk and LAN access are 10,000 times less
campus today is the 2.5 Gbps WAN link to the Pacific expensive. This price gap is likely to decline to 10:1 or
Northwest GigaPOP. It takes three 1 Gbps Ethernet links even 3:1 over the next decade. As suggested in
to saturate the WAN link. LAN speeds are about to rise subsequent sections, when bandwidth is sufficient and
to 10 Gbps, and then to 10 GBps via switched point-to- inexpensive, local disks can act as a cache for commonly
point networking. used data and a buffer for pre-fetched data.

Latency due to the speed of light (60 ms round trip 5. Caching: Location, Location, and Location
within North America, within Europe, and within Asia)
will be with us forever, but terabit-per-second bandwidth Processor clock speeds have been improving, as has
will allow us to design systems that cache data locally, the parallelism within the processor. Modern processors
and quickly access remote data if needed. are capable of issuing four or more instructions in parallel
and pipelining instruction execution.
Traditionally, high-speed networking has been
limited by software overheads. The cost of sending a In theory, current quad-issue Intel processors are able
message is [10]: Time = senderCPU + receiverCPU + to execute three billion instructions per second 4
bytes/bandwidth instructions per clock and 750 M clocks per second. In
The sender and receiver cpu costs have typically been practice, real benchmarks see CPI (clocks per instruction)
10,000 instructions and then 10 instructions per byte. So of 1 to 3, and the CPI is rising as processor speeds
to send 10 KB cost 120,000 instructions or something like outpace memory latency improvements [6,7,8].
a millisecond of cpu time. The transmit time of 10,000
 The memory subsystem cannot feed data to the caches beyond smaller-is-better and locality-is better.
processor fast enough to keep the pipelines full. But, two good rules have evolved for disk data locality
Architects have added 2-level and 3-level caches to the and caching. It is possible to quantitatively estimate
processors in order to improve this situation, but if when you should cache a disk page in memo ry: trading
programs do not have good data locality, there is not off memory consumption against disk arm utilization.
much the architects can do to mask “compulsorily” cache
misses. As mentioned before, disk arms are precious. If a
disk costs $1200 and does 120 accesses per second, then a
Software designers are learning that careful program disk access per second costs $10. It would be
and data placement and cache sensitive algorithms with advantageous to spend up to $10, to save one access per
good locality give 3x speedups on current processors. As second. Well, $10 buys about 10MB of DRAM, so if a
processor speeds continue to outpace memory speeds, cache of that size would indeed save one access per
there will be increasing incentives for software designers second, it would be a good investment.
to look for algorithms with small instruction cache
footprints, with predictable branching behavior, and with One can ask the question, how frequently should a
good or predictable data locality (read clustered or disk-resident object be accessed to justify caching it in
sequential). main memory? When does the rent of RAM space
balance the cost of an access? The analysis in [15] shows
There is a hardware trend to design huge (256 way) that:
multiprocessors that operate on a shared memory. These BreakEvenReferenceInterval (seconds) =
systems are especially prone to instruction stretch in PagesPerMBofRAM x PricePerDiskDrive
which bus and cache interference from other processors AccessPerSecondPerDisk PricePerMBofDRAM
causes each processor to slow down. Getting good For randomly accessed data, the first term (call the
performance from these massive SMPs will require access pattern) is approximately 1, the second term
careful attention to data partitioning, data locality, and (called the technology ratio) varies from 100 to 400
processor affinity. today. So, the breakeven interval is about 2 minutes to 5
minutes.
An alternative design opts for many nodes each with
its own IO and bus bandwidth and all using a dataflow For sequentially accessed data the access pattern term
programming model and communicating via a high-speed is approximately 0.1 (1MB “pages” and 10 pages per
network [14]. These designs have given rise to very second) so the break-even interval is 10 to 40 seconds.
impressive performance, for example, the sort speed of
computer systems has been doubling each year for the last This analysis gives the rules:
15 years through a combination of increased node speed 19. The 5-minute random rule: cache randomly accessed
(about 60%/year) and parallelism (about 40%/year). The disk pages that a re re-used every 5 minutes.
1999 terabyte sort used nearly 2,000 processors and disks, 20. The 1-minute sequential rule: cache sequentially
http://research.microsoft.com/~gray/sort_benchmark. accessed disk pages that are re-used within a minute.

The argument for the many-little scalable design tries A related rule that has not seen much use is that one
to leverage the fact that mainframe:mini:commodity price can spend 1 byte of RAM to save 1 MIPS. The argument
ratios are approximate 100:10:1. That is, mainframes cost goes that RAM costs about 1$/MB and today one can get
about 100 times more than commodity components, and a 100 extra MIPS from Intel for 100 extra dollars
semi-custom mini-computers have a 10:1 markup over (approximately). So, the marginal cost of an instruction
commodity components (see prices for comparable per second is approximately the marginal cost of a byte.
systems at the www.tpc.org benchmarks). The cluster Fifteen years ago, the ratio was 10:1, but since then Intel
advocates admit the many-little design is less efficient, and VLSI has made processors much less expensive.
but they argue that it is more cost-effective. 21. Spend 1 byte of RAM to save 1 MIPS.

There seems no good general rule of thumb for cpu- Now let’s consider web page caching. We can use
logic similar to the five-minute rule to decide when it
pays to cache web pages. The basic diagram is shown in
client cache Link server Figure 2, where the link speed varies from 100 KBps for
intranets, to modem speeds of 5 KBps, to wireless speeds
Figure 2. The client-side or proxy web cache improves
of 1 KBps. In case of a modem and wireless links, we
response time by eliminate link transmission times and
assume a local browser cache. For high-speed links, the
server times.
cache could either be a browser cache or a proxy cache.
In case of a proxy, we assume a fast connection between wait (3 seconds in the examples above), and if the object
the user and the cache (e.g., a 100Mb/s LAN), so that cost is in the browser cache local access avoids the
of accessing data from a remote proxy disk is not transmission time. If the local access saves both, then the
significantly larger than that from a local disk. R_local is a few hundred milliseconds.
Hence,
Given these assumptions consider three questions: R_local = 100ms (browser cache)
(1) How much does web caching improve response = 300ms (proxy cache intranet)
times? = 2s (proxy cache modem)
(2) When should a web page be cached? = 10s (proxy cache wireless)
(3) How large should a web cache be? Proxy cache studies indicate that H_proxy_cache =
0.4 is an upper bound [16,17]. Anecdotal evidence
Assume that the average web object is 10KB. Define suggests browser hit ratios are smaller: assume.
R_remote: response time to access an object at server. H_browser_cache = 0.20. Assuming a 20$/hr human
R_local: response time to access the object from cache. cost, each second costs 0.55 cents. Using that, Table 3
H: cache hit ratio (fraction of requests that cache computes the response time savings using the
satisfies) Response_Time_Improvement equation at left.
Then: Response_Time_Improvement =
R_remote - (H * R_local + (1-H) * R_remote) = Table 3: Shows the benefits of browser and proxy caching
H * (R_remote - R_local) (pennies saved) assuming people’s time is worth 20$/hr.
connection cache R_remote R_local H People
We now estimate R_remote and R_local. R_remote seconds seconds hit Savings
consists the server response time and the download rate ¢/page
network time. The server response time (the queuing LAN proxy 3 0.3 .4 0.6
delay and the service time) can range from several LAN browser 3 0.1 .2 0.3
hundred milliseconds to several seconds. Assume a Modem proxy 5 2 .4 0.7
response time of 3 seconds. Modem browser 5 0.1 .2 0.5
Mobile proxy 13 10 .4 0.7
Mobile browser 13 0.1 .2 1.4
The download time over the network depends on
network conditions and on link speeds. WAN Links are
typically shared, so the user bandwidth is smaller than the If a user makes ten requests per hour, and uses web
typical link bandwidth (a bottlenecked link at the server 400 hours per year then the benefit of caching is about 7
may further reduce the bandwidth/request). Assume that cents/hour and 20$/year. This should be balanced against
the effective LAN/WAN bandwidth is 100KB/s; hence the cost of the disk to store the pages – but as mentioned
time to transmit a 10KB object is a tenth of a second, and earlier, $20 will buy a LOT of disk space.
the R_remote of 3 seconds is dominated by the server
time. Having computed the savings for a cached page
(Table 3), we can now compute the point where caching a
Modem bandwidth available on a dial-up link is 56 page begins to pay off. Table 4 has the calculation. The
KB. With compression, the effective bandwidth is often first column of Table 4 estimates download costs from
twice that, but there are also start/stop overheads. We Odlysko [13 table 7] and assumes a wireless (1KBps)
assume an effective modem bandwidth of 5KB/s. Hence, link costs $0.1/minute ($6/hr). The second column
the modem transmit time for a 10 KB object is 2 seconds, assumes desktop disks cost 30$/GB and last 3 years,
and R_remote is 5 seconds. while mobile storage devices are 30x more expensive.

A mobile user on a wireless link gets 1KB/s, and so it The break-even cost of storing a page happens when
takes 10 seconds to download a 10KB object and the storage rent matches the download cost. The
R_remote is 13 seconds. We ignore the fact that mobile download cost has two components: the network time (A
systems often compress the data to make the
objects much smaller. Summarizing: Table 4: Caching is a very good deal: cache web pages if they
R_remote will be re-used within the few years.
= 3 + .1 = 3s (high speed connection) A B Time =A/B C Time=
$/10 KB $/10 KB Break-even People Cost (A+C)/B
= 3 + 2 = 5s (modem connection) download storage/mo cache Of download Break Even
= 3 + 10 = 13s (wireless connection) network cost storage time $ (table 3)
Internet/LAN 1e-4 1e-4 100 months 3E-3 400 months
Modem 2E-4 1e-4 250 months 5E-3 750 months
R_local depends many details, but
Wireless 1E-2 3E-3 56 months 1E-2 102 months
fundamentally local access avoids the server-time
in Table 4) and the people time C. The fourth column of 6. Summary
the table shows the calculation ignoring people’s time, C.
In that case the break-even interval is 8 years rather than Data stores will become huge. Our biggest challenge
many decades. In either case, the table indicates that is to make it easy to access and manage them.
caching is very attractive: cache a page if will be Automating all the tasks of data organization, accesses,
referenced within the next 5 years months (longer than the and protection.
lifetime of the system (!)).
Disk technology is overtaking tapes, but at the same
Certainly, our assumptions are questionable, but the time disks are morphing into tape-like devices with
astonishing thing is that a very wide spectrum of primarily sequential access to optimize the use of disk
assumptions concludes that a “cache everything” strategy arms. Meanwhile, RAM improvements encourage us to
is desirable. build machines with massive main memory. Indeed, the
main change to Amdahl’s balanced system law is that
How will Table 4 change with time? Network speeds alpha (=MIPS/DRAM size) is rising from 1 to 10.
are predicted to increase and network costs are predicted Network bandwidth is improving at a rate that
to drop. Column 4, Time=A/B, may drop from 100 challenges many of our design assumptions. LAN/SAN
months to one day. But column 6, Time=(A+C)/B, will software is being streamlined so it is no longer the
grow as people’s time grows in value, while the cost of bottleneck. This may well allow a re-centralization of
technology (A and B) decline. In summary, technology computing.
trends suggest that web page caching will continue be a
popular, especially for bandwidth-limited mobile devices. Still, data caching is an important optimization. Disk
caching still follows the 5-minute random rule and the
How much would it cost to cache all web accesses one-minute sequential rule. Web caching encourages
for a year? If users make 10 requests per hour with a hit designs that simply cache all pages.
ratio of H=0.4 the cache gets 4 hits and 6 new objects per
user hour. For an 8-hour workday, this is 480KB per user 7. References
per day. If H=0.2, then it is 640KB per user per day. In
both cases, this is about a penny a day. So, again we [1] IBM UltraStar72, http://www.storage.ibm.com/
conclude a simple “cache everything” strategy is a good hardsoft/diskdrdl/ultra/72zxdata.htm.
default. [2] Brewster Kahle, private communication, http://archive.org
[3] Data heat is the number of times the data is accessed per
These calculations suggest the simple rule: second.
22. Cache web pages if there is any chance they will be [4] Dell tpcC: http://www.tpc.org/results/individual_results
re-referenced within their lifetime. /Dell/ dell_8450_99112201_es.pdf
[5] Compaq tpcH: http://www.tpc.org/results/individual_results/
Compaq/compaq.8000.h.99110901.es.pdf
Web object lifetimes are bi-modal, or even tri-modal [6] J. L. Hennessy, D.A. Patterson, Computer Architecture, a
in some cases. Studies show median lifetimes to be a few Quantitative Approach. Morgan Kaufman, San Francisco,
days or few tens of days [18]. The average page has a 75- 1990, ISBN 1-55860-069-8
day lifetime (ignoring the modalities and non-uniform [7] K. Keeton, D. A. Patterson, Y. Q. He, R. C. Raphael, W. E.
access.) A heuristic that recognized high-velocity pages Baker, “Performance Characterization Of A Quad Pentium
would both improve usability (by not showing stale Pro SMP Using OLTP Workloads,” ACM ISCA p. 15-26.
cached pages) and would save cache storage. June 1998.
[8] A. Ailamaki, D. J. DeWitt, M. D. Hill, D. A. Wood.
“DBMSs On A Modern Processor: Where Does Time Go?”
A major assumption in these calculations is that
VLDB 99, pp. 266-277, Sept 1999.
server performance will continue to be poor: 3 seconds on [9] H. Garcia-Molina, A. Park, L.R. Rogers: “Performance
average. Popular servers tend to be slow because web site Through Memory.” ACM SIGMETRICS, Performance
owners are not investing enough in servers and Evaluation Review 15(1), May 1987. pp. 122-131.
bandwidth. With declining costs, web site owners could [10] J. Gray, “The Cost of Messages,” ACM PODC, 1988, p1-7
invest more and reduce the 3-second response time to less [11] Virtual Interface Architecture: http: //www.viarch.org
than a second. If that happens, then the web cache’s [12] G. Gilder, “Fiber Keeps Its Promise: Get ready. Bandwidth
people cost savings will evaporate, and the need for will triple each year for the next 25.” Forbes, 7 April 1997,
caching would be purely to save network bandwidth and http://www.forbes.com/asap/97/0407/090.htm
[13] A. M. Odlysko “The Economics of the Internet: Utility,
download time -- which we believe will not be a scarce
Utilization, Pricing, and Quality of Service,
resource except for mobile devices. http://www.research.att.com/~amo/doc/networks.html
[14] R.H. Arpaci-Dusseau, E. Anderson, N. Treuhaft, D.E.
Culler, J.M. Hellerstein, D.A. Patterson, “Rivers. Cluster
I/O with River: Making the Fast Case Common.” IOPADS
'99.
[15] J. Gray, G. Graefe, “The 5 minute rule, ten years later,”
SIGMOD Record 26(4): 63-68, 1997
[16] R. Tewari and M. Dahlin and H M. Vin and J. Kay,
”Beyond Hierarchies: Design Considerations for
Distributed Caching on the Internet”, IEEE ICDCS'99
June, 1999.
[17] A. Wolman and G. Voelker and N. Sharma and N.
Cardwell, A. Karlin, H. Levy,”On the scale and
performance of cooperative web proxy caching”, ACM
SOSP'99, pp.16--21, Dec., 1999.
[18] J. Gwertzman, M. Seltzer, “World-Wide Web Cache
Consistency,” 1996 USENIX Annual Technical
Conference, Jan. 1996.