IP Library Granted Patent US 12,212,623
Granted Patent B2
US 12,212,623 · App. 17/808,263 · Granted Jan 28, 2025

Recovering a data chunk from a portion of a set of encoded data slices

Inventors: Jason K. Resch (Warwick, RI); Wesley B. Leggette (Chicago, IL)
Assignee: Pure Storage, Inc.
H04L67/1097G06F11/1076H03M13/611H03M13/616H04L9/08H04L9/085H04L67/1008H04L67/61G06F3/067H03M13/1515H04L47/2475H04L67/06
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,212,623
App. No.
17/808,263
Granted
Jan 28, 2025
Kind
B2
Abstract

A method for execution by a computing device of a storage network includes obtaining at least a “T” number of encoded data slices of a set of encoded data slices, where a plurality of data chunks are all-or-nothing encoded in accordance with distributed data storage parameters to produce the set of encoded data slices. The method further includes decoding a first section of the at least the “T” number of encoded data slices to recover a first data chunk of a plurality of data chunks. The method further includes decoding a second section of the at least the “T” number of encoded data slices to recover a second data chunk of the plurality of data chunks.

Claims (45)

1. A method for execution by a computing device of a storage network, the method comprising:

obtaining only a first section of each of at least a “T” number of encoded data slices of a set of encoded data slices, wherein a plurality of data chunks are all-or-nothing (AONT) encoded in accordance with distributed data storage parameters to produce the set of encoded data slices, wherein the at least the “T” number of encoded data slices include a plurality of sections, and wherein the plurality of sections includes the first sections; and

decoding the first sections of the at least the “T” number of encoded data slices to recover a first data chunk of the plurality of data chunks.

2. The method of claim 1 further comprises:

obtaining a second section of each of at least a second “T” number of encoded data slices of the set of encoded data slices, wherein the at least the second “T” number of encoded data slices include a second plurality of sections, and wherein the second plurality of sections includes the second sections;

decoding the second sections of the at least the second “T” number of encoded data slices to recover a second data chunk of the plurality of data chunks; and

recovering, in accordance with the distributed data storage parameters, a data segment based on the recovered first and second data chunks.

3. The method of claim 1 further comprises:

obtaining a second section of each of the at least the “T” number of encoded data slices; and

decoding second sections of the at least the “T” number of encoded data slices to recover a second data chunk of the plurality of data chunks.

4. The method of claim 3 further comprises:

recovering, in accordance with the distributed data storage parameters, a data segment based on the recovered first and second data chunks.

5. The method of claim 1 , wherein the decoding the first sections further comprises:

matrix multiplying the “T” number of encoded data slices with a decoding matrix to produce a data matrix; and

reconstructing the first data chunk from the data matrix.

6. The method of claim 5 , wherein the data matrix includes a plurality of sets of AONT encoded data pieces.

7. The method of claim 6 further comprises:

rearranging a first set of AONT encoded data pieces of the plurality of sets of AONT encoded data pieces to produce the first data chunk.

8. The method of claim 7 further comprises:

rearranging a second set of AONT encoded data pieces of the plurality of sets of AONT encoded data pieces to produce a second data chunk.

9. The method of claim 1 , wherein the distributed data storage parameters include the “T” number and an “R” number of encoded data slices to be included in the set of encoded data slices, and wherein the “R” number is greater than the “T” number.

10. A computing device of a storage network comprises:

memory;

an interface; and

a processing module, wherein the memory and the interface are operably coupled to the processing module, wherein the processing module is operable to:

obtain only a first section of each of at least a “T” number of encoded data slices of a set of encoded data slices, wherein a plurality of data chunks are all-or-nothing (AONT) encoded in accordance with distributed data storage parameters to produce the set of encoded data slices, wherein the at least the “T” number of encoded data slices include a plurality of sections, and wherein the plurality of sections includes the first sections; and

decode the first sections of the at least the “T” number of encoded data slices to recover a first data chunk of the plurality of data chunks.

11. The computing device of claim 10 , wherein the processing module is further operable to:

obtain a second section of each of at least a second “T” number of encoded data slices of the set of encoded data slices, wherein the at least the second “T” number of encoded data slices include a second plurality of sections, and wherein the second plurality of sections includes the second sections;

decode the second sections of the at least the second “T” number of encoded data slices to recover a second data chunk of the plurality of data chunks; and

recover, in accordance with the distributed data storage parameters, a data segment based on the recovered first and second data chunks.

12. The computing device of claim 10 , wherein the processing module is further operable to:

obtain a second section of each of the at least the “T” number of encoded data slices; and

decode the second sections of the at least the “T” number of encoded data slices to recover a second data chunk of the plurality of data chunks.

13. The computing device of claim 10 , wherein the processing module is further operable to:

recover, in accordance with the distributed data storage parameters, a data segment based on the recovered first and second data chunks.

14. The computing device of claim 10 , wherein the processing module is further operable to decode the first sections by:

matrix multiplying the “T” number of encoded data slices with a decoding matrix to produce a data matrix; and

reconstructing the first data chunk from the data matrix.

15. The computing device of claim 14 , wherein the data matrix includes a plurality of sets of AONT encoded data pieces.

16. The computing device of claim 15 , wherein the processing module is further operable to:

rearranging a first set of AONT encoded data pieces of the plurality of sets of AONT encoded data pieces to produce the first data chunk.

17. The computing device of claim 16 , wherein the processing module is further operable to:

rearranging a second set of AONT encoded data pieces of the plurality of sets of AONT encoded data pieces to produce a second data chunk.

18. The computing device of claim 10 , wherein the distributed data storage parameters include the “T” number and an “R” number of encoded data slices to be included in the set of encoded data slices, and wherein the “R” number is greater than the “T” number.

Assignments (2)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 23, 2022
From: RESCH, JASON K.; LEGGETTE, WESLEY B.
To: INTERNATIONAL BUSINESS MACHINES CORPORATION
Reel/Frame 060284/0667 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 23, 2022
From: INTERNATIONAL BUSINESS MACHINES CORPORATION
To: PURE STORAGE, INC.
Reel/Frame 060435/0352 →
Continuity (8)
Continuation 16989043 · Aug 10, 2020
Continuation 15823171 · Nov 27, 2017
Continuation In Part 15688162 · Aug 28, 2017
Continuation In Part 14153319 · Jan 13, 2014
Continuation In Part 12838407 · Jul 16, 2010
Provisional Application 61769588 · Feb 26, 2013
Provisional Application 61256226 · Oct 29, 2009
Related Publication 20220321653A1 · Oct 6, 2022
References Cited (110)
US 4092732A · Ouchi · 1978 [cited by applicant]
US 5454101A · Mackay · 1995 [cited by applicant]
US 5485474A · Rabin · 1996 [cited by applicant]
US 5774643A · Lubbers · 1998 [cited by applicant]
US 5802364A · Senator · 1998 [cited by applicant]
US 5809285A · Hilland · 1998 [cited by applicant]
US 5890156A · Rekieta · 1999 [cited by applicant]
US 5987622A · Lo Verso · 1999 [cited by applicant]
US 5991414A · Garay · 1999 [cited by applicant]
US 6012159A · Fischer · 2000 [cited by applicant]
US 6058454A · Gerlach · 2000 [cited by applicant]
US 6128277A · Bruck · 2000 [cited by applicant]
US 6175571B1 · Haddock · 2001 [cited by applicant]
US 6192472B1 · Garay · 2001 [cited by applicant]
US 6256688B1 · Suetaka · 2001 [cited by applicant]
US 6272658B1 · Steele · 2001 [cited by applicant]
US 6301604B1 · Nojima · 2001 [cited by applicant]
US 6356949B1 · Katsandres · 2002 [cited by applicant]
US 6366995B1 · Nikolaevich · 2002 [cited by applicant]
US 6374336B1 · Peters · 2002 [cited by applicant]
US 6415373B1 · Peters · 2002 [cited by applicant]
US 6418539B1 · Walker · 2002 [cited by applicant]
US 6449688B1 · Peters · 2002 [cited by applicant]
US 6567948B2 · Steele · 2003 [cited by applicant]
US 6571282B1 · Bowman-Amuah · 2003 [cited by applicant]
US 6609223B1 · Wolfgang · 2003 [cited by applicant]
US 6718361B1 · Basani · 2004 [cited by applicant]
US 6760808B2 · Peters · 2004 [cited by applicant]
US 6785768B2 · Peters · 2004 [cited by applicant]
US 6785783B2 · Buckland · 2004 [cited by applicant]
US 6826711B2 · Moulton · 2004 [cited by applicant]
US 6879596B1 · Dooply · 2005 [cited by applicant]
US 7003688B1 · Pittelkow · 2006 [cited by applicant]
US 7024451B2 · Jorgenson · 2006 [cited by applicant]
US 7024609B2 · Wolfgang · 2006 [cited by applicant]
US 7080101B1 · Watson · 2006 [cited by applicant]
US 7103824B2 · Halford · 2006 [cited by applicant]
US 7103915B2 · Redlich · 2006 [cited by applicant]
US 7111115B2 · Peters · 2006 [cited by applicant]
US 7140044B2 · Redlich · 2006 [cited by applicant]
US 7146644B2 · Redlich · 2006 [cited by applicant]
US 7171493B2 · Shu · 2007 [cited by applicant]
US 7222133B1 · Raipurkar · 2007 [cited by applicant]
US 7240236B2 · Cutts · 2007 [cited by applicant]
US 7272613B2 · Sim · 2007 [cited by applicant]
US 7636724B2 · de la Torre · 2009 [cited by applicant]
US 8327141B2 · Vysogorets · 2012 [cited by applicant]
US 9292700B2 · Parker · 2016 [cited by applicant]
US 10757187B2 · Resch · 2020 [cited by applicant]
US 20020062422A1 · Butterworth · 2002 [cited by applicant]
US 20020166079A1 · Ulrich · 2002 [cited by applicant]
US 20030018927A1 · Gadir · 2003 [cited by applicant]
US 20030037261A1 · Meffert · 2003 [cited by applicant]
US 20030065617A1 · Watkins · 2003 [cited by applicant]
US 20030084020A1 · Shu · 2003 [cited by applicant]
US 20040024963A1 · Talagala · 2004 [cited by applicant]
US 20040122917A1 · Menon · 2004 [cited by applicant]
US 20040215998A1 · Buxton · 2004 [cited by applicant]
US 20040228493A1 · Ma · 2004 [cited by applicant]
US 20050100022A1 · Ramprashad · 2005 [cited by applicant]
US 20050114594A1 · Corbett · 2005 [cited by applicant]
US 20050125593A1 · Karpoff · 2005 [cited by applicant]
US 20050131993A1 · Fatula, Jr. · 2005 [cited by applicant]
US 20050132070A1 · Redlich · 2005 [cited by applicant]
US 20050144382A1 · Schmisseur · 2005 [cited by applicant]
US 20050229069A1 · Hassner · 2005 [cited by applicant]
US 20060047907A1 · Shiga · 2006 [cited by applicant]
US 20060136448A1 · Cialini · 2006 [cited by applicant]
US 20060156059A1 · Kitamura · 2006 [cited by applicant]
US 20060224603A1 · Correll, Jr. · 2006 [cited by applicant]
US 20070079081A1 · Gladwin · 2007 [cited by applicant]
US 20070079082A1 · Gladwin · 2007 [cited by applicant]
US 20070079083A1 · Gladwin · 2007 [cited by applicant]
US 20070088970A1 · Buxton · 2007 [cited by applicant]
US 20070174192A1 · Gladwin · 2007 [cited by applicant]
US 20070214285A1 · Au · 2007 [cited by applicant]
US 20070234110A1 · Soran · 2007 [cited by applicant]
US 20070283167A1 · Venters, III · 2007 [cited by applicant]
US 20090094251A1 · Gladwin · 2009 [cited by applicant]
US 20090094318A1 · Gladwin · 2009 [cited by applicant]
US 20100023524A1 · Gladwin · 2010 [cited by applicant]
US 20100228906A1 · Ramiya Mothilal · 2010 [cited by applicant]
US 20100268966A1 · Leggette et al. · 2010 [cited by applicant]
US 20100299313A1 · Orsini · 2010 [cited by applicant]
US 20110107036A1 · Resch · 2011 [cited by applicant]
US 20110107112A1 · Resch · 2011 [cited by applicant]
US 20110182424A1 · Grube · 2011 [cited by examiner]
US 20110246766A1 · Orsini · 2011 [cited by applicant]
US 20120166576A1 · O'Hare · 2012 [cited by applicant]
US 20120254562A1 · Morrison · 2012 [cited by applicant]
US 20180351731A1 · Karame · 2018 [cited by applicant]
US 20220321653A1 · Resch · 2022 [cited by examiner]
Chung; An Automatic Data Segmentation Method for 3D Measured Data Points; National Taiwan University; pp. 1-8; 1998. [cited by applicant]
Harrison; Lightweight Directory Access Protocol (LDAP): Authentication Methods and Security Mechanisms; IETF Network Working Group; RFC 4513; Jun. 2006; pp. 1-32. [cited by applicant]
Kubiatowicz, et al.; OceanStore: An Architecture for Global-Scale Persistent Storage; Proceedings of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 20… [cited by applicant]
LEGG; Lightweight Directory Access Protocol (LDAP): Syntaxes and Matching Rules; IETF Network Working Group; RFC 4517; Jun. 2006; pp. 1-50. [cited by applicant]
Plank, T1: Erasure Codes for Storage Applications; FAST2005, 4th Usenix Conference on File Storage Technologies; Dec. 13-16, 2005; pp. 1-74. [cited by applicant]
Rabin; Efficient Dispersal of Information for Security, Load Balancing, and Fault Tolerance; Journal of the Association for Computer Machinery; vol. 36, No. 2; Apr. 1989; pp. 335-348. [cited by applicant]
Satran, et al.; Internet Small Computer Systems Interface (iSCSI); IETF Network Working Group; RFC 3720; Apr. 2004; pp. 1-257. [cited by applicant]
Sciberras; Lightweight Directory Access Protocol (LDAP): Schema for User Applications; IETF Network Working Group; RFC 4519; Jun. 2006; pp. 1-33. [cited by applicant]
Sermersheim; Lightweight Directory Access Protocol (LDAP): The Protocol; IETF Network Working Group; RFC 4511; Jun. 2006; pp. 1-68. [cited by applicant]
Shamir; How to Share a Secret; Communications of the ACM; vol. 22, No. 11; Nov. 1979; pp. 612-613. [cited by applicant]
Smith; Lightweight Directory Access Protocol (LDAP): Uniform Resource Locator; IETF Network Working Group; RFC 4516; Jun. 2006; pp. 1-15. [cited by applicant]
Smith; Lightweight Directory Access Protocol (LDAP): String Representation of Search Filters; IETF Network Working Group; RFC 4515; Jun. 2006; pp. 1-12. [cited by applicant]
WILDI; Java iSCSi Initiator; Master Thesis; Department of Computer and Information Science, University of Konstanz; Feb. 2007; 60 pgs. [cited by applicant]
Xin, et al.; Evaluation of Distributed Recovery in Large-Scale Storage Systems; 13th IEEE International Symposium on High Performance Distributed Computing; Jun. 2004; pp. 172-181. [cited by applicant]
Zeilenga; Lightweight Directory Access Protocol (LDAP): Directory Information Models; IETF Network Working Group; RFC 4512; Jun. 2006; pp. 1-49. [cited by applicant]
Zeilenga; Lightweight Directory Access Protocol (LDAP): Internationalized String Preparation; IETF Network Working Group; RFC 4518; Jun. 2006; pp. 1-14. [cited by applicant]
Zeilenga; Lightweight Directory Access Protocol (LDAP): String Representation of Distinguished Names; IETF Network Working Group; RFC 4514; Jun. 2006; pp. 1-15. [cited by applicant]
Zeilenga; Lightweight Directory Access Protocol (LDAP): Technical Specification Road Map; IETF Network Working Group; RFC 4510; Jun. 2006; pp. 1-8. [cited by applicant]