When Cycles Are Cheap, Some Tables Can Be Huge
Error message
You are not authorized to post comments.Bin Fan, Dong Zhou, and Hyeontaek Lim, Carnegie Mellon University; Michael Kaminsky, Intel Labs; David G. Andersen, Carnegie Mellon University
The goal of this paper is to raise a new question: What changes in operating systems and networks if it were feasible to have a (type of) lookup table that supported billions, or hundreds of billions, of entries, using only a few bits per entry. We do so by showing that the progress of Moore’s law, continuing to give more and more transistors per chip, makes it possible to apply formerly ludicrous amounts of brute-force parallel computation to find spacesavings opportunities.
We make two primary observations: First, that some applications can tolerate getting an incorrect answer from the table if they query for a key that is not in the table. For these applications, we can discard the keys entirely, using storage space only for the values. Further, for some applications, the value is not arbitrary. If the range of output values is small, we can instead view the problem as one of set separation. These two observations allow us to shrink the size of the mapping by brute force searching for a “perfect mapping” from inputs to outputs that (1) does not store the input keys; and (2) avoids collisions (and thus the related storage). Our preliminary results show that we can reduce memory consumption by an order of magnitude compared to traditional hash tables while providing competitive or better lookup performance.
Open Access Media
USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.
author = {Bin Fan and Dong Zhou and Hyeontaek Lim and Michael Kaminsky and David G. Andersen},
title = {When Cycles Are Cheap, Some Tables Can Be Huge},
booktitle = {14th Workshop on Hot Topics in Operating Systems (HotOS XIV)},
year = {2013},
address = {Santa Ana Pueblo, NM},
url = {https://www.usenix.org/conference/hotos13/session/fan},
publisher = {USENIX Association},
month = may
}
connect with us