# US 8,543,544 B2 · Checkpoint based progressive backup

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,543,544 B2
- Document ID: US8543544B2
- Status: Granted
- Kind: B2
- Application number: 13/345,584
- Filed: 2012-01-06
- Published: 2013-07-11
- Granted: 2013-09-24
- Earliest claimed: 2012-01-06
- Assignees: Apple Inc.
- Applicants: Frank Lu; James Qiu; Jonathan Thatcher; Murali Vemulapati; Carl Wang; Terrence Barwegen
- Inventors: Frank Lu; James Qiu; Jonathan Thatcher; Murali Vemulapati; Carl Wang; Terrence Barwegen
- Web page: https://patentgrep.com/patent/US8543544B2

## CPC

- G06F 11/1446: Point-in-time backing up or restoration of persistent data
- G06F 16/2322: {using timestamps}
- G06F 2201/84: Using snapshots, i.e. a logical point-in-time copy of the data
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Methods, program products, and systems for checkpoint based progressive backup are described. When a system receives a request to update a page of a storage device storing database files of a database, the system can update the page and replicate the updated page in a shadow page in a backup queue. The backup queue can store multiple shadow pages, where each updated page can correspond to at most a specified number of shadow pages in the queue. Each shadow page can be associated with a timestamp of a latest update. At pre-specified temporal checkpoints, the system can write the shadow pages in the queue to a backup file in the order of the timestamps. Upon receiving a restoration request, the system can restore the database to a state as of the time of the checkpoint using the backup file.

## Claims

### Claim 1

A method comprising:
designating, by one or more processors, a first temporal checkpoint and a checkpoint interval, wherein after each checkpoint interval, a new temporal checkpoint is designated;
at a time after the first temporal checkpoint, receiving, by the one or more processors, a first update request to update data stored in a page of a storage device, wherein the page is a contiguous block of memory designated as a unit for storing data;
determining, by the one or more processors, a first update action based on whether a prior update request was received between the first temporal checkpoint and time the first update request was received, wherein:
when no prior update request was received, the first update action comprises:
updating the data stored in the page according to the first update request; and placing a first copy of the updated page into a queue; and
when a prior update request was received, the first update action comprises updating a prior copy of the page stored in the queue according to the first update request;
receiving a second update request to update the data stored in the page; and
determining, by the one or more processors, a second update action based on whether a time threshold is satisfied, the time threshold being satisfied when receiving the first update request and receiving the second update request occurred between two neighboring temporal checkpoints separated by a checkpoint interval, wherein:
when the time threshold is not satisfied, the second update action comprises:
updating data stored in the page according to the second update request; generating a second copy of the page as updated according to the second update request; and placing the second copy of the updated page into the queue; and
when the time threshold is satisfied, the second update action comprises updating the first copy of the page stored in the queue according to the second update request.

### Claim 2 (depends on 1)

The method of claim 1, wherein the block of memory of the page has a fixed-length or variable-length.

### Claim 3 (depends on 1)

The method of claim 1, wherein the checkpoint interval is adjustable to correspond to a frequency of update.

### Claim 4 (depends on 1)

The method of claim 1, wherein:
the queue comprises one or more copies of pages, each copy including a latest update for each page in a time period, the copy being associated with a timestamp of the latest update on data stored in the copy.

### Claim 5 (depends on 4)

The method of claim 4, comprising:
upon reaching the new temporal checkpoint, saving one or more pages in the queue to a log file in a sequence according to the timestamp associated with each page; and
removing at least a portion of the one or more saved pages from the queue.

### Claim 6 (depends on 5)

The method of claim 5, comprising:
reconstructing data stored in the page on the storage device to a state at the checkpoint according to the log file.

### Claim 7 (depends on 1)

The method of claim 1, wherein the page is stored in a page set comprising a plurality of pages, each of the plurality of pages including a portion of a database file, an entire database file, or multiple database files.

### Claim 8

A non-transitory storage medium storing instructions operable to cause one or more processors to perform operations comprising:
designating a first temporal checkpoint and a checkpoint interval, wherein after each checkpoint interval, a new temporal checkpoint is designated;
at a time after the first temporal checkpoint, receiving a first update request to update data stored in a page of a storage device, wherein the page is a contiguous block of memory designated as a unit for storing data;
determining a first update action based on whether a prior update request was received between the first temporal checkpoint and time the first update request was received, wherein:
when no prior update request was received, the first update action comprises:
updating the data stored in the page according to the first update request; and
placing a first copy of the updated page into a queue; and
when a prior update request was received, the first update action comprises updating a prior copy of the page stored in the queue according to the first update request;
receiving a second update request to update the data stored in the page; and
determining a second update action based on whether a time threshold is satisfied, the time threshold being satisfied when receiving the first update request and receiving the second update request occurred between two neighboring temporal checkpoints separated by a checkpoint interval, wherein:
when the time threshold is not satisfied, the second update action comprises: updating data stored in the page according to the second update request; generating a second copy of the page as updated according to the second update request; and placing the second copy of the updated page into the queue; and
when the time threshold is satisfied, the second update action comprises updating the first copy of the page stored in the queue according to the second update request.

### Claim 9 (depends on 8)

The medium of claim 8, wherein the block of the page has a fixed-length or variable-length.

### Claim 10 (depends on 8)

The medium of claim 8, wherein the checkpoint interval is adjustable to correspond to a frequency of update.

### Claim 11 (depends on 8)

The medium of claim 8, wherein:
the queue comprises one or more copies of pages, each copy including a latest update for each page in a time period, the copy being associated with a timestamp of the latest update on data stored in the copy.

### Claim 12 (depends on 11)

The medium of claim 11, the operations comprising:
upon reaching the new temporal checkpoint, saving one or more pages in the queue to a log file in a sequence according to the timestamp associated with each page; and
removing at least a portion of the one or more saved pages from the queue.

### Claim 13 (depends on 12)

The medium of claim 12, the operations comprising:
reconstructing data stored in the page on the storage device to a state at the checkpoint according to the log file.

### Claim 14 (depends on 8)

The medium of claim 8, wherein the page is stored in a page set comprising a plurality of pages, each of the plurality of pages including a portion of a database file, an entire database file, or multiple database files.

### Claim 15

A system, comprising:
one or more processors configured to perform operations comprising:
designating a first temporal checkpoint and a checkpoint interval, wherein after each checkpoint interval, a new temporal checkpoint is designated;
at a time after the first temporal checkpoint, receiving a first update request to update data stored in a page of a storage device wherein the page is a contiguous block of memory designated as a unit for storing data;
determining a first update action based on whether a prior update request was received between the first temporal checkpoint and time the first update request was received, wherein:
when no prior update request was received, the first update action comprises:
updating the data stored in the page according to the first update request; and
placing a first copy of the updated page into a queue; and
when a prior update request was received, the first update action comprises updating a prior copy of the page stored in the queue according to the first update request;
receiving a second update request to update the data stored in the page; and
determining, by the one or more processors, a second update action based on whether a time threshold is satisfied, the time threshold being satisfied when receiving the first update request and receiving the second update request occurred between two neighboring temporal checkpoints separated by a checkpoint interval, wherein:
when the time threshold is not satisfied, the second update action comprises: updating data stored in the page according to the second update request; generating a second copy of the page as updated according to the second update request; and placing the second copy of the updated page into the queue; and
when the time threshold is satisfied, the second update action comprises updating the first copy of the page stored in the queue according to the second update request.

### Claim 16 (depends on 15)

The system of claim 15, wherein the checkpoint interval is adjustable to correspond to a frequency of update.

### Claim 17 (depends on 15)

The system of claim 15, wherein the queue comprises one or more copies of pages, each copy including a latest update for each page in a time period, the copy being associated with a timestamp of the latest update on data stored in the copy.

### Claim 18 (depends on 17)

The system of claim 17, the operations comprising:
upon reaching the new temporal checkpoint, saving one or more pages in the queue to a log file in a sequence according to the timestamp associated with each page; and
removing at least a portion of the one or more saved pages from the queue.

### Claim 19 (depends on 18)

The system of claim 18, the operations comprising:
reconstructing data stored in the page on the storage device to a state at the checkpoint according to the log file.

### Claim 20 (depends on 15)

The system of claim 15, wherein the page is stored in a page set comprising a plurality of pages, each of the plurality of pages including a portion of a database file, an entire database file, or multiple database files.