Managing operations on stored data units

Patent metadata

Field	Value
Publication number	US-9959070-B2
Application number	US-201313787138-A
Country	US
Kind code	B2
Filing date	Mar 6, 2013
Priority date	Mar 6, 2013
Publication date	May 1, 2018
Grant date	May 1, 2018

Abstract

A system for managing storage of data units includes a data storage system configured to store multiple data blocks, at least some of the data blocks containing multiple data units, and configured to store, for at least some of the data blocks, corresponding historical information about prior removal of one or more data units from that data block, the removal affecting at least some addresses of data units in that data block. The system is configured to perform at least one operation that accesses at least a first data unit stored in a first data block according to address information interpreted based on any stored historical information corresponding to the first data block.

First claim

What is claimed is:

1. A system for managing storage of data units, the system including:
a data storage system configured to store multiple data blocks, at least some of the data blocks containing multiple data units, and configured to store, for at least some of the data blocks, corresponding historical information about prior removal of one or more data units from that data block, the removal affecting at least some addresses of data units already stored in that data block other than the one or more data units removed; and
an interface, including at least one processor, coupled to the data storage system, and configured to perform at least one operation, where that operation accesses at least a first data unit stored in a first data block according to address information, and where that address information is interpreted based on any stored historical information corresponding to the first data block, and where the interpretation of the address information takes into account any shifts due to removal of one or more data units.

2. The system of claim 1 , wherein the historical information corresponding to the first data block includes information about prior removal of one or more data units from the first data block affecting relative offsets of data units that have been decompressed from the first data block.

3. The system of claim 1 , wherein at least some of the data blocks are compressed data blocks.

4. The system of claim 3 , wherein the interface is configured to perform two or more operations with respect to data units, the operations including:
a read operation that retrieves a data unit to be read based at least in part on address information that locates the data unit relative to a reference address, and
a delete operation that removes a data unit to be deleted, and stores historical information about the deleted data unit for interpreting address information for other data units to take into account any shifts relative to the reference address due to removal of the data unit to be deleted.

5. The system of claim 3 , wherein the interface is configured to perform two or more operations with respect to data units, the operations including:
a first read operation that retrieves a data unit to be read based at least in part on historical information corresponding to a compressed data block, and
a delete operation that replaces a first compressed data block containing a data unit to be deleted with a second compressed data block that does not contain the deleted data unit, and stores information about the deleted data unit in historical information corresponding to the second compressed data block.

6. The system of claim 5 , wherein the first read operation decompresses a particular compressed data block to recover a set of decompressed data units and retrieves the data unit to be read at a particular offset from a reference location based at least in part on the historical information corresponding to that particular compressed data block.

7. The system of claim 6 , wherein the first read operation determines whether or not the historical information includes information about one or more previously deleted data units.

8. The system of claim 7 , wherein, if the historical information includes information about one or more previously deleted data units, the first read operation determines whether or not to adjust the particular offset based on comparing the particular offset to a value in the historical information that indicates an offset of at least one of the previously deleted data units.

9. The system of claim 8 , wherein, if the particular offset is to be adjusted, the first read operation adjusts the particular offset based on offsets and sizes of one or more previously deleted data units.

10. The system of claim 5 , wherein the delete operation expands a stored size of the second compressed data block to account for a difference in size between the second compressed data block and the first compressed data block.

11. The system of claim 10 , wherein the stored size of the second compressed data block is expanded by storing overhead information associated with the second compressed data block in addition to the historical information corresponding to the second compressed data block.

12. The system of claim 5 , wherein the delete operation stores a new error-detecting code associated with the second compressed data block to replace an error-detecting code associated with the first compressed data block.

13. The system of claim 5 , wherein the operations include an add operation that stores a data unit to be added in association with a set of recently added data units.

14. The system of claim 13 , wherein the processor is further configured to compress the set of recently added data units as a compressed data block stored in the storage medium.

15. The system of claim 5 , wherein the operations include a second read operation, different from the first read operation, that decompresses one or more compressed data blocks and reads multiple decompressed data units sequentially.

16. The system of claim 15 , wherein the operations include a third read operation, different from the first and second read operations, that decompresses a particular compressed data block indicated by an index as including a data unit having a particular identifier, to recover a set of decompressed data units, and searches for the data unit having the particular identifier within the decompressed data units.

17. The system of claim 1 , wherein at least some of the historical information is stored in the data storage system.

18. The system of claim 17 , wherein at least a portion of the historical information is interleaved between different data blocks.

19. The system of claim 17 , wherein at least a portion of historical information corresponding to a particular data block is stored in a predetermined portion of that particular data block.

20. A system for managing storage of data units, the system including:
means for storing multiple data blocks, at least some of the data blocks containing multiple data units, and storing, for at least some of the data blocks, corresponding historical information about prior removal of one or more data units from that data block, the removal affecting at least some addresses of data units already stored in that data block other than the one or more data units removed; and
means for performing at least one operation, where that operation accesses at least a first data unit stored in a first data block according to address information, and where that address information is interpreted based on any stored historical information corresponding to the first data block, and where the interpretation of the address information takes into account any shifts due to removal of one or more data units.

21. A method for managing storage of data units, the method including:
storing multiple data blocks in a data storage system, at least some of the data blocks containing multiple data units, and storing, for at least some of the data blocks, corresponding historical information about prior removal of one or more data units from that data block, the removal affecting at least some addresses of data units already stored in that data block other than the one or more data units removed; and
performing, using at least one processor, at least one operation, where that operation accesses at least a first data unit stored in a first data block according to address information, and where that address in

Assignees

• Ab Initio Technology Llc

Inventors

• Vishniac Ephraim Meriwether
• Schmidt Stephen J

Classifications

• G06F3/0608

  Saving storage space on storage systems · CPC title

• G06F3/0671

  In-line storage system · CPC title

• G06F16/00

  Information retrieval; Database structures therefor; File system structures therefor · CPC title

• G06F3/064 Primary

  Management of blocks · CPC title

• G06F17/30

  Physics · mapped topic