Estimating a number of entries in a dispersed hierarchical index

• US 10,387,382 B2
• Filed: 10/27/2016
• Issued: 08/20/2019
• Est. Priority Date: 12/30/2015
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Dhuse, Greg R., Freese, Kevin M., Resch, Jason K., Scholl, Daniel J., Wozniak, Ethan S.
• Primary Examiner(s): Raab, Christopher J
• Application Number:
  US15/336,410
• Publication Number:
  US 20170193023A1
• Time in Patent Office: 1,027 Days
• Field of Search: None
• 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 12/0684 with feedback, e.g. presence or absence of unit detected by addressing, overflow detection
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0888 using selective caching, e.g. bypass
• CPC Class Codes: G06F 12/1408 by using cryptography for digital transmission H04L9/00
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 2212/154 Networked environment
• CPC Class Codes: G06F 2212/263 Network storage, e.g. SAN or NAS
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0623 in relation to content
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0652 : Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0653 : Monitoring storage devices or systems
• CPC Class Codes: G06F 3/0659 : Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0661 : Format or protocol conversion arrangements
• CPC Class Codes: G06F 3/0665 : at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/067 : Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• 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 43/0852 : Delays
• CPC Class Codes: H04L 43/0876 : Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 43/0888 : Throughput
• CPC Class Codes: H04L 43/16 : Threshold monitoring
• 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]

Abstract

Methods and systems for estimating a number of entries in a dispersed hierarchical index. The method and systems involve determining a number of random walks N to perform on the dispersed hierarchical index, conducting N walkthroughs based on the number of walkthroughs, determining a number of walk entries for each of the N random walks and averaging the number of walk entries for each of the N random walks to produce an estimated total number of entries for the dispersed hierarchical index. The determining may be based on one or more of a number of levels, a desired confidence interval, a predetermination, and interpretation of system registry information, and an interpretation of a request. Each random walk starts at a root node and ends at a leaf node through L levels of the dispersed hierarchical index.

Claims

1. A method of estimating a number of entries in a dispersed hierarchical index of a dispersed storage network comprising:

determining a number of walks to perform on the dispersed hierarchical index of the dispersed storage network to produce a determination, where the dispersed hierarchical index includes a root node, a plurality of index nodes and a plurality of leaf nodes, where the root node indexes the plurality of index nodes, and the plurality of index nodes index the plurality of leaf nodes;

conducting a plurality of walks based on the determination, where each respective walk of the plurality of walks starts at the root node and ends at a respective leaf node of the plurality of leaf nodes;

determining a respective number of walk entries associated with each respective walk of the plurality of walks; and

averaging the respective number of walk entries associated with each respective walk of the plurality of walks to produce an estimated total number of entries for the dispersed hierarchical index.

2. The method of claim 1, wherein the plurality of walks are random walks.

3. The method of claim 1, wherein the dispersed hierarchical index is use to locate a plurality of data objects stored as a plurality of sets of encoded data slices.

4. The method of claim 3, wherein the plurality of sets of encoded data slices are associated with a dispersed storage network address.

5. The method of claim 4, further comprising using the dispersed hierarchical index to locate the dispersed storage network address using keyword searching.

6. The method of claim 1, wherein one or more of the root node, the plurality of index nodes and the plurality of leaf nodes comprise a plurality of entries of one or more of an associated index key range, node pointers, and pointers to data objects stored in the dispersed storage network.

7. The method of claim 6, wherein one or more of the node pointers and pointers to data objects stored in the dispersed storage network include a virtual dispersed storage network address corresponding to one or more of a storage location of a node and a storage location of a data object.

8. The method of claim 1, further comprising dispersed storage error encoding one or more of the root node, the plurality of index nodes, and the plurality of leaf nodes, to produce a set of index slices.

9. The method of claim 1, wherein the dispersed hierarchical index includes dimensions associated with one or more index attributes, wherein the index attributes include one or more of a maximum number of levels, a minimum number of levels, a maximum number of child nodes in a parent-child node relationship, a minimum number of child nodes in the parent-child node relationship, a maximum number of sibling nodes at a common level, a minimum number of sibling nodes at a common level, a maximum number of entries in a node, and a minimum number of entries in the node.

10. A dispersed storage processing unit for estimating a number of entries in a dispersed hierarchical index of a dispersed storage network, the dispersed storage processing unit comprising:

a communications interface;

a memory; and

a computer processor;

where the memory includes instructions for causing the computer processor to;

determine a number of walks to perform on the dispersed hierarchical index of the dispersed storage network to produce a determination, where the dispersed hierarchical index includes a root node, a plurality of index nodes and a plurality of leaf nodes, where the root node indexes the plurality of index nodes, and the plurality of index nodes index the plurality of leaf nodes;

conduct a plurality of walks based on the determination, where each respective walk of the plurality of walks starts at the root node and ends at a respective leaf node of the plurality of leaf nodes;

determine a respective number of walk entries associated with each respective walk of the plurality of walks; and

average the respective number of walk entries associated with each respective walk of the plurality of walks to produce an estimated total number of entries for the dispersed hierarchical index.

11. The dispersed storage processing unit of claim 10, wherein the plurality of walks are random walks.

12. The dispersed storage processing unit of claim 10, wherein the dispersed hierarchical index is use to locate a plurality of data objects stored as a plurality of sets of encoded data slices.

13. The dispersed storage processing unit of claim 12, wherein the plurality of sets of encoded data slices are associated with a dispersed storage network address.

14. The dispersed storage processing unit of claim 13, wherein the memory further includes instructions for causing the processor to use the dispersed hierarchical index to locate the dispersed storage network address using keyword searching.

15. The dispersed storage processing unit of claim 10, wherein one or more of the root node, the plurality of index nodes and the plurality of leaf nodes comprise a plurality of entries of one or more of an associated index key range, node pointers, and pointers to data objects stored in the dispersed storage network.

16. The dispersed storage processing unit of claim 15, wherein one or more of the node pointers and pointers to data objects stored in the dispersed storage network include a virtual dispersed storage network address corresponding to one or more of a storage location of a node and a storage location of a data object.

17. The dispersed storage processing unit of claim 10, wherein the memory further includes instructions for causing the processor to dispersed storage error encoding one or more of the root node, the plurality of index nodes, and the plurality of leaf nodes, to produce a set of index slices.

18. The dispersed storage processing unit of claim 10, wherein the dispersed hierarchical index includes dimensions associated with one or more index attributes, wherein the index attributes include one or more of a maximum number of levels, a minimum number of levels, a maximum number of child nodes in a parent-child node relationship, a minimum number of child nodes in the parent-child node relationship, a maximum number of sibling nodes at a common level, a minimum number of sibling nodes at a common level, a maximum number of entries in a node, and a minimum number of entries in the node.

19. A dispersed storage network comprising:

a plurality of dispersed storage units storing encoded data slices of a set of encoded data slices;

a dispersed storage processing unit including;

a communications interface;

a memory; and

a computer processor;

where the memory includes instructions for causing the computer processor to;

determine a number of walks to perform on a dispersed hierarchical index of the dispersed storage network to produce a determination, where the dispersed hierarchical index includes a root node, a plurality of index nodes and a plurality of leaf nodes, where the root node indexes the plurality of index nodes, and the plurality of index nodes index the plurality of leaf nodes;

conduct a plurality of walks based on the determination, where each respective walk of the plurality of walks starts at the root node and ends at a respective leaf node of the plurality of leaf nodes;

determine a respective number of walk entries associated with each respective walk of the plurality of walks; and

average the respective number of walk entries associated with each respective walk of the plurality of walks to produce an estimated total number of entries for the dispersed hierarchical index.

20. The dispersed storage network of claim 19, wherein the plurality of walks are random walks.