Handling data shard fanouts in a deduplication file system

A system comprising:

• a processor;
• and memory configured to store one or more sequences of instructions which, when executed by the processor, cause the processor to carry out the steps of:
• representing files in a file system by segment trees, the segment trees comprising multiple segment levels arranged in a hierarchy, the files comprising a file having been segmented into a plurality of upper-level segments, the upper-level segments comprising references to segments of the file that form a lowest-level of a segment tree for the file and the upper-level segments being aligned at fixed-size boundaries in the file, each upper-level segment thereby starting at a file offset that is a multiple of a size of an upper-level segment;
• forming a plurality of shards for each upper-level segment, each shard comprising a subset of references from a respective upper-level segment and being assigned to a respective similarity group within which deduplication is performed;
• determining that a count of shards in a particular plurality of shards bounded within a particular upper-level segment exceeds a threshold shard count by an excess shard count;
• identifying, in the particular plurality of shards, a subset of shards, equal to the excess shard count, wherein each shard in the subset includes a number of references that is less than a number of references in any other shard outside the subset of the particular plurality of shards;
• merging a shard in the subset with another shard immediately adjacent to the shard to create a merged shard;
• storing the merged shard on storage of the file system;
• and
• repeating the merging for each other shard in the subset to reduce the count of shards in the particular plurality of shards to the threshold shard count.

A computer program product, comprising a non-transitory computer-readable medium having a computer-readable program code embodied therein, the computer-readable program code adapted to be executed by one or more processors to implement a method comprising:

• representing files in a file system by segment trees, the segment trees comprising multiple segment levels arranged in a hierarchy, the files comprising a file having been segmented into a plurality of upper-level segments, the upper-level segments comprising references to segments of the file that form a lowest-level of a segment tree for the file and the upper-level segments being aligned at fixed-size boundaries in the file, each upper-level segment thereby starting at a file offset that is a multiple of a size of an upper-level segment;
• forming a plurality of shards for each upper-level segment, each shard comprising a subset of references from a respective upper-level segment and being assigned to a respective similarity group within which deduplication is performed;
• determining that a count of shards in a particular plurality of shards bounded within a particular upper-level segment exceeds a threshold shard count by an excess shard count;
• identifying, in the particular plurality of shards, a subset of shards, equal to the excess shard count, wherein each shard in the subset includes a number of references that is less than a number of references in any other shard outside the subset of the particular plurality of shards;
• merging a shard in the subset with another shard immediately adjacent to the shard to create a merged shard;
• storing the merged shard on storage of the file system;
• and
• repeating the merging and storing for each other shard in the subset to reduce the count of shards in the particular plurality of shards to the threshold shard count.