Method and apparatus for storing and retrieving data

A method and apparatus for storing and retrieving data. The embodiment may maintain all previously-written data in a portion of a storage device, such as a hard disk, writable optical media, or memory, for an indefinite period. Old data is not overwritten unless the storage capacity of the storage device is exceeded. Accordingly, prior versions of data may be accessed by the embodiment as desired.

BACKGROUND OF THE INVENTION

1. Technical Field

The present invention relates generally to a method and apparatus for storing and retrieving data, and more particularly to methods and apparatuses for retrieving data affected by a virus, disk error, or other catastrophic failure.

2. Description of Related Art

Much of the world's information is stored in computers. Storage devices come in a variety of formats, including memory-based, magnetic, and optical. Most, if not all, storage devices are vulnerable to errors in reading and writing data, which may corrupt valuable information. Similarly, malicious parties often release programs or applications designed to corrupt data. These programs are commonly referred to as “viruses.” Viruses, or intrusion into a computer's storage by a third party through other means, can cause irreparable loss of data.

Accordingly, there is a need in the art for an improved method and apparatus for saving, restoring, and auditing data and computer-accessible information.

BRIEF SUMMARY OF THE INVENTION

One embodiment of the present invention takes the form of a method and apparatus for storing and retrieving data. The embodiment may maintain all previously-written data in a portion of a storage device, such as a hard disk, writable optical media, or memory, for an indefinite period. Old data is not overwritten unless the storage capacity of the storage device is exceeded. Accordingly, prior versions of data may be accessed by the embodiment as desired.

The invention may transform an append-only disk write operation into a single available disk write operation, thus keeping all the written data previously stored on the storage device. Accordingly, such data may be retrieved as necessary. In one embodiment, three general operations are carried out by the embodiment to permit such retrieval: (1) the embodiment determines the physical blocks storing data corresponding to a particular “snapshot” of a given time; (2) the embodiment determines what physical blocks store data corresponding to a logical view used by a file system or host; and (3) the embodiment determines which physical blocks are available for data storage, and which are in use. The embodiment may, for example, employ a time log table, logical/physical block conversion table, and available block bitmap to carry out these operations.

The embodiment may employ such information to roll back and/or forward to any moment of the history of the storage device's operation. Thus, the embodiment may recover data from any moment, irregardless of any sort of data corruption caused by a virus or operational error.

Another embodiment of the present invention embodiment may segment a storage element (such as a magnetic disk, optical read/write disk, or flash memory storage) into a first-write, or “virgin” area, and a later-write, or “overwrite” area. When a file or data is written to a storage element for the first time, it is written into the virgin area. When a file or data is written to the storage element any time after the first write, it is written into a block in the overwrite area. A record, including a timestamp, is created in a table for each write operation, regardless of whether the write occurred in the virgin or overwrite area.

The embodiment may restore data from the storage device by determining a restore time. The embodiment scans the records in the table to determine if the records' timestamps are equal to or predate the restore time. The embodiment locates the chronologically latest record for each unique file/data that occurs prior to at the same time as the restore time, and retrieves the corresponding iteration of the file/data. That iteration replaces the current version of the file/data.

Such restoring may prove particularly useful in recovering from a computer virus, crash, or corrupt files.

An embodiment of the present invention may take the form of a method for storing data on a storage medium, including the operations of writing a first datum to the storage medium at a first physical location, associating a first host view location with the first physical location, storing an indicator of the writing of the first datum, and storing the association between the first host view location and the first physical location.

Another embodiment of the present invention may take the form of an apparatus for storing data, including a metadata area, a storage area operatively associated with the metadata area and comprising at least a first and second physical block, a host view block table operative to associate a first host block with the first physical block, and a first log operatively associated with a first datum.

Yet another embodiment may take the form of an apparatus for controlling storage of a datum on a storage medium, the data provided by a host, the apparatus including a module for controlling the writing of the datum to a physical block of a storage medium, a module for updating a host view block table by creating a correspondence between the physical block and a host view block seen by the host, and a module for creating a log corresponding to the writing of data. In such an embodiment, the log may include a pointer associating the log with the host view block table, an order indicator; and a previous block address associating the log with a prior storage of the datum.

Still another embodiment may take the form of a method for retrieving a datum from a storage medium, including the operations of determining a desired time at which the datum was written to a first physical block on the storage medium, accessing a first log of a plurality of logs, the first log containing a previous physical address corresponding to a second physical block, resetting a host view block to point to the second physical block by means of the previous physical address, and determining if the first log was generated after the desired time. In such an embodiment, in the event the first log was generated after the desired time, the following operations may also be performed: A) accessing a second log of the plurality of logs, the second log containing a second previous physical address corresponding to a third physical block; B) resetting the host view block to point to the third physical block by means of the second previous physical address; and C) determining if the second log was generated after the desired time.

These and other advantages, benefits, and features of the present invention will become apparent to those of ordinary skill in the art upon reading the detailed description.

DETAILED DESCRIPTION

One embodiment of the present invention takes the form of a method and apparatus for storing and recovering data. Generally speaking, the embodiment may segment a storage element (such as a magnetic disk, optical read/write disk, or flash memory storage) into a first-write, or “virgin” area, and a later-write, or “overwrite” area. When data is written to a storage element for the first time, it is written into the virgin area. When data is written to the storage element any time after the first write, it is written into the overwrite area. It should be noted that the term “disk” is used for purposes of convenience throughout this document to describe any form of readable and writable computer-implemented storage, and accordingly is not necessarily limited to magnetic storage media. It should also be understood that the various embodiments described below may be contained on one or more of the following: the storage element, a second storage element, chips embedded on the storage element, controllers for the storage element, or any other storage element or hardware device. The various methods and embodiments described herein may, for example, be configured as one or more software or hardware modules operative to carry out the disclosed functions. Further, embodiments of the present invention may be located with a host, a storage device (alternately referred to as a “storage medium”), or may stand alone. Embodiments of the present invention may communicate with either the host or storage device through a network, such as the Internet, an Ethernet, a wireless network, a wired network, a telephone system, or any other network known to those of ordinary skill in the art.

FIG. 1depicts a typical computing environment100. A host105generally includes a central processing unit (CPU)110, and may include one or more additional elements, such as a display device115, a storage device120(which may be magnetic, optical, or memory-based), a network adapter125, a memory130, and so forth. The CPU110performs a variety of functions and typically controls the overall operation of the host105and interaction of the various host elements.

Some embodiments of the present invention may permit the host105to access a remotely-located storage device135across a network140, as also shown inFIG. 1. Yet other embodiments may omit the network140, and permit a host105to access only a local storage device120. The operation of the embodiment with respect to the reading and writing of data from a storage device is functionally identical, regardless of whether or not the storage device is accessed by means of a system bus (or other local means) or across a network140.

Most hosts105,145employ an operating system to manage and direct the operation of various applications as well as the reading and writing of data to and from storage media and devices120,135. The operating system typically employs a file system, such as a file allocation table (FAT), NT file system (NTFS), Macintosh file system, distributed file system, high performance file system, and so forth, to store and access data on a storage device. For example, the FAT file system divides a hard disk or other magnetic storage medium into partitions, each of which contain clusters. Each cluster may include one or more sectors, depending on the size of the disk partition. Each cluster is either allocated to a file or directory or is free (i.e., unused for data storage). A directory lists the name, size, modification time and starting cluster of each file or subdirectory it contains. As used herein, the term “block” refers to a generic unit of storage on a storage device, and may be any numbers of clusters or sectors.

At the start of each disk partition is a table (the FAT) with one entry for each block. Each entry gives the number of the next block in the same file, a special value indicating the block is not allocated, or a special value indicating the block is the last in the chain. The first few blocks after the FAT typically contain a root directory. Thus, the FAT file system manages data access and storage, and keeps a table indicating what data is stored at or on a particular block of the storage medium.

Current file systems, however, are relatively poor for backing up data. Most file systems require a user make a copy of the data, or that an application do the same. The copy is treated as a completely separate file and data element by the file system. Thus, backing up data is relatively inefficient. Further, most file systems do not provide any method for restoring data in the event data is corrupted. For example, bad writes to the storage medium may corrupt a computer file, or a virus or third party attack on a file system may result in data loss. Viruses are of particular concern insofar as they may replicate themselves, remain dormant for a time, and resurface to corrupt data again and again.

In a first embodiment, three data structures may be used to provide time-sensitive data retrieval. The embodiment may, for example, present a view of data resident on the disk at any prior time by using these three data structures. That is, the effective state of the storage device135may be “rolled back” to permit a user to access data blocks as they existed at a prior time. The embodiment may effectively provide a “snapshot” of a storage device's135status, including the data resident thereon, at any given time up to the present. This may be particularly useful, for example, where a data block underwent an unintentional or malicious change, such as due to an accidental overwrite or corruption from a computer virus.

The first data structure employed by the embodiment is referred to as the “available block bitmap.” The available block bitmap is essentially a bitmap of the available blocks in the disk. Each bit of the map represents the availability of a corresponding data block. As used herein, the term “block” refers to a logically contiguous sector (or series of sectors) of a hard disk or other storage device.

An example may assist in conceptualizing the available block bitmap.FIG. 2depicts one implementation of the available block bitmap200, as discussed in this example. Presume a storage device135includes 100 blocks of storage space. The corresponding available block bitmap200consists of 100 bits, with each bit205a-205mrepresenting a corresponding block. That is, Bit #0205amay represent block #0, bit #1205bmay represent block #1, and so on.

Each bit205a-205mis generally set to a first state to indicate a block of the storage device135is available for data to be written thereon, and a second state to indicate the block is unavailable. A block may be unavailable for writing if it already contains data. In the present embodiment, a bit205of the available block bitmap200is set to zero if the corresponding may accept data, and one if the corresponding block is unavailable for writing. Alternate embodiments may reverse this configuration.

The allocation of available blocks may now be discussed in some detail. Selection of an open block from the available block bitmap200may vary, depending on the selection algorithm employed. One exemplary selection algorithm is to select the next closest block to the right to the last allocated block (with respect to the view of the available block bitmap200shown inFIG. 2). Thus, the embodiment may write to sequential blocks of the storage device135. A variable may point to the next block open block to permit the embodiment to determine where the next write operation occurs. For example, in the bitmap200shown inFIG. 2, presuming the last allocated block was #3, the next available block becomes #4.

Prior to the first write operation to a storage device135, all entries in the bitmap200will be zero, since the storage device135contains no data. That is, the bitmap200will contain all zeros when the disk is newly available to the system for the first time. As storage blocks are occupied with data, the bits205a-205mof the corresponding blocks in the bitmap200will be changed to ones. Continuing with the example, the available block bitmap200shown inFIG. 2indicates the first four blocks of the disk contain data (and thus are unavailable for further writing), while the remaining blocks may be written to.

Typically, storage devices120,135allocate storage space in terms of bytes and/or kilobytes. The size of the available block bitmap200may be determined by dividing the capacity of the storage device135by the minimum block size. For example, many commonly-available storage devices120,135set the minimum size of a storage block at four kilobytes. Presuming a storage device135may hold 216 gigabytes of information, the available block bitmap200for the storage device135in this example would be 54 megabits, or nine megabytes, long.

Most storage devices120,135employ a file system or an input/output (“I/O”) system to keep track of the blocks at which particular data is stored. The exact implementation of the file or I/O system may vary between storage devices120,135, but each such system typically employs particular mapping algorithms to 1) logically view the storage device135as a collection of storage blocks for reading data therefrom and writing data thereto; and 2) mapping the physical structure of the storage device135to this logical view. As used herein, the term “host view block number” refers to the block number a file or I/O system (collectively, “file system”) of a host assigns to a particular physical block of a storage device. It should be noted the host view block number may be different than the entry in an available block bitmap200, or the physical block number of a storage device135. Data written by the host to a particular logically-viewed block is typically rewritten by the host to the same logically-viewed block.

The present embodiment employs a “current physical block table” to track the relationship between the physical block number of a storage device and the corresponding host view block number.FIG. 3depicts an exemplary current physical block table300. Essentially, the current physical block table keeps a snapshot of the relationship between actual physical blocks305a-305kand the host view blocks310a-310k. Thus, the current physical block table300may be used to determine the actual physical blocks305a-305kupon which data resides, as opposed to merely providing the logically-viewed blocks upon which data is resident.

In the example provided inFIG. 3, each entry of the first column of the current physical block table300contains a block number310that the file system views and/or assigns for the reading and writing of data to the storage device. The entries in the second column contain the physical block numbers305a-305kcorresponding to each host view block number310a-310k. For example, data stored in host view block number zero310ais actually stored in physical block number eighteen305aof the storage device135. Additionally, it should be noted that host view block number four310dof the exemplary table has not yet had data written thereto. Accordingly, there is no corresponding physical block number305d. Thus, the entry in the second column of the current physical block table300is “null.”

Regardless of the number that the host's file system or disk I/O system assigns as the host view block number310, the present embodiment allocates a new empty block every time data is written to the storage device135, thus preventing any block from being overwritten. Returning to the above example, the actual physical block305fof the host view block five310fis forty-seven. This means data assigned by the logical view of the file system to block five310fis located on block forty-seven305fof the physical storage device135. However, block five305fof the logical host view may have been previously assigned to a completely different physical block at some prior point, and may be assigned to a different physical block at a future point.

The embodiment may also employ a third data structure to provide a data snapshot of a given time. The third data structure is generally referred to as a “time log,” and works in conjunction with the available block bitmap and current physical block table to provide data snapshots.

FIG. 4depicts an exemplary time log400. The time log400generally maintains records405a-405gof the time and date at which data was written to the storage device135. In the present embodiment, the records405a-405gare kept in chronological order, i.e., t1<t2<t3<t4<t5. Each record405a-405gin the time log400includes at least four entries: a timestamp410; a host view block number415; a previous physical block number420; and a current physical block number425. The timestamp410indicates the time at which data was written to the storage device135. The host view block number415indicates the logical block, as viewed by the host145, to which data was written. The current physical block number425indicates the current physical block of the storage device135at which the data is stored. Finally, the previously physical block number420indicates the previous physical block of the storage device135at which the data was stored before the write operation in question. Each write operation generates a unique record in the time log400.

Generally speaking, the timestamp410for each record405a-405gmay serve as a record identifier, or a separate identifier may be assigned to each record405a-405gin the time log400.

In the example shown inFIG. 4, data written to host view block one415at time t1410is stored at current physical block fifty-six425. The data is stored in a new physical block, rather than being stored in the same block occupied prior to time t1410(i.e., physical block twenty-five420), to avoid overwriting the older version of the data. At time t2410, a second set of data is written to host view block five415. This is the first time this second set of data is written to the storage device135, since the entry in the “previous physical block”420column of the table for this write operation is “null.”

Continuing the example, the data resident at host view block five415is rewritten to the storage device135at times t5and t6410at physical blocks ninety-two and forty-seven425, respectively. In a typical storage device/computing system employing a typical file system, the data would be rewritten to the same physical block of the storage device135at times t2, t5, and t6410.

Since the embodiment does not rewrite data to the same physical block (only the same logical, or host-view block), old versions of data are never overwritten. Instead, each new version of any given data maintains the same host view block number415, but is written to a different, open physical block. An “open” block is one that is available to accept data.

Having described the available block bitmap200, current physical block table300, and time log400, the operation of the embodiment will now be discussed.FIG. 5depicts an exemplary flowchart for a write operation in accordance with the present embodiment.

Initially, a command to write data500to the storage device135is received from the file system in operation500. The write command will generally include the host view block number to which data is to be written, as specified by the host and/or file system.

Next, in operation505, the embodiment may select an open block from the available block bitmap200. Some embodiments allocate the open block nearest the physical beginning of the storage device135, in order to minimize fragmentation of the storage device135. Yet other embodiments may select the smallest contiguous set of blocks that may accept the entirety of the data, to minimize data fragmentation. Still other embodiments may employ other selection algorithms. Regardless, once the open block is selected by the embodiment, data is written to the selected block in operation510.

Following (or concurrently with) data being written to the physical block of the storage device135in operation510, the available block bitmap200is updated to ensure the physical block of the storage device135to which data is written is flagged as “unavailable.” Next, in operation515, the embodiment updates the current physical block table300to indicate the physical block305corresponding to the host view block310. Finally in operation820, a new record405is generated520in the time log400, indicating the time410the write operation occurred, the host view block415to which data was written, the prior physical block420corresponding to the host view block415, and the current physical block425corresponding to the host view block415.

It should be noted that, upon receiving the disk write command in operation500, the current physical block305from the current physical block table300is retrieved and is added to the present record405of the time log400as the previous physical block420. This typically occurs upon completion of the actual data write operation. It should also be noted that the update of the available block bitmap200, current physical block table300, and time log400may occur in any order after the write operation.

The present embodiment is particularly suited to providing a snapshot of a disk's state, and the corresponding data, at a prior time. This is colloquially referred to as “rolling back” a storage device135. To roll back a storage device135, the embodiment updates the current physical block table300so that the current physical block number305for each host view block310matches the current physical block number425identified in the time log400for the time410to which the device135is rolled back. An example may illustrate this operation.

Consider the various data structures ofFIGS. 2-4. Presume the storage device135is to be rolled back to time t1410. Such a rollback effectively undoes the write operations occurring after t1. Accordingly, the current physical block table300is updated to reflect the snapshot at time t1. In this example, three host view blocks310must be rolled back, namely host view blocks two, three, and five310c,310d,310f. (Host view block one310bwas last written at time t1410, and thus remains untouched by the embodiment.) The host view blocks two, three, and five310c,310d,310fmay be reset to point to the physical blocks seventy-two, seventy-seven, and null, respectively, restoring the status of these host view blocks310c,310,310fat time t1410. This may be accomplished because the present embodiment does not overwrite any written-to physical blocks, as discussed above.

The embodiment may employ the time log400to determine the proper physical block numbers for any time by going chronologically backward through the records405a-405gin the time log400, and setting the value of the “current physical block number”305column of the current physical block table300equal to the value of the “previous physical block”420column of the time log400for the host view block415in the record405. This process continues for each record405a-405guntil the rollback time is reached.

Accordingly, the embodiment would perform the following operations to roll back from time t6410to time t1410:

1. Set the current physical block number305fto92for host view block five310fin the current physical block table300(corresponding to record t6405f);

2. Set the current physical block number305fto91for host view block five310fin the current physical block table300(corresponding to record t5405e);

3. Set the current physical block number305fto77for host view block three310fin the current physical block table300(corresponding to record t4405d);

4. Set the current physical block number305cto72for host view block two310cin the current physical block table300(corresponding to record t3405c);

5. Set the current physical block number305fto NULL for host view block five310fin the current physical block table300(corresponding to record t2405b); and

6. Stop at the record405ahaving timestamp t1410in the time log400(corresponding to record t1405a).

An alternate embodiment may scan the time log400from time t1410forward until the earliest record for each host view block415is found, and set the current physical block305for each host view block310equal to the previous physical block420value for the earliest record405corresponding to each host view block415. In such an embodiment, the following operations may occur:

1. Set the current physical block number305bto25for host view block one310bin the current physical block table300(corresponding to record t1405a);

2. Set the current physical block number305fto “NULL” for host view block five310fin the current physical block table300(corresponding to record t2405b);

3. Set the current physical block number305cto72for host view block two310cin the current physical block table300(corresponding to record t3405c);

4. Set the current physical block number305dto seventy-seven for host view block three310din the current physical block table300(corresponding to record t4405d);

5. Ignore the record405ehaving timestamp t5410, since the current physical block table300has been previously reset for host view block five310f(corresponding to record t5405e); and

6. Again ignore the record405fhaving timestamp t6410, since the current physical block table300has been previously reset for host view block five305f(corresponding to record t6405f).

It should be noted that only the current physical block table300is updated, leaving the bitmap200and the time log400intact. In the foregoing example, if the embodiment rolls backward to time410of t1, all the physical blocks written after t1cannot be accessed. However, this does not cause storage leakage, since the snapshot of the storage device135at time t1410is accurate and all data is properly located for that time. Further, blocks storing versions of data written after the rollback time may be retrieved as necessary during a roll forward operation, because the time log table400contains all the necessary information on those blocks.

In addition to rolling backward, the present embodiment may also roll forward through the time log400to provide a snapshot of data. For example, after rolling backward to time t1410, as discussed above, the embodiment may roll forward from time t1410to time t5410. To perform a roll forward, the embodiment analyzes each record405a-405gin the time log400from the time reflected by the storage device135(here, t1) until the record corresponding to the desired time410is reached (here, t5). As the embodiment analyzes a given time record405a-405g, it updates the current physical block number305of the current physical block table300, for the host415listed in the record405, with the value in the “current physical block number”425column of the record405. That is, when a record405is accessed, the embodiment determines the corresponding host view block415and current physical block425for that record405. The embodiment then finds the entry in the current physical block table425corresponding to the corresponding host view block415, and copies the value from the time log400record's “current physical block”425column to the current physical block table300entry for the host view block310. Effectively, the embodiment reprocesses each record405a-405goccurring from the time the storage device135shows (the “disk time”) to the roll forward time.

As an example, refer again to the data structures ofFIGS. 2-4. Presume the storage device135currently reflects time t1410, and the embodiment wishes to roll forward to time t5410. The following operations would occur:

1. The current physical block number entry305fin the current physical block table300corresponding to host view block five310fwould be set to ninety-one (corresponding to the write operation at time t2410);

2. The current physical block number entry305cin the current physical block table300corresponding to host view block two310cwould be set to thirty-two (corresponding to the write operation at time t3410);

3. The current physical block number entry305din the current physical block table300corresponding to host view block three310dwould be set to thirty-three (corresponding to the write operation at time t4410); and

4. The current physical block number entry305fin the current physical block table300corresponding to host view block five310fwould be set to ninety-two (corresponding to the write operation at time t5410).

Note that the embodiment does not process record t1405aduring the roll forward, since the storage device135already reflects the data status as of that time. Once again, the bitmap200and time log400remain unaltered, permitting future rollback and/or roll forward operations.

The entirety of the storage device's135capacity will eventually be consumed as the disk is being used over time, since the embodiment does not generally reallocate used blocks. When insufficient storage capacity remains for a write operation, the embodiment returns some physical blocks containing old data to the pool of available physical blocks.

Certain data may be corrupted by a virus, write error, and so forth. Blocks containing corrupt data may be returned to the pool of available blocks by setting the corresponding bits205in the bitmap200to zero, thus making them available for future use.

However, during this process consistency between the bitmap and time log tables200,400must be maintained. When a physical block is returned to the pool of available blocks, the corresponding entries in the time log table400should reflect the fact that the block is no longer available to store old data. Such consistency can be maintained in the time log table400by adding an extra column to the time log400.

Returning toFIG. 4, the time log400may be provided with an additional column. This column is shown inFIG. 4under the header “R” (for “reuse”)430. Blocks may be flagged for reuse by setting a bit in the corresponding record405to one in the reuse430column. (In alternate embodiments, the bit may be set to zero). If a record's reuse430column is flagged, then the physical block disclosed in the record's405“current physical block number”425column may not contain the data corresponding to the host view block at the record time. Instead, this data may be overwritten.

Returning used blocks to the pool of available blocks and maintaining consistency between available blocks (as represented in the bitmap200) and the time log table400is relatively straightforward, once the invention is appreciated. However, actual selection of candidate blocks to be returned to the pool of available blocks may vary between embodiments. Different embodiments may employ different strategies or policies to determine the order in which blocks are released into the pool of available blocks. Release of blocks into the pool of available blocks also updates the available block bitmap200to reflect the released blocks' new status.

As one example, when a block is infected by a virus, the embodiment may return the block to the pool. Infection may be detected, for example, when retrieval of data from the block fails.

As another example, all blocks corresponding to records405a-405gaccessed during a rollback operation may be released into the pool of available blocks. Simply releasing these blocks does not necessarily mean the data stored on them is unavailable in the event of a roll-forward. Rather, such data is available until the block is actually reassigned and overwritten. Accordingly, an embodiment employing this strategy for release of blocks may track when such released blocks are reassigned and overwritten.

Similarly, the time log400also continues to grow with each write operation, thus occupying an ever-greater portion of the storage device's135capacity. At some point, it may prove advantageous to return at least a portion of the storage capacity occupied by the time log400to the storage device135. The time log400may be truncated, and sufficiently old records405a-405gdeleted.

It should be noted that the deletion of old records405a-405gto truncate the time log400may also free blocks for reuse. Once a record405is removed from the time log400, the corresponding blocks in the “previous physical block number”420and “current physical block number”425columns may be released into the pool of available blocks. Continuing the example, suppose the entries from t1to t4of the time log400(shown inFIG. 3) are truncated. The resulting time log400is shown inFIG. 6.

Since the records405a-405dhave been purged from the time logs400, the corresponding previous physical blocks420can no longer be accessed and data may not be retrieved therefrom. Accordingly, these previous physical blocks420(i.e., physical blocks25,72, and77) may be returned to the pool of available blocks and the available block bitmap200updated accordingly.

The three data structures discussed with respect to the present embodiment may be stored outside the ordinary partition of a storage device135. For example, these data structures may be stored in a separate secondary storage device to speed up input/output operations of a primary storage device135(i.e., the storage device actually storing data). A device controller600may be used to implement such a segmentation, as shown inFIG. 7.

The primary storage device605shown inFIG. 7may contain the data and metadata of a specific file system, written as discussed herein. The secondary storage device610may contain the various data structures herein described. The device controller600may issue commands to the secondary storage device610to facilitate the look-up and update of the three data structures concurrently with storage device commands issued to the primary storage device605to access data stored thereon. This segmentation of data structures and data storage may expedite reading and writing operations of the embodiment.

A second embodiment of the present invention generally divides at least a portion of a disk700(or other storage device, including those described above) into a virgin area705and a rewrite area710, as shown inFIG. 8. Each area consists of multiple clusters715,720, and each such cluster715,720consists of multiple sectors725a-725n,730a-730n. It should be understood that the number of sectors725a-725n,730-730nmay vary from one embodiment to another. Accordingly, sectors725nand730nrepresent generic end sectors, and do not imply a particular number of sectors per cluster. Data may be written to the sectors725a-725n,730a-725nby the embodiment. It should be understood the view shown inFIG. 8(and consequently inFIG. 10) of a storage device700is a logical representation, rather than a physical one. Accordingly, the view is used for illustrative purposes only.

The general write operation of the embodiment is depicted in the flowchart ofFIG. 9. In operation800, when the embodiment receives a command to write data to the storage device700, the embodiment first determines in operation805if the data (or more generally, the file containing the data) has been written to a block of the storage device700previously. The embodiment may employ, for example, a look-up table (discussed in more detail below) to determine if the data has been previously written. If the write operation is the first write operation for the given data, the data is recorded in the virgin area705of the storage device700in operation810. If, however, the data has been previously written to the storage device700, the data is recorded instead in the overwrite section710in operation815.

The term “data” is used generally herein to denote not only the particular data in question or being discussed, but also the structure containing the data and metadata associated with the data. For example, a block might contain data corresponding to a word processing document. As the document is revised, the data changes, but the block (i.e., the structure containing the data) maintains certain metadata, such as the block name. When the changed document is saved, the data is updated to reflect these changes but the block name and certain metadata are not necessarily changed. Thus, the embodiment typically analyzes the metadata or structure to determine whether the associated data has been previously written to the storage device in a prior iteration.

Regardless of whether or not the write to the storage device700is to the virgin or overwrite areas705,710, the embodiment, in operation820, then updates the look-up table (or other means of keeping track of block locations) with the location of the data. Typically, the location takes the form of a disk address, such as a specific cluster and sector. Some embodiments of the present invention may include an additional field or bit in the address identifying whether the data location is in the virgin or overwrite areas705,710.

Typically, writing of data occurs sequentially on the storage device or disk700. That is, sectors725a-725n,730a-730nand clusters715,720are generally logically filled in a chronological order. Thus, returning to the logical illustration inFIG. 8, both the virgin and overwrite areas705,710would be written with new data from left to right. In alternate embodiments, data writing may occur to any non-allocated sector725,730or cluster715,720within the appropriate area.

FIGS. 10 and 11, taken together, serve to illustrate the write operation of the embodiment. Initially, presume a storage device700is divided into two sections, the aforementioned virgin and overwrite areas705,710. The virgin area705extends from block zero735ato block M735m, while the overwrite area710extends from block M+1735nto block N735z. It should be understood that the number of blocks735a-735m,735n-735zmay vary from one embodiment to another. Accordingly, blocks735mand735zrepresent generic end blocks, and do not imply a particular number of blocks per virgin area or overwrite area705,710, respectively.

A first data (block1) is initially written at a specific time (T0) to the storage device700. Since T0is the first write operation for block1, block1is stored in the virgin segment705of the storage device/disk700. In the present example, block1is written to block one thousand735dof the virgin area705. As used herein, the term “block” denotes a generic data storage segment, such as a cluster725a-725n,730a-730nor sector715,720, appropriate to the storage device700being used.

Once the data is written to the storage device700, the embodiment creates an entry in the table1000. The entry generally includes a timestamp1010setting out the time and date at which the write operation took place, an identifier1020of the block735a-735zto which the data was written, and an identifier1030of the data itself (in this case, “Block1”). Some embodiments may also include a flag indicating whether the write operation occurred in the virgin or overwrite areas705,710. This may, for example, speed data retrieval by permitting the storage device700to seek the block735dwithin a smaller segment of blocks735a-735m. Further, the flag may provide a quicker response if a host queries the table1000to determine whether data was written in the virgin or overwrite areas705,710.

Next, block2is written for the first time to block one thousand six hundred735kof the virgin area705at a particular time. As with the first write of block1, the timestamp1010, block written to identifier1020, and block data identifier1030are all stored in the table1000.

At yet another time, block2is rewritten to the disk700. The embodiment may check the table1000and determine block2was previously written to the virgin area705. Accordingly, the present write operation takes place in the overwritten area710, and in this example occurs at block M+2600735p. Similarly, block1is written to the disk's700overwrite area710twice more, once at time T1at block M+3000735rand again at time T2at block M+10,000735x. As these writes take place, other writes may also occur in the overwrite area710. Additionally, the first write operation for any other data will continue to occur in the virgin area705.

It should be noted with respect toFIG. 11that the present embodiment keeps a unique record1040a-1040ffor each write iteration of data. That is, every time data is written to the storage device700, a record1040is created. Accordingly, a single block may have multiple entries, each reflecting a different write operation for the block.

At some point, the overwrite area710will fill with written data. When this occurs, the embodiment writes over the data stored in the overwrite area710, beginning with the chronologically oldest data stored therein. In other words, and with respect to the views ofFIGS. 8 and 10, the embodiment begins overwriting data on the leftmost side of the overwrite area710, proceeding towards the right. Some embodiments may check the entry in the table1000for a given data prior to overwriting. If the entry indicates the data in question is the last (or latest) write for that particular data, the embodiment will instead skip the data and overwrite the next oldest data, in chronological order. In this manner, the embodiment may prevent overwriting the most recent iteration of any given data.

Continuing with the example ofFIGS. 10 and 11, at time TC, which occurs later than time T2, the embodiment has filled the overwrite region710and begun writing over old data. Thus, at time TC, the embodiment writes the latest iteration of block1to block M+3800735u. Further, at time TC blocks M+1 to M+3799735n,735tof the overwrite region710have been written over. Thus, the chronological order of data stored in the overwrite region710runs from block M+3801 (oldest)735vto block N735z, and wraps around from block M+1735nto block M+3800 (newest)735u. This presumes no data in blocks1-3799is the most recent copy of that data.

Similar procedures may occur in the virgin area705. Once the virgin area705fills to block M735m, the embodiment may begin overwriting the virgin area705from block zero735a. Alternately, the embodiment may repartition the virgin and overwrite areas705,710, allocating additional space to the virgin area705from the overwrite area710. As yet another option, the embodiment may create additional virgin write space on a second storage device.

It is anticipated that filling the virgin area705would take a significant period of time, insofar as each block is written only once to the virgin area705. If even 10% of a 100 gigabyte (GB) disk is devoted to a virgin area705, the virgin area705can hold 10 GB of unique data written for the first time. Additionally, certain embodiments may filter the data written to the virgin area705to prevent non-critical data from being written therein. For example, some embodiments may prevent certain operating system files, such as swap files or temporary files, or disk caches, from being written into the virgin area705. Alternate embodiments may write only blocks of up to a maximum size into the virgin area705, or only blocks of certain types (for example, having certain extensions). In this manner, the virgin area705may be reserved for specific blocks or data, which in turn may optimize use of the virgin area705. In yet other embodiments, a user may be able to specify which blocks or data, or types of data or blocks, are written into the virgin area705.

Since the embodiment tracks each write of a block/data to a storage device700, the embodiment may determine not only the present location of the most recent block/data iteration, but also the location on the storage device700of the block/data at any prior time. This may prove especially useful, for example, in recovering data lost due to a computer virus, malicious attack on or deletion of data, or software crash. The present embodiment may easily retrieve the last version of a block or data known to be error-free in the following manner.

In the event a virus corrupts blocks or data, or data is otherwise damaged, a restore time may be determined. The restore time is the time from which data/blocks are to be restored, and generally is the point at which blocks were last known to be uncorrupted. The embodiment may pick a specific time (for example, three days earlier), data or the operating system's file system may be analyzed to determine the time at which data was corrupted and roll back before that tie, or the user may specify a time. In any event, once the restore time is known, the embodiment may restore the last version of the block or data stored on or prior to the restore date.

The embodiment may begin with the record having the timestamp1010closest, but equal or prior, to the restore date. The embodiment may proceed chronologically backward through the records1040a-1040fin the table1000, restoring each block or data in turn. Once an iteration of a block or data has been restored, chronologically earlier versions of that block or data are ignored.

The invention may restore the data or block in a variety of ways, several of which will be discussed in turn.

In the present embodiment, the look-up table1000may be scanned until a record having a timestamp1010earlier than, or equal to, the restore time is identified for each block or data. Again, the embodiment typically identifies or flags only the chronologically most recent record for each block during this operation.

Once a record1040a-1040fis identified for each block in the table1000and/or overwrite area710, the data stored in the blocks corresponding to that record may be copied into the virgin area705. The table1000may then be populated with a new series of records1040indicating the most recent write for the blocks/data in question occurred in the virgin area705. Such records1040are formatted in the same manner as discloser earlier herein. That is, the records1040will indicate the time the write to the virgin area705occurred, the blocks in which the data is recorded, and the identifier for each block/data. In some embodiments, a flag may be set to indicate the data is recorded in the virgin area705.

An example may assist in understanding this concept. Returning toFIG. 10, presume at time TC it is discovered that a virus corrupted certain data and/or blocks. Further presume the last known uncorrupted data version occurred at time T2. Accordingly, the restore time would be time T2. The embodiment would scan the table1000ofFIG. 11, looking for records having a timestamp1010equal to or predating time T2for each block. The embodiment would then copy the corresponding data to the virgin area705. Presume block1is copied to block one thousand two hundred735fof the virgin area705, and block2to block one thousand three hundred735hof the virgin area705.

After copying, the embodiment may generate new records1040g-1040hindicating the time and write location of the blocks to the virgin area705, as shown inFIG. 12A. The embodiment may further erase the overwrite area710up to time T2, since the most recent version of each block prior to time T2is now resident in the virgin area705. In the present example, block M+3801 to M+9,999735v,735wwould be erased (since blocks M+1 to M+3800735n,735uhave been overwritten by the embodiment with chronologically later data).

Further, since the virgin area705now contains clean records1040g-1040has of the restore time (T2, in the example ofFIGS. 10 and 11), the overwrite area710may be erased from the restore time forward to eliminate corrupted versions of data/blocks. In the example given with respect toFIGS. 10 and 11, blocks M+1 to M+3800735n,735uwould be erased, as would block M+10,001 to N735y,735z.

In still another embodiment, the entire overwrite area710may be erased, since blocks occurring after time T2(the restore time) may be corrupt, and the latest version of each block prior to time T2is resident in the virgin area705.

Still another embodiment may operate as just described, but each record in the table may include an additional timestamp indicating the last time at which the block in question was written to the virgin area705.FIG. 13depicts such a table1100. When the embodiment copies the record to the virgin area705, all the records for that particular block/data may be updated to reflect the writing of the most recent, clean version of the block to the virgin area705.

In a different embodiment, the table1000may simply be truncated and all records1040a-fcreated on a date later than the restore deleted. In such an embodiment, the various file pointers would be updated to point to the location of the most recent record for each block remaining after table truncation. This is shown, for example, inFIG. 12B.

In yet another embodiment, the embodiment may scan chronologically backwards from the restore date. As the first record1040for each unique block or data is encountered, that record1040may be duplicated in the table1000with a timestamp1010equal to the time of duplication. Essentially, a new record1040is created in the table1000for each block with a timestamp1010equal to the time and date at which the restore operation commenced, or alternately at the time the old record1040was identified by the embodiment during the restore operation.

In still another embodiment, the latest record1040for each block or data that is nonetheless chronologically prior to the restore date may be updated with a new timestamp1010reflecting the time of the restore operation (or the time at which the record1040was identified).

In a further embodiment, the embodiment may locate the version of the block corresponding to the record1040closest in time, but prior to, to the restore date. The embodiment may then copy the block from the block(s) specified in that record to the block(s) specified in the latest record for that block. In this manner, no table entries are changed, but the uncorrupted blocks nonetheless replace corrupted ones. It may be advantageous to include a field for each record1040corresponding to such an updated block pointing back to the original record1040corresponding to the block from which data is copied.

Other methods for restoring data, files, and/or and blocks will occur to those skilled in the art upon reading the present description of the embodiment's operation and the implementation of the look-up table.

The look-up table may be loaded into the memory of the host to permit quicker operation during a read or write operation from or to the storage device.

A third exemplary embodiment of the present invention is depicted inFIG. 14. The third embodiment may include, among other elements, a super block1405, a disk log1410, a host view block table (“HVBT”)1415, a lot map1420, and a cache1425. The super block1405points to the locations where necessary information for the embodiment to write, read, access, audit, and recover data is stored. The disk log1410contains logs, as described in more detail below, for data written to the storage device using the embodiment. The HVBT1415, which is similar to the “current physical block” table300previously described with reference to first embodiment, tracks the relationship between the physical block number of the storage device1430and the corresponding host view block number. The lot map1420, which is similar to the “available bit map”200previously described with reference to the first embodiment, tracks the number of blocks used in a lot and the availability of a lot for data storage. As used herein, a “lot” refers to a collection of blocks. Each block is a unit of data storage. A block may be, for example, one bit, one byte, or other length.

Software, hardware and other drivers and applications (“hosts”)1435that issue I/O requests may communicate with, and receive communications from, the embodiment and any associated storage devices1430. Some host1435I/O requests may be pass-through writes to the storage device1430, which generally means the write does not require block address mapping. Such pass-through writes will generally not require various read and write operations between the various elements of the embodiment. Other host I/O requests will result in various read and write operations between elements of the embodiment, the storage device1430, and the host1435. For example, a host1435may issue an I/O request to the embodiment to write some data to the storage device1430. Upon receiving the write data request, the embodiment may read and write logs from and to the disk log1410, the HVBT1415, the lot map1420, and the storage device1430. Continuing with the example, the embodiment may write the data to the storage device1430. Prior to writing the data to the storage device1430, the embodiment may read the lot map1420to determine the next available lot for storage on the storage device1430. When the embodiment writes the data to the next available lot, the embodiment may update the lot map1420to indicate that the lot is no longer available. During this write operation, the embodiment may update the disk log1410to contain information about the write operation such as start and end time of the write operation. The embodiment may also read the HVBT1415to determine where any data overwritten by the host's1435write request was previously stored on the storage device1430and write this information into a log in the disk log1410. The embodiment may further update the HVBT1415to indicate the physical addresses/blocks where the data from the write request was stored. Various ways to the embodiment may interact with the host1435and the storage device1430will be described in more detail below. Further, as previously described above for other embodiments, the various tables and other data structures and algorithms of the third embodiment may be located on one or more separate storage devices, chips embedded on the storage device, control cards, or other hardware devices.

The third embodiment of the present invention may divide at least a portion of a storage device1430into a reserved area1505, a metadata area1510, and a data area1515, as shown inFIG. 15. Information from the host1435that passes through the embodiment may map to one or more of these areas1505,1510,1515. The metadata area1510may contain the super block1405, the HVBT1415, the lot map1420, and a “snapshot” of the HVBT1415. The data area1515may contain the disk log1410and the data stored on the storage device1430. One or more copies of the super block1405may be contained in the metadata area1510, the data area1515, or both.

As an example, a storage device1430with a 160 gigabyte capacity with lot sizes of 16 data blocks may be divided so that a fat allocation partition table, the super block1405, the lot map1420, the HVBT1415, a snapshot of the HVBT1415, and the disk log1410occupy approximately 22,632 megabytes of space. Of this space, approximately two megabytes may be set aside for a file allocation partition table, eight kilobytes for the super block1405, 36 megabytes for the lot map1420, 2,195 megabytes for the HVBT1420, 2195 megabytes for a snapshot of the HVBT1420, and 18,204 megabytes for the disk log1410. The remaining space for the storage device1430may be used for data storage or other purposes. This foregoing example is merely illustrative of a potential way to assign the number of data blocks in a lot and to allocate a storage device's1430space for the tables and other data structures discussed herein. Accordingly, other lot sizes, allocations of space for the tables and other data structures, or storage devices of differing capacities, may be utilized. Further, as previously described above with respect to other embodiments, the various tables, data structures and algorithms of the third embodiment may be located on one or more separate storage devices, one or more hardware elements embedded on or associated with the storage device, control cards, or other hardware devices.

The super block1410of the third embodiment may be similar to a super block employed for a hard disk drive's file system. For example, the super block1410may contain information regarding the storage device's1430identification number, the current version of any related software, and the size of the storage device1430reported to a host1435. Additionally, the super block1410may contain information regarding the number of blocks per lot, the sizes and locations of the lot map1420and/or HVBTs1415, the size of an entry for the HVBT1415, the next lot available for data storage, the number of free lots, the next log identification number, the total number of lots on the storage device1430, the number of lots that are immediately available for use, the “current lot index”, and the “origin lot index”, and any other information of interest. The “current lot index” is the index to the next available free lot.

Initially, the “origin lot index” is the index to the lot corresponding to the initial write operation performed by the embodiment and may be used to indicate where the embodiment should start to find lots to return to the lot pool during a free lot operation, as described below. The “origin lot index” may change over time. For example, after executing a return old lots to the available pool, as described below, the “origin lot index” may be changed to indicate that the next lot physically after the last lot selected to be returned to the free lot pool is the “origin lot” (or, alternatively, the selected lot may become the origin lot). Lots prior to the new origin lot are flushed from the history of operations by the embodiment. Thus, from that point on, the embodiment would regard the lot in question as corresponding to the initial write operation, and the lot becomes the origin point.

Accordingly, from a conceptual point of view, the “origin lot” is the lot corresponding to the “first” write operation for the embodiment, and the “origin lot index” indicates the “origin lot.” Additionally, lots located between the “origin lot,” as indicated by the “origin lot index,” and the next available lot, as indicated by the “current lot index,” are considered to be located within an “in-history” region. Any lots located within the “in-history” region are potentially available for return to the lot pool during a free lot operation in which the algorithm begins by searching from lots to return starting with the oldest lot.

A logical representation of a layout for lots1600a-non the storage device1430is depicted inFIG. 16. It should be understood that the number of lots100a-nmay vary from one embodiment to another. Accordingly, lot1600nrepresents a generic end lot, and does not imply a particular number of lots per storage device1430. Each lot1600a-nmay include a log1605and a data field1610. The log1605, as described in more detail below, may contain control information for a lot1600a. The data field1610may contain the actual data stored on the storage device1430for the lot1600. In the embodiment depicted inFIG. 16, each log1605is one sector and each data field1610is sixteen sectors. It should be understood that the number of sectors for a log1605and a data field1610for any lot1600a-nmay differ from the example presented inFIG. 16. Further, the log1605and data field1610for any lot1600a-nmay be side-by-side as depicted inFIG. 16or may be separated.

An example of a data structure for a record1705of the lot map1420is depicted inFIG. 17. The lot map's record1705may include a flag field1710and a number field1715for a lot. The flag field1710may include an in-history flag, a check-point flag, a valid data flag, or any other control information of interest for the lot. The in-history flag may indicate if a lot1600is located in an in-history region, as described above. The check-point flag may indicate if a lot1600has been investigated for check-pointing. The valid data flag may indicate if at least one block in the lot1600contains data. The number field1715may indicate the actual number of blocks in the lot that contain data.

An example of a data structure for the HVBT1415is depicted inFIG. 18. The HVBT1415may include a flag field1805and disk block field1810. The flag field1805may include a valid data flag. The valid data flag may indicate if the block contains data. The disk block field1810may indicate the physical address/block to which the host view address/block currently points.

An example of a data structure for a log1600is depicted inFIG. 19. It should be understood this date structure is exemplary. Alternate embodiments may omit some or all of the listed fields or may include additional fields. Each log1600a-nmay include fields for control information1905and fields for one or more “previous block entries”1910a-n. It should be understood that the numbers of “previous block entries” may vary from one log1600to another. Accordingly, “previous block entry”1910nrepresents a generic end “previous block entry,” and does not imply a particular number of “previous block entries” per log1600. The previous block entry field generally identifies to what prior physical block, if any, the data corresponding to the log was last written.

The control information fields1905may include an operation code fields1915(identifying, for example, if the log corresponds to a read or write operation), timestamp fields1920,1925indicating the start and end times of the associated operation, a block length field1930indicating the block length for the operation, a “previous block entry count” field1935indicating the number of “previous block entries”1910a-nappended to this log1605, and host start and end block fields1940,1945indicating the starting and ending host addresses/blocks for the operation. Effectively, the host start and end block fields function as a pointer to one or more host view blocks associated with the log.

When a log1605is recorded, it generally should be wholly recorded or not recorded at all because any partial writing of a log1605may compromise the integrity of the log records stored by the embodiment. When a log1605requires only one sector, hardware associated with the storage device1430will generally alert a user if a log1605was only partially recorded to a sector. However, when more than one sector is required for a log1605, hardware associated with the storage may fail to alert a user if a log1605was successfully recorded to the multi-sectors. Accordingly, the control information fields1905may also include a multi-sector sequence number field1950, which may be used to store a predefined number to check if a log1605has been properly recorded when more than one sector is required to contain the log1605. The check may be done by writing a number in a sector and the same predefined number in the next sector. If these numbers match, the multi-sector write was likely successful.

Each “previous block entry”1910a-nmay include a partial length field1955indicating the number of the blocks referenced in particular “previous block entry”1910a-nand fields1960,1965for indicating the previous starting and ending physical addresses/blocks for these blocks. The number of “previous block entries”1910a-nmay vary for each log1605.

An example may assist in conceptualizing a log1605.FIG. 20depicts a portion of the control information field1950and the “previous block entry” fields1910a-nfor three logs1605a, d, nthat correspond to three write operations. For simplification, only logical representations of portions of the control information field1905for each log1605a, d, n, specifically, the starting host block address field1940and the block length field1930, are shown inFIG. 20. With respect to any “previous block entries”1910a-nfor a log1605a, d, n, only logical representations of the fields1955,1960,1965for partial block length and the starting and ending previous physical addresses/blocks are shown inFIG. 20.

As part of the example, assume a first write operation. This first write operation is represented by log #01065aand writes16logical blocks starting from host view address/block10and ending at host view address/block25. Further, assume that the 16 logical blocks for the first write operation are written to physical addresses/blocks one through 16 on the storage device1430. Accordingly at the first write operation, host view address/block10points to physical address/block one (functioning as a pointer), host view address/block11points to physical address/block two, and so on. A first log1605awill be recorded reflecting this write operation. For the control structure fields1905of this first log1605a, the starting host view address/block is10and the block length is16. Since this is the first write operation, there will be one “previous block entry”1910afor the first log1605a. The partial length for this “previous block entry” is16(representing 16 blocks) and the “previous physical address entry” is NULL (since this is the first time a write operation has occurred at host view addresses/blocks10through26).

Now assume a fifth write operation time occurs at a later time. This fifth write operation is represented by log #41605d, and writes16logical blocks starting from host view address/block11and ending at host view address/block27. Further, assume that the 16 logical blocks for the fifth write operation are written to physical addresses/blocks69through84on the storage device1430. Finally, assume that host view addresses/blocks11through25have only been previously written to at the first write operation and that host view address/block26has not yet been written to. Accordingly, just prior to the fifth write operation, host view addresses/blocks11through25point to physical addresses/blocks two through16, respectively, and host view address/block26points to NULL. After the fifth write operation, host view addresses/blocks11through25points to physical addresses/blocks69through83, respectively, and host view address/block26points to physical address/block84.

Continuing the example, a fifth log1605dis recorded corresponding to this fifth write operation. For the control structure fields1905of this fifth log1605d, the starting host view address/block is11and the block length is16. There are two “previous block entries”1910a-bfor the fifth log1605dbecause host view addresses/blocks11through25(i.e., 15 of the host view addresses/blocks) are overwritten for the first time and host view address/block26is written to for the first time. For the first “previous block entry”1910aof the fifth log1605d, the partial length is15because 15 consecutive host view addresses/blocks (i.e., host view addresses/blocks11through25) are overwritten, and the “previous starting physical block address” is2since host view address/block11pointed to physical address/block2prior to the fifth write operation. For the second “previous block entry”1910bof the fifth log1605d, the partial length is one because one host view address/block (i.e., host view address/block26) is written to for the first time, and the “previous physical starting block address” is NULL.

Continuing with the example, assume an eleventh write operation occurs at a later time. This eleventh write operation is represented by log #101605n, and writes16logical blocks starting from host view address/block10and ending at host view address/block25. Further, assume that the 16 logical blocks for the eleventh write operation are written to physical addresses/blocks171through186on the storage device1430. Finally, assume that host view address/block10has only been previously written to at the first write operation and that host view addresses/blocks10through25have only been previously written to at the first and fifth write operations. Accordingly, just prior to the eleventh write operation, host view address/block10points to physical address/block1, and host view addresses/blocks11through25point to physical addresses/blocks69through83, respectively. After the eleventh write operation, host view addresses/blocks10through25point to physical addresses/blocks171through186, respectively.

An eleventh log1605nis recorded corresponding to this eleventh write operation. For the control structure fields1905of this eleventh log, the starting host view address/block is19and the block length is16. There are two “previous block entries”1910a-bfor the eleventh log because host view address/block10is overwritten for the first time and host view addresses/blocks11through25are overwritten for the second time. For the first “previous block entry”1910aof the eleventh log1605n, the partial length is one because a single host view address/block (i.e., host view address/block10) is overwritten for the first time, and the “previous starting physical address” is one since host view address/block10pointed to physical address/block one prior to the eleventh write operation. For the second “previous block entry”1910bof the eleventh log1605n, the partial length is15because 15 consecutive host view addresses/blocks (i.e., host view addresses/blocks11through25) are overwritten for the second time, and the “previous starting physical block address” is69since host view address/block11pointed to physical address/block69prior to the eleventh write operation.

The general write operation of the third embodiment is depicted in the flowchart ofFIG. 21. In operation2100, the embodiment receives a command to set timestamp for a write data request to the storage device1430. Next, the embodiment determines in operation2105if the write data operation will be a pass-through write. If the write operation is a pass-through write, then, in operation2110the data is written to the storage device1430and the process ends. If the write operation is not a pass-through write, in operation2115the embodiment is accessed and determines an available lot to write the data. The embodiment also updates the super block1405and the lot map1420with the corresponding lot and/or write information. Next in operation2120, the embodiment updates the HVBT1415with the newly allocated lot address.

In operation2125, the embodiment determines if another lot is required to write the data. This typically occurs if the size of the data is greater than a single lot's storage capacity. If another lot is required, the embodiment returns to operation2115to allocate additional lots. If another lot is not required, the embodiment executes operation2130and determines if a specified threshold capacity of the metadata area1510(“flush threshold”), which may or may not be the storage space set aside for the metadata area1510, has been reached. If the flush threshold has been reached, the existing metadata may be approaching a limit and some metadata may need to be purged to facilitate further operation of the embodiment. Accordingly, in operation2135, the embodiment deletes select metadata in the metadata area1510to free up space in the metadata area1610. Typically, the oldest lot map records1705and corresponding HVBT1415entries are deleted. This may result in the return of old lots to the free lot pool, as described below.

Regardless of whether or not the embodiment flushes metadata, in operation2140the embodiment determines if the number of free lots available on the storage device1430is under a specified lot threshold number, which may be any number of lots greater than or equal zero. Alternatively, the specified lot threshold number may be the minimum number of lots required for writing the data to the storage device1430. If the number of free lots is less than the lot threshold number, the embodiment executes operation2145and may alert a user that occupied lots on the storage device1430need to be returned (or otherwise made available) for use in future write operations. Alternatively, the embodiment may automatically act to free lots, with or without notifying the use. Regardless of whether or not the embodiment alerts a user that occupied lots on the storage device1430need to be returned, the embodiment, in operation2150, writes the data to the storage device1430.

The general read operation of the third embodiment is depicted in the flowchart ofFIG. 22. In operation2200, the embodiment determines if a read data request is a pass-through read. If the read data request is a pass-through read, the embodiment accesses operation2205and reads the data from the storage device1430. If the read data request is not a pass-through read, the embodiment executes operation2210and collects the block address to be read. The block addresses to be read may be collected from corresponding entries in the HVBT1415. The embodiment then, in operation2215, reads data in the block addresses collected in operation2210.

Since data is only overwritten when necessary or authorized by a user, data (or corresponding files) from a particular prior time may be retrieved by the embodiment. Generally,FIG. 23is a flowchart depicting a series of operations executed by the embodiment to retrieve data in the state it existed at a previous time (a “snapshot” of the data as of the time in question). It should be noted that the desired time may be user-specified.

Initially, in operation2300, the embodiment disables any lot return operations. The lot return operation is discussed in more detail below. Briefly, the lot return operation permits the embodiment to reallocate used lots as free lots to facilitate further data storage.

Next, in operation2305, the embodiment copies the HVBT1415in its current format to a snapshot zone designated on the storage medium1430. The snapshot zone may be in the metadata portion1510of the storage medium1430, or it may be in the data storage portion1515of the storage medium1430. By copying the HVBT1415in this manner, the embodiment may effectively “roll back” through the various lots' logs and return the HVBT1415to the state it occupied at the specified prior time, without altering the actual HVBT1415.

In operation2310, the embodiment accesses the log1605of the prior lot. The first time the embodiment executes operation2310, the prior lot is the last lot written before the snapshot retrieval operation commences. The embodiment may use the log1605of the lot to update the snapshot HVBT addresses in operation2315. Specifically, the embodiment may retrieve the previous block entries1910a-nfrom the lot log1605, which (as discussed above) indicate which physical addresses/blocks the host addresses/blocks pointed to prior to the execution of the operation corresponding to the lot in question. That is, the previous block entries1910a-nmay indicate where the host blocks were written on the physical blocks of the storage medium1430before the write operation of the log1605occurred. The embodiment may employ this information to change the records of the snapshot HVBT; the entries of the snapshot HVBT are updated so that the host view blocks correspond to the physical blocks in accordance with the retrieved previous block entries. Essentially, this returns the snapshot HVBT to the state the HVBT1415was in prior to execution of the operation associated with the prior lot.

In operation2320, the embodiment determines if the target lot has been reached. The “target lot” is the lot written at the time of the snapshot, or, if no such log exists, the first lot written prior to the time of the snapshot. If the target lot has not been reached, the embodiment returns to operation2310and accesses the log1605of the prior lot. Now, the “prior lot” is the lot prior to the one previously accessed in operation2315. Effectively, the lot accessed is decremented by one, thus permitting the embodiment to continue the process of rolling back the snapshot HVBT.

When the target lot is reached, the snapshot HVBT's state will be updated to match the state of the HVBT1415at the desired time. Thus, the embodiment may provide a view of the data resident on the storage medium1430matching the view at the desired time- or, in other words, the embodiment may provide the desired snapshot. The embodiment may, for example, present the snapshot to a user through a display (such as a computer monitor, television, other display screen, printer, and so forth). Accordingly, the retrieval of the snapshot is complete, and the lot return operation may be re-enabled in operation2325.

FIG. 24depicts a method that may be executed by the embodiment in order to recover old data that may appear to the host to be overwritten, such as an old version of a file. Initially, in operation2400, the embodiment retrieves a snapshot of the storage medium1430as of the desired time, which is typically the time at which the old data existed. The method for retrieving a snapshot in this manner is generally discussed above with respect toFIG. 23.

After retrieving the snapshot, the embodiment may execute operation2405, in which it seeks the target file (or data) on the snapshot of the HVBT1415. The embodiment seeks the target file on the snapshot of the HVBT1415as generally described above and also as known to those of ordinary skill in the art, in accordance with (for example) the file system and operating system used to access data on the storage medium1430.

In operation2410, the embodiment may read the file data accessed from the snapshot HVBT. In operation2415, the embodiment may write the file data to the storage medium1430through the file system, generate a lot and log1605for the write operation, and update the original (non-snapshot) HVBT1415accordingly. In this manner the retrieval and writing of the old data/old file may be logged by the embodiment in a manner similar to a standard write operation.

Finally, in operation2420, the various lot return processes may be re-enabled.

In addition, the snapshot retrieval process may be employed to “roll back” the entire storage medium1430to the desired time (i.e., the time of the snapshot). After the snapshot retrieval procedure ofFIG. 23is performed, the embodiment may enable all input/output operations (such as reads and writes to the storage medium1430), copy the snapshot HVBT over the original HVBT1415, and update the file system accordingly to reflect the changes in the HVBT1415. It should be noted that the operations associated with updating the file system may vary with the type of file system employed. The lots and lot logs1605may likewise be updated, lots occurring after the snapshot time may be deleted or ignored, or such lots may be unaltered. It should also be noted that the snapshot HVBT need not necessarily be copied over the original HVBT1415. The embodiment may instead update the file system to reference and employ the snapshot HVBT instead of the original HVBT1415. In this manner, should a user wish to return the disk to a pre-rollback state, the embodiment may update the file system to reference and employ the original, unaltered HVBT1415.

FIG. 25generally depicts a method for returning old lots to the available pool. This may be desirable, for example, when the data writing portion of the storage medium1430nears its capacity. By returning old lots to the available pool, additional write operations in accordance with the embodiment's operation may be performed.

Initially, the embodiment selects a lot in operation2500. The oldest lot is generally chosen because it represents the oldest data written to the storage medium1430, and thus the data least likely to need recovering at a later date. The oldest lot is earliest lot between the current write point/operation and a current origin point. It should be noted that the current origin point may be moved, as described below.

With respect to the origin point,FIG. 26generally depicts a storage medium1430with an initial origin2605and a current origin2610. The “current origin”2610is the origin point as of the current time, while the “initial origin”2605is the origin point at the time the first write operation to the storage medium1430was executed by the embodiment. As the origin point moves, lots may fall between the initial origin2605and current origin2610. Such lots are generally referred to as “out-of-history lots.” By contrast, lots between the current write operation and current origin are “in-history lots.” InFIG. 26, occupied lots are generally shown as black boxes.

Returning toFIG. 25, once the operation has identified the oldest lot, it may act to free certain out-of-history lots and return such lots to the pool of available physical blocks (“available pool”). In operation2505, the embodiment identifies which out-of-history lots were overwritten by the selected, oldest lot. That is, certain out-of-history lots may be older version of the data stored in the oldest lot. The embodiment (still in operation2505) may remove the data block from such out-of-history lots.

In operation2510, the embodiment may remove the data block from the oldest lot, so long as the oldest lot has been overwritten by an in-history lot.

In operation2515, the embodiment may remove the in-history flag from the selected, oldest lot. This identifies the oldest lot as no longer being an in-history lot, and sets the current origin to equal the oldest lot.

In operation2520, the embodiment may update the super block1405and lot map1420. Such updates generally include removing any or all log data associated with the out-of-history lots acted upon in operation2505and log data associated with the oldest lot. The embodiment may also update the lot map1420and super block1405to indicate these physical blocks are again free lots.

In operation2525, the embodiment determines if sufficient lots have been returned to the available pool. In the event no more lots are needed, the process terminates. Otherwise, the embodiment returns to operation2500and reiterates the process. (Because the oldest lot identified in the second iteration of operation2500is different from the oldest lot identified in the first iteration, different out-of-history lots may be flagged in operation2505to be returned to the available pool.)

Generally, the embodiment does not simply return all out-of-history lots to the available pool. It is conceivable that an out-of-history lot may be the most recent copy of data or a file, and thus returning it as a free lot would cause the most recent copy of the data to be lost. Accordingly, the afore-described operation prevents such losses.

FIG. 27generally depicts a method for returning all lots (or blocks) associated with a particular file to the available pool. Initially, in operation2700, the embodiment deletes the file through the file system in a conventional manner. Next, in operation2705, the embodiment flushes the storage medium1430, partition, or other volume to reflect this deletion.

In operation2710, the embodiment disables the lot return operation described above with respect toFIGS. 25 and 26. This prevents inadvertent allocation of lots to the available pool during the present process.

Next, in operation2715, the embodiment creates a snapshot of the HVBT1415and copies the snapshot HVBT to the snapshot zone. This procedure was generally described above with respect toFIG. 23. In this particular process, the desired time of the snapshot is the time at which the process ofFIG. 27is initiated.

In operation2720, the embodiment cleans the metadata of the file system. This typically includes clearing the file system bitmap and the lot map1420. The file system bitmap referenced in operation2720is that of the standard file system employed by the storage medium and/or host. “Cleaning” the file system bitmap is the operation of setting the blocks of the file that is to be deleted to a free state in the bitmap of the file system.

Continuing with operation2720, the embodiment also removes the current lot, if corresponding to (or occupied by) some version of the deleted file, from the lot map. This, in turn, flags the lots as free and returns them to the available pool. It should be noted that the cleanup operations of operation2720are executed only if the current lot corresponds to the deleted file. If the current lot does not correspond to the deleted file, no metadata must be cleaned.

In operation2725, the snapshot of the HVBT1415is rolled back in a manner described above, inFIG. 23, with respect to operations2300-2325. That is, the snapshot HVBT is adjusted to the state the HVBT1415occupied immediately prior to the write operation corresponding to the last write of the deleted file (i.e., the last lot of the deleted file). Essentially, the snapshot HVBT is updated to remove the operations associated with the last lot of the file, and the correspondence between host view blocks and physical blocks is rolled back accordingly.

In operation2730, the embodiment determines if the origin lot has been reached. If the origin lot has not been reached, then all prior write operations associated with the file being deleted may not have been removed. Accordingly, the embodiment proceeds to the next-most recent lot and re-executes operation2720. Thus, the embodiment rolls back through all lots until the origin lot is reached, deleting only those lots associated with some version of the deleted file. All other lots are ignored and the lot map1420is not adjusted. Only when a lot associated with some version of the deleted file is found and cleaned is the lot map1420updated.

After the embodiment reaches the origin lot, operation2735is accessed and lot return operations are again enabled. It should be noted that, following operation2730, the embodiment may erase the snapshot HVBT.

Alternative embodiments may entirely omit the process of making a snapshot HVBT and instead update the standard HVBT.

As previously mentioned, the storage device may be located remotely from the host and accessed across a network. In such situations, it may be relatively simply to add an additional storage device to be accessed by the host (or hosts) across the network when either the virgin or overwrite areas of the first storage device become filled. This would prevent overwriting of data. Such an embodiment would be especially advantageous where the remote storage devices could be presented to the host as a locally-accessible device, rather than a device accessed across a network. Local presentation of the storage devices may simplify interaction between the storage devices and the host, including the reading, writing, and restoring of data. This presentation may be accomplished by means of a driver, software application, firmware, or hardware. For example, the NetDisk product manufactured by XIMETA, Inc. of Irvine, Calif. may be especially useful in certain applications and embodiments described herein.

Those of ordinary skill in the art will appreciate that the storage device, look-up table, and methods for storage may all take a variety of forms. Although the invention has been described with respect to particular embodiments and methods of operation, it should be understood that those embodiments and methods of operation are exemplary, rather than limiting. Accordingly, alternate embodiments and/or methods of operation may occur to those skilled in the art upon reading this disclosure, and are embraced by the present invention.