OPTIMIZED DATA PLACEMENT FOR INDIVIDUAL FILE ACCESSES ON DEDUPLICATION-ENABLED SEQUENTIAL STORAGE SYSTEMS

• US 20140006363A1
• Filed: 06/29/2012
• Published: 01/02/2014
• Est. Priority Date: 06/29/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: CONSTANTINESCU, MIHAIL C., GHARAIBEH, ABDULLAH, LU, MAOHUA, PEASE, DAVID A., SHARMA, ANURAG
• Granted Patent: US 9,208,820 B2
• Time in Patent Office: Days
• US Class Current: 707/692
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/24557 Efficient disk access during query execution
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0682 Tape device
• CPC Class Codes: G11B 27/032 on tapes G11B27/036, G11B27/038 take precedence
• CPC Class Codes: G11B 5/86 Re-recording, i.e. transcribing information from one magnetisable record carrier on to one or more similar or dissimilar record carriers by varying the order of the information G11B27/029, G11B27/036

Abstract

Data deduplication for data storage tapes comprises determining the read throughput of a deduplicated set of individual files on a single data storage tape, and determining a placement of deduplicated file data on a single data storage tape to reduce an average number of per-file gaps on the tape. Deduplicated file data is placed on the single data storage tape based on said placement to increase an average read throughput for a deduplicated set of individual files.

Claims

1. A method of data deduplication for data storage tapes, comprising:

determining the read throughput of a deduplicated set of individual files on a single data storage tape; and

determining a placement of deduplicated file data on a single data storage tape to reduce an average number of per-file gaps on the tape; and

placing deduplicated file data on the single data storage tape based on said placement to increase an average read throughput for a deduplicated set of individual files.

2. The method of claim 1, further comprising:

placing deduplicated file data on a single data storage tape to reduce an average number of per-file gaps on the tape with, and without, re-duplicating deduplicated data, thereby optimizing individual file accesses.

3. The method of claim 1, further comprising:

placing deduplicated file data chunks on a single data storage tape to bound per-file access latency.

4. The method of claim 1, further comprising:

iteratively optimizing deduplicated data placement on the storage tape for a pre-defined metric, while maintaining a target per-file stretch ratio.

5. The method of claim 1, further comprising:

reading chunks of a deduplicated set of individual files into a stage buffer by sequentially reading the data storage tape, and re-constructing the chunks in the stage buffer by following the in-file order of the chunks.

6. The method of claim 4, wherein:

a segment comprises a continuous sequence of chunks that either duplicate or are unique but surrounded by duplicate chunks; and

segments of the same file are placed as close as possible, such that segments with the lowest frequency are candidates to be moved and to be merged with other segments.

7. The method of claim 4, further comprising:

performing linear data placement for a deduplicated set of files based on local optimization for individual file accesses.

8. The method of claim 6, wherein:

non-shared chunks of a file are around the shared chunks, such that shared chunks are denoted as pivot chunks;

said optimization comprises moving and merging chunks within the same file to meet said pre-defined metrics; and

said local optimization operates among neighboring pivot chunks.

9. The method of claim 8, wherein:

said optimization is based on a trade-off read between throughput for a set of individual files and the amount of re-duplicated data under tape storage space constraints.

10. The method of claim 8, further comprising:

performing re-duplication of segments based on a per-file metric.

11. The method of claim 1, further comprising:

reading a deduplicated set of individual files with a stage buffer, wherein out-of-order chunks are read sequentially from the storage tape, and re-constructed in the stage buffer.

12. A computer program product for data deduplication for data storage tapes, the computer program product comprising:

a tangible storage medium readable by a computer system and storing instructions for execution by the computer system for performing a method comprising;

determining a placement of deduplicated file data on a single data storage tape to reduce an average number of per-file gaps on the tape; and

placing deduplicated file data on the single data storage tape based on said placement to increase an average read throughput for a deduplicated set of individual files.

13. The computer program product of claim 12, further comprising:

placing deduplicated file data on a single data storage tape to reduce an average number of per-file gaps on the tape with, and without, re-duplicating deduplicated data.

14. The computer program product of claim 12, further comprising:

placing deduplicated file data chunks on a single data storage tape to bound per-file access latency.

15. The computer program product of claim 12, further comprising:

iteratively optimizing deduplicated data placement on the storage tape for a pre-defined metric, while maintaining a target per-file stretch ratio.

16. The computer program product of claim 15, wherein:

a segment comprises a continuous sequence of chunks that either duplicate or are unique but surrounded by duplicate chunks; and

segments of the same file are placed as close as possible, such that segments with the lowest frequency are candidates to be moved and to be merged with other segments.

17. The computer program product of claim 16, further comprising:

performing linear data placement for a deduplicated set of files based on local optimization for individual file accesses.

18. The computer program product of claim 17, wherein:

non-shared chunks of a file are placed around the shared chunks, such that shared chunks are denoted as pivot chunks;

said optimization comprises moving and merging chunks within the same file to meet said pre-defined metrics;

said local optimization operates among neighboring pivot chunks; and

said optimization is based on a trade-off read between throughput for a set of individual files and the amount of re-duplicated data under tape storage space constraints.

19. A tape storage system, comprising:

a tape drive for storing data on a storage tape; and

a controller that determines the read throughput of a deduplicated set of individual files on a single data storage tape, determines a placement of deduplicated file data on a single data storage tape to reduce an average number of per-file gaps on the tape, and places deduplicated file data on the single data storage tape based on said placement to increase an average read throughput for a deduplicated set of individual files.

20. The system, of claim 19, wherein:

the controller iteratively optimizes deduplicated data placement on the storage tape for a pre-defined metric, while maintaining a target per-file stretch ratio.