Methods and systems for improving read performance in data de-duplication storage
View Patent ↗The present invention is directed toward methods and systems for data de-duplication. More particularly, in various embodiments, the present invention provides systems and methods for data de-duplication that may utilize a data de-duplication system that retrieves data from a data storage device in an order based on the location of blocks on the data storage device. Some embodiments break a data stream into multiple blocks of data and store the blocks of data on a data storage device of a data de-duplication system, wherein a code representing a redundant block of data is stored in place of the block of data. A location for each block of data may be stored. Additionally, the blocks may be read in an order that is determined based on the location of the blocks.
1. A non-transitory computer-readable medium storing computer-executable instructions that when executed by a computer control the computer to perform a method, the method comprising:
receiving first data identifying a first order for reading a set of de-duplicated sub-blocks of data from a storage pool of de-duplicated sub-blocks of data;
acquiring location information concerning physical locations of members of the set of de-duplicated sub-blocks of data, where location information for a de-duplicated sub-block is acquired when the de-duplicated sub-block is added to the storage pool;
storing the location information for the de-duplicated sub-block with metadata associated with the de-duplicated sub-block;
determining a second order for reading the set of de-duplicated sub-blocks of data based on the location information, where the second order is configured to improve read performance as compared to the first order;
reading the set of de-duplicated data sub-blocks in the second order; and
providing the set of de-duplicated sub-blocks of data in the first order.
2. The computer-readable medium of claim 1 , where at least a portion of the storage pool resides on a flash memory based solid state drive (SSD).
3. The computer-readable medium of claim 2 , where the location information identifies a physical location on the flash memory based SSD where at least one sub-block from the set of de-duplicated sub-blocks is stored.
4. The computer-readable medium of claim 1 , where acquiring location information for a de-duplicated sub-block is performed when the de-duplicated sub-block is added to the storage pool.
5. The computer-readable medium of claim 1 , where acquiring the location information is performed as part of a read operation that determined the first order and before members of the set of de-duplicated sub-blocks are read.
6. A non-transitory computer-readable medium storing computer-executable instructions that when executed by a computer control the computer to perform a method, the method comprising:
receiving first data identifying a first order for reading a set of de-duplicated sub-blocks of data from a storage pool of de-duplicated sub-blocks of data
acquiring location information concerning physical locations of members of the set of de-duplicated sub-blocks of data, where location information for a de-duplicated sub-block is acquired when the de-duplicated sub-block is added to the storage pool;
determining a second order for reading the set of de-duplicated sub-blocks of data based on the location information, where the second order is configured to improve read performance as compared to the first order;
reading the set of de-duplicated data sub-blocks in the second order; and
providing the set of de-duplicated sub-blocks of data in the first order,
where a first portion of the storage pool is stored on a first data storage device and where a second portion of the storage pool is stored on a second, different data storage device.
7. The computer-readable medium of claim 6 , where the location information includes device information and where the second order is based, at least in part, on the device information.
8. A non-transitory computer-readable medium storing computer-executable instructions that when executed by a computer control the computer to perform a method, the method comprising:
receiving first data identifying a first order for reading a set of de-duplicated sub-blocks of data from a storage pool of de-duplicated sub-blocks of data;
acquiring location information concerning physical locations of members of the set of de-duplicated sub-blocks of data, where location information for a de-duplicated sub-block is acquired when the de-duplicated sub-block is added to the storage pool;
determining a second order for reading the set of de-duplicated sub-blocks of data based on the location information, where the second order is configured to improve read performance as compared to the first order;
reading the set of de-duplicated data sub-blocks in the second order; and
providing the set of de-duplicated sub-blocks of data in the first order,
where determining the second order comprises evaluating the first order with respect to a single data storage device from which a subset of the set of de-duplicated sub-blocks is to be read, or with respect to two or more data storage devices from which a subset of the set of de-duplicated sub-blocks is to be read.
9. A data de-duplication system, comprising:
a data storage device configured to store sub-blocks of de-duplicated data;
a memory configured to store instructions; and
a processor configured to read instructions from the memory and to execute the instructions, where executing the instructions causes the processor to:
acquire location information concerning the physical location in a fragmented de-duplication storage pool of members of a set of sub-blocks to be read by the de-duplication system; and
read the set of sub-blocks from the fragmented de-duplication storage pool in an order that is based on the locations of members of the set of sub-blocks as identified by the location information,
where the de-duplication storage pool is fragmented due to a number of the set of sub-blocks not residing in sequential order in the storage pool or on a single storage device of the storage pool.
10. The data de-duplication system of claim 9 , where the data storage device is a flash memory based solid state drive (SSD).
11. The data de-duplication system of claim 10 , where the order for reading the set of sub-blocks from the fragmented de-duplication storage pool depends, at least in part, on a relationship between at least two members of the set of sub-blocks, where the at least two members are co-located on a page in the SSD.
12. The data de-duplication system of claim 9 , where at least a portion of the de-duplication storage pool is stored on the data storage device.
13. The data de-duplication system of claim 9 , comprising a plurality of data storage devices and where the de-duplication storage pool is stored on the plurality of data storage devices.
14. The data de-duplication system of claim 9 , comprising a plurality of data storage devices, where at least two of the plurality of data storage devices are different types of data storage devices, and where the de-duplication storage pool is stored on the plurality of data storage devices.
15. The data de-duplication system of claim 14 , where at least one member of the plurality of data storage devices is a flash memory based solid state drive (SSD).
16. The data de-duplication system of claim 14 , where the order for reading the set of sub-blocks from the fragmented de-duplication storage pool depends, at least in part, on a relationship between at least two members of the set of sub-blocks that are co-located on a page in the SSD.