The Internet has become indispensable in the developing world. It has become an important tool for providing entertainment, for enabling and bettering human communication, for delivering effective education, for conducting research, for spreading news, and for organizing people to rally to various causes. However, today, only a third of the world's population has quality access to the Internet. The Internet has two primary hindrances for expansion. First, the high cost of networkconnectivity in developing regions and second, the high cost of establishing new data centers to reduce the load on the existing data centers. Fortunately, caches in various forms help address both these problems by storing reusable content near the clients. Despite theirimportance, today's caches are limited in their scale because of the trends in the evolution of current memory-storage technologies.
The widening gap between memory and storage is limiting the performance of applications like caches. The ever-increasing amount of data and the need to access more of it quickly have further magnified the gap. Limited DRAM capacity of servers makes it difficult to obtain good in-memory hit-rates that are vital for avoiding high-latency disk accesses. This dissertation presents two new complementary methods (HashCache and SSDAlloc) to bridge this gap for caches that affect the performance of many applications including HTTP Web Proxy caches, wide area network accelerators, content distribution networks, and file backup services. First, we will develop HashCache, a novel method to drastically improve the memory efficiency of caches. By reducing the amount of memory needed for caching by up to 20 times, it reduces the cache's total cost of ownership. While HashCache makes more effective use of limited RAM in a system, SSDAlloc introduces a tier of new memory technology like NAND-Flash between RAM and disk to further bridge the gap.
SSDAlloc removes the impediments to the integration of new high-capacity memory technologies like NAND-Flash into the memory hierarchy. SSDAlloc is a novel memory manager that helps applications like HashCache tier data transparently and efficiently between DRAM and NAND-Flash. With only a few modifications to an existing application, restricted to the memory allocation portions of the code, one can reap the benefits of new memory technologies. Additionally, with SSDAlloc, applications can obtain 90% of the raw performance of NAND-Flash, while existing transparent tiering mechanisms deliver only 6-30% of that. Furthermore, by cleverly discerning application behavior, SSDAlloc writes up to 32 times less data to NAND-Flash when compared to similar existing mechanisms. This greatly increases the reliability of NAND-Flash that has a limited lifetime unlike DRAM.