Optimizing performance for routing operations

• US 8,984,162 B1
• Filed: 11/02/2011
• Issued: 03/17/2015
• Est. Priority Date: 11/02/2011
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Allen, Nicholas A., Dykhno, Elena
• Primary Examiner(s): Joo, Joshua
• Assistant Examiner(s): Naji, Younes
• Application Number:
  US13/287,843
• Time in Patent Office: 1,231 Days
• US Class Current: 709/242
• CPC Class Codes: G06F 13/385 for adaptation of a particular data processing system to different peripheral devices

Abstract

A deploy service is provided to determine a set of software artifacts that needs to be transmitted to a target machine upon receiving an application deployment request from a user of a client device. For instance, the deploy service may compare versions of software artifacts on the target machine with the software artifacts of the application that the user desires to deploy to determine the set of software artifacts that needs to be transmitted. Instead of having to transmit the entire application, some embodiments transmit only a small portion that is reflective of what has been changed between the old version of the application and the new version of the application. This enables the transfer of large files across the Internet to be more efficient.

Claims

1. A computer-implemented method, comprising:

receiving, by a computer system, a cache operation associated with a cache key;

selecting, by the computer system, a front end node from a plurality of front end nodes in a distributed system, each of the plurality of front end nodes having a bucket map and a routing table, wherein the bucket map provides a mapping between a plurality of cache keys and a plurality of identifiers;

enabling the front end node to select a particular cache node from a set of cache nodes on which to perform a cache operation, the particular cache node selected based at least in part on the bucket map and the routing table;

detecting, by the computer system, a mutation event for the set of cache nodes, the mutation event indicating an increase in a number of the set of cache nodes operable at a threshold level;

upon detecting the mutation event, calculating a hashing function for the bucket map that provides for a plurality of the set of cache nodes to remain mapped to a number of same identifiers as provided in the bucket map; and

modifying the bucket map with the calculated hashing function, wherein modifying the bucket map includes redistributing cache operations to new nodes after one or more cache nodes in the set of cache nodes have failed, wherein the new nodes are configured to receive less traffic than other nodes in the set of cache nodes;

wherein upon receiving another cache operation, another front end from the plurality of front end nodes is selected to perform the other cache operation on at least one of the set of cache nodes, the number of the set of cache nodes corresponding to the increase in the number of the set of cache nodes from detection of the mutation event.

2. The computer-implemented method of claim 1, wherein the routing table provides a mapping for the plurality of identifiers to the set of cache nodes.

3. The computer-implemented method of claim 2, wherein the particular cache node is selected by a load balancer when either the routing table or the bucket map is unavailable.

4. The computer-implemented method of claim 1, wherein the routing table is provided through a routing table service that is contacted by the front end when the front end is determining the particular cache node to perform the cache operation.

5. The computer-implemented method of claim 1, wherein the mutation event is detected when a pre-specified heartbeat response is not received from at least one of the set of cache nodes within a threshold duration.

6. The computer-implemented method of claim 1, wherein an amount of redistributed cache operations received by the new nodes increases as a function of time.

7. The computer-implemented method of claim 1, wherein the new nodes are assigned cache operations that correspond to buckets that have not been used within a predefined period of time.

8. The computer-implemented method of claim 1, further comprising maintaining a historical record for the particular cache node, the historical record indicating one or more originators of cache operations for which the particular cache node was selected, wherein selecting the particular cache node is further based at least in part on the maintained historical data.

9. A computer-implemented method, comprising:

receiving, by a computer system, a first cache operation to be performed on a particular cache node of a set of cache nodes, the particular cache node selected by mapping a cache key associated with the first cache operation to an identifier in a bucket map and by selecting the particular cache node corresponding to the identifier using a routing table, the bucket map providing a mapping for a plurality of cache keys to a plurality of identifiers and the routing table providing a mapping for the plurality of identifiers to the set of cache nodes;

detecting, by the computer system, a mutation event for the set of cache nodes, the mutation event indicating a change in a number of the set of cache nodes operable at a threshold level;

upon detecting the mutation event, calculating a hashing function for the bucket map that provides for a plurality of the set of cache nodes to remain mapped to a number of same identifiers as provided in the bucket map;

modifying the bucket map with the calculated hashing function, wherein modifying the bucket map includes redistributing cache operations to new nodes after one or more cache nodes in the set of cache nodes have failed, wherein the new nodes are configured to receive less traffic than other nodes in the set of cache nodes;

updating the routing table to provide that the set of cache nodes to which the plurality of identifiers is mapped corresponds to the change in the number of the set of cache nodes; and

receiving a second cache operation to be performed on the particular cache node of the set of cache nodes;

wherein detection of the mutation event causes the second cache operation to be performed on another cache node in the set of cache nodes besides the particular cache node.

10. The computer-implemented method of claim 9, wherein the particular cache node is a durable storage that persists throughout a particular caching request.

11. The computer-implemented method of claim 9, wherein the mutation event is caused by discovering an additional cache node that is operable to perform cache operations.

12. The computer-implemented method of claim 9, wherein the routing table is rerouted based at least in part on traffic going through each of the set of cache nodes to provide a workload among the set of cache nodes that is evenly distributed.

13. The computer-implemented method of claim 9, wherein detecting the mutation event comprises:

periodically requesting a response from each of the set of cache nodes; and

failing to receive an expected response from at least one of the set of cache nodes.

14. The computer-implemented method of claim 9, wherein the mutation event is detected when a heartbeat response is not received from at least one of the set of cache nodes within a threshold duration.

15. The computer-implemented method of claim 9, wherein the routing table is updated based on traffic going through each of the set of cache nodes and a number of entries to which each of the set of cache nodes are mapped to in the routing table.

16. An electronic device, comprising:

a processor; and

a memory device including instructions that, when executed by the processor, cause the electronic device to;

receive a first cache operation to be performed on a particular cache node of a set of cache nodes, the particular cache node selected by mapping a cache key associated with the first cache operation to an identifier in a bucket map and by selecting the particular cache node corresponding to the identifier using a routing table, the bucket map providing a mapping for a plurality of cache keys to a plurality of identifiers and the routing table providing a mapping for the plurality of identifiers to the set of cache nodes;

detect a mutation event for the set of cache nodes, the mutation event indicating a change in a number of the set of cache nodes operable at a threshold level;

upon detecting the mutation event, calculate a hashing function for the bucket map that provides for a plurality of the set of cache nodes to remain mapped to a number of same identifiers as provided in the bucket map;

modify the bucket map with the calculated hashing function, wherein modifying the bucket map includes redistributing cache operations to new nodes after one or more cache nodes in the set of cache nodes have failed, wherein the new nodes are configured to receive less traffic than other nodes in the set of cache nodes;

update the routing table to provide that the set of cache nodes to which the plurality of identifiers is mapped corresponds to the change in the number of the set of cache nodes; and

receive a second cache operation to be performed on the particular cache node of the set of cache nodes;

wherein detection of the mutation event causes the second cache operation to be performed on another cache node in the set of cache nodes besides the particular cache node.

17. The electronic device of claim 16, wherein a cached copy of the routing table is stored on each of a plurality of front end nodes configured to direct cache operations to cache nodes.

18. The electronic device of claim 16, wherein the routing table is provided through a routing table service that is contacted by a front end when the front end is determining which cache node to perform the first cache operation.

19. The electronic device of claim 16, wherein the first cache operation and the second cache operation are at least one of a write request or a read request.

20. A non-transitory computer-readable storage medium including instructions for identifying items, the instructions when executed by a processor of a computing device causing the computing device to:

receive a first cache operation to be performed on a particular cache node of a set of cache nodes, the particular cache node selected by mapping a cache key associated with the first cache operation to an identifier in a bucket map and by selecting the particular cache node corresponding to the identifier using a routing table, the bucket map providing a mapping for a plurality of cache keys to a plurality of identifiers and the routing table providing a mapping for the plurality of identifiers to the set of cache nodes;

detect a mutation event for the set of cache nodes, the mutation event indicating a change in a number of the set of cache nodes operable at a threshold level;

upon detecting the mutation event, calculate a hashing function for the bucket map that provides for a plurality of the set of cache nodes to remain mapped to a number of same identifiers as provided in the bucket map;

modify the bucket map with the calculated hashing function, wherein modifying the bucket map includes redistributing cache operations to new nodes after one or more cache nodes in the set of cache nodes have failed, wherein the new nodes are configured to receive less traffic than other nodes in the set of cache nodes;

update the routing table to provide that the set of cache nodes to which the plurality of identifiers is mapped corresponds to the change in the number of the set of cache nodes; and

receive a second cache operation to be performed on the particular cache node of the set of cache nodes;

wherein detection of the mutation event causes the second cache operation to be performed on another cache node in the set of cache nodes besides the particular cache node.

21. The non-transitory computer-readable storage medium of claim 20, wherein the mutation event is caused by determining that a cache node in the set of cache nodes is no longer operable to perform cache operations.

22. The non-transitory computer-readable storage medium of claim 20, wherein the routing table is rerouted based at least in part on traffic going through each of the set of cache nodes to provide a workload among the set of cache nodes that is evenly distributed.

23. The non-transitory computer-readable storage medium of claim 20, wherein the first cache operation directed to a particular cache node is received from a particular client, the method further comprising:

directing the second cache operation to the same particular cache node upon receiving the second cache operation from the same particular client.