research-article

Open access

Ludo Hashing: Compact, Fast, and Dynamic Key-value Lookups for Practical Network Systems

Authors:

Chen QianAuthors Info & Claims

Proceedings of the ACM on Measurement and Analysis of Computing Systems, Volume 4, Issue 2

Article No.: 22, Pages 1 - 32

https://doi.org/10.1145/3392140

Published: 12 June 2020 Publication History

Abstract

Key-value lookup engines running in fast memory are crucial components of many networked and distributed systems such as packet forwarding, virtual network functions, content distribution networks, distributed storage, and cloud/edge computing. These lookup engines must be memory-efficient because fast memory is small and expensive. This work presents a new key-value lookup design, called Ludo Hashing, which costs the least space (3.76 + 1.05l bits per key-value item for l-bit values) among known compact lookup solutions including the recently proposed partial-key Cuckoo and Bloomier perfect hashing. In addition to its space efficiency, Ludo Hashing works well with most practical systems by supporting fast lookups, fast updates, and concurrent writing/reading. We implement Ludo Hashing and evaluate it with both micro-benchmark and two network systems deployed in CloudLab. The results show that in practice Ludo Hashing saves 40% to 80%+ memory cost compared to existing dynamic solutions. It costs only a few GB memory for 1 billion key-value items and achieves high lookup throughput: over 65 million queries per second on a single node with multiple threads.

References

[1]

CloudLab. https://www.cloudlab.us/.

[2]

Implementation of farmhash. https://github.com/google/farmhash.

[3]

Implementation of Ludo Hashing in C

[4]

. https://github.com/QianLabUCSC/Ludo.

[5]

Implementation of Othello: a concise and fast data structure for classification. https://github.com/sdyy1990/Othello.

[6]

Intel DPDK: Data Plane Development Kit. https://www.dpdk.org.

[7]

Pktgen-DPDK. https://github.com/pktgen/Pktgen-DPDK.

[8]

Implementation of presized cuckoo map. https://github.com/tensorflow/tensorflow/blob/master/tensorflow/core/util/presized_cuckoo_map.h, 2016.

[9]

Abu-Libdeh, H., Costa, P., Rowstron, A., O'Shea, G., and Donnelly, A. Symbiotic routing in future data centers. In Proc. of ACM SIGCOMM (2010).

Digital Library

[10]

Belazzougui, D., Boldi, P., Pagh, R., and Vigna, S. Monotone minimal perfect hashing: searching a sorted table with $O(1)$ accesses. In Proc. of ACM SODA (2009).

[11]

Belazzougui, D., and Botelho, F. C. Hash, displace, and compress. In Proc. of Algorithms-ESA (2009).

[12]

Bloom, B. H. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM 13, 7 (1970), 422--426.

Digital Library

[13]

Cain, J. A., Sanders, P., and Wormald, N. The Random Graph Threshold for k-orientiability and a Fast Algorithm for Optimal Multiple-Choice Allocation. In Proc. of ACM-SIAM SODA (2007).

[14]

Charles, D., and Chellapilla, K. Bloomier Filters: A Second Look. In Proc. of European Symposium on Algorithms (2008).

Digital Library

[15]

Charles, D., and Chellapilla, K. Bloomier Filters: A Second Look. In Proc. of ESA (2008).

Digital Library

[16]

Chazelle, B., Kilian, J., Rubinfeld, R., and Tal, A. The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Tables. In Proc. of ACM SODA (2004), pp. 30--39.

[17]

Eisenbud, D. E., Yi, C., Contavalli, C., Smith, C., Kononov, R., Mann-Hielscher, E., Cilingiroglu, A., Cheyney, B., Shang, W., and Hosein, J. D. Maglev: A Fast and Reliable Software Network Load Balancer. In Proc. of USENIX NSDI (2016).

Digital Library

[18]

Erlingsson, U., Manasse, M., and McSherry, F. A cool and practical alternative to traditional hash tables. In Proc. 7th Workshop on Distributed Data and Structures (WDAS'06) (2006).

[19]

Esposito, E., Graf, T. M., and Vigna, S. Recsplit: Minimal perfect hashing via recursive splitting. Tech. rep., 2019.

[20]

Fan, B., Andersen, D., and Kaminsky, M. MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing. In Proc. of USENIX NSDI (2013).

[21]

Fan, B., Andersen, D. G., Kaminsky, M., and Mitzenmacher, M. D. Cuckoo filter: Practically better than bloom. In Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies (2014), ACM.

Digital Library

[22]

Fan, B., Zhou, D., Lim, H., Kaminsky, M., and Andersen, D. G. When cycles are cheap, some tables can be huge. In Proc. of USENIX HotOS (2013).

[23]

Fan, L., Cao, P., Almeida, J., and Broder, A. Z. Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol. IEEE/ACM Transactions on Networking (2000).

[24]

Fernholz, D., and Ramachandran, V. The k-orientability Thresholds for $G_n,p$. In Proc. of ACM/SIAM SODA (2007).

[25]

Fountoulakis, N., Khosla, M., and Panagiotou, K. The multiple-orientability thresholds for random hypergraphs. In Proc. of ACM/SIAM SODA (2011).

[26]

Gao, P., and Wormald, N. C. Load balancing and orientability thresholds for random hypergraphs. In Proc. of ACM STOC (2010).

Digital Library

[27]

Genuzio, M., Ottaviano, G., and Vigna, S. Fast Scalable Construction of (Minimal Perfect Hash) Functions. In Proceedings of the International Symposium on Experimental Algorithms (2016).

Digital Library

[28]

Greenberg, A., Hamilton, J. R., Jain, N., Kandula, S., Kim, C., Lahiri, P., Maltz, D. A., Patel, P., and Sengupta, S. VL2: a scalable and flexible data center network. In Proceedings of ACM SIGCOMM (2009).

Digital Library

[29]

Jain, S., Chen, Y., Jain, S., and Zhang, Z.-L. VIRO: A Scalable, Robust and Name-space Independent Virtual Id ROuting for Future Networks. In Proc. of IEEE INFOCOM (2011).

[30]

Kim, C., Caesar, M., and Rexford, J. Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises. In Proc. of Sigcomm (2008).

Digital Library

[31]

Kirsch, A., and Mitzenmacher, M. Using a queue to de-amortize cuckoo hashing in hardware. In Proceedings of the Forty-Fifth Annual Allerton Conference on Communication, Control, and Computing (2007), vol. 75.

[32]

Kirsch, A., Mitzenmacher, M., and Wieder, U. More robust hashing: Cuckoo hashing with a stash. SIAM Journal on Computing (2009).

[33]

Larisch, J., Choffnes, D., Levin, D., Maggs, B. M., Mislove, A., and Wilson, C. CRLite: A Scalable System for Pushing All TLS Revocations to All Browsers. In Proc. of IEEE S&P (2017).

[34]

Lelarge, M. A new approach to the orientation of random hypergraphs. In Proc. of ACM-SIAM SODA (2012).

[35]

Li, X., Andersen, D., Kaminsky, M., and Freedman, M. J. Algorithmic improvements for fast concurrent cuckoo hashing. In Proc. of ACM EuroSys (2014).

Digital Library

[36]

Lim, H., Fan, B., Andersen, D. G., and Kaminsky, M. SILT: A Memory-Efficient, High-Performance Key-Value Store. In Proc. of ACM SOSP (2011).

Digital Library

[37]

Maggs, B. M., and Sitaraman, R. K. Algorithmic Nuggets in Content Delivery. ACM SIGCOMM Computer Communication Review (2015).

[38]

Majewski, B. S., Wormald, N. C., Havas, G., and Czech, Z. J. A Family of Perfect Hashing Methods. The Computer Journal (1996).

[39]

Mao, R., Zeng, H., Kim, C., Lee, J., and Yu, M. SilkRoad: Making Stateful Layer-4 Load Balancing Fast and Cheap Using Switching ASICs. In Proc. of ACM SIGCOMM (2017).

Digital Library

[40]

Martn Dietzfelbinger and Christoph Weidling . Balanced allocation and dictionaries with tightly packed constant size bins. Theoretical Computer Science (2007).

[41]

McKeown, N., Anderson, T., Balakrishnan, H., Parulkar, G., Peterson, L., Rexford, J., Shenker, S., and Turner, J. Openflow: Enabling innovation in campus networks. SIGCOMM Comput. Commun. Rev. (2008).

[42]

Pagh, R., and Rodler, F. F. Cuckoo hashing. Journal of Algorithms (2004).

[43]

Parekh, A. K., and Gallager, R. G. A generalized processor sharing approach to flow control in integrated services networks: the single-node case. IEEE/ACM Transactions on Networking 1, 3 (1993), 344--357.

Digital Library

[44]

Patel, P., Bansal, D., Yuan, L., Murthy, A., Greenberg, A., Maltz, D. A., Kern, R., Kumar, H., Zikos, M., Wu, H., Kim, C., and Karri, N. Ananta: Cloud scale load balancing.

[45]

Pontarelli, S., Reviriego, P., and Mitzenmacher, M. Emoma: Exact match in one memory access. IEEE Transactions on Knowledge and Data Engineering (2017).

[46]

Qian, C., and Lam, S. ROME: Routing On Metropolitan-scale Ethernet. In Proceedings of IEEE ICNP (2012).

Digital Library

[47]

Raab, M., and Steger, A. Balls into Bins -- A Simple and Tight Analysis. In Lecture Notes in Computer Science (1998).

[48]

Raychaudhuri, D., Nagaraja, K., and Venkataramani, A. MobilityFirst: A Robust and Trustworthy MobilityCentric Architecture for the Future Internet. Mobile Computer Communication Review (2012).

[49]

Schlinker, B., et al. Engineering Egress with Edge Fabric: Steering Oceans of Content to the World. In Proc. of ACM SIGCOMM (2017).

Digital Library

[50]

Shi, S., Qian, C., and Wang, M. Re-designing Compact-structure based Forwarding for Programmable Networks. In Proc. of IEEE ICNP (2019).

[51]

Shi, W., Cao, J., Zhang, Q., Li, Y., and Xu, L. Edge computing: Vision and challenges. IEEE Internet of Things Journal 3, 5 (2016).

[52]

Wang, M., et al. Collaborative Validation of Public-Key Certificates for IoT by Distributed Caching. In Proc. of IEEE INFOCOM (2019).

[53]

Wang, M., Zhou, M., Shi, S., and Qian, C. Vacuum filters: more space-efficient and faster replacement for bloom and cuckoo filters. Proceedings of the VLDB Endowment (2019).

Digital Library

[54]

Wang, M., Zhou, M., Shi, S., and Qian, C. Vacuum Filters: More Space-Efficient and Faster Replacement for Bloom and Cuckoo Filters. In Proceedings of VLDB (2020).

[55]

Weil, S. A., Brandt, S. A., Miller, E. L., Long, D. D. E., and Maltzahn, C. Ceph: A scalable, high-performance distributed file system. In Proc. of USENIX OSDI (2006).

Digital Library

[56]

Wieder, U. Hashing, Load Balancing and Multiple Choice. Now Publishers, 2017.

[57]

Yang, T., Yang, D., Jiang, J., Gao, S., Cui, B., Shi, L., and Li, X. Coloring Embedder: a Memory Efficient Data Structure for Answering Multi-set Query. In Proc. of IEEE ICDE (2019).

[58]

Yap, K.-K., et al. Taking the Edge off with Espresso: Scale, Reliability and Programmability for Global Internet Peering. In Proc. of ACM SIGCOMM (2017).

Digital Library

[59]

Yu, M., Fabrikant, A., and Rexford, J. BUFFALO: Bloom filter forwarding architecture for large organizations. In Proc. of ACM CoNEXT (2009).

Digital Library

[60]

Yu, Y., Belazzougui, D., Qian, C., and Zhang, Q. Memory-efficient and Ultra-fast Network Lookup and Forwarding using Othello Hashing. IEEE/ACM Transactions on Networking (2018).

[61]

Yu, Y., Li, X., and Qian, C. SDLB: A Scalable and Dynamic Software Load Balancer for Fog and Mobile Edge Computing. In Proc. of ACM SIGCOMM Workshop on Mobile Edge Computing (MECCOM) (2017).

Digital Library

[62]

Zhou, D., Fan, B., Lim, H., Andersen, D. G., Kaminsky, M., Mitzenmacher, M., Wang, R., and Singh, A. Scaling up clustered network appliances with scalebricks. In SIGCOMM (2015).

[63]

Zhou, D., Fan, B., Lim, H., Kaminsky, M., and Andersen, D. G. Scalable, High Performance Ethernet Forwarding with CuckooSwitch. In Proc. of ACM CoNEXT (2013).

Digital Library

Cited By

Wu YWang FZhu YFan ZXiong ZYang TCui B(2024)VisionEmbedder: Bit-Level-Compact Key-Value Storage with Constant Lookup, Rapid Updates, and Rare Failure2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00324(4248-4261)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00324
Tripathi RSingh PSingh S(2024)Robust Left-Right Hashing Scheme for Ubiquitous ComputingEngineering Research Express10.1088/2631-8695/ad6d2aOnline publication date: 8-Aug-2024
https://doi.org/10.1088/2631-8695/ad6d2a
Liu YWang MShi SWang YQian CSha KBanerjee SChen J(2023)EdgeCut: Fast and Low-overhead Access of User-associated Contents from Edge ServersProceedings of the Eighth ACM/IEEE Symposium on Edge Computing10.1145/3583740.3628439(228-240)Online publication date: 6-Dec-2023
https://dl.acm.org/doi/10.1145/3583740.3628439

Index Terms

Ludo Hashing: Compact, Fast, and Dynamic Key-value Lookups for Practical Network Systems
1. Networks
  1. Network algorithms
    1. Data path algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
    2. Streaming, sublinear and near linear time algorithms
      1. Bloom filters and hashing

Recommendations

Ludo Hashing: Compact, Fast, and Dynamic Key-value Lookups for Practical Network Systems
SIGMETRICS '20: Abstracts of the 2020 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems

Key-value lookup engines running in fast memory are crucial components of many networked and distributed systems such as packet forwarding, virtual network functions, content distribution networks, distributed storage, and cloud/edge computing. These ...
Ludo Hashing: Compact, Fast, and Dynamic Key-value Lookups for Practical Network Systems

Ludo Hashing is a key-value lookup design for networked and distributed systems such as packet forwarding and distributed storage. Ludo costs the least space (3.76 + 1.05l bits per key-value item for l -bit values) among known compact lookup solutions ...
Smash: Flexible, Fast, and Resource-efficient Placement and Lookup of Distributed Storage
SIGMETRICS '23

Smash is a new placement and lookup method for distributed storage systems. It achieves full placement flexibility and low DRAM cost to store ID-to-location mappings, two desired features that could not be achieved simultaneously by any prior method.

Comments

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Measurement and Analysis of Computing Systems

Proceedings of the ACM on Measurement and Analysis of Computing Systems Volume 4, Issue 2

SIGMETRICS

June 2020

623 pages

EISSN:2476-1249

DOI:10.1145/3405833

Editors:
Augustin Chaintreau
Columbia University
,
Leana Golubchik
University of Southern California
,
Zhi-Li Zhang
University of Minnesota

Issue’s Table of Contents

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 June 2020

Online AM: 07 May 2020

Published in POMACS Volume 4, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Georgian National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
988
Total Downloads

Downloads (Last 12 months)232
Downloads (Last 6 weeks)19

Reflects downloads up to 19 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wu YWang FZhu YFan ZXiong ZYang TCui B(2024)VisionEmbedder: Bit-Level-Compact Key-Value Storage with Constant Lookup, Rapid Updates, and Rare Failure2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00324(4248-4261)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00324
Tripathi RSingh PSingh S(2024)Robust Left-Right Hashing Scheme for Ubiquitous ComputingEngineering Research Express10.1088/2631-8695/ad6d2aOnline publication date: 8-Aug-2024
https://doi.org/10.1088/2631-8695/ad6d2a
Liu YWang MShi SWang YQian CSha KBanerjee SChen J(2023)EdgeCut: Fast and Low-overhead Access of User-associated Contents from Edge ServersProceedings of the Eighth ACM/IEEE Symposium on Edge Computing10.1145/3583740.3628439(228-240)Online publication date: 6-Dec-2023
https://dl.acm.org/doi/10.1145/3583740.3628439
Girondi MChiesa MBarbette T(2021)High-speed Connection Tracking in Modern Servers2021 IEEE 22nd International Conference on High Performance Switching and Routing (HPSR)10.1109/HPSR52026.2021.9481841(1-8)Online publication date: 7-Jun-2021
https://doi.org/10.1109/HPSR52026.2021.9481841

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents