SHARING METHOD AND APPARATUS USING DIRECTED GRAPHS

摘要

A method and apparatus is used to divide a storage volume into shards (202-210). 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 (304), associating a weight with each directed edge that represents the dissimilarity for the shard of blocks between the corresponding pair of vertices (306), selecting a maximum number of shards (K) for dividing the storage volume (402), identifying a minimum aggregate weight associated with a current vertex for a combination of no more than K shards (512-514), performing the identification of the minimum aggregate weight for vertices in the directed graph (406), 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 (408).