Apportioning namespace ranges in accordance with dispersed storage unit capacity

• US 10,365,968 B2
• Filed: 10/21/2016
• Issued: 07/30/2019
• Est. Priority Date: 10/30/2015
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Motwani, Manish
• Primary Examiner(s): Talukdar, Arvind
• Application Number:
  US15/331,504
• Publication Number:
  US 20170123976A1
• Time in Patent Office: 1,012 Days
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 11/1096 Parity calculation or recalculation after configuration or reconfiguration of the system
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 12/0646 Configuration or reconfiguration
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency ensuring consistency in mirrored systems G06F11/2064
• CPC Class Codes: G06F 2212/1008 Correctness of operation, e.g. memory ordering
• CPC Class Codes: G06F 2212/657 Virtual address space management
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0622 in relation to access
• CPC Class Codes: G06F 3/0623 in relation to content
• CPC Class Codes: G06F 3/0635 by changing the path, e.g. traffic rerouting, path reconfiguration
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 9/4856 resumption being on a different machine, e.g. task migration, virtual machine migration G06F9/5088 takes precedence
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• CPC Class Codes: H04L 41/0816 : the condition being an adaptation, e.g. in response to network events
• CPC Class Codes: H04L 47/803 : Application aware
• CPC Class Codes: H04L 63/0428 : wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/0457 : wherein the sending and receiving network entities apply dynamic encryption, e.g. stream encryption cryptographic mechanisms or cryptographic arrangements for stream encryption H04L9/065
• CPC Class Codes: H04L 63/06 : for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• CPC Class Codes: H04L 63/068 : using time-dependent keys, e.g. periodically changing keys cryptographic mechanisms or cryptographic arrangements for controlling usage of secret information H04L9/088
• CPC Class Codes: H04L 63/08 : for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 63/101 : Access control lists [ACL]
• CPC Class Codes: H04L 67/1097 : for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 9/0861 : Generation of secret information including derivation or calculation of cryptographic keys or passwords
• CPC Class Codes: H04L 9/14 : using a plurality of keys or algorithms

Abstract

A method for execution by a computing device of a dispersed storage network (DSN) to generate memory mapping of logical DSN addresses to storage units of the DSN. The method begins by equally dividing a namespace among groups of storage units of the DSN to produce a set of namespace sections. The method continues by for a first group of storage units, determining storage capacity for each storage unit of the first group of storage units, determining a total storage capacity for the first group of storage units, for a storage unit of a first group of storage units, determining a namespace fraction based on the storage capacity of the storage unit of the first group of storage units and on the total storage capacity and allocating a portion of the first namespace section based on the namespace fraction to the storage unit of the first group of storage units.

Claims

1. A method for execution by a computing device of a dispersed storage network (DSN) to generate a memory mapping of logical DSN addresses to storage units of the DSN, the method comprises:

identifying, by the computing device, a total number of names in a DSN namespace of a plurality of DSN namespaces of the DSN;

equally dividing, by the computing device, the DSN namespace among groups of storage units of the DSN to produce a set of namespace sections, wherein the DSN namespace represents a range of the logical DSN addresses, wherein a first group of storage units of the groups of storage units is allocated a first namespace section of the set of namespace sections and a second group of storage units of the groups of storage units is allocated a second namespace section of the set of namespace sections, wherein data is dispersed storage error encoded into pluralities of sets of encoded data slices in accordance with dispersed data storage parameters that include a pillar width number and a decode threshold number, wherein a number of the groups of storage units is equal to or greater than the decode threshold number, and wherein the first namespace section is responsible for storing encoded data slices of the pluralities of sets of encoded data slices having a first pillar number and the second namespace section is responsible for storing encoded data slices of the pluralities of sets of encoded data slices having a second pillar number;

for the first group of storage units;

determining, by the computing device, storage capacity for each storage unit of the first group of storage units;

determining, by the computing device, a total storage capacity for the first group of storage units based on the storage capacity for each storage unit;

individually dividing, by the computing device, the first namespace section into a first set of namespace fractions based on the storage capacity for each storage unit and the total storage capacity;

allocating, by the computing device, a namespace fraction of the first set of namespace fractions to each storage unit of the first group of storage units, wherein the first group of storage units process access requests regarding the encoded data slices having the first pillar number; and

for the second group of storage units;

determining, by the computing device, a second storage capacity for each storage unit of the second group of storage units;

determining, by the computing device, a second total storage capacity for the second group of storage units based on the second storage capacity for each storage unit;

individually dividing, by the computing device, the second namespace section into a second set of namespace fractions based on the second storage capacity for each storage unit and the second total storage capacity;

allocating, by the computing device, a namespace fraction of the second set of namespace fractions to each storage unit of the second group of storage units, wherein the second group of storage units process access requests regarding the encoded data slices having the second pillar number.

2. The method of claim 1 further comprises:

determining to generate or update the memory mapping in response to an addition, deletion, or replacement of a storage unit to the DSN.

3. The method of claim 1 further comprises:

writing the pluralities of sets of encoded data slices to the groups of storage units in accordance with corresponding pillar numbers of the encoded data slices of the pluralities of sets of encoded data slices.

4. The method of claim 1, wherein the determining storage capacity for each storage unit of the first group of storage units comprises:

determining first physical memory size of a first storage unit of the first group of storage units;

determining second physical memory size of a second storage unit of the first group of storage units; and

determining third physical memory size of a third storage unit of the first group of storage units.

5. The method of claim 4, wherein the determining the total storage capacity for the first group of storage units comprises:

adding the first, second, and third physical memory sizes to produce the total storage capacity.

6. The method of claim 5 further comprises:

dividing the first physical memory size by the total storage capacity to produce the namespace fraction for the first storage unit; and

dividing the second physical memory size by the total storage capacity to produce the namespace fraction for the second storage unit; and

dividing the third physical memory size by the total storage capacity to produce the namespace fraction for the third storage unit.

7. The method of claim 1 further comprises:

for a third group of storage units of the groups of storage units that is allocated a third namespace section of the set of namespace sections;

determining, by the computing device, a third storage capacity for each storage unit of the third group of storage units;

determining, by the computing device, a third total storage capacity for the third group of storage units based on the third storage capacity for each storage unit;

individually dividing, by the computing device, the third namespace section into a third set of namespace fractions based on the third storage capacity for each storage unit and the third total storage capacity

allocating, by the computing device, a namespace fraction of the third set of namespace fractions to each storage unit of the third group of storage units, wherein the third group of storage units process access requests regarding the encoded data slices having the third pillar number.

8. The method of claim 1, wherein the determining the storage capacity for each storage unit of the first group of storage units comprises:

sending a first request to a first storage unit of the first group of storage units regarding the storage capacity of the first storage unit; and

sending a second request to a second storage unit of the first group of storage units regarding the storage capacity of the second storage unit.

9. A computing device of a dispersed storage network (DSN), the computing device comprises:

an interface;

memory; and

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

generate a memory mapping of logical DSN addresses to storage units of the DSN by;

identifying a total number of names in a DSN namespace of a plurality of DSN namespaces of the DSN;

equally dividing the DSN namespace among groups of storage units of the DSN to produce a set of namespace sections, wherein the namespace represents a range of the logical DSN addresses, wherein a first group of storage units of the groups of storage units is allocated a first namespace section of the set of namespace sections and a second group of storage units of the groups of storage units is allocated a second namespace section of the set of namespace sections, wherein data is dispersed storage error encoded into pluralities of sets of encoded data slices in accordance with dispersed data storage parameters that include a pillar width number and a decode threshold number, wherein a number of the groups of storage units is equal to or greater than the decode threshold number, and wherein the first namespace section is responsible for storing encoded data slices of the pluralities of sets of encoded data slices having a first pillar number and the second namespace section is responsible for storing encoded data slices of the pluralities of sets of encoded data slices having a second pillar number;

for the first group of storage units;

determining storage capacity for each storage unit of the first group of storage units;

determining a total storage capacity for the first group of storage units based on the storage capacity for each storage unit;

individually dividing, by the computing device, the first namespace section into a first set of namespace fractions based on the storage capacity for each storage unit and the total storage capacity

allocating a namespace fraction of the first set of namespace fractions to each storage unit of the first group of storage units, wherein the first group of storage units process access requests regarding the encoded data slices having the first pillar number; and

for the second group of storage units;

determining a second storage capacity for each storage unit of the second group of storage units;

determining a second total storage capacity for the second group of storage units based on the second storage capacity for each storage unit;

individually dividing, by the computing device, the second namespace section into a second set of namespace fractions based on the second storage capacity for each storage unit and the second total storage capacity;

allocating a second namespace fraction of the second set of namespace fractions to each storage unit of the second group of storage units, wherein the second group of storage units process access requests regarding the encoded data slices having the second pillar number.

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

determine to generate or update the memory mapping in response to an addition, deletion, or replacement of a storage unit to the DSN.

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

write the pluralities of sets of encoded data slices to the groups of storage units in accordance with corresponding pillar numbers of the encoded data slices of the pluralities of sets of encoded data slices.

12. The computing device of claim 9, wherein the processing module is further operable to determine the storage capacity for each storage unit of the first group of storage units by:

determining first physical memory size of a first storage unit of the first group of storage units;

determining second physical memory size of a second storage unit of the first group of storage units; and

determining third physical memory size of a third storage unit of the first group of storage units.

13. The computing device of claim 12, wherein the processing module is further operable to determine the total storage capacity for the first group of storage units by:

adding the first, second, and third physical memory sizes to produce the total storage capacity.

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

divide the first physical memory size by the total storage capacity to produce the namespace fraction for the first storage unit; and

divide the second physical memory size by the total storage capacity to produce the namespace fraction for the second storage unit; and

divide the third physical memory size by the total storage capacity to produce the namespace fraction for the third storage unit.

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

for a third group of storage units of the groups of storage units that is allocated a third namespace section of the set of namespace sections;

determine a third storage capacity for each storage unit of the third group of storage units;

determine a third total storage capacity for the third group of storage units based on the third storage capacity for each storage unit;

individually dividing, by the computing device, the third namespace section into a third set of namespace fractions based on the third storage capacity for each storage unit and the third total storage capacity;

allocate a namespace fraction of the third set of namespace fractions to each storage unit of the third group of storage units, wherein the third group of storage units process access requests regarding the encoded data slices having the third pillar number.

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

send a first request to a first storage unit of the first group of storage units regarding the storage capacity of the first storage unit; and

send a second request to a second storage unit of the first group of storage units regarding the storage capacity of the second storage unit.