Skip to main content
Erschienen in: Distributed and Parallel Databases 3/2015

01.09.2015

Optimizing B+-tree for hybrid storage systems

verfasst von: Peiquan Jin, Puyuan Yang, Lihua Yue

Erschienen in: Distributed and Parallel Databases | Ausgabe 3/2015

Einloggen

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

search-config
loading …

Abstract

Flash-memory-based solid state drives (SSD) have been widely used in computer systems. Due to the high price and some specific features of SSD such as asymmetric read/write speeds and limited erasure endurance, it has been a very common solution, e.g., in modern data centers, to use hybrid storage systems involving SSD and traditional hard disks (HDD). However, the SSD/HDD-based hybrid storage systems introduce some new problems in the indexing schemes for data management. In this paper, we propose a new B+-tree-based index for such hybrid storage systems, which is called HybridB tree. The HybridB tree aims to reduce the random writes to SSD while keeping high time performance and low buffer costs. Particularly, we introduce a new design called huge leaf to avoid the splits and merges on B+-tree. A huge leaf node contains two or more leaf nodes in different states. We place the leaf nodes on HDD or SSD according to their current states, and dynamically adapt the states of leaf nodes when they are read or updated. After a detailed explanation on the structure and operations of the HybridB tree, we give a theoretical analysis on the costs of the HybridB tree. Then, we conduct experiments on two TPC-C traces, using a real hybrid storage system including one HDD and two SSDs, and compare the performance of our proposal with two implementations of B+-tree, namely the B+-tree on HDD and the B+-tree on SSD/HDD. The results show that our proposal has the best time performance and the fewest buffer costs. Moreover, our proposal is able to effectively reduce the random writes to SSD.

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!

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!

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!

Literatur
1.
Zurück zum Zitat Levandoski, J.J., Sengupta, S.: The BW-tree: a latch-free B-tree for log-structured flash storage [J]. IEEE Data Eng. Bull. 36(2), 56–62 (2013) Levandoski, J.J., Sengupta, S.: The BW-tree: a latch-free B-tree for log-structured flash storage [J]. IEEE Data Eng. Bull. 36(2), 56–62 (2013)
2.
Zurück zum Zitat Wu, C.-H., Lin, Y.-H.: A concurrency buffer control in B-trees for flash-memory storage systems [J]. Embed. Syst. Lett. 4(1), 9–12 (2012)CrossRef Wu, C.-H., Lin, Y.-H.: A concurrency buffer control in B-trees for flash-memory storage systems [J]. Embed. Syst. Lett. 4(1), 9–12 (2012)CrossRef
3.
Zurück zum Zitat Roh, H., Park, S., Kim, S., Shin, M., Lee, S.-W.: B+-tree index optimization by exploiting internal parallelism of flash-based solid state drives [J]. Proc. VLDB Endow. 5(4), 286–297 (2011)CrossRef Roh, H., Park, S., Kim, S., Shin, M., Lee, S.-W.: B+-tree index optimization by exploiting internal parallelism of flash-based solid state drives [J]. Proc. VLDB Endow. 5(4), 286–297 (2011)CrossRef
4.
Zurück zum Zitat Havasi, F.: An improved B+ tree for flash file systems [C]. Proceedings of SOFSEM, pp. 297–307. Springer, Berlin (2011) Havasi, F.: An improved B+ tree for flash file systems [C]. Proceedings of SOFSEM, pp. 297–307. Springer, Berlin (2011)
5.
Zurück zum Zitat Chen, S.: FlashLogging: exploiting flash devices for synchronous logging performance [C]. Proceedings of SIGMOD, pp. 73–86 (2009) Chen, S.: FlashLogging: exploiting flash devices for synchronous logging performance [C]. Proceedings of SIGMOD, pp. 73–86 (2009)
6.
Zurück zum Zitat Graefe, G.: Integrating flash devices [J]. Commun. ACM 52(4), 97 (2009)CrossRef Graefe, G.: Integrating flash devices [J]. Commun. ACM 52(4), 97 (2009)CrossRef
7.
Zurück zum Zitat Lv, Y., Cui, B., Chen, X., Li, J.: Hotness-aware buffer management for flash-based hybrid storage systems [C]. Proceedings of of CIKM, pp. 1631–1636 (2013) Lv, Y., Cui, B., Chen, X., Li, J.: Hotness-aware buffer management for flash-based hybrid storage systems [C]. Proceedings of of CIKM, pp. 1631–1636 (2013)
8.
Zurück zum Zitat Liu, X., Salem, K.: Hybrid storage management for database systems [J]. Proc. VLDB Endow. 6(8), 541–552 (2013)CrossRef Liu, X., Salem, K.: Hybrid storage management for database systems [J]. Proc. VLDB Endow. 6(8), 541–552 (2013)CrossRef
9.
Zurück zum Zitat Koltsidas, I., Viglas, S.: Flashing up the storage layer [J]. Proc. VLDB Endow. 1(1), 514–525 (2008)CrossRef Koltsidas, I., Viglas, S.: Flashing up the storage layer [J]. Proc. VLDB Endow. 1(1), 514–525 (2008)CrossRef
10.
Zurück zum Zitat Yang, P., Jin, P., Yue, L.: Hybrid storage with disk based write cache [C], Proceedings of DASFAA Workshops, pp. 264–275 (2011) Yang, P., Jin, P., Yue, L.: Hybrid storage with disk based write cache [C], Proceedings of DASFAA Workshops, pp. 264–275 (2011)
11.
Zurück zum Zitat Cui, K., Jin, P., Yue, L.: HashTree: a new hybrid index for flash disks [C]. Proceedings of APWeb, pp. 45–51 (2010) Cui, K., Jin, P., Yue, L.: HashTree: a new hybrid index for flash disks [C]. Proceedings of APWeb, pp. 45–51 (2010)
12.
Zurück zum Zitat Agrawal, D., Ganesan, D., Sitaraman, R.K., Diao, Y., Singh, S.: Lazy-adaptive tree: an optimized index structure for flash devices [J]. Proc. VLDB Endow. 2(1), 361–372 (2009)CrossRef Agrawal, D., Ganesan, D., Sitaraman, R.K., Diao, Y., Singh, S.: Lazy-adaptive tree: an optimized index structure for flash devices [J]. Proc. VLDB Endow. 2(1), 361–372 (2009)CrossRef
13.
Zurück zum Zitat Li, Y., He, B., Yang, J., Luo, Q., Yi, K.: Tree indexing on solid state drives [J]. Proc. VLDB Endow. 3(1), 1195–1206 (2010)CrossRef Li, Y., He, B., Yang, J., Luo, Q., Yi, K.: Tree indexing on solid state drives [J]. Proc. VLDB Endow. 3(1), 1195–1206 (2010)CrossRef
14.
Zurück zum Zitat Li, Y., He, B., Luo, Q., Yi, K.: Tree indexing on flash disks [C]. Proceedings of ICDE, pp. 1303–1306 (2009) Li, Y., He, B., Luo, Q., Yi, K.: Tree indexing on flash disks [C]. Proceedings of ICDE, pp. 1303–1306 (2009)
15.
Zurück zum Zitat Nath, S., Kansal, A.: FlashDB: dynamic self-tuning database for NAND Flash [C]. Procedings of IPSN, pp. 410–419 (2007) Nath, S., Kansal, A.: FlashDB: dynamic self-tuning database for NAND Flash [C]. Procedings of IPSN, pp. 410–419 (2007)
16.
Zurück zum Zitat Canim, M., Mihaila, G.A., Bhattacharjee, B., Ross, K.A., Lang, C.A.: SSD bufferpool extensions for database systems [J]. Proc. VLDB Endow. 3(2), 1435–1446 (2010)CrossRef Canim, M., Mihaila, G.A., Bhattacharjee, B., Ross, K.A., Lang, C.A.: SSD bufferpool extensions for database systems [J]. Proc. VLDB Endow. 3(2), 1435–1446 (2010)CrossRef
17.
Zurück zum Zitat Soundararajan, G., Prabhakaran, V., Balakrishnan, M., Wobber, T.: Extending SSD lifetimes with disk-based write caches [C]. Proceedings of FAST, pp. 101–114 (2010) Soundararajan, G., Prabhakaran, V., Balakrishnan, M., Wobber, T.: Extending SSD lifetimes with disk-based write caches [C]. Proceedings of FAST, pp. 101–114 (2010)
18.
Zurück zum Zitat Viglas, S.: Adapting the B +-tree for asymmetric I/O [C]. Proceedings of ADBIS, pp. 399–412 (2012) Viglas, S.: Adapting the B +-tree for asymmetric I/O [C]. Proceedings of ADBIS, pp. 399–412 (2012)
19.
Zurück zum Zitat Roh, H., Kim, W.-C., Kim, S.-W., Park, S.: A B-tree index extension to enhance response time and the life cycle of flash memory [J]. Inf. Sci. 179(18), 3136–3161 (2009)MathSciNetCrossRef Roh, H., Kim, W.-C., Kim, S.-W., Park, S.: A B-tree index extension to enhance response time and the life cycle of flash memory [J]. Inf. Sci. 179(18), 3136–3161 (2009)MathSciNetCrossRef
20.
Zurück zum Zitat Lu, K., Jin, P., Yang, P., Wan, S., Yue, L.: Adaptive in-page logging for flash-memory storage systems [J]. Front. Comput. Sci. 8(1), 131–144 (2014)MathSciNetCrossRef Lu, K., Jin, P., Yang, P., Wan, S., Yue, L.: Adaptive in-page logging for flash-memory storage systems [J]. Front. Comput. Sci. 8(1), 131–144 (2014)MathSciNetCrossRef
21.
Zurück zum Zitat Zhao, H., Jin, P., Yang, P., Yue, L.: BPCLC: an efficient write buffer management scheme for flash-based solid state disks [J]. Int. J. Digit. Contents Appl. 4(6), 123–133 (2010) Zhao, H., Jin, P., Yang, P., Yue, L.: BPCLC: an efficient write buffer management scheme for flash-based solid state disks [J]. Int. J. Digit. Contents Appl. 4(6), 123–133 (2010)
22.
Zurück zum Zitat Bonnet, P., Bouganim, L., Koltsidas, I., Viglas, S.: System co-design and data management for flash devices [J]. Proc. VLDB Endow. 4(12), 1504–1505 (2011) Bonnet, P., Bouganim, L., Koltsidas, I., Viglas, S.: System co-design and data management for flash devices [J]. Proc. VLDB Endow. 4(12), 1504–1505 (2011)
Metadaten
Titel
Optimizing B+-tree for hybrid storage systems
verfasst von
Peiquan Jin
Puyuan Yang
Lihua Yue
Publikationsdatum
01.09.2015
Verlag
Springer US
Erschienen in
Distributed and Parallel Databases / Ausgabe 3/2015
Print ISSN: 0926-8782
Elektronische ISSN: 1573-7578
DOI
https://doi.org/10.1007/s10619-014-7157-7

Weitere Artikel der Ausgabe 3/2015

Distributed and Parallel Databases 3/2015 Zur Ausgabe