System and method for tracking service results

• US 9,391,825 B1
• Filed: 03/24/2009
• Issued: 07/12/2016
• Est. Priority Date: 03/24/2009
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Beal, Jeff B., Goetz, Jeromey R., Robbins, Alan Stuart, Porter, Brandon W., McAlister, Grant A. M., Ellsworth, Joseph L.
• Primary Examiner(s): Tang, Karen
• Application Number:
  US12/410,313
• Time in Patent Office: 2,667 Days
• Field of Search: 709/224, 709/218
• US Class Current: 1/1
• CPC Class Codes: H04L 41/50 Network service management, e.g. ensuring proper service fulfilment according to agreements
• CPC Class Codes: H04L 43/106 using time related information in packets, e.g. by adding timestamps
• CPC Class Codes: H04L 65/00 Network arrangements, protocols or services for supporting real-time applications in data packet communication real-time or near real-time messaging, e.g. instant messaging [IM] H04L51/04; selective video distribution H04N21/00
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/561 Adding application-functional data or data for application control, e.g. adding metadata
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests
• CPC Class Codes: H04L 69/28 Timers or timing mechanisms used in protocols

Abstract

Various embodiments of a system and method for tracking service requests are described. Embodiments may include call tree generation logic configured to receive multiple request identifiers associated with a respective one of multiple service requests. Each given request identifier may include an origin identifier, a depth value, and a request stack comprising one or more interaction identifiers. The call tree generation logic may also be configured to, based on multiple request identifiers that each include an origin identifier associated with a particular root request, generating a data structure that specifies a hierarchy of services called to fulfill that particular root request. Based on one or more of the interaction identifiers and one or more of the depth values, the generated data structure may specify for each given service of the hierarchy: a parent service that called the given service, and one or more child services called by the given service.

Claims

1. A computer-implemented method for tracking service requests within a service-oriented system comprising a plurality of services, the method comprising:

performing, by one or more computers comprising one or more processors and memory;

receiving multiple request identifiers each associated with a respective one of a plurality of service requests, wherein each given request identifier includes an origin identifier associated with a root request, a depth value specifying a location of the associated service request within a sequence of service requests, and a request stack comprising one or more interaction identifiers each assigned to a service request issued from one service to another service;

based on multiple ones of said request identifiers that each include an origin identifier associated with a particular root request, generating a data structure that specifies a hierarchy of services called to fulfill that particular root request;

wherein, based on one or more of said interaction identifiers and one or more of said depth values, the generated data structure specifies for each of multiple services of said hierarchy;

a particular service, a parent service that called the particular service, and one or more child services called by the particular service;

for a given request identifier of said multiple request identifiers, determining one or more timestamps indicating one or more of;

a time at which the corresponding request was received by the associated service of said plurality of services and a time at which the corresponding request was sent by a service that issued the corresponding request; and

for each of a plurality services of said hierarchy, indicating latency information associated with transmission of one or more service requests of said hierarchy within the data structure, wherein said latency information is based on one or more of said timestamps.

2. The method of claim 1, wherein said generating comprises:

determining that each of a subset of said multiple request identifiers comprises the same origin identifier, and indicating each associated service request as a node of said hierarchy within said data structure;

for each node within said hierarchy, assigning the node to a level within the hierarchy based on the depth value of the request identifier associated with the service request corresponding to that node;

in response to determining that the request stack of a given node at a given level within said hierarchy includes an interaction identifier that is the same as an interaction identifier of the request stack of an other node located within an adjacent level of the hierarchy, indicating a service call as an edge between said given node and said other node.

3. The method of claim 1, wherein the method comprises, determining that a first service issued a particular service request to a second service, wherein that determination is based on a request stack of a request identifier associated with an other service request issued by the second service and not based on a request identifier associated with the particular service request.

4. The method of claim 1, further comprising constraining the size of the request stack of at least some of the request identifiers to a particular quantity of interaction identifiers.

5. The method of claim 4, further comprising determining said particular quantity of interaction identifiers based on one or more of:

bandwidth requirements, storage requirements and fault tolerance requirements.

6. The method of claim 1, further comprising appending one or more of said timestamps as metadata to one or more services of the hierarchy within the data structure.

7. The method of claim 1, further comprising determining error information indicating one or more errors associated with processing a given request and appending said error information to the hierarchy as metadata within the data structure.

8. The method of claim 1, further comprising determining task information indicating one or more completed tasks associated with processing a given request and appending said task information to the hierarchy as metadata within the data structure.

9. A system, comprising:

a memory comprising program instructions; and

one or more processors coupled to said memory, wherein the program instructions are executable by at least one of said one or more processors to;

receive multiple request identifiers each associated with a respective one of a plurality of service requests, wherein each given request identifier includes an origin identifier associated with a root request, a depth value specifying a location of the associated service request within a sequence of service requests, and a request stack comprising one or more interaction identifiers each assigned to a service request issued from one service to another service;

based on multiple ones of said request identifiers that each include an origin identifier associated with a particular root request, generate a data structure that specifies a hierarchy of services called to fulfill that particular root request;

wherein, based on one or more of said interaction identifiers and one or more of said depth values, the generated data structure specifies for each of multiple services of said hierarchy;

a particular service, a parent service that called the particular service, and one or more child services called by the particular service;

for a given request identifier of said multiple request identifiers, determine one or more timestamps indicating one or more of;

a time at which the corresponding request was received by the associated service of said plurality of services and a time at which the corresponding request was sent by a service that issued the corresponding request; and

for each of a plurality services of said hierarchy, indicate latency information associated with transmission of one or more service requests of said hierarchy within the data structure, wherein said latency information is based on one or more of said timestamps.

10. The system of claim 9, wherein to generate the data structure, the program instructions are configured to:

determine that each of a subset of said multiple request identifiers comprises the same origin identifier, and indicate each associated service request as a node of said hierarchy within said data structure;

for each node within said hierarchy, assign the node to a level within the hierarchy based on the depth value of the request identifier associated with the service request corresponding to that node;

in response to determining that the request stack of a given node at a given level within said hierarchy includes an interaction identifier that is the same as an interaction identifier of the request stack of an other node located within an adjacent level of the hierarchy, indicate a service call as an edge between said given node and said other node.

11. The system of claim 9, wherein the program instructions are configured to determine that a first service issued a particular service request to a second service, wherein that determination is based on a request stack of a request identifier associated with an other service request issued by the second service and not based on a request identifier associated with the particular service request.

12. The system of claim 9, wherein the program instructions are configured to constrain the size of the request stack of at least some of the request identifiers to a particular quantity of interaction identifiers.

13. The system of claim 12, wherein the program instructions are configured to determine said particular quantity of interaction identifiers based on one or more of:

bandwidth requirements, storage requirements and fault tolerance requirements.

14. The system of claim 9, wherein the program instructions are configured to append one or more of said timestamps as metadata to one or more services of the hierarchy within the data structure.

15. The system of claim 9, wherein the program instructions are configured to determine error information indicating one or more errors associated with processing a given request and append said error information to the hierarchy as metadata within the data structure.

16. The system of claim 9, wherein the program instructions are configured to determine task information indicating one or more completed tasks associated with processing a given request and append said task information to the hierarchy as metadata within the data structure.

17. A non-transitory computer-readable storage medium storing program instructions computer-executable to:

receive multiple request identifiers each associated with a respective one of a plurality of service requests, wherein each given request identifier includes an origin identifier associated with a root request, a depth value specifying a location of the associated service request within a sequence of service requests, and a request stack comprising one or more interaction identifiers each assigned to a service request issued from one service to another service;

based on multiple ones of said request identifiers that each include an origin identifier associated with a particular root request, generate a data structure that specifies a hierarchy of services called to fulfill that particular root request;

wherein, based on one or more of said interaction identifiers and one or more of said depth values, the generated data structure specifies for each of multiple services of said hierarchy;

a particular service, a parent service that called the particular service, and one or more child services called by the particular service;

determine a particular quantity of interaction identifiers based on one or more of;

bandwidth requirements, storage requirements and fault tolerance requirements; and

constrain the size of the request stack of at least some of the request identifiers to the particular quantity of interaction identifiers.

18. The non-transitory computer-readable storage medium of claim 17, wherein to generate the data structure, the program instructions are configured to:

determine that each of a subset of said multiple request identifiers comprises the same origin identifier, and indicate each associated service request as a node of said hierarchy within said data structure;

for each node within said hierarchy, assign the node to a level within the hierarchy based on the depth value of the request identifier associated with the service request corresponding to that node;

in response to determining that the request stack of a given node at a given level within said hierarchy includes an interaction identifier that is the same as an interaction identifier of the request stack of an other node located within an adjacent level of the hierarchy, indicate a service call as an edge between said given node and said other node.

19. The non-transitory computer-readable storage medium of claim 17, wherein the program instructions are configured to determine that a first service issued a particular service request to a second service, wherein that determination is based on a request stack of a request identifier associated with an other service request issued by the second service and not based on a request identifier associated with the particular service request.

20. The non-transitory computer-readable storage medium of claim 17, wherein the program instructions are configured to, for a given request identifier of said multiple request identifiers, determine one or more timestamps indicating one or more of:

a time at which the corresponding request was received by the associated service of said plurality of services and a time at which the corresponding request was sent by a service that issued the corresponding request.

21. The non-transitory computer-readable storage medium of claim 20, wherein the program instructions are configured to, for each of a plurality services of said hierarchy, indicate latency information associated with transmission of one or more service requests of said hierarchy within the data structure, wherein said latency information is based on one or more of said timestamps.

22. The non-transitory computer-readable storage medium of claim 20, wherein the program instructions are configured to append one or more of said timestamps as metadata to one or more services of the hierarchy within the data structure.

23. The non-transitory computer-readable storage medium of claim 17, wherein the program instructions are configured to determine error information indicating one or more errors associated with processing a given request and append said error information to the hierarchy as metadata within the data structure.

24. The non-transitory computer-readable storage medium of claim 17, wherein the program instructions are configured to determine task information indicating one or more completed tasks associated with processing a given request and append said task information to the hierarchy as metadata within the data structure.