Distributed storage system with web services client interface

• US 20070156842A1
• Filed: 03/08/2006
• Published: 07/05/2007
• Est. Priority Date: 12/29/2005
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Cormie, John, Vermeulen, Allan, Wagner, Eric, Atlas, Alan, Fischman, Ami, Barth, David, Sorenson, James
• Granted Patent: US 7,716,180 B2
• Time in Patent Office: Days
• US Class Current: 709/217
• CPC Class Codes: G06F 16/184 implemented as replicated file system
• CPC Class Codes: G06F 9/547 Remote procedure calls [RPC]; Web services
• 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/01 Protocols
• 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 distributed, web-services based storage system. A system may include a web services interface configured to receive, according to a web services protocol, a given client request for access to a given data object, the request including a key value corresponding to the object. The system may also include storage nodes configured to store replicas of the objects, where each replica is accessible via a respective unique locator value, and a keymap instance configured to store a respective keymap entry for each object. For the given object, the respective keymap entry includes the key value and each locator value corresponding to replicas of the object. A coordinator may receive the given client request from the web services interface, responsively access the keymap instance to identify locator values corresponding to the key value and, for a particular locator value, retrieve a corresponding replica from a corresponding storage node.

Claims

1. A system, comprising:

a plurality of computing nodes configured to implement;

a web services interface configured to receive, according to a web services protocol, client requests for access to data objects, wherein a given one of said client requests for access to a given one of said data objects includes a key value corresponding to said given data object;

a plurality of storage nodes configured to store replicas of said data objects, wherein each of said replicas is accessible via a respective locator value, and wherein each of said locator values is unique within said system;

a keymap instance configured to store a respective keymap entry for each of said data objects, wherein for said given data object, said respective keymap entry includes said key value and each locator value corresponding to each stored replica of said given data object; and

a coordinator configured to receive said client requests for access to said data objects from said web services interface, wherein in response to said given client request, said coordinator is configured to access said keymap instance to identify one or more locator values corresponding to said key value and, for a particular one of said one or more locator values, to access a corresponding storage node to retrieve a corresponding replica.

2. The system as recited in claim 1, wherein subsequent to retrieving said corresponding replica, said coordinator is further configured to convey said corresponding replica via said web services interface to a client according to said given client request.

3. The system as recited in claim 1, wherein said web services interface is further configured to determine, prior to retrieving said corresponding replica, whether said given client request is sufficiently privileged to access said given data object, and if said given client request is not sufficiently privileged, to reject said given client request.

4. The system as recited in claim 1, wherein said web services interface is further configured to receive, according to said web services protocol, client requests to store data objects, wherein a particular one of said client requests to store a particular one of said data objects includes a key value corresponding to said particular data object.

5. The system as recited in claim 4, wherein said web services interface is further configured to determine a charge for storing said particular data object.

6. The system as recited in claim 4, wherein said coordinator is further configured to receive said client requests to store data objects from said web services interface, wherein in response to said particular client request, said coordinator is configured to store one or more replicas of said particular data object to one or more corresponding storage nodes, wherein in response to storing a given replica of said particular data object, a given one of said storage nodes is configured to return a locator value corresponding to said given replica to said coordinator.

7. The system as recited in claim 5, wherein said coordinator is further configured to instruct said keymap instance to update said respective keymap entry corresponding to said particular data object to include said locator value corresponding to said given replica.

8. The system as recited in claim 5, wherein said one or more corresponding storage nodes to which said one or more replicas of said particular data object are stored are selected according to a storage policy.

9. The system as recited in claim 8, wherein said storage policy specifies a number of replicas required to be indicated as durably stored to corresponding storage nodes before said coordinator indicates that said particular client request to store said particular data object is complete.

10. The system as recited in claim 9, wherein said storage policy additionally specifies a desired number of replicas of said particular data object to be generated.

11. The system as recited in claim 10, wherein said desired number of replicas exceeds said number of replicas.

12. The system as recited in claim 10, wherein said plurality of computing nodes is further configured to implement a replicator configured to examine said respective keymap entries of said keymap instance to determine whether, for a given one of said keymap entries, each replica corresponding to a respective locator value in said given keymap entry is accessible.

13. The system as recited in claim 12, wherein for said given keymap entry, if a number of accessible replicas corresponding to respective locator values in said given keymap entry is less than said desired number of replicas, said replicator is further configured to generate additional replicas sufficient to satisfy said desired number of replicas.

14. The system as recited in claim 8, wherein said plurality of storage nodes is distributed among a plurality of areas, and wherein said storage policy specifies a minimum number of areas to which said one or more replicas are required to be indicated as durably stored before said coordinator indicates that said particular client request to store said particular data object is complete.

15. The system as recited in claim 14, wherein a correlation of likelihood of failure of storage nodes between any two of said plurality of areas is less than a threshold amount.

16. The system as recited in claim 14, wherein said storage policy additionally specifies that, if possible, at least one of said one or more replicas is to be written to a storage node located in a given one of said areas, wherein said coordinator is also located in said given area.

17. The system as recited in claim 8, wherein said plurality of storage nodes is distributed among a plurality of areas, and wherein said storage policy specifies that, if possible, at least one of said one or more replicas is to be written to a storage node located in a given one of said areas.

18. The system as recited in claim 17, wherein said given area is selected according to said storage policy to minimize communication latency between said given area and a client associated with said particular client request.

19. The system as recited in claim 1, wherein said key value corresponding to said given data object is specified by a client via said web services interface.

20. The system as recited in claim 1, wherein a particular one of said client requests for access to said given data object received by said web services interface includes a particular locator value corresponding to a particular replica of said given data object.

21. The system as recited in claim 20, wherein in response to receiving said particular client request for access from said web services interface, said coordinator is further configured to retrieve said particular replica from a corresponding storage node via said particular locator value without accessing said keymap instance.

22. The system as recited in claim 1, wherein said web services protocol implements a representational state transfer (REST) web services model.

23. The system as recited in claim 22, wherein to receive said given client request according to said web services protocol, said web services interface is further configured to receive a request formatted according to a version of Hypertext Transfer Protocol (HTTP).

24. The system as recited in claim 23, wherein contents of said given client request are included in said request as parameters formatted according to a version of eXtensible Markup Language (XML).

25. The system as recited in claim 1, wherein said web services protocol implements a document-based web services model.

26. The system as recited in claim 25, wherein to receive said given client request according to said web services protocol, said web services interface is further configured to receive a document encapsulated according to a version of Simple Object Access Protocol (SOAP), wherein contents of said given client request are included in said document and formatted according to a version of XML.

27. The system as recited in claim 1, wherein said keymap instance is further configured to index its stored keymap entries within an index data structure including a plurality of index nodes arranged hierarchically and each having an associated tag value, wherein each of said stored keymap entries corresponds to a respective one of said index nodes, and wherein for said given keymap entry having a given corresponding index node, each tag value associated with each ancestor of said given corresponding index node is a prefix of said given key value.

28. A method, comprising:

receiving client requests for access to data objects via a web services interface according to a web services protocol, wherein a given one of said client requests for access to a given one of said data objects includes a key value corresponding to said given data object;

storing replicas of said data objects on a plurality of storage nodes, wherein each of said replicas is accessible via a respective locator value, and wherein each of said locator values is unique within said system;

storing a respective keymap entry for each of said data objects, wherein for said given data object, said respective keymap entry includes said client-specified key value and each locator value corresponding to each stored replica of said given data object; and

in response to receiving said given client request, accessing said respective keymap entries to identify one or more locator values corresponding to said key value and, for a particular one of said one or more locator values, accessing a corresponding storage node and retrieving a corresponding replica.

29. The method as recited in claim 28, further comprising conveying said retrieved corresponding replica via said web services interface to a client according to said given client request.

30. The method as recited in claim 28, further comprising determining, prior to retrieving said corresponding replica, whether said given client request is sufficiently privileged to access said given data object, and if said given client request is not sufficiently privileged, rejecting said given client request.

31. The method as recited in claim 28, further comprising:

receiving client requests to store data objects via said web services interface according to said web services protocol, wherein a particular one of said client requests to store said a particular one of said data objects includes a key value corresponding to said particular data object.

32. The method as recited in claim 31, further comprising determining a charge for storing said particular data object.

33. The method as recited in claim 31, further comprising:

in response to said particular client request, storing one or more replicas of said particular data object to one or more corresponding storage nodes; and

in response to storing a given replica of said particular data object to a given one of said storage nodes, receiving a locator value corresponding to said given replica.

34. The method as recited in claim 33, further comprising updating said respective keymap entry corresponding to said particular data object to include said locator value corresponding to said given replica.

35. The method as recited in claim 33, further comprising selecting, according to a storage policy, said one or more corresponding storage nodes to which said one or more replicas of said particular data object are stored.

36. The method as recited in claim 35, wherein said storage policy specifies a number of replicas required to be indicated as durably stored to corresponding storage nodes before said coordinator indicates that said particular client request to store said particular data object is complete.

37. The method as recited in claim 36, wherein said storage policy additionally specifies a desired number of replicas of said particular data object to be generated.

38. The method as recited in claim 37, wherein said desired number of replicas exceeds said number of replicas.

39. The method as recited in claim 37, further comprising examining said respective keymap entries to determine whether, for a given one of said keymap entries, each replica corresponding to a respective locator value in said given keymap entry is accessible.

40. The method as recited in claim 39, further comprising:

for said given keymap entry, if a number of accessible replicas corresponding to respective locator values in said given keymap entry is less than said desired number of replicas, generating additional replicas sufficient to satisfy said desired number of replicas.

41. The method as recited in claim 35, wherein said plurality of storage nodes is distributed among a plurality of areas, and wherein said storage policy specifies a minimum number of areas to which said one or more replicas are required to be indicated as durably stored before said coordinator indicates that said particular client request to store said particular data object is complete.

42. The method as recited in claim 41, wherein a correlation of likelihood of failure of storage nodes between any two of said plurality of areas is less than a threshold amount.

43. The method as recited in claim 41, wherein said storage policy additionally specifies that, if possible, at least one of said one or more replicas is to be written to a storage node located in a given one of said areas, wherein said coordinator is also located in said given area.

44. The method as recited in claim 35, wherein said plurality of storage nodes is distributed among a plurality of areas, and wherein said storage policy specifies that, if possible, at least one of said one or more replicas is to be written to a storage node located in a given one of said areas.

45. The method as recited in claim 44, wherein said given area is selected according to said storage policy to minimize communication latency between said given area and a client associated with said particular client request.

46. The method as recited in claim 28, wherein said key value corresponding to said given data object is specified by a client via said web services interface.

47. The method as recited in claim 28, wherein a particular one of said client requests for access to said given data object received by said web services interface includes a particular locator value corresponding to a particular replica of said given data object.

48. The method as recited in claim 47, further comprising:

in response to receiving said particular client request for access from said web services interface, retrieving said particular replica from a corresponding storage node via said particular locator value without accessing any of said respective keymap entries.

49. The method as recited in claim 28, wherein said web services protocol implements a representational state transfer (REST) web services model.

50. The method as recited in claim 49, wherein receiving said given client request according to said web services protocol includes receiving a request formatted according to a version of Hypertext Transfer Protocol (HTTP).

51. The method as recited in claim 49, wherein contents of said given client request are included in said request as parameters formatted according to a version of eXtensible Markup Language (XML).

52. The method as recited in claim 28, wherein said web services protocol implements a document-based web services model.

53. The method as recited in claim 52, wherein receiving said given client request according to said web services protocol includes receiving a document encapsulated according to a version of Simple Object Access Protocol (SOAP), wherein contents of said given client request are included in said document and formatted according to a version of XML.

54. The method as recited in claim 28, wherein storing said respective keymap entries for each of said data objects comprises indexing said keymap entries within an index data structure including a plurality of index nodes arranged hierarchically and each having an associated tag value, wherein each of said keymap entries corresponds to a respective one of said index nodes, and wherein for a given one of said keymap entries having a given corresponding index node, each tag value associated with each ancestor of said given corresponding index node is a prefix of said given key value.

55. A computer-accessible medium comprising instructions, wherein the instructions are executable to:

process client requests for access to data objects, wherein said client requests for access to said data objects are received via a web services interface according to a web services protocol, and wherein a given one of said client requests for access to a given one of said data objects includes a key value corresponding to said given data object;

instruct that replicas of said data objects be stored on a plurality of storage nodes, wherein each of said replicas is accessible via a respective locator value, and wherein each of said locator values is unique within said system; and

instruct that a respective keymap entry for each of said data objects be stored, wherein for said given data object, said respective keymap entry includes said client-specified key value and each locator value corresponding to each stored replica of said given data object;

wherein processing said given client request includes accessing said respective keymap entries to identify one or more locator values corresponding to said key value and, for a particular one of said one or more locator values, accessing a corresponding storage node and retrieving a corresponding replica.

56. The computer-accessible medium as recited in claim 55, wherein the instructions are further executable to:

process client requests to store data objects, wherein said client requests to store data objects are received via said web services interface according to said web services protocol, and wherein a particular one of said client requests to store said a particular one of said data objects includes a key value corresponding to said particular data object.

57. The computer-accessible medium as recited in claim 56, wherein the instructions are further executable to determine a charge for storing said particular data object.

58. The computer-accessible medium as recited in claim 56, wherein the instructions are further executable to:

in response to said particular client request, store one or more replicas of said particular data object to one or more corresponding storage nodes; and

in response to storing a given replica of said particular data object to a given one of said storage nodes, receive a locator value corresponding to said given replica.

59. The computer-accessible medium as recited in claim 57, wherein the instructions are further executable to instruct that said respective keymap entry corresponding to said particular data object be updated to include said locator value corresponding to said given replica.

60. The computer-accessible medium as recited in claim 58, wherein the instructions are further executable to instruct that said one or more corresponding storage nodes to which said one or more replicas of said particular data object are stored be selected according to a storage policy.

61. The computer-accessible medium as recited in claim 60, wherein said storage policy specifies a number of replicas required to be indicated as durably stored to corresponding storage nodes before said coordinator indicates that said particular client request to store said particular data object is complete.

62. The computer-accessible medium as recited in claim 61, wherein said storage policy additionally specifies a desired number of replicas of said particular data object to be generated.

63. The computer-accessible medium as recited in claim 62, wherein said desired number of replicas exceeds said number of replicas.

64. The computer-accessible medium as recited in claim 60, wherein said plurality of storage nodes is distributed among a plurality of areas, and wherein said storage policy specifies a minimum number of areas to which said one or more replicas are required to be indicated as durably stored before said coordinator indicates that said particular client request to store said particular data object is complete.

65. The computer-accessible medium as recited in claim 64, wherein a correlation of likelihood of failure of storage nodes between any two of said plurality of areas is less than a threshold amount.

66. The computer-accessible medium as recited in claim 64, wherein said storage policy additionally specifies that, if possible, at least one of said one or more replicas is to be written to a storage node located in a given one of said areas, wherein said coordinator is also located in said given area.

67. The computer-accessible medium as recited in claim 60, wherein said plurality of storage nodes is distributed among a plurality of areas, and wherein said storage policy specifies that, if possible, at least one of said one or more replicas is to be written to a storage node located in a given one of said areas.

68. The computer-accessible medium as recited in claim 67, wherein said given area is selected according to said storage policy to minimize communication latency between said given area and a client associated with said particular client request.

69. The computer-accessible medium as recited in claim 55, wherein a particular one of said client requests for access to said given data object includes a particular locator value corresponding to a particular replica of said given data object.

70. The computer-accessible medium as recited in claim 69, wherein the instructions are further executable to:

in response to said particular client request for access, retrieve said particular replica from a corresponding storage node via said particular locator value without accessing any of said respective keymap entries.

71. The computer-accessible medium as recited in claim 55, wherein said web services protocol implements a representational state transfer (REST) web services model.

72. The computer-accessible medium as recited in claim 71, wherein receiving said given client request according to said web services protocol includes receiving a request formatted according to a version of Hypertext Transfer Protocol (HTTP).

73. The computer-accessible medium as recited in claim 72, wherein contents of said given client request are included in said request as parameters formatted according to a version of eXtensible Markup Language (XML).

74. The computer-accessible medium as recited in claim 55, wherein said web services protocol implements a document-based web services model.

75. The computer-accessible medium as recited in claim 74, wherein receiving said given client request according to said web services protocol includes receiving a document encapsulated according to a version of Simple Object Access Protocol (SOAP), wherein contents of said given client request are included in said document and formatted according to a version of XML.