Apparatus, systems, and methods for data recovery

Patent metadata

Field	Value
Publication number	US-2016196186-A1
Application number	US-201514590694-A
Country	US
Kind code	A1
Filing date	Jan 6, 2015
Priority date	Jan 6, 2015
Publication date	Jul 7, 2016
Grant date	—

Abstract

The embodiments disclosed herein provide a flash aware snapshot technique for two-way data recovery and back-in-time execution. The disclosed snapshot technique is designed to reduce the number of write operations to improve the performance on flash-based storage systems. The disclosed snapshot technique can guarantee data recovery no matter which of the production site or the backup site fails. The disclosed snapshot technique can also reduce the storage space requirement for snapshots by exploiting content locality. Furthermore, the disclosed snapshot technique can be implemented using hardware, software, firmware, or any combination of them. In case of hardware implementation, only minor hardware modifications are needed.

First claim

1 . A system comprising:
one or more storage devices comprising a first memory block and a second memory block configured to maintain data, wherein the first memory block comprises a prior snapshot and the second memory block comprises a current snapshot of data stored in the first memory block; an interface configured to provide communication with a remote storage device; and a memory controller in communication with the one or more storage devices and the interface, the memory controller configured to:
receive the prior snapshot and the current snapshot from the one or more storage devices;
perform a commutative binary operator on the prior snapshot and the current snapshot to generate a combined snapshot; and
cause the combined snapshot to be stored in the one or more storage devices and the remote storage device, wherein the combined snapshot can be used to recover any lost data when the one or more storage devices or the remote storage device is inoperative.

2 . The system of claim 1 , wherein the commutative binary operator comprises an exclusive OR operator.

3 . The system of claim 1 , wherein the remote storage device is configured to maintain a full-clone snapshot of the one or more storage devices for a first time instance, a first combined snapshot of a second time instance, and a second combined snapshot of a third time instance, wherein the one or more storage devices is configured to maintain data associated with the third time instance, the first combined snapshot of the second time instance, and the second combined snapshot of the third time instance.

4 . The system of claim 3 , wherein the memory controller is caused to recover data for the second time instance when the remote storage device is inoperative, the memory controller being configured to:
retrieve the second combined snapshot of the third time instance from the one or more storage devices, wherein the second combined snapshot is indicative of at least one memory block that has changed value between the second time instance and the third time instance; perform an inverse commutative binary operator on the second combined snapshot of the third time instance and the at least one memory block of the data associated with the third time instance to recover a prior snapshot of the third time instance; and substitute the at least one memory block of the data based on the prior snapshot of the third time instance to recover the data for the second time instance.

5 . The system of claim 3 , wherein the memory controller is caused to recover data for the second time instance when the one or more storage devices is inoperative, the memory controller being configured to:
retrieve the first combined snapshot of the second time instance and the full-clone snapshot of the first time instance from the remote storage device, wherein the combined snapshot is indicative of at least one memory block that has changed value between the first time instance and the second time instance; perform an inverse commutative binary operator on the combined snapshot of the first time instance and the at least one memory block of the full-clone snapshot of the first time instance to recover a current snapshot of the second time instance; and substitute the at least one memory block of the full-clone snapshot of the first time instance based on the current snapshot of the second time instance to recover the data for the second time instance.

6 . The system of claim 1 , wherein the memory controller is configured to index the prior snapshot using a flash translation layer that associates a logical block address and a physical memory location.

7 . The system of claim 1 , wherein the memory controller is configured to index the current snapshot using a mapping table.

8 . The system of claim 1 , wherein the one or more storage devices comprises flash memory and the one or more storage devices are arranged in a redundant array configuration.

9 . The system of claim 1 , wherein the remote storage device resides in a data center and the memory controller is configured to communicate with the remote storage device using the interface over the Internet.

10 . A method comprising:
receiving, by a memory controller, a prior snapshot of a first memory block and a current snapshot of the first memory block; performing, by the memory controller, a commutative binary operator on the prior snapshot and the current snapshot to generate a combined snapshot; and causing, by the memory controller, the combined snapshot to be stored in the one or more storage devices and the remote storage device, wherein the combined snapshot can be used to recover any lost data when the one or more storage devices or the remote storage device is inoperative.

11 . The method of claim 10 , wherein the commutative binary operator comprises an exclusive OR operator.

12 . The method of claim 10 , comprising maintaining a full-clone snapshot of the one or more storage devices for a first time instance, a first combined snapshot of a second time instance, and a second combined snapshot of a third time instance, and maintaining data for the third time instance, the first combined snapshot of the second time instance, and the second combined snapshot of the third time instance.

13 . The method of claim 12 , comprising:
retrieving the second combined snapshot of the third time instance from the one or more storage devices, wherein the second combined snapshot is indicative of at least one memory block that has changed value between the second time instance and the third time instance; operating an inverse commutative binary operator on the second combined snapshot of the third time instance and the at least one memory block of the data for the third time instance to recover a prior snapshot of the third time instance; and substituting the at least one memory block of the data for the third time instance based on the prior snapshot of the third time instance to recover the data for the second time instance.

14 . The method of claim 12 , comprising
retrieving the first combined snapshot of the second time instance and the full-clone snapshot of the first time instance from the remote storage device, wherein the first combined snapshot is indicative of at least one memory block that has changed value between the first time instance and the second time instance; operating an inverse commutative binary operator on the combined snapshot of the first time instance and the at least one memory block of the full-clone snapshot of the first time instance to recover a current snapshot of the second time instance; and substituting the at least one memory block of the full-clone snapshot of the first time instance based on the current snapshot of the second time instance to recover the data for the second time instance.

15 . The method of claim 10 comprising indexing the prior snapshot using a flash translation layer that associates a logical block address and a physical memory location.

16 . The method of claim 10 , comprising indexing the current snapshot using a mapping table.

17 . A computer program product comprised of a series of instructions executable on a computer, the computer program product implementing the steps of:
receiving, by a memory controller, a prior snapshot of a first memory block and a current snapshot of the first memory block; performing, by the memory controller, a commutative binary operator on the prior snapshot and the current snapshot to generate a combined snapshot; and causing, by the memory controller, the combined snap

Assignees

• HGST Netherlands BV

Inventors

• Yang Ken Qing

Classifications

• G06F11/1456

  Hardware arrangements for backup · CPC title

• G06F11/1469

  Backup restoration techniques · CPC title

• G06F2201/84

  Using snapshots, i.e. a logical point-in-time copy of the data · CPC title

• G06F11/1451 Primary

  by selection of backup contents · CPC title

• G06F11/1435

  using file system or storage system metadata · CPC title