Optimized data placement for individual file accesses on deduplication-enabled sequential storage systems

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

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

determining a placement of deduplicated file data on the single data storage tape based on sorting non-duplicate segments of different files around shared segments for reducing an average number of per-file gaps on the single data storage tape, wherein the sorting comprises ordering forward-related non-duplicate segments in a same file as following shared segments from largest segment to smallest segment, and ordering backward-related non-duplicate segments in the same file as previous shared segments from smallest to largest; and

writing the deduplicated file data on the single data storage tape based on said placement to increase the read throughput for the deduplicated set of individual files and to reduce the average number of per-file gaps on the single data storage tape by re-duplicating deduplicated data for meeting optimization of individual file accesses.

2. The method of claim 1 , further comprising:

writing deduplicated file data chunks on the single data storage tape to bound per-file access latency,

wherein determining said placement comprises iteratively optimizing deduplicated data placement on the single data storage tape, and determining candidate segments to move and concatenate that have a lowest access frequency for each iteration.

3. The method of claim 1 , further comprising:

iteratively optimizing placement of deduplicated data written on the single data storage tape for a pre-defined metric comprising gaps per gigabyte (GB), while maintaining a target per-file stretch ratio.

4. The method of claim 3 , 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.

5. The method of claim 3 , further comprising:

performing linear data placement for a set of files that have been deduplicated, wherein the linear data placement is based on local optimization for individual file accesses.

6. The method of claim 5 , wherein:

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

said iteratively optimizing comprises moving and merging chunks within a same deduplicated file to meet said pre-defined metric; and

said local optimization operates among neighboring pivot chunks.

7. The method of claim 6 , wherein:

said iteratively optimizing is based on a trade-off between read throughput for the deduplicated set of individual files and the amount of re-duplicated data under single data storage tape space constraints,

and non-duplicate segments of a file are combined with a first non-duplicate segment of said file for forming a non-duplicate segment that is larger than the first non-duplicate segment for said file.

8. The method of claim 6 , further comprising:

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

9. The method of claim 1 , further comprising:

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

10. The method of claim 1 , further comprising:

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

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

a non-transitory computer-readable medium storing instructions for execution by the computer system for performing a method comprising:

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

determining a placement of deduplicated file data on the single data storage tape based on sorting non-duplicate segments of different files around shared segments for reducing an average number of per-file gaps on the single data storage tape, wherein the sorting comprises ordering forward-related non-duplicate segments in a same file as following shared segments from largest segment to smallest segment, and ordering backward-related non-duplicate segments in the same file as previous shared segments from smallest to largest; and

writing the deduplicated file data on the single data storage tape based on said placement to increase the read throughput for the deduplicated set of individual files and to reduce the average number of per-file gaps on the single data storage tape by re-duplicating deduplicated data for meeting optimization of individual file accesses.

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

writing deduplicated file data chunks on the single data storage tape to bound per-file access latency,

wherein determining the placement comprises iteratively optimizing deduplicated data placement on the single data storage tape, and determining candidate segments to move and concatenate that have a lowest access frequency for each iteration.

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

iteratively optimizing placement of deduplicated data written on the single data storage tape for a pre-defined metric comprising gaps per gigabyte (GB), while maintaining a target per-file stretch ratio.

14. The computer program product of claim 13 , 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.

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

performing linear data placement for a set of files that have been deduplicated, wherein the linear data placement is based on local optimization for individual file accesses.

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

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

said iteratively optimizing comprises moving and merging chunks within a same deduplicated file to meet said pre-defined metric;

said local optimization operates among neighboring pivot chunks; and

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

17. A tape storage system, comprising:

a tape drive configured to store data on a single data storage tape, the tape drive including

a hardware tape controller configured to:

determine a read throughput of a deduplicated set of individual files on the single data storage tape,

determine a placement of deduplicated file data on the single data storage tape based on sorting non-duplicate segments of different files around shared segments for reducing an average number of per-file gaps on the single data storage tape,

sort the non-duplicate segments based on ordering forward-related non-duplicate segments in a same file as following shared segments from largest segment to smallest segment, and ordering backward-related non-duplicate segments in the same file as previous shared segments from smallest to largest, and

write the deduplicated file data on the single data storage tape based on said placement to increase the read throughput for the deduplicated set of individual files and to reduce the average number of per-file gaps on the single data storage tape by re-duplicating deduplicated data for meeting optimization of individual file accesses.

18. The system, of claim 17 , wherein:

the hardware tape controller is configured to: iteratively optimize placement of deduplicated data written on the single data storage tape for a pre-defined metric, while maintaining a target per-file stretch ratio; and

determine candidate segments to move and concatenate that have a lowest access frequency for each iteration.