Method and apparatus for storing data with reduced redundancy using data clusters

• US 20060282457A1
• Filed: 03/10/2006
• Published: 12/14/2006
• Est. Priority Date: 03/11/2005
• Status: Active Grant

• Current Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Original Assignee: Rocksoft Limited
• Inventors: Williams, Ross Neil
• Granted Patent: US 7,814,129 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: Y10S 707/914 Video
• CPC Class Codes: Y10S 707/915 Image
• CPC Class Codes: Y10S 707/916 Audio

Abstract

Method and apparatus for storing data in a reduced redundancy form. Binary Large Objects (BLOBs) are partitioned into subblocks according to a partitioning method, and the subblocks are stored in subblock clusters. Each BLOB is represented as a list of spans of subblocks which identifies a contiguous sequence of subblocks within a cluster. Storage redundancy can be reduced because the spans of two different BLOBs can refer to the same subblocks. An index may be used to map subblock hashes to subblock cluster numbers.

Claims

1. A method for storing a BLOB comprising:

dividing the BLOB into a plurality of subblocks;

storing the subblocks in a plurality of clusters; and

creating a representation of the BLOB as a plurality of spans, where each span identifies a sequence of subblocks within a cluster and where at least one subblock is referred to by more than one span.

2. A method according to claim 1 wherein each span identifies a sequence of one or more contiguous subblocks within a cluster.

3. A method according to claim 1 wherein the plurality of spans is an ordered list.

4. A method according to claim 1 wherein the plurality of spans is a tree of spans.

5. The method of claim 1 wherein two or more subblocks are stored as a contiguous sequence of bytes in a cluster with no intervening metadata.

6. The method of claim 1 wherein the subblocks are interleaved with some subblock metadata.

7. The method of claim 1 wherein each span identifies a sequence of contiguous subblocks within a cluster using at least one of the following:

a cluster identifier, a cluster address, a subblock identifier, a subblock location within a cluster, a length.

8. The method of claim 7 wherein the length is a number of subblocks.

9. The method of claim 7 wherein the length is a number of bytes.

10. The method of claim 1 wherein an upper bound is placed on the number of subblocks in each cluster.

11. The method of claim 1 wherein an upper bound is placed on the number of bytes in each cluster.

12. The method of claim 1 wherein the data is divided by partitioning the set of data b into a plurality of subblocks at least one position k|k+1 within b for which b[k−

A+1 . . . k+B] satisfies a predetermined constraint and wherein A and B are natural numbers.

13. The method of claim 1 wherein the data structures to store the data are created, but the data itself is not stored.

18. The method of claim 1 wherein each cluster has a directory of subblocks and the directory contains at least one of:

the length of each subblock, the hash of each subblock, the position of each subblock within the cluster, an identifier for each subblock.

19. The method of claim 18 wherein the cluster directory is stored within the cluster.

20. The method of claim 18 wherein the cluster directory is stored separately from the cluster.

21. The method of claim 18 wherein the cluster directory has a fixed length regardless of the number of subblocks that the cluster contains.

22. The method of claim 18 wherein the cluster directories are of fixed length and are stored separately from the clusters in a fixed length array of cluster directories.

23. The method of claim 18 wherein the cluster records the boundaries between contiguous runs of subblocks in the cluster.

24. The method of claim 18 wherein a boundary between subblocks in a cluster is identified by employing ordered identifiers and by allocating a non-contiguous identifier to a subblock at a boundary.

25. The method of claim 1 including the further step of:

compressing at least one cluster using a compression algorithm.

26. The method of claim 1 including the further step of compressing at least one subblock using a compression algorithm.

27. The method of claim 1 wherein at least two adjacent subblocks are compressed using a compression algorithm.

28. The method of claim 1 including the further step of:

maintaining an index that maps at least one subblock to the cluster containing the subblock.

29. The method of claim 1 including the further step of:

maintaining an index that maps the hash of at least one subblock to the cluster containing the subblock.

30. The method of claim 28 wherein the index includes the position of each subblock within the cluster containing the subblock.

31. The method of claims 28 wherein the index is implemented as a digital search tree whose keys are subblock hashes.

32. The method of claim 28 wherein the index is implemented as a Btree.

33. The method of claim 28 wherein only every T'"'"'th subblock in each BLOB is indexed where T is a predetermined positive integer.

34. The method of claim 29 wherein only every T'"'"'th subblock in each BLOB is indexed where T is a predetermined positive integer.

35. The method of claim 28 wherein the index is implemented as one or more hash tables.

36. The method of claim 35 wherein a hash table entry for a subblock contains all or part of the hash of the subblock.

37. The method of claim 35 wherein the hash table contains buckets.

38. The method of claim 1 wherein each span refers to a finite sequence of one or more bytes within the cluster.

39. The method of claim 1 wherein each span contains at least one skip value x that indicates that the extent of the span is to be reduced by x bytes.

40. The method of claim 1 wherein each span contains at least one extension value x that indicates that the extent of the span is to be increased by x bytes.

41. The method of claim 28 including the step of:

checking for duplicate subblocks by checking the index before adding a subblock to a cluster.

42. The method of claim 29 including the step of:

checking for duplicate subblocks by comparing the hashes of subblocks to be stored with the hashes of at least one of the subblocks in a cluster where an index indicates a subblock is stored.

43. The method of claim 1 wherein spans identify a subblock using part or all of the hash of the subblock.

44. The method of claim 1 wherein at least one contiguous run of less that T present subblocks is duplicated in the store of subblocks, where T is a predefined threshold of subblocks.

45. The method of claim 44 wherein T is two.

46. The method of claim 1 wherein at least one contiguous run of one or more subblocks is duplicated in the store of subblocks.

47. The method of claim 1 wherein at least one span X is augmented with an alternative span that refers to a copy of the data referred to by span X.

48. The method of claim 28 wherein once the index has been used to find the location of a subblock X within a cluster, the cluster is searched forwards from subblock X to find the longest matching run of subblocks with the subblocks being stored.

49. The method of claim 29 wherein once the index has been used to find the location of a subblock X within a cluster, the cluster is searched forwards from subblock X to find the longest matching run of subblocks with the subblocks being stored.

51. A data processing apparatus according to claim 43 wherein the processing means maintains an index that maps each subblock to the cluster containing the subblock.

52. A data processing apparatus according to claim 44 wherein the processing means checks for duplicate subblocks by checking the index before adding a subblock to a cluster.

59. The method of claims 29 wherein the index includes the position of each subblock within the cluster containing the subblock.

60. The method of claim 29 wherein the index is implemented as a digital search tree whose keys are subblock hashes.

14. A method for storing a set of data comprising:

dividing the data into a plurality of subblocks;

storing the subblocks in a plurality of clusters; and

creating a representation of the set of data as a plurality of spans, where each span identifies a sequence of subblocks within a cluster and where at least one subblock is referred to by more than one span.

15. The method of claim 14 wherein the data is a data file.

16. The method of claim 14, comprising the further step of reconstructing the set of data from the subblocks referenced by the group of spans.

17. The method of claim 14 wherein the data is divided by partitioning the set of data b into a plurality of subblocks at least one position k|k+1 within b for which b[k−

A+1 . . . k+B] satisfies a predetermined constraint and wherein A and B are natural numbers.

50. A data processing apparatus for storing a BLOB of data comprising:

data processing means for dividing the BLOB into two or more subblocks;

data storage means for storing the subblocks in one or more clusters; and

for representing the BLOB as an ordered list of spans or a tree of spans, where each span identifies a sequence of one or more contiguous subblocks within a cluster and where at least one subblock is referred to by more than one span.

53. A computer readable memory, encoded with data representing a computer program, that can be used to direct a programmable device for storing a BLOB of data, comprising:

processing means for operating the computer readable memory to divide the BLOB into two or more subblocks;

data storage means usable by the computer readable memory for storing the subblocks in one or more clusters; and

for representing the BLOB as an ordered list of spans or a tree of spans, where each span identifies a sequence of one or more contiguous subblocks within a cluster and where at least one subblock is referred to by more than one span.

54. A computer readable memory according to claim 53 wherein:

the processing means maintains an index that maps each subblock to the cluster containing the subblock.

55. A computer readable memory according to claim 54 wherein:

the processing means checks for duplicate subblocks by checking the index before adding a subblock to a cluster.

56. A computer program element comprising a computer program code means for storing a BLOB of data to make a programmable device execute:

a first function of dividing the BLOB into a plurality of subblocks;

a second function of storing the subblocks in a plurality of clusters; and

a third function of representing the BLOB as a group of associated spans, where each span identifies a sequence of one or more subblocks within a cluster and where at least one subblock is referred to by more than one span.

57. A computer program element according to claim 56 wherein:

a fourth function maintains an index that maps each subblock to the cluster containing the subblock.

58. A computer program element according to claim 57 wherein:

a fifth function checks for duplicate subblocks by checking the index before adding a subblock to a cluster.