Skip to main content
Top

2019 | OriginalPaper | Chapter

Effective Local Reconstruction Codes Based on Regeneration for Large-Scale Storage Systems

Authors : Quanqing Xu, Hong Wai Ng, Weiya Xi, Chao Jin

Published in: Advances in Information and Communication Networks

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We introduce Regenerating-Local Reconstruction Codes (R-LRC) and describe their encoding and decoding techniques in this paper. After that their repair bandwidths of different failure patterns are investigated. We also explore an alternative of R-LRC, which gives R-LRC lower repair bandwidth. Since R-LRC is an extended version of Pyramid codes, optimization of repair bandwidth of a single failure will also apply to R-LRC. Compared with Pyramid Codes, Regenerating-Local Reconstruction Codes have two benefits: (1) In an average, they use around 2.833 blocks in repairing 2 failures while the Pyramid codes use about 3.667 blocks. Hence, they have lower IOs than Pyramid Codes. (2) When there are 2 failures occurring at common block group and special block group, they require only around M/2, which is lower compared with M in Pyramid codes when k ≥ 2. In addition, we present an efficient interference alignment mechanism in R-LRC, which performs algebraic alignment so that the useless and unwanted dimension is decreased. Therefore, the network bandwidth consumption is reduced.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

Literature
1.
go back to reference Huang, C., Simitci, H., Xu, Y., Ogus, A., Calder, B., Gopalan, P., Li, J., Yekhanin, S.: Erasure coding in windows azure storage. In: 2012 USENIX Annual Technical Conference, pp. 15–26 Huang, C., Simitci, H., Xu, Y., Ogus, A., Calder, B., Gopalan, P., Li, J., Yekhanin, S.: Erasure coding in windows azure storage. In: 2012 USENIX Annual Technical Conference, pp. 15–26
2.
go back to reference Sathiamoorthy, M., Asteris, M., Papailiopoulos, D.S., Dimakis, A.G., Vadali, R., Chen, S., Borthakur, D.: Xoring elephants: novel erasure codes for big data. PVLDB 6(5), 325–336 (2013) Sathiamoorthy, M., Asteris, M., Papailiopoulos, D.S., Dimakis, A.G., Vadali, R., Chen, S., Borthakur, D.: Xoring elephants: novel erasure codes for big data. PVLDB 6(5), 325–336 (2013)
3.
go back to reference Rashmi, K.V., Shah, N.B., Gu, D., Kuang, H., Borthakur, D., Ramchandran, K.: A “hitchhiker’s” guide to fast and efficient data reconstruction in erasure-coded data centers. In: ACM SIGCOMM 2014 Conference, pp. 331–342 (2014) Rashmi, K.V., Shah, N.B., Gu, D., Kuang, H., Borthakur, D., Ramchandran, K.: A “hitchhiker’s” guide to fast and efficient data reconstruction in erasure-coded data centers. In: ACM SIGCOMM 2014 Conference, pp. 331–342 (2014)
4.
go back to reference Ford, D., Labelle, F., Popovici, F.I., Stokely, M., Truong, V., Barroso, L., Grimes, C., Quinlan, S.: Availability in globally distributed storage systems. In: OSDI 2010, pp. 61–74 (2010) Ford, D., Labelle, F., Popovici, F.I., Stokely, M., Truong, V., Barroso, L., Grimes, C., Quinlan, S.: Availability in globally distributed storage systems. In: OSDI 2010, pp. 61–74 (2010)
5.
go back to reference Xu, Q., Arumugam, R.V., Yong, K.L., Mahadevan, S.: Efficient and scalable metadata management in EB-scale file systems. IEEE Trans. Parallel Distrib. Syst. 25(11), 2840–2850 (2014)CrossRef Xu, Q., Arumugam, R.V., Yong, K.L., Mahadevan, S.: Efficient and scalable metadata management in EB-scale file systems. IEEE Trans. Parallel Distrib. Syst. 25(11), 2840–2850 (2014)CrossRef
6.
go back to reference Dimakis, A.G., Godfrey, B., Wu, Y., Wainwright, M.J., Ramchandran, K.: Network coding for distributed storage systems. IEEE Trans. Inf. Theory 56(9), 4539–4551 (2010)CrossRef Dimakis, A.G., Godfrey, B., Wu, Y., Wainwright, M.J., Ramchandran, K.: Network coding for distributed storage systems. IEEE Trans. Inf. Theory 56(9), 4539–4551 (2010)CrossRef
7.
go back to reference Li, R., Lin, J., Lee, P.P.C.: CORE: augmenting regenerating coding-based recovery for single and concurrent failures in distributed storage systems. In: Proceedings of IEEE Conference on Mass Storage Systems and Technologies (MSST 2013) (2013) Li, R., Lin, J., Lee, P.P.C.: CORE: augmenting regenerating coding-based recovery for single and concurrent failures in distributed storage systems. In: Proceedings of IEEE Conference on Mass Storage Systems and Technologies (MSST 2013) (2013)
8.
go back to reference Duminuco, A., Biersack, E.: A practical study of regenerating codes for peer-to-peer backup systems. In: 29th IEEE International Conference on Distributed Computing Systems (ICDCS 2009), pp. 376–384 (2009) Duminuco, A., Biersack, E.: A practical study of regenerating codes for peer-to-peer backup systems. In: 29th IEEE International Conference on Distributed Computing Systems (ICDCS 2009), pp. 376–384 (2009)
9.
go back to reference Hu, Y., Chen, H.C.H., Lee, P.P.C., Tang, Y.: Nccloud: applying network coding for the storage repair in a cloud-of-clouds. In: FAST 2012, p. 21 (2012) Hu, Y., Chen, H.C.H., Lee, P.P.C., Tang, Y.: Nccloud: applying network coding for the storage repair in a cloud-of-clouds. In: FAST 2012, p. 21 (2012)
10.
go back to reference Gopalan, P., Huang, C., Simitci, H., Yekhanin, S.: On the locality of codeword symbols. IEEE Trans. Inf. Theory 58(11), 6925–6934 (2011)MathSciNetCrossRef Gopalan, P., Huang, C., Simitci, H., Yekhanin, S.: On the locality of codeword symbols. IEEE Trans. Inf. Theory 58(11), 6925–6934 (2011)MathSciNetCrossRef
11.
go back to reference Huang, C., Chen, M., Li, J.: Pyramid codes: flexible schemes to trade space for access efficiency in reliable data storage systems. TOS 9(1), 3 (2013)CrossRef Huang, C., Chen, M., Li, J.: Pyramid codes: flexible schemes to trade space for access efficiency in reliable data storage systems. TOS 9(1), 3 (2013)CrossRef
12.
go back to reference Xu, Q., Xi, W., Yong, K.L., Jin, C.: Concurrent regeneration code with local reconstruction in distributed storage systems. In: The 9th International Conference on Multimedia and Ubiquitous Engineering, pp. 415–422 (2015) Xu, Q., Xi, W., Yong, K.L., Jin, C.: Concurrent regeneration code with local reconstruction in distributed storage systems. In: The 9th International Conference on Multimedia and Ubiquitous Engineering, pp. 415–422 (2015)
13.
go back to reference Kamath, G.M., Prakash, N., Lalitha,V., Kumar, P.V.: Codes with local regeneration. In: Proceedings of the IEEE International Symposium on Information Theory (ISIT), Istanbul, Turkey, pp. 1606–1610, July 2013 Kamath, G.M., Prakash, N., Lalitha,V., Kumar, P.V.: Codes with local regeneration. In: Proceedings of the IEEE International Symposium on Information Theory (ISIT), Istanbul, Turkey, pp. 1606–1610, July 2013
14.
go back to reference Rawat, A.S., Koyluoglu, O.O., Silberstein, N., Vishwanath, S.: Secure locally repairable codes for distributed storage systems. In: Proceedings of the IEEE International Symposium on Information Theory (ISIT), pp. 2224–2228 (2013) Rawat, A.S., Koyluoglu, O.O., Silberstein, N., Vishwanath, S.: Secure locally repairable codes for distributed storage systems. In: Proceedings of the IEEE International Symposium on Information Theory (ISIT), pp. 2224–2228 (2013)
15.
go back to reference Wu, Y., Dimakis, A.G.: Reducing repair traffic for erasure coding-based storage via interference alignment. In: IEEE International Symposium on Information Theory, ISIT 2009, Seoul, Korea, Proceedings, 28 June–3 July 2009, pp. 2276–2280. IEEE (2009) Wu, Y., Dimakis, A.G.: Reducing repair traffic for erasure coding-based storage via interference alignment. In: IEEE International Symposium on Information Theory, ISIT 2009, Seoul, Korea, Proceedings, 28 June–3 July 2009, pp. 2276–2280. IEEE (2009)
Metadata
Title
Effective Local Reconstruction Codes Based on Regeneration for Large-Scale Storage Systems
Authors
Quanqing Xu
Hong Wai Ng
Weiya Xi
Chao Jin
Copyright Year
2019
DOI
https://doi.org/10.1007/978-3-030-03405-4_19