IP Library Granted Patent US 12,353,287
Granted Patent B2
US 12,353,287 · App. 18/679,623 · Granted Jul 8, 2025

Storing encoded data slices in primary storage slots

Inventors: Ravi V. Khadiwala (Bartlett, IL); Wesley B. Leggette (Chicago, IL); Andrew D. Baptist (Mt. Pleasant, WI); Greg R. Dhuse (Chicago, IL); Ilya Volvovski (Chicago, IL); Jason K. Resch (Warwick, RI); Manish Motwani (Chicago, IL)
Assignee: Pure Storage, Inc.
G06F11/1435G06F3/0619G06F3/064G06F3/067G06F11/1076H03M13/353H04L67/1097G06F2211/1028
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,353,287
App. No.
18/679,623
Granted
Jul 8, 2025
Kind
B2
Abstract

A method for execution by one or more computing devices of a storage network includes dispersed storage error encoding a data segment of data into a set of encoded data slices in accordance with an information dispersal algorithm width number and a decode threshold number, where the decode threshold number of encoded data slices of the set of encoded data slices are needed to reconstruct the data segment. The method further includes storing the set of encoded data slices in primary storage slots of a set of storage units deployed across multiple sites of the storage network in accordance with a mapping of the primary storage slots to storage units of the set of storage units, where a number of the primary storage slots is equal to or greater than the information dispersal algorithm width number.

Claims (57)

1. A method for execution by one or more computing devices of a storage network, the method comprises:

dispersed storage error encoding a data segment of data into a set of encoded data slices in accordance with an information dispersal algorithm width number and a decode threshold number, wherein the decode threshold number of encoded data slices of the set of encoded data slices are needed to reconstruct the data segment; and

storing the set of encoded data slices in primary storage slots of a set of storage units deployed across multiple sites of the storage network in accordance with a mapping of the primary storage slots to storage units of the set of storage units, wherein a number of the primary storage slots is equal to or greater than the information dispersal algorithm width number.

2. The method of claim 1 , wherein determining the information dispersal algorithm width number comprises:

obtaining a site failure toleration goal number; and

determining the information dispersal algorithm width number based on the site failure toleration goal number and the mapping of primary storage slots to the storage units at each site such that when a number of failed sites of the multiple sites is less than or equal to the site failure toleration goal number for a particular time period, the decode threshold number of encoded data slices are available at non-failed sites of the multiple sites.

3. The method of claim 1 further comprises:

determining the number of primary storage slots from a second number of storage slots associated with the set of storage units deployed across multiple sites.

4. The method of claim 1 further comprises:

sending configuration information to the set of storage units, wherein the configuration information includes the mapping, and wherein the storing is in accordance with the configuration information.

5. The method of claim 1 , wherein determining the mapping of the primary storage slots to storage units comprises:

determining a number of storage units at each site of the multiple sites;

determining a system primary slot distribution scheme; and

determining the mapping based on the number of storage units for each site and the system primary slot distribution scheme.

6. The method of claim 1 , wherein determining the mapping of the primary storage slots to storage units comprises:

assigning, as the primary storage slots, available storage slots from each storage unit of the set of storage units at each site of the multiple sites in a substantially even distribution such that each site of the multiple sites has approximately a same number of primary storage slots.

7. The method of claim 1 , wherein the storing the set of encoded data slices comprises:

issuing write slice requests to the storage units in accordance with the mapping, wherein the write slice requests includes the set of encoded data slices.

8. The method of claim 7 further comprises:

receiving write responses from the set of storage units;

determining a failure when less than the information dispersal algorithm width number of favorable write responses are received within a response timeframe; and

in response to the determining the failure, issuing an additional write slice request to another storage slot of the number of storage slots, wherein the additional write slice request includes an encoded data slice of the set of encoded data slices associated with the failure.

9. The method of claim 8 , wherein determining the other storage slot comprises:

determining a storage unit of the set of storage units that is associated with a favorable write response of the write responses;

determining an available storage slot of the number of storage slots associated with the storage unit; and

assigning the available storage slot as the other storage slot.

10. The method of claim 8 , wherein determining the other storage slot comprises accessing a list of available storage slots.

11. A computing device of a storage network, the computing device comprises:

memory;

an interface; and

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

dispersed storage error encode a data segment of data into a set of encoded data slices in accordance with an information dispersal algorithm width number and a decode threshold number, wherein the decode threshold number of encoded data slices of the set of encoded data slices are needed to reconstruct the data segment; and

store, via the interface, the set of encoded data slices in primary storage slots of a set of storage units deployed across multiple sites of the storage network in accordance with a mapping of the primary storage slots to storage units of the set of storage units, wherein a number of the primary storage slots is equal to or greater than the information dispersal algorithm width number.

12. The computing device of claim 11 , wherein the processing module is operable to determine the information dispersal algorithm width number by:

obtaining a site failure toleration goal number; and

determining the information dispersal algorithm width number based on the site failure toleration goal number and the mapping of primary storage slots to the storage units at each site such that when a number of failed sites of the multiple sites is less than or equal to the site failure toleration goal number for a particular time period, the decode threshold number of encoded data slices are available at non-failed sites of the multiple sites.

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

determine the number of primary storage slots from a second number of storage slots associated with the set of storage units deployed across multiple sites.

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

send, via the interface, configuration information to the set of storage units, wherein the configuration information includes the mapping, and wherein the storing is in accordance with the configuration information.

15. The computing device of claim 11 , wherein 11, wherein the processing module is operable to determine the mapping of the primary storage slots to storage units by:

determining a number of storage units at each site of the multiple sites;

determining a system primary slot distribution scheme; and

determining the mapping based on the number of storage units for each site and the system primary slot distribution scheme.

16. The computing device of claim 11 , wherein the processing module is operable to determine the mapping of the primary storage slots to storage units by:

assigning, as the primary storage slots, available storage slots from each storage unit of the set of storage units at each site of the multiple sites in a substantially even distribution such that each site of the multiple sites has approximately a same number of primary storage slots.

17. The computing device of claim 11 , wherein the processing module is operable to perform the storing the set of encoded data slices by:

issuing write slice requests to the storage units in accordance with the mapping, wherein the write slice requests includes the set of encoded data slices.

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

receive, via the interface, write responses from the set of storage units;

determine a failure when less than the information dispersal algorithm width number of favorable write responses are received within a response timeframe; and

in response to the determining the failure, issue, via the interface, an additional write slice request to another storage slot of the number of storage slots, wherein the additional write slice request includes an encoded data slice of the set of encoded data slices associated with the failure.

19. The computing device of claim 18 , wherein the processing module is operable to determine the other storage slot by:

determining a storage unit of the set of storage units that is associated with a favorable write response of the write responses;

determining an available storage slot of the number of storage slots associated with the storage unit; and

assigning the available storage slot as the other storage slot.

20. The computing device of claim 18 , wherein the processing module is operable to determine the other storage slot by accessing a list of available storage slots.

Assignments (3)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 3, 2024
From: INTERNATIONAL BUSINESS MACHINES CORPORATION
To: PURE STORAGE, INC.
Reel/Frame 067607/0458 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded May 31, 2024
From: LEGGETTE, WESLEY B.; BAPTIST, ANDREW D.; DHUSE, GREG R.; VOLVOVSKI, ILYA; RESCH, JASON K.; MOTWANI, MANISH
To: PURE STORAGE, INC.
Reel/Frame 067585/0828 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded May 31, 2024
From: KHADIWALA, RAVI V.
To: INTERNATIONAL BUSINESS MACHINES CORPORATION
Reel/Frame 067585/0833 →
Continuity (7)
Continuation 18141451 · Apr 30, 2023
Continuation 17660890 · Apr 27, 2022
Continuation 16427420 · May 31, 2019
Continuation In Part 15350672 · Nov 14, 2016
Continuation 14527139 · Oct 29, 2014
Provisional Application 61924196 · Jan 6, 2014
Related Publication 20240311251A1 · Sep 19, 2024
References Cited (107)
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 7035914B1 · Payne · 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 7818518B2 · Gladwin · 2010 [cited by applicant]
US 9229824B2 · Resch · 2016 [cited by applicant]
US 9594639B2 · Khadiwala · 2017 [cited by applicant]
US 10540111B2 · Shah · 2020 [cited by applicant]
US 10592335B2 · Hegde · 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 20030028673A1 · Lin et al. · 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 · 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 20120311345A1 · Dhuse · 2012 [cited by applicant]
US 20140298134A1 · Grube · 2014 [cited by applicant]
US 20140351674A1 · Grube · 2014 [cited by applicant]
US 20230208909A1 · Brandwine · 2023 [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]