IP Library Granted Patent US 12,223,166
Granted Patent B2
US 12,223,166 · App. 18/060,431 · Granted Feb 11, 2025

Memory allocation for block rebuilding in a storage network

Inventors: Jason K. Resch (Warwick, RI); Andrew D. Baptist (Mt. Pleasant, WI); Wesley B. Leggette (Chicago, IL)
Assignee: Pure Storage, Inc.
G06F3/0604G06F3/061G06F3/0619G06F3/0635G06F3/0638G06F3/064G06F3/0644G06F3/067G06F11/1076H04L67/025H04L67/1008H04L67/1097H04L67/306H04L67/52G06F2206/1012G06F2211/1028H03M13/1515
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,223,166
App. No.
18/060,431
Granted
Feb 11, 2025
Kind
B2
Abstract

A method begins by identifying a plurality of encoded data slices requiring rebuilding. The method continues by determining an amount of memory required for rebuilding the plurality of encoded data slices and allocating memory in one or more storage units for the rebuilding the plurality of encoded data slices as reserve memory. The method continues by obtaining a plurality of rebuilt encoded data slices associated with the plurality of encoded data slices requiring rebuilding and storing the plurality of rebuilt encoded data slices in the reserve memory.

Claims (55)

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

identifying a plurality of encoded data slices requiring rebuilding;

in response to the identifying, determining an amount of memory required for rebuilding the plurality of encoded data slices;

allocating memory in one or more storage units for the rebuilding the plurality of encoded data slices as reserve memory;

obtaining a plurality of rebuilt encoded data slices, wherein the plurality of rebuilt encoded data slices are associated with the plurality of encoded data slices requiring rebuilding; and

storing the plurality of rebuilt encoded data slices in the reserve memory.

2. The method of claim 1 , further comprising:

accessing memory utilization information to identify unallocated memory associated with the one or more storage units.

3. The method of claim 2 , wherein the information sufficient to identify unallocated memory includes an amount of memory used for stored encoded data slices, an amount of memory that is unused.

4. The method of claim 1 , wherein the amount of memory required for rebuilding the plurality of encoded data slices is more than an amount of memory required for storing the plurality of encoded data slices.

5. The method of claim 1 further comprising:

designating all utilized and reserve memory as utilized.

6. The method of claim 1 , wherein identifying the plurality of encoded data slices includes at least one of:

receiving a request to rebuild a portion of a virtual memory block;

detecting a missing encoded data slice;

detecting a corrupted encoded data slice; and

monitoring downloads to memory meeting minimum read/write (R/W) threshold numbers of encoded data slices but not including a full pillar width of encoded data slices.

7. The method of claim 1 , wherein identifying the plurality of encoded data slices further comprises querying vaults related to the plurality of encoded data slices to determine one or more missing or corrupted encoded data slices.

8. The method of claim 1 , further comprising:

modifying memory utilization information to include the plurality of rebuilt encoded data slices.

9. The method of claim 8 , further comprising sending modified memory utilization information to one or more of:

a storage unit of the storage network;

a managing unit of the storage network; and

a user device.

10. The method of claim 1 , further comprising obtaining the plurality of rebuilt encoded data slices by at least one of: receiving the rebuilt encoded data slices, generating the rebuilt encoded data slices and accessing one or more other computing devices of the storage network.

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

an interface;

a local memory; and

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

identify a plurality of encoded data slices requiring rebuilding;

in response to an identification of a plurality of encoded data slices requiring rebuilding, determine an amount of memory required for rebuilding the plurality of encoded data slices;

allocate memory in one or more storage units for the rebuilding the plurality of encoded data slices as reserve memory;

obtain a plurality of rebuilt encoded data slices, wherein the plurality of rebuilt encoded data slices are associated with the plurality of encoded data slices requiring rebuilding; and

store the plurality of rebuilt encoded data slices in the reserve memory.

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

access memory utilization information to identify unallocated memory associated with the one or more storage units.

13. The computing device of claim 12 , wherein the information sufficient to identify unallocated memory includes an amount of memory used for stored encoded data slices, an amount of memory that is unused.

14. The computing device of claim 11 , wherein the amount of memory required for rebuilding the plurality of encoded data slices is more than an amount of memory required for storing the plurality of encoded data slices.

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

designate all utilized and reserve memory as utilized.

16. The computing device of claim 11 , wherein the plurality of encoded data slices are identified by at least one of:

receiving a request to rebuild a portion of a virtual memory block;

detecting a missing encoded data slice;

detecting a corrupted encoded data slice; and

monitoring downloads to memory meeting minimum read/write (R/W) threshold numbers of encoded data slices but not including a full pillar width of encoded data slices.

17. The computing device of claim 11 , wherein the plurality of encoded data slices are identified by querying vaults related to the plurality of encoded data slices to determine one or more missing or corrupted encoded data slices.

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

modify memory utilization information to include the plurality of rebuilt encoded data slices.

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

send updated memory utilization information to one or more of:

a storage unit of the storage network;

a managing unit of the storage network; and

a user device.

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

obtain the plurality of rebuilt encoded data slices by at least one of: receiving the rebuilt encoded data slices, generating the rebuilt encoded data slices and accessing one or more other computing devices of the storage network.

Assignments (2)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Dec 2, 2022
From: INTERNATIONAL BUSINESS MACHINES CORPORATION
To: PURE STORAGE, INC.
Reel/Frame 062044/0306 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Dec 1, 2022
From: RESCH, JASON K.; BAPTIST, ANDREW D.; LEGGETTE, WESLEY B.
To: INTERNATIONAL BUSINESS MACHINES CORPORATION
Reel/Frame 061939/0922 →
Continuity (6)
Continuation 16732530 · Jan 2, 2020
Continuation 15900525 · Feb 20, 2018
Continuation In Part 15345172 · Nov 7, 2016
Division 14307625 · Jun 18, 2014
Provisional Application 61860498 · Jul 31, 2013
Related Publication 20230100323A1 · Mar 30, 2023
References Cited (104)
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 8874868B2 · Baptist · 2014 [cited by applicant]
US 8996910B2 · Gladwin · 2015 [cited by applicant]
US 9026758B2 · Baptist · 2015 [cited by applicant]
US 9141307B2 · Resch · 2015 [cited by applicant]
US 9152514B2 · Resch · 2015 [cited by examiner]
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 20090254702A1 · Kumano · 2009 [cited by applicant]
US 20100023524A1 · Gladwin · 2010 [cited by applicant]
US 20110289283A1 · Baptist · 2011 [cited by applicant]
US 20120311345A1 · Dhuse · 2012 [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]