Managing operations on stored data units

Patent metadata

Field	Value
Publication number	US-10133500-B2
Application number	US-201313787055-A
Country	US
Kind code	B2
Filing date	Mar 6, 2013
Priority date	Mar 6, 2013
Publication date	Nov 20, 2018
Grant date	Nov 20, 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, with at least a group of the data blocks being stored contiguously, thereby supporting a first read operation that retrieves data units from at least two adjacent data blocks in the group. The system is configured to perform two or more operations with respect to data units. The operations include: a second read operation, different from the first read operation, that retrieves a data unit to be read based at least in part on an address of a data block containing the data unit to be read, and a delete operation that replaces a first data block containing a data unit to be deleted with a second data block that does not contain the deleted data unit.

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, with at least a group of the data blocks being stored contiguously, thereby supporting a first read operation that retrieves data units from at least two adjacent data blocks in the group; and
an interface, including at least one processor, coupled to the data storage system, and configured to perform two or more operations with respect to data units, the operations including:
a second read operation, different from the first read operation, that retrieves a data unit to be read based at least in part on an address of a data block containing the data unit to be read and address information interpreted based on historical information about prior removal of one or more data units from that data block, and
a delete operation that replaces a first data block containing a data unit to be deleted with a second data block that does not contain the deleted data unit;

wherein the data storage system is 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.

2. The system of claim 1 , wherein the second read operation accesses at least a first data unit stored in a particular data block according to the address information interpreted based on any stored historical information corresponding to the particular data block.

3. The system of claim 1 , wherein the delete operation stores information about the deleted data unit in historical information corresponding to the new data block.

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

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

6. The system of claim 4 , 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.

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

8. The system of claim 7 , wherein the second 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.

9. The system of claim 7 , wherein the first read operation decompresses multiple compressed data blocks and reads multiple decompressed data units sequentially.

10. The system of claim 7 , 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 7 , 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 7 , 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 1 , wherein the second read operation locates the data block including the data unit to be read based on an index that indicates the data block as containing data units having particular identifiers, to recover a set of decompressed data units, and searches for the data unit to be read within the decompressed data units.

16. The system of claim 1 , wherein the data storage system is configured to store overhead information identifying the data blocks in the group as conforming to a predetermined storage format.

17. The system of claim 16 , wherein the overhead information includes an identifier in a header of each data block in the group identifying the predetermined storage format.

18. The system of claim 16 , wherein the first read operation is compatible with the predetermined storage format.

19. 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, with at least a group of the data blocks being stored contiguously, thereby supporting a first read operation that retrieves data units from at least two adjacent data blocks in the group; and
means for performing two or more operations with respect to data units, the operations including:
a second read operation, different from the first read operation, that retrieves a data unit to be read based at least in part on an address of a data block containing the data unit to be read and address information interpreted based on historical information about prior removal of one or more data units from that data block, and
a delete operation that replaces a first data block containing a data unit to be deleted with a second data block that does not contain the deleted data unit;

wherein the means for storing is 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.

20. 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, with at least a group of the data blocks being stored contiguously, thereby supporting a first read operation that retrieves data units from at least two adjacent data blocks in the group; and
performing, using at least one processor, two or more operations with respect to data units, the operations including:
a second read operation, different from the first read operation, that retrieves a data unit to be read based at least in part on an address of a data block containing the data unit to be read and address information interpreted based on historical information about prior removal of one or more data units from that data block, and
a delete operation that replaces a first data block containing a data unit to be deleted with a second data block that does not contain the deleted data unit;

wherein the data storage system is 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.

21. The method of claim 20 , wherein the second read operation accesses at least a first data unit stored in a particular data block according to the address information interpreted based on any stored historical information corresponding to the particular data block.

Assignees

• Ab Initio Technology Llc

Inventors

• Vishniac Ephraim Meriwether
• Schmidt Stephen J

Classifications

• G06F3/0652

  Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket · CPC title

• G06F16/22

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F3/0608 Primary

  Saving storage space on storage systems · CPC title

• G06F3/0673

  Single storage device · CPC title

• G06F3/061

  Improving I/O performance · CPC title