Methods of encoding and storing multiple versions of data, method of decoding encoded multiple versions of data and distributed storage system

A method of decoding encoded multiple versions of data, the encoded multiple versions of data comprising a plurality of codewords, each codeword corresponding a respective version of a data object, the method comprising:

• erasure decoding a codeword corresponding to a version of the data object from the plurality of codewords to obtain a compressed difference object, the difference object representing a difference between said version of the data object and another version of the data object;
• decompressing the compressed difference object to recover the difference object;
• and
• recovering said version of the data object based on at least the recovered difference object and said another version of the data object.

An encoder system for encoding multiple versions of data, the encoder comprising:

• a difference object generator module configured to compute a difference between a version of a data object and a subsequent version of the data object to produce a difference object;
• a sparsity level determination module configured to determine a sparsity level of the difference object;
• a sparsity level comparator module configured to determine whether the sparsity level satisfies a predetermined condition;
• a compression module configured to compress the difference object to produce a compressed difference object;
• and
• an erasure encoder configured to encode the compressed difference object to produce a codeword,
• wherein the compression module is configured to compress the difference object and the erasure encoder is configured to encode the compressed difference object if the sparsity level is determined by the sparsity level comparator module to satisfy the predetermined condition.

A distributed storage system, the system comprising:

• a plurality of secondary servers, each secondary server configured to store codewords for multiple versions of a data object;
• and
• a group server associated with the plurality of secondary servers, wherein
• each secondary server comprises a difference object generator module configured to compute a difference between a version of the data object and a subsequent version of the data object to produce a difference object, and
• the group server comprises:
• a sparsity level determination module configured to determine a sparsity level of the difference object received from the secondary server;
• a sparsity level comparator module configured to determine whether the sparsity level satisfies a predetermined condition;
• a compression module configured to compress the difference object to produce a compressed difference object;
• and
• an erasure encoder configured to encode the compressed difference object to produce a codeword for storing in the secondary server,
• wherein the compression module is configured to compress the difference object and the erasure encoder is configured to encode the compressed difference object if the sparsity level is determined by the sparsity level comparator module to satisfy the predetermined condition.

A method of storing multiple versions of data in a distributed storage system, the distributed storage system comprising:

• a plurality of secondary servers, each secondary server configured to store codewords for multiple versions of a data object;
• and
• a group server associated with the plurality of secondary servers,
• the method comprising:
• computing, at one of the plurality of secondary servers, a difference between a version of a data object and a subsequent version of the data object to produce a difference object;
• determining, at the group server, a sparsity level of the difference object received from the secondary server;
• determining, at the group server, whether the sparsity level satisfies a predetermined condition;
• and
• compressing, at the group server, the difference object to produce a compressed difference object and erasure encoding, at the group server, the compressed difference object to produce a codeword for storage in the secondary server if the sparsity level is determined to satisfy the predetermined condition.

A computer program product, embodied in one or more non-transitory computer-readable storage mediums, comprising instructions executable by one or more computer processors to perform a method of encoding multiple versions of data, the method comprising:

• computing a difference between a version of a data object and a subsequent version of the data object to produce a difference object;
• determining a sparsity level of the difference object;
• determining whether the sparsity level satisfies a predetermined condition;
• and
• compressing the difference object to produce a compressed difference object and erasure encoding the compressed difference object to produce a codeword if the sparsity level is determined to satisfy the predetermined condition.