Intelligent data integration

• US 8,930,364 B1
• Filed: 03/29/2012
• Issued: 01/06/2015
• Est. Priority Date: 03/29/2012
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Brooker, Marc J., Parthasarathy, Madhuvanesh, Certain, Tate Andrew, Lee, Kerry Q.
• Primary Examiner(s): Ly, Anh
• Application Number:
  US13/434,728
• Time in Patent Office: 1,013 Days
• Field of Search: 707/736, 707/764, 707/655, 707/610, 707/E17.005, 707/E17.044, 707/E17.032, 707/999.202, 711/162, 711/100, 711/E12.001, 711/E12.103, 714/4.11, 709/214, 709/241, 709/245, 709/223, 709/238, 370/399, 370/400, 370/229, 370/235, 370/231, 370/449
• US Class Current: 707/736
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0614 Improving the reliability of storage systems
• CPC Class Codes: G06F 3/0646 Horizontal data movement in storage systems, i.e. moving data in between storage devices or systems
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/068 Hybrid storage device

Abstract

A storage controller is implemented for controlling a storage system. The storage controller may be implemented using a distributed computer system and may include components for servicing client data requests based on the characteristics of the distributed computer system, the client, or the data requests. The storage controller is scalable independently of the storage system it controls. All components of the storage controller, as well as the client, may be virtual or hardware-based instances of a distributed computer system.

Claims

1. A computer-implemented method for merging data, comprising:

under control of one or more computer systems configured with executable instructions,

implementing at least one technique for identifying changed data, the changed data being accessible to a client entity of the one or more computer systems;

while reassigning, by the client entity, the data from a first storage node that is inaccessible to the client entity to a second storage node, receiving, by the client entity, a notification that access by the client entity to the first storage node has been at least partially restored;

determining, by the client entity and using at least in part information from the at least one technique for identifying changed data, whether reassigned data on the second storage node has been modified by the client entity; and

when the reassigned data on the second storage node has been modified,

determining, by the client entity and using at least in part information from the at least one technique for identifying changed data, a subset of the reassigned data that has been modified;

determining, by the client entity and at least in part by processing, by the client entity, the modified subset of reassigned data, whether to complete the data reassignment; and

when determined by the client entity that the data reassignment should be completed, then completing the data reassignment, and when determined by the client entity that the data reassignment should be not be completed, then merging, by the client entity and using at least the information from the at least one technique for identifying changed data, the reassigned data on the second storage node with original data on the first storage node, both the reassigned data and the original data are accessible on the first storage node by the client entity.

2. The computer-implemented method of claim 1, wherein the technique for identifying changed data is a write journal that is implemented on the client entity.

3. The computer-implemented method of claim 1, wherein the technique for identifying changed data is a write journal that is implemented on at least one of the first storage node or the second storage node.

4. The computer-implemented method of claim 1, wherein the technique for identifying changed data is an implementation of at least one data differencing procedure.

5. The computer-implemented method of claim 1, wherein implementing the technique for identifying changed data further comprises:

associating consistency tags with subsets of the data;

processing, by at least a hash function, the consistency tags to produce hashes; and

organizing the hashes into at least one hash tree,

wherein the information from the technique for identifying changed data is generated by processing the hash tree to determine which of the data subsets have been changed.

6. The computer-implemented method of claim 1, wherein determining whether to complete the data reassignment is further based at least in part on characteristics of the client'"'"'s access to the second storage node.

7. A computer-implemented method for merging data, comprising:

under control of one or more computer systems configured with executable instructions,

implementing at least one technique for identifying changed data that is stored on a storage system, the changed data being accessible to a client instance of the one or more computer systems;

determining, by a device of the one or more computer systems and at least using information from the implemented at least one technique for identifying changed data, whether an initial configuration of the storage system should be restored;

when determined by the device that the initial configuration should be restored, then restoring the initial configuration by at least;

merging, by the device and at least using information from the at least one technique for identifying changed data, a modified subset of the data with an unmodified subset of the data, thereby creating a merged set of data;

providing, by the restored initial configuration, the client instance access to the merged set of data; and

updating a mapping, the mapping being configured to enable, by associating client data requests with corresponding locations of the stored data on the storage system, access by the client instance to the merged set of data.

8. The computer-implemented method of claim 7, wherein the storage system includes data volumes that are accessible by a plurality of client instances, and wherein the data volumes are implemented by a plurality of data storage devices.

9. The computer-implemented method of claim 7, further comprising:

while reassigning the data from a first storage node of the storage system that is inaccessible to a client instance to a second storage node of the storage system, receiving a notification that access by the client instance to the first storage node has been at least partially restored,

wherein the initial configuration of the storage system includes at least the first storage node.

10. The computer-implemented method of claim 9, further comprising, when determined that the initial configuration should not be restored, then completing the reassignment of the data to the second storage node.

11. The computer-implemented method of claim 9, wherein the second storage node is accessible to the client instance.

12. The computer-implemented method of claim 7, wherein:

the technique for identifying changed data is implemented by the client instance; and

the client instance includes the device of the one or more computer systems.

13. A computer system for merging data, comprising:

one or more processors; and

memory, including instructions executable by the one or more processors to cause the computer system to at least;

track at least one technique for identifying changed data stored on a storage system, the changed data being accessible to a client instance of the computer system;

determine, by a device of the computer system and using information from the tracked at least one technique for identifying changed data, which storage configuration among a first storage system configuration and a second storage system configuration should be used to access the stored data;

determine, by the device and using the at least one technique for identifying changed data, a subset of changed data from the stored data; and

merge, by the device and using information from the tracked at least one technique for identifying changed data, the subset of changed data with data outside the subset, the merged data being accessible by the client instance using the determined storage configuration; and

update a mapping, the mapping being configured to enable, by associating client data requests with corresponding locations of the stored data on the storage system, access by the client instance to the merged data.

14. The computer system of claim 13, wherein the tracked at least one technique for identifying changed data is at least one of a write journal, a data differencing algorithm, or a hierarchical tree of hashed consistency tags that are associated with chunks of the stored data.

15. The computer system of claim 13, wherein determining which storage configuration to use is further based at least in part on a length of time required to implement the first storage system configuration relative to a length of time required to implement the second storage system configuration.

16. The computer system of claim 13, wherein determining which storage configuration to use is further based at least in part on an amount of computer system resources required to implement the first storage system configuration relative to an amount of computer system resources required to implement the second storage system configuration.

17. The computer system of claim 13, wherein determining which storage configuration to use is further based at least in part on a difference in at least one ability to provide data access to the client instance between the first storage system configuration and the second storage system configuration.

18. One or more non-transitory computer-readable storage media having collectively stored thereon executable instructions that, when executed by one or more processors of a computing resource provider'"'"'s computer system, cause the computer system to at least:

retain at least one technique for identifying changed data that is stored on a storage system, the at least one technique for identifying changed data indicating whether the changed data that is stored on the storage system has been modified, the changed data being accessible to a client instance of the computer system; and

in response to a notification that, while reassigning data from a first storage device that is inaccessible to the client instance to a second storage device, the first storage device becomes accessible to the client instance;

determine, by a device of the computer system and using the at least one technique for identifying changed data, an optimal storage device for providing the client instance access to the data, the optimal storage device being determined from among the first storage device and the second storage device;

copy, by the device and using the at least one technique for identifying changed data, modified data to the optimal storage device;

provide, by the device, information enabling the client instance to access the optimal storage device; and

update a mapping, the mapping being configured to enable, by associating client data requests with corresponding locations of the data on the storage system, access by the client instance to the stored data.

19. The non-transitory computer-readable storage media of claim 18, wherein the instructions further cause the computer system to determine, by at least processing the at least one technique for identifying changed data, whether at least one subset of data has been modified.

20. The non-transitory computer-readable storage media of claim 19, wherein the instructions further cause the computer system to determine, when determined that at least one subset of data has been modified and by at least processing the at least one technique for identifying changed data, the at least one subset of modified data from the stored data.

21. The non-transitory computer-readable storage media of claim 18, wherein the instructions further cause the computer system to:

associate consistency tags with chunks of the stored data;

apply a hash function to the consistency tags to generate associated hashes;

organize the hashes into a hash tree; and

generate, by at least processing the hash tree, metadata that indicates which of the data chunks has been modified.

22. The non-transitory computer-readable storage media of claim 18, wherein:

the computer system is a network of computing resources that includes the client instance and the device;

the client instance includes at least the device; and

the instructions cause the device of the client instance to at least;

retain the metadata; and

determine the optimal storage device.

23. The non-transitory computer-readable storage media of claim 22, wherein the instructions further cause the computer system to update a mapping to include the optimal storage device, the mapping being used at least by the client instance to access the stored data.