Sharding method and apparatus using directed graphs

• US 7,043,621 B2
• Filed: 05/15/2003
• Issued: 05/09/2006
• Est. Priority Date: 05/16/2003
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Merchant, Arif, Swaminathan, Ram, Kallahalla, Mahesh
• Primary Examiner(s): Padmanabhan, Mano
• Assistant Examiner(s): KO, DANIEL BOKMIN
• Application Number:
  US10/439,977
• Publication Number:
  US 20040230764A1
• Time in Patent Office: 1,090 Days
• Field of Search: None
• US Class Current: 711/173
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0629 Configuration or reconfiguration of storage systems
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

A method and apparatus is used to divide a storage volume into shards. The division is made using a directed graph having a vertex for each block in the storage volume and directed-edges between pairs of vertices representing a shard of blocks, associating a weight with each directed edge that represents the dissimilarity for the shard of blocks between the corresponding pair of vertices, selecting a maximum number of shards (K) for dividing the storage volume, identifying a minimum aggregate weight associated with a current vertex for a combination of no more than K shards, performing the identification of the minimum aggregate weight for vertices in the directed graph, and picking the smallest aggregated weight associated with the last vertex to determine a sharding that spans the storage volume and provides a minimal dissimilarity among no more than K shards of blocks.

Claims

1. A method of dividing a storage volume into shards, comprising:

creating a directed graph having a vertex for each block in the storage volume and directed-edges between pairs of vertices representing a shard of blocks;

associating a weight with each directed edge that represents the dissimilarity for the shard of blocks between the corresponding pair of vertices;

selecting a maximum number of shards (K) for dividing the storage volume;

identifying a minimum aggregate weight associated with a current vertex for a combination of no more than K shards;

performing the identification of the minimum aggregate weight for all vertices in the directed graph; and

picking the smallest aggregated weight associated with the last vertex to determine a sharding that spans the storage volume and provides a minimal dissimilarity among no more than K shards of blocks.

2. The method of claim 1 wherein the pairs of vertices represents every permutation of blocks combined in sequence and the corresponding different shards of blocks.

3. The method of claim 1 wherein the dissimilarity for a shard having two or more blocks is determined by combining the pair wise dissimilarity measurement between pairs of blocks in the shard.

4. The method of claim 3 wherein the pair wise dissimilarity further comprises:

monitoring storage access activity in an area of storage space;

measuring at least one characteristic of the storage access activity of a plurality of individual portions of the area of storage space according to a predetermined parameter; and

determining whether the characteristic of storage access activity of one individual portion is similar to that of another portion according to predetermined criteria.

5. The method of claim 4 wherein the predetermined criteria to determine the characteristic of storage access activity to that of another portion includes comparing the I/O size measurement of the each portion.

6. The method of claim 4 wherein the predetermined criteria to determine the characteristic of storage access activity to that of another portion includes comparing the read/write ratio of the each portion.

7. The method of claim 4 wherein the predetermined criteria to determine the characteristic of storage access activity to that of another portion includes comparing the I/O density of the each portion.

8. The method of claim 1 wherein selecting the maximum number of shards (K) improves overall efficiency of accessing data on the storage volume.

9. The method of claim 8 wherein the maximum number of shards (K) corresponds to the number of physical drives in the storage volume.

10. The method of claim 8 wherein the maximum number of shards (K) corresponds to the number of different access patterns within the storage volume.

11. The method of claim 1 wherein the minimum aggregate weight is determined by combining a weight from an immediately preceding directed edge with a minimum weight associated with a neighboring vertex.

12. A method of mapping shards in a storage volume to a directed graph for analysis, comprising:

identifying potential shards in the storage volume;

creating vertices and directed edges between pairs of the vertices in the directed graph for each potential shard in the storage volume; and

associating a weight to each directed edge to represent the dissimilarty of the sequence of blocks corresponding to the directed edge.

13. The method of claim 12 wherein potential shards in the storage volume corresponds to a pair wise sequence of blocks spanning the storage volume.

14. The method of claim 12 wherein an edge represents the sequence of blocks between the corresponding pair of vertices.

15. A computer program product for dividing a storage volume into shards, tangibly stored on a computer-readable medium, comprising instructions operable to cause a programmable processor to:

create a directed graph having a vertex for each block in the storage volume and directed-edges between pairs of vertices representing a shard of blocks;

associate a weight with each directed edge that represents the dissimilarity for the shard of blocks between the corresponding pair of vertices;

select a maximum number of shards (K) for dividing the storage volume;

identify a minimum aggregate weight associated with a current vertex for a combination of no more than K shards;

perform the identification of the minimum aggregate weight for vertices in the directed graph; and

pick the smallest aggregated weight associated with the last vertex to determine a sharding that spans the storage volume and provides a minimal dissimilarity among no more than K shards of blocks.

16. A computer program product for mapping shards in a storage volume to a directed graph for analysis, tangibly stored on a computer-readable medium, comprising instructions operable to cause a programmable processor to:

identify potential shards in the storage volume;

create vertices and directed edges between pairs of the vertices in the directed graph for each potential shard in the storage volume; and

associate a weight to each directed edge to represent the dissimilarity of the sequence of blocks corresponding to the directed edge.

17. An apparatus that divides a storage volume into shards comprising:

a processor;

a memory having instructions capable of being executed on the processor that create a directed graph having a vertex for each block in the storage volume and directed-edges between pairs of vertices representing a shard of blocks, associated a weight with each directed edge that represents the dissimilarity for the shard of blocks between the corresponding pair of vertices, select a maximum number of shards (K) for dividing the storage volume, identify a minimum aggregate weight associated with a current vertex for a combination of no more than K shards, perform the identification of the minimum aggregate weight for vertices in the directed graph, and picks the smallest aggregated weight associated with the last vertex to determine a sharding that spans the storage volume and provides a minimal dissimilarity among no more than K shards of blocks.

18. An apparatus that maps shards in a storage volume to a directed graph for analysis, comprising:

a processor;

a memory having instructions capable of being executed on the processor that identifies potential shards in the storage volume, creates vertices and directed edges between pairs of the vertices in the directed graph for each potential shard in the storage volume, associates a weight to each directed edge to represent the dissimilarity of the sequence of blocks corresponding to the directed edge.

19. An apparatus for dividing a storage volume into shards, comprising:

means for creating a directed graph having a vertex for each block in the storage volume and directed-edges between pairs of vertices representing a shard of blocks;

means for associating a weight with each directed edge that represents the dissimilarity for the shard of blocks between the corresponding pair of vertices;

means for selecting a maximum number of shards (K) for dividing the storage volume;

means for identifying a minimum aggregate weight associated with a current vertex for a combination of no more than K shards;

means for performing the identification of the minimum aggregate weight for vertices in the directed graph; and

means for picking the smallest aggregated weight associated with the last vertex to determine a sharding that spans the storage volume and provides a minimal dissimilarity among no more than K shards of blocks.

20. An apparatus for mapping shards in a storage volume to a directed graph for analysis, comprising:

means for identifying potential shards in the storage volume;

means for creating vertices and directed edges between pairs of the vertices in the directed graph for each potential shard in the storage volume; and

means for associating a weight to each directed edge to represent the dissimilarity of the sequence of blocks corresponding to the directed edge.