nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

Redesigning the Sorting Engine for Persistent Memory

verfasst von : Yifan Hua, Kaixin Huang, Shengan Zheng, Linpeng Huang

Erschienen in: Database Systems for Advanced Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Emerging persistent memory (PM, also termed as non-volatile memory) technologies can promise large capacity, non-volatility, byte-addressability and DRAM-comparable access latency. Such amazing features have inspired a host of PM-based storage systems and applications that store and access data directly in PM. Sorting is an important function for many systems, but how to optimize sorting for PM-based systems has not been systematically studied yet. In this paper, we conduct extensive experiments for many existing sorting methods, including both conventional sorting algorithms adapted for PM and recently-proposed PM-friendly sorting techniques, on a real PM platform. The results indicate that these sorting methods all have drawbacks for various workloads. Some of the results are even counterintuitive compared to running on a DRAM-simulated platform in their papers. To the best of our knowledge, we are the first to perform a systematic study on the sorting issue for persistent memory. Based on our study, we propose an adaptive sorting engine, namely SmartSort, to optimize the sorting performance for different conditions. The experimental results demonstrate that SmartSort remarkably outperforms existing sorting methods in a variety of cases.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel PAS: Enable Partial Consensus in the Blockchain

Nächstes Kapitel ImputeRNN: Imputing Missing Values in Electronic Medical Records

In this paper, we call the attribute for sorting in a record as key and the other attributes as value.

In this paper, we assume that PM is always large enough to accommodate all records and unsorted records are initially stored in PM while DRAM is not always sufficient relative to PM.

Kültürsay, E., Kandemir, M., Sivasubramaniam, A., Mutlu, O.: Evaluating STT-RAM as an energy-efficient main memory alternative. In: IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), Austin, TX, pp. 256–267 (2013)

Wong, H.-S.P., Raoux, S., et al.: Phase change memory. Proc. IEEE 98(12), 2201–2227 (2010)CrossRef

Hady, F.T., Foong, A., Veal, B., Williams, D.: Platform storage performance With 3D XPoint technology. Proc. IEEE 105(9), 1822–1833 (2017)CrossRef

Peng, I.B., Gokhale, M.B., Green, E.W.: System evaluation of the Intel optane byte-addressable NVM. In: Proceedings of the International Symposium on Memory Systems, pp. 304–315 (2019)

Qureshi, M.K., et al.: Enhancing lifetime and security of PCM-based main memory with start-gap wear leveling. In: 2009 42nd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO) (2009)

Huang, K., Mei, Y., Huang, L.: Quail: using NVM write monitor to enable transparent wear-leveling. J. Syst. Archit. 102, 101658 (2020)MathSciNetCrossRef

Xu, J., Swanson, S.: NOVA: a log-structured file system for hybrid volatile/non-volatile main memories. In: Proceedings of the 14th USENIX Conference on File and Storage Technologies, pp. 323–338 (2016)

Zheng, S., Hoseinzadeh, M., Swanson, S.: Ziggurat: a tiered file system for non-volatile main memories and disks. In: Proceedings of the 17th USENIX Conference on File and Storage Technologies, pp. 207–219 (2019)

Coburn, J., Caulfield, A., Akel, A., et al.: NV-heaps: making persistent objects fast and safe with next-generation, non-volatile memories. In: Proceedings of the Sixteenth International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 105–118 (2011)

10.

Kaiyrakhmet, O., Lee, S., Nam, B., Noh, S.H., Choi, Y.: SLM-DB: single-level key-value store with persistent memory. In: Proceedings of the 17th USENIX Conference on File and Storage Technologies, pp. 191–205 (2019)

11.

Seo, J., Kim, W.-H., Baek, W., Nam, B., Noh, S.H.: Failure-atomic slotted paging for persistent memory. SIGARCH Comput. Archit. News 45(1), 91–104 (2017)CrossRef

12.

Viglas, S.D.: Write-limited sorts and joins for persistent memory. Proc. VLDB Endow. 7(5), 413–424 (2014)CrossRef

13.

Liang, Y.-P., et al.: B*-sort: enabling Write-once Sorting for persistent memory. IEEE Trans. Comput.-Aided Design Integr. Circ. Syst. PP(99), 1 (2020)

14.

Yang, J., Kim, J., Hoseinzadeh, M., et al.: An empirical guide to the behavior and use of scalable persistent memory. In: Proceedings of the 18th USENIX Conference on File and Storage Technologies, pp. 168–182 (2020)

15.

Hwang, D., Kim, W., Won, Y., Nam, B.: Endurable transient inconsistency in byte-addressable persistent B+-tree. In: Proceedings of the 16th USENIX Conference on File and Storage Technologies, pp. 187–200 (2018)

16.

Chen, Y., Lu, Y., Fang, K., Wang, Q., Shu, J.: uTree: a persistent B+-tree with low tail latency. Proc. VLDB Endow. 13(12), 2634–2648 (2020)CrossRef

17.

Liu, M., Xing, J., Chen, K., Wu, Y.: Building scalable NVM-based B+tree with HTM. In: Proceedings of the 48th International Conference on Parallel Processing, pp. 1–10 (2019)

18.

Yang, J., Wei, Q., Chen, C., Wang, C., Yong, K.L., He, B.: NV-Tree: reducing consistency cost for NVM-based single level systems. In: Proceedings of the 13th USENIX Conference on File and Storage Technologies, FAST 2015, pp. 167–181 (2015)

19.

Chen, S., Jin, Q.: Persistent B+-trees in non-volatile main memory. PVLDB 8(7), 786–797 (2015)

20.

Oukid, I., Lasperas, J., Nica, A., Willhalm, T., Lehner, W.: FPTree: a hybrid SCM-dram persistent and concurrent b-tree for storage class memory. In: Proceedings of the 2016 International Conference on Management of Data, pp. 371–386 (2016)

21.

Andrei, M., Lemke, C., et al.: Sorting with asymmetric read and write costs guy. In: Annual ACM Symposium on Parallelism in Algorithms and Architectures, vol. 2015, no. 6, pp. 1–12 (2015)

22.

Woźniak, M., Marszałek, Z., Gabryel, M., Nowicki, R.K.: Preprocessing large data sets by the use of quick sort algorithm. In: Skulimowski, A.M.J., Kacprzyk, J. (eds.) Knowledge, Information and Creativity Support Systems: Recent Trends, Advances and Solutions. AISC, vol. 364, pp. 111–121. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-19090-7_9CrossRef

23.

Hayfron-Acquah, J.B., Appiah, O., Riverson, K.: Improved selection sort algorithm. Int. J. Comput. Appl. (0975–8887) 110(5), 29–33 (2015)

24.

Marszałek, Z.: Parallelization of modified merge sort algorithm. Symmetry 9(9), 176 (2017)CrossRef

25.

Khorasani, E., Paulovicks, B.D., Sheinin, V., Yeo, H.: Parallel implementation of external sort and join operations on a multi-core network-optimized system on a chip. In: Xiang, Y., Cuzzocrea, A., Hobbs, M., Zhou, W. (eds.) ICA3PP 2011. LNCS, vol. 7016, pp. 318–325. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-24650-0_27CrossRef

26.

Quartz. https://github.com/HewlettPackard/quartz. Accessed 27 Oct 2020

27.

Sort Benchmark Home Page. http://sortbenchmark.org/. Accessed 27 Oct 2020

28.

Huang, K., Li, S., Huang, L., Tan, K., Mei, H.: Lewat: a lightweight, efficient, and wear-aware transactional persistent memory system. IEEE Trans. Parallel Distrib. Syst. 32(03), 649–664 (2021)CrossRef

29.

Volos, H., Tack, A.J., Swift, M.M.: Mnemosyne: lightweight persistent memory. ACM SIGARCH Comput. Archit. News 39(1), 91–104 (2011)CrossRef

30.

Dulloor, S.R., et al.: System software for persistent memory. In: Proceedings of the Ninth European Conference on Computer Systems (2014)

31.

Xia, F., et al.: HiKV: a hybrid index key-value store for DRAM-NVM memory systems. In: 2017 USENIX Annual Technical Conference (2017)

32.

Psaropoulos, G., et al.: Bridging the latency gap between NVM and DRAM for latency-bound operations. In: Proceedings of the 15th International Workshop on Data Management on New Hardware (2019)

33.

Wan, H., et al.: Empirical study of redo and undo logging in persistent memory. In: 2016 5th Non-Volatile Memory Systems and Applications Symposium (NVMSA) (2016)

34.

Huang, Y., et al.: Closing the performance gap between volatile and persistent key-value stores using cross-referencing logs. In: 2018 USENIX Annual Technical Conference (2018)

35.

DeBrabant, J., Arulraj, J., et al.: A prolegomenon on OLTP database systems for non-volatile memory. Proc. VLDB Endow. 7(14), 57–63 (2014)

36.

Luo, Y., Chu, Z., Jin, P., Wan, S.: Efficient sorting and join on NVM-based hybrid memory. In: Qiu, M. (ed.) ICA3PP 2020, Part I. LNCS, vol. 12452, pp. 15–30. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-60245-1_2CrossRef

37.

Garcia-Molina, H., Salem, K.: Main memory database systems: an overview. IEEE Trans. Knowl. Data Eng. 4(6), 509–516 (1992)CrossRef

Titel: Redesigning the Sorting Engine for Persistent Memory
verfasst von: Yifan Hua
Kaixin Huang
Shengan Zheng
Linpeng Huang
Verlag: Springer International Publishing
Buch: Database Systems for Advanced Applications
Print ISBN: 978-3-030-73199-1

Electronic ISBN: 978-3-030-73200-4

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-3-030-73200-4_27

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"