Data storage mapping and management

• US 8,918,392 B1
• Filed: 03/29/2012
• Issued: 12/23/2014
• 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,638
• Time in Patent Office: 999 Days
• Field of Search: 707/736, 707/764, 707/655, 707/610, 707/E17.005, 707/E17.044, 707/E17.032, 707/999.202, 707/626, 707/652, 707/657, 707/661, 711/162, 711/100, 711/E12.001, 711/E12.103, 714/4.11, 370/399, 370/400, 370/229, 370/235, 370/231, 370/449, 370/466, 370/355, 709/214, 709/241, 709/245, 709/223, 709/238, 709/203, 709/230
• US Class Current: 707/736
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 3/0617 in relation to availability
• 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: H04L 67/00 Network arrangements or protocols for supporting network services or applications user-to-user messaging H04L51/00; network arrangements, protocols or services for supporting real-time applications in data packet communications networks H04L65/00
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

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 accessing data storage devices, comprising:

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

implementing, using one or more resources of the one or more computer systems, a map authority that non-transitively stores at least one data map, the map authority being independent of a client and at least in part thereby enabling fault tolerance with respect to client availability, the client being a virtual computer system instance implemented at least in part with one or more computing resources of a distributed computing system, the at least one data map including information that associates block addresses of the client to one or more locations within a storage system that store a client-attached data volume for the client;

upon receiving, by the map authority, a change notification from the client, then at least responding to the change notification by providing the client with a receipt affirmation of the request;

when the change notification indicates that the client lacks information in a client data map to locate data within the client-attached data volume of the storage system, then further responding to the change notification by providing, to the client, at least a portion of the data map that enables the client to locate the data within the storage system; and

when the change notification includes information indicating that the client entity is requesting a change to the stored data map in response to a change of data location within the client-attached data volume, then further responding to the change notification by updating the stored data map to reflect at least a subset of the change of data location within the client-attached volume.

2. The computer-implemented method of claim 1, further comprising:

receiving, from the client, information relating to the client data requests, the information including whether the client has dissolved or disassociated;

receiving, from the storage system, information relating to at least an operational characteristic of the storage system;

determining, based on at least the client data request-related information and the storage system characteristic-related information, whether data stored upon the storage system should be moved from a first location of the storage system to a second location of the storage system; and

when determined that the stored data should be moved, then at least;

causing the storage system to move the data from the first location to the second location; and

updating, based at least on information relating to the moved data, the non-transitively stored at least one data map.

3. The computer-implemented method of claim 2, wherein the determination of whether the stored data should be moved is a determination by the map authority to improve an operational efficiency of the storage system.

4. The computer-implemented method of claim 2, wherein the map authority further provides, to the client, at least a portion of the updated data map that enables the client to locate the moved data, the portion of the updated data map being less than all the updated data map.

5. The computer-implemented method of claim 2, wherein the determination of whether the stored data should be moved is, based at least in part on an analysis of data requests by the client over a time period, a determination by the map authority to preemptively optimize data access for the client at least in part by moving the data from a high durability data store to a low latency data store.

6. The computer-implemented method of claim 1, wherein the storage system contains a plurality of data volumes that are each accessible to the client, each data volume being distributed among a plurality of hardware storage devices.

7. A computer-implemented method for accessing data storage devices, comprising:

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

storing, by a map authority service at least one data map for a client, the map authority service being independent of a client and at least in part thereby enabling fault tolerance with respect to client availability, the client being a virtual computer system instance implemented at least in part with one or more computing resources of a distributed computing system, that is usable to locate block storage for the client within a storage system;

causing, by the map authority service and via a network connection, at least a portion of the data map to be sent to the client in response to receiving an indication that at least a portion of the block storage for the client is inaccessible; and

upon receiving the indication, then at least responding with an affirmation of the indication.

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

receiving information relating to client data requests, the information including whether the client has dissolved or disassociated;

receiving information relating to at least an operational characteristic of the storage system;

determining, based on at least the client data request-related information and the storage system characteristic-related information, whether the storage system should reconfigured; and

when determined that the storage system should be reconfigured, then at least;

determining a new storage system configuration;

submitting, to the storage system, server commands that reconfigure the storage system in accordance with the new storage system configuration; and

updating, based at least on information relating to the new storage system configuration, the stored at least one data map to reflect the new storage system configuration.

9. The computer-implemented method of claim 8, wherein the determined new storage configuration is configured to preemptively optimize data access for at least one client submitting the client data requests.

10. The computer-implemented method of claim 8, wherein the received client data request-related information indicates that at least a subset of data stored on the storage system is inaccessible by the client.

11. The computer-implemented method of claim 8, wherein said reconfiguring server commands are effective to reconfigure a data volume that is implemented on a first subset of data storage devices to be implemented on a second subset of data storage devices, the second subset of data storage devices including at least one data storage device that is outside of the first subset.

12. The computer-implemented method of claim 7, wherein the indication is sent by the client.

13. The computer-implemented method of claim 7, wherein when the indication includes information that the client requires the stored data map to locate the block storage, then at least responding by providing the stored data map to the client.

14. The computer-implemented method of claim 7, wherein the indication includes information that a fault of at least the storage system is detected.

15. The computer-implemented method of claim 7, wherein the indication includes information that the client lacks the data map.

16. The computer-implemented method of claim 7, wherein the indication includes information that network connectivity to at least a portion of the storage system was lost.

17. The computer-implemented method of claim 7, further comprising causing, by the map authority service and via a network connection, at least a portion of the data map to be sent to the client in response to receiving an indication that at least a portion of the block storage is subject to a data request level that is higher than a predetermined level.

18. The computer-implemented method of claim 7, further comprising causing, by the map authority service and via a network connection, at least a portion of the data map to be sent to the client in response to receiving an indication that the client requires an increased level of performance for at least a portion of the block storage.

19. The computer-implemented method of claim 7, wherein the map authority service is implemented across a plurality of computer systems.

20. The computer-implemented method of claim 7, further comprising, upon authentication, by an entity of the one or more computer systems, of clients for connecting to the storage system, causing, by the map authority service and via a network connection, at least portions of data maps to be sent to corresponding authenticated clients.

21. A computer system for accessing data storage devices, comprising:

one or more processors; and

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

store data maps for translating client data requests into data location commands enabling location of data within a storage system, at least a portion of the stored data maps being independent of the client and at least in part thereby enabling fault tolerance with respect to client availability, the client being a virtual computer system instance implemented at least in part with one or more computing resources of a distributed computing system;

acknowledge received notifications that relate to the stored data maps;

provide copies of the stored data maps to clients of the computer system when the received notifications indicate that the clients are unable to locate the data within the storage system as a result of lacking a copy of the stored data maps;

updating the stored data maps when the received notifications indicate that the stored data maps inaccurately locate at least a subset of the data

responding with an affirmation of the indication that the clients are unable to locate the data within the storage system.

22. The computer system of claim 21, wherein the executable instructions cause the computer system to further:

receive information relating to the client data requests, the information including whether the client has dissolved or disassociated;

receive information relating to at least an operational characteristic of the storage system;

determine, based on at least the client data request-related information and the storage system characteristic-related information, whether the storage system should be reconfigured; and

when determined that the storage system should be reconfigured, then at least;

determine a new storage system configuration;

submit, to the storage system, server commands that reconfigure the storage system in accordance with the new storage system configuration; and

update, based at least on information relating to the new storage system configuration, the non-transitively stored data maps to reflect the new storage system configuration.

23. The computer system of claim 22, wherein the new storage system configuration is configured to place data that are frequently accessed by at least a data-requesting client on at least one data storage device in the storage system, the at least one data storage device being capable of a data transaction rate that is greater than at least one data storage device used prior to the reconfiguration.

24. The computer system of claim 23, wherein the at least one data storage device includes a server configured with at least one solid-state storage device.

25. The computer system of claim 22, wherein when the clients dissolve or disassociate, the stored data maps become inaccessible.

26. The computer system of claim 21, wherein the data maps are logical block address maps that are operable to map data blocks located on the storage system to logical blocks exposed to the clients.

27. 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:

in response to information indicating an update to at least one of a location of data upon a storage system or a configuration of the storage system, at least update a data mapping stored non-transitively in accordance with the information, the non-transitively stored data mapping being independent of a client entity and at least in part thereby enabling fault tolerance with respect to client entity availability, upon the one or more computer-readable storage media in accordance with the information, the data mapping being configurable to translate incoming client entity data requests into data location commands that enable location of data within the storage system, the client being a virtual computer system instance implemented at least in part with one or more computing resources of a distributed computing system;

in response to information indicating that the client entity of the computer system is unable, as a result of lacking a copy of the non-transitively stored mapping, to locate data upon the storage system, provide the client entity with a copy of the stored mapping; and

upon receiving the information, then at least responding with an affirmation of the indication.

28. The non-transitory computer-readable storage media of claim 27, wherein the executable instructions are executed by the client entity.

29. The non-transitory computer-readable storage media of claim 27, wherein the executable instructions cause the computer system to further, in response to information indicating that a copy of the stored data mapping on the client entity is less accurate than the non-transitively stored mapping, provide the client entity with a new copy of the non-transitively stored mapping.

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

receive information relating to the client data requests, the information including whether the client entity has dissolved or disassociated;

receive information relating to at least an operational characteristic of the storage system;

determine, based on at least the client data request-related information and the storage system characteristic-related information, whether the storage system should be reconfigured; and

when determined that the storage system should be reconfigured, then at least;

determine a new storage system configuration;

submit, to the storage system, server commands that reconfigure the storage system in accordance with the new storage system configuration; and

update, based at least on information relating to the new storage system configuration, the non-transitively stored data mapping to reflect the new storage system configuration.

31. The non-transitory computer-readable storage media of claim 30, wherein:

the new storage system configuration improves access to data by at least one of caching or prefetching the data using a block data storage service.

32. The non-transitory computer-readable storage media of claim 30, wherein:

the new storage system configuration is configured to improve data access; and

the new storage system configuration is determined by analyzing at least one of client data usage patterns, characteristics of client-accessed data, or client requirements for data.