Sequential access storage and data de-duplication

• US 9,569,134 B2
• Filed: 08/23/2010
• Issued: 02/14/2017
• Est. Priority Date: 08/23/2010
• Status: Active Grant

• Current Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Original Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Inventors: Wideman, Roderick B.
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): DARE, RYAN A
• Application Number:
  US12/861,231
• Publication Number:
  US 20120047324A1
• Time in Patent Office: 2,367 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 11/3664 Environments for testing or debugging software
• CPC Class Codes: G06F 2009/45562 Creating, deleting, cloning virtual machine instances
• CPC Class Codes: G06F 2009/45591 Monitoring or debugging support
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0686 Libraries, e.g. tape libraries, jukebox
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects
• CPC Class Codes: G06F 9/5077 Logical partitioning of resources; Management or configuration of virtualized resources specific details on emulation or internal functioning of virtual machines G06F9/455

Abstract

An example method includes determining a configuration of two or more partitions for a sequential access medium. At least one partition stores data de-duplication data structures while at least one other partition stores a repository of unique data blocks associated with the data structures. The method also includes controlling a data de-duplication computer to configure the sequential access medium according to the configuration. The method includes producing an output sequence for writing the data structures and a set of unique data blocks associated with the set of data structures to the sequential access medium as configured with the two or more partitions. One embodiment includes controlling a data de-duplication computer to write the data de-duplication data structures and the set of unique data blocks to the sequential access medium according to the output sequence.

Claims

1. A method, comprising:

producing an input sequence for acquiring, from a sequential access medium associated with a sequential access device, a set of unique data blocks associated with a data de-duplication application, where the set of unique data blocks are identified in one or more data reconstitution recipes, where the input sequence depends, at least in part, on the order in which the set of unique data blocks appear on the sequential access medium, where the input sequence is a sorted list of unique data blocks, where the sorted list is sorted in order from a unique data block that will be encountered first during a sequential read from the sequential access medium to the unique data block that will be encountered last during the sequential read from the sequential access medium,

where the sequential access medium is configured with two partitions, where the sequential access medium stores one or more data de-duplication data structures in a first partition, and stores a repository of one or more unique data blocks associated with the data de-duplication data structures in a second partition, where the order of data structures in the partition storing the data de-duplication data structures is one of, index first and recipes second, and recipes first and index second, and

controlling a data de-duplication computer to acquire the set of unique data blocks from the sequential access medium according to the input sequence, where the sequential access medium is linear tape, and where the sequential access device is a tape drive.

2. The method of claim 1, where the one or more data de-duplication structures comprise an index, where the index stores information for determining whether a block of data is present in the repository.

3. The method of claim 2, where the one or more data de-duplication data structures further comprise a catalog of recipes.

4. The method of claim 3, where the one or more data de-duplication data structures further comprise a data reconstitution recipe, where a data reconstitution recipe describes which blocks comprise a data item, and the order of blocks in a data item.

5. The method of claim 1, where the sequential access medium is configured with at least three partitions.

6. The method of claim 5, where a first of the at least three partitions stores the index, where a second of the at least three partitions stores a recipe, and where a third of the at least three partitions stores the repository.

7. A method, comprising:

determining a configuration for a sequential access medium to store one or more data de-duplication data structures and a repository of unique data blocks associated with the one or more data de-duplication data structures, where the sequential access medium is linear tape, where the sequential access medium is configurable with more than two partitions, and where the configuration depends, at least in part, on a number of partitions available to create on the sequential access medium;

controlling a data de-duplication computer to configure the sequential access medium according to the configuration;

producing an input sequence for acquiring, from the sequential access medium, a retrieval set of unique data blocks associated with a data de-duplication application; and

controlling the data de-duplication computer to acquire the retrieval set of unique blocks from the sequential access medium according to the input sequence.

8. The method of claim 7, comprising:

producing an output sequence for writing the one or more data de-duplication data structures and a set of unique data blocks associated with the set of data de-duplication data structures to the sequential access medium as configured, and

controlling a data de-duplication computer to write the one or more data de-duplication data structures and the set of unique data blocks to the sequential access medium according to the output sequence.

9. The method of claim 8, where the configuration also depends on an order for the partitions on the sequential access medium and one or more of, the contents of a partition on the sequential access medium, and the order of the contents of a partition on the sequential access medium.

10. An apparatus, comprising:

a processor;

a memory; and

an interface connecting the processor, the memory, and a set of logics, the set of logics comprising;

a configuration logic that prepares a sequential access medium to store a set of data de-duplication data structures and a repository of data blocks associated with the set of data de-duplication data structures, where preparing the sequential access medium comprises partitioning the sequential access medium into three or more partitions, where the sequential access medium is linear tape; and

a write logic that writes the set of data de-duplication data structures and the repository of data blocks to the sequential access medium, where one member of the set of data de-duplication data structures is written to one partition, where a second member of the set of data de-duplication data structures is written to a second, different partition, and where the repository of data blocks is written to a third, different partition.

11. The apparatus of claim 10, the set of logics comprising:

a planning logic that determines an input plan for sequentially reading a set of data blocks from the sequential access medium; and

a read logic that reads the set of data blocks according to the input plan.

12. The apparatus of claim 11, the set of logics comprising:

an assembly logic that assembles one or more data items from the set of data blocks after members of the set of data blocks are acquired from the sequential access medium.

13. The apparatus of claim 11, where the configuration logic considers a number of partitions available on the sequential access medium and one or more of, a number of data structures in the set of data de-duplication data structures, and an order of data structures, while preparing the sequential access medium.

14. The apparatus of claim 11, where the input plan comprises a sorted list of blocks.