Method and apparatus for backup and recovery system using storage based journaling

1. A method for processing data in an application data store comprising:

producing at least a first snapshot of an application data store, the application data store configured to receive data by way of write operations issued from a host device;

storing each journal entry for each write operation issued from the host device in a journal data store, thereby accumulating a list of journal entries;

monitoring an amount of free space on the journal data store;

when the amount of free space falls below a first threshold value, then removing one or more journal entries from the journal data store, thereby increasing the amount of free space, wherein enough of the journal entries are removed so that the amount of free space rises above a second threshold value, and

wherein each journal entry comprises a fixed-size header portion and a variable-size data portion, wherein the journal data store comprises a first storage area within which a plurality of header portions are defined and a second storage area for storing a plurality of data portions, and wherein storing a journal entry includes allocating one of the journal headers and allocating a sufficient amount of space in the data portion to contain data associated with the write operation.

2. The method of claim 1 wherein removing one or more journal entries includes updating the first snapshot by applying one or more journal entries to the first snapshot, beginning with an oldest journal entry, wherein journal entries applied to the first snapshot are removed from the list of journal entries thereby increasing the amount of free space of the journal data store.

3. The method of claim 1 wherein removing one ormore journal entries includes looking for a most recent snapshot, removing journal entries in the journal data store that are earlier in time than the most recent snapshot.

4. The method of claim 1 wherein the first threshold value and the second threshold value are different.

5. The method of claim 1 wherein storing each journal entry includes allocating one of the journal headers from the first portion such that the journal headers are always allocated in sequential manner and when the last journal header is allocated then allocating journal headers from the beginning of the first portion in sequential manner.

6. A data processing method comprising:

producing at least a first snapshot of at least a portion of an application data store, the application data store being configured to receive write operations issued from a host device;

recording a plurality ofjournal entries, each journal entry being recorded for a write operation issued from the host device, each journal entry being stored in a journal data store thereby consuming an amount of free space of the journal data store;

updating the at least first snapshot with at least one journal entry and removing the at least one journal entry when the amount of free space falls below a first threshold value thereby increasing the amount of free space of the journal data store so that the amount of free space rises above a second threshold value,

associating sequence numbers to the first snapshot and to the journal entries;

receiving a target time;

determining a beginning journal entry based on the sequence numbers associated with the journal entries and the sequence number associated with the first snapshot;

updating the first snapshot by applying the beginning journal entry to it; and

performing additional updates to the first snapshot by applying journal entries that are subsequent in time to the beginning journal entry and prior in time to the target time.

7. The method of claim 6 wherein the step of updating includes periodically monitoring the amount of free space of the journal data store and if the amount of free space falls below the first threshold value then updating the at least first snapshot.

8. The method of claim 7 wherein the step of updating the at least first snapshot is repeated for a number ofjournal entries so that the amount of free space rises above the second threshold value.

9. A data processing method comprising:

producing at least a first snapshot of at least a portion of an application data store, the application data store being configured to receive write operations issued from a host device;

recording a plurality ofjournal entries, each journal entry being recorded for a write operation issued from the host device, each journal entry being stored in a journal data store thereby consuming an amount of free space of the journal data store;

updating the at least first snapshot with at least one journal entry and removing the at least one journal entry when the amount of free space falls below a first threshold value thereby increasing the amount of free space of the journal data store so that the amount of free space rises above a second threshold value;

producing additional snapshots thereby accumulating a plurality of snapshots;

associating sequence numbers to the snapshots and to the journal entries;

receiving a target time;

determining a selected snapshot based on the target time;

determining a beginning journal entry based on the sequence numbers associated with the journal entries and the sequence number associated with the selected snapshot;

updating the selected snapshot by applying the beginning journal entry to it; and

performing additional updates to the selected snapshot by applying journal entries that are subsequent in time to the beginning journal entry and prior in time to the target time.

10. The method of claim 9 wherein the selected snapshot is a first snapshot.

11. The method of claim 9 wherein the selected snapshot is closest in time to the target time and prior in time to the target time.

12. A storage system for processing data comprising:

a production data store configured to receive write operations from a host device;

a snapshot data store configured to store one or more snapshots of at least a portion of the production data store;

a journal data store configured to store one or more journal entries; and

a controller configured to:

access the production data store and the snapshot data store to store one or more snapshots of at least a portion of the production data store on the snapshot data store;

access the journal data store to record a journal entry for each write operation from the host device;

update one of the snapshots with some, but not all, of the journal entries thereby leaving some journal entries for a data recovery operation and removing at least one journal entry when an amount of free space in the journal data store falls below a first threshold value so that the amount of free space rises above a second threshold value,

wherein the controller is further configured to:

associate sequence numbers to the snapshots and to the journal entries;

receive a target time;

select a snapshot based on the target time;

determine a beginning journal entry based on the sequence numbers associated with the journal entries and the sequence number of the selected snapshot;

update the selected snapshot by applying the beginning journal entry to it; and

perform additional updates to the selected snapshot by applying journal entries that are later in time than the beginning journal entry and earlier in time than the target time.