Sharding method and apparatus using directed graphs
First Claim
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.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
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. - View Dependent Claims (13, 14)
-
-
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.
-
Specification