EKRM: Efficient Key-Value Retrieval Method to Reduce Data Lookup Overhead for Redis | SpringerLink
Skip to main content
Springer Nature Link
Log in

EKRM: Efficient Key-Value Retrieval Method to Reduce Data Lookup Overhead for Redis

  • Conference paper
  • First Online:
Euro-Par 2024: Parallel Processing (Euro-Par 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14801))

Included in the following conference series:

  • 577 Accesses

Abstract

As an open-source key-value system, Redis has been widely used in internet service stations. A key-value lookup in Redis usually involves several chained memory accesses, and the address translation overhead can significantly increase the lookup latency. This paper introduces a new software-based approach that can reduce chained memory accesses and total address translation overhead of lookup requests by placing key-value entries in a specially managed memory space organized as huge pages with a fast hash table and enabling a fast lookup approach with simple hash functions, while keeping the integrity of Redis data structure. The new approach brings up to 1.38\(\times \) average speedup for the key-value retrieval process, and significantly reduces misses in TLB and last-level cache. It outperforms SLB, an address caching software approach and has match the performance to STLT, a software-hardware co-designed address-centric design.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 6863
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 8579
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Kwon, M., Lee, S., Choi, H., Hwang, J., Jung, M.: Realizing strong determinism contract on log-structured merge key-value stores. ACM Trans. Storage 19, 1–29 (2023). https://doi.org/10.1145/3582695

    Article  Google Scholar 

  2. Ye, C., Xu, Y., Shen, X., Liao, X., Jin, H., Solihin, Y.: Hardware-based address-centric acceleration of key-value store. In: 2021 IEEE International Symposium On High-Performance Computer Architecture (HPCA), pp. 736–748 (2021)

    Google Scholar 

  3. Cooper, B., Silberstein, A., Tam, E., Ramakrishnan, R., Sears, R.: Benchmarking Cloud Serving Systems with YCSB. Association for Computing Machinery (2010). https://doi.org/10.1145/1807128.1807152

  4. Wu, X., Ni, F., Jiang, S.: Search lookaside buffer: efficient caching for index data structures. In: Proceedings of the 2017 Symposium on Cloud Computing, pp. 27–39 (2017). https://doi.org/10.1145/3127479.3127483

  5. Basu, A., Gandhi, J., Chang, J., Hill, M., Swift, M.: Efficient virtual memory for big memory servers. In: Proceedings of the 40th Annual International Symposium on Computer Architecture, pp. 237–248 (2013). https://doi.org/10.1145/2485922.2485943

  6. Pan, C., Luo, Y., Wang, X., Wang, Z.: PRedis: penalty and locality aware memory allocation in redis. In: Proceedings of the ACM Symposium on Cloud Computing, pp. 193–205 (2019). https://doi.org/10.1145/3357223.3362729

  7. Wang, K., Liu, J., Chen, F.: Put an elephant into a fridge: optimizing cache efficiency for in-memory key-value stores. Proc. VLDB Endow. 13, 1540–1554 (2020). https://doi.org/10.14778/3397230.3397247

  8. Ni, F., Jiang, S., Jiang, H., Huang, J., Wu, X.: SDC: a software defined cache for efficient data indexing. In: Proceedings of the ACM International Conference on Supercomputing, pp. 82–93 (2019). https://doi.org/10.1145/3330345.3330353

  9. Kocberber, O., Grot, B., Picorel, J., Falsafi, B., Lim, K., Ranganathan, P.: Meet the Walkers: Accelerating Index Traversals for in-Memory Databases. Association for Computing Machinery (2013). https://doi.org/10.1145/2540708.2540748

  10. Zhang, G., Sanchez, D.: Leveraging caches to accelerate hash tables and memoization. In: Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture, pp. 440–452 (2019). https://doi.org/10.1145/3352460.3358272

  11. Pagh, R., Rodler, F.: Cuckoo hashing. J. Algorithms 51, 122–144 (2004). https://www.sciencedirect.com/science/article/pii/S0196677403001925

  12. Lepers, B., Balmau, O., Gupta, K., Zwaenepoel, W.: KVell: the design and implementation of a fast persistent key-value store. In: Proceedings of the 27th ACM Symposium on Operating Systems Principles, pp. 447–461 (2019). https://doi.org/10.1145/3341301.3359628

  13. Zhang, K., Hu, J., He, B., Hua, B.: DIDO: dynamic pipelines for in-memory key-value stores on coupled CPU-GPU architectures. In: 2017 IEEE 33rd International Conference on Data Engineering (ICDE), pp. 671–682 (2017)

    Google Scholar 

  14. Kaiyrakhmet, O., Lee, S., Nam, B., Noh, S., Choi, Y.: \(\{\)SLM-DB\(\}\): \(\{\)Single-Level\(\}\)\(\{\)Key-Value\(\}\) store with persistent memory. In: 17th USENIX Conference on File and Storage Technologies (FAST 2019), pp. 191–205 (2019)

    Google Scholar 

  15. Zhang, T., et al.: FPGA-accelerated compactions for \(\{\)LSM-based\(\}\)\(\{\)Key-Value\(\}\) store. In: 18th USENIX Conference on File and Storage Technologies (FAST 2020), pp. 225–237 (2020)

    Google Scholar 

  16. Liu, H., Liu, R., Liao, X., Jin, H., He, B., Zhang, Y.: Object-level memory allocation and migration in hybrid memory systems. IEEE Trans. Comput. 69, 1401–1413 (2020)

    Article  Google Scholar 

  17. Heo, T., Wang, Y., Cui, W., Huh, J., Zhang, L.: Adaptive page migration policy with huge pages in tiered memory systems. IEEE Trans. Comput. 71, 53–68 (2020)

    Article  Google Scholar 

  18. Chen, J., et al.: \(\{\)HotRing\(\}\): a \(\{\)Hotspot-Aware\(\}\)\(\{\)In-Memory\(\}\)\(\{\)Key-Value\(\}\) store. In: 18th USENIX Conference on File and Storage Technologies (FAST 2020), pp. 239–252 (2020)

    Google Scholar 

  19. Atikoglu, B., Xu, Y., Frachtenberg, E., Jiang, S., Paleczny, M.: Workload analysis of a large-scale key-value store. In: Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems, pp. 53–64 (2012)

    Google Scholar 

  20. Wu, X., Zhang, L., Wang, Y., Ren, Y., Hack, M., Jiang, S.: Zexpander: a key-value cache with both high performance and fewer misses. In: Proceedings of the Eleventh European Conference on Computer Systems, pp. 1–15 (2016)

    Google Scholar 

  21. Cao, Z., Dong, S., Vemuri, S., Du, D.: Characterizing, modeling, and benchmarking \(\{\)RocksDB\(\}\)\(\{\)Key-Value\(\}\) workloads at Facebook. In: 18th USENIX Conference on File and Storage Technologies (FAST 2020), pp. 209–223 (2020)

    Google Scholar 

  22. Gilad, E., et al.: EvenDB: optimizing key-value storage for spatial locality. In: Proceedings of the Fifteenth European Conference on Computer Systems, pp. 1–16 (2020)

    Google Scholar 

  23. Gaur, J., Chaudhuri, M., Subramoney, S.: Bypass and insertion algorithms for exclusive last-level caches. In: Proceedings of the 38th Annual International Symposium on Computer Architecture, pp. 81–92 (2011)

    Google Scholar 

  24. Park, J., Park, Y., Mahlke, S.: A bypass first policy for energy-efficient last level caches. In: 2016 International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation (SAMOS), pp. 63–70 (2016)

    Google Scholar 

  25. Atikoglu, B., Xu, Y., Frachtenberg, E., Jiang, S., Paleczny, M.: Workload analysis of a large-scale key-value store. SIGMETRICS Perform. Eval. Rev. 40, 53–64 (2012). https://doi.org/10.1145/2318857.2254766

  26. Carlson, T., Heirman, W., Eyerman, S., Hur, I., Eeckhout, L.: An evaluation of high-level mechanistic core models. ACM Trans. Archit. Code Optim. 11 (2014). https://doi.org/10.1145/2629677

  27. Linux kernel. https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git. Accessed 15 Mar 2024

  28. Redis. https://redis.io/. Accessed 15 Mar 2024

  29. Memcached. https://memcached.org/. Accessed 15 Mar 2024

  30. Redis documentation. https://redis.io/docs/management/optimization/latency/. Accessed 15 Mar 2024

  31. Mutilate. https://github.com/leverich/mutilate. Accessed 15 Mar 2024

  32. Gem5. https://github.com/gem5/gem5. Accessed 15 Mar 2024

Download references

Acknowledgments

The research is supported in part by the National Key R&D Program of China under Grant No. 2022YFB4500701, and by the National Science Foundation of China (Nos. 62032001, 62032008, 62372011).

Author information

Authors and Affiliations

  1. National Key Laboratory for Multimedia Information Processing, School of Computer Science, Peking University, Beijing, 100871, China

    Yiming Yao, Xiaolin Wang, Diyu Zhou, Liujia Li, Jianyu Wu, Liren Zhu & Yingwei Luo

  2. The Swiss Federal Institute of Technology in Lausanne, Lausanne, Switzerland

    Diyu Zhou

  3. Michigan Technological University, Houghton, USA

    Zhenlin Wang

Authors
  1. Yiming Yao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xiaolin Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Diyu Zhou
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Liujia Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Jianyu Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Liren Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Zhenlin Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  8. Yingwei Luo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yiming Yao .

Editor information

Editors and Affiliations

  1. University Carlos III of Madrid, Madrid, Madrid, Spain

    Jesus Carretero

  2. University of Oregon, Eugene, OR, USA

    Sameer Shende

  3. University Carlos III of Madrid, Madrid, Spain

    Javier Garcia-Blas

  4. TU Wien, Vienna, Austria

    Ivona Brandic

  5. Universidad Complutense de Madrid, Madrid, Spain

    Katzalin Olcoz

  6. Université Grenoble Alpes, Saint Martin d'Hères, France

    Martin Schreiber

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Yao, Y. et al. (2024). EKRM: Efficient Key-Value Retrieval Method to Reduce Data Lookup Overhead for Redis. In: Carretero, J., Shende, S., Garcia-Blas, J., Brandic, I., Olcoz, K., Schreiber, M. (eds) Euro-Par 2024: Parallel Processing. Euro-Par 2024. Lecture Notes in Computer Science, vol 14801. Springer, Cham. https://doi.org/10.1007/978-3-031-69577-3_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-69577-3_12

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-69576-6

  • Online ISBN: 978-3-031-69577-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation