Optimized consistent request distribution for balanced load distribution in a content delivery network
View Patent ↗Some embodiments provide a proprietary 64-bit consistent distribution scheme that preserves the efficiencies of CARP while providing a significantly more balanced distribution of requests that is on par with schemes reliant on computationally expensive cryptographic hashes. The scheme performs hashing of requested URLs and identifiers of available servers over a 64-bit space while optimizing the hashing to remove computationally expensive operations. Some embodiments provide a variant of the scheme to provide a differentiated distribution on the basis of one or more differentiating factors. A first variant utilizes load factor values to adjust the resulting hashes and to produce a first distribution of differentiated content that varies from a second distribution of undifferentiated content. A second variant identifies requests for differentiated content from requests for undifferentiated content and utilizes a first scheme to distribute the differentiated content and a second altered scheme to distribute the undifferentiated content.
1. A computer-implemented method for distributing content requests amongst a set of servers with a load distribution server, the computer-implemented method comprising:
obtaining a list of identifiers comprising different identifiers identifying each server in the set of servers;
producing a first 64-bit hash for each identifier in the list of identifiers, wherein producing the first 64-bit hash for a particular identifier in the list of identifiers comprises initializing a first 64-bit variable and for each character in the particular identifier, bitshifting a previous value of the first 64-bit variable by a first seed value and adding a value of the character to the first 64-bit variable;
receiving a request comprising a URL identifying content being requested;
producing a second 64-bit hash of the URL, wherein producing the second 64-bit hash comprises initializing a second 64-bit variable and for each character in the URL, bitshifting a previous value of the second 64-bit value by a second seed value and adding a value of the character to the second 64-bit variable;
combining the second 64-bit hash with each first 64-bit hash;
selecting a server from the set of servers to process the request based on a result of combining the second 64-bit hash with each first 64-bit hash; and
distributing the request to the selected server.
2. The computer-implemented method of claim 1 further comprising advertising an IP address to receive any requests designated for the set of servers.
3. The computer-implemented method of claim 1 , wherein the list of identifiers is a first list of identifiers, the computer-implemented method further comprising obtaining a second list of identifiers identifying differentiated content from undifferentiated content.
4. The computer-implemented method of claim 3 further comprising analyzing the request using the second list of identifiers and identifying the request as one for differentiated content or undifferentiated content.
5. The computer-implemented method of claim 4 further comprising adjusting the first 64-bit hash for each particular server of the set of servers by a specific load factor value assigned to that particular server when said identifying identifies the request as one for differentiated content, and wherein combining the second 64-bit result with each first 64-bit result comprises combining the second 64-bit result with each first 64-bit result as adjusted by a load factor value.
6. The computer-implemented method of claim 1 further comprising aggregating a log from each server of the set of servers, each log recording a number of times different content was requested from that server.
7. The computer-implemented method of claim 6 further comprising processing each log from the set of servers to identify a subset of hot content, the subset of hot content representing content requested more than a specified threshold in a particular period of time.
8. The computer-implemented method of claim 7 further comprising processing the URL of the request to determine if the request is one for content identified in the subset of hot content.
9. The computer-implemented method of claim 8 further comprising modifying a result of combining the second 64-bit hash with each first 64-bit hash by a load factor when the request is for content identified in the subset of hot content.
10. The computer-implemented method of claim 9 further comprising not modifying the result of combining the second 64-bit hash with each first 64-bit hash when the request is not for content identified in the subset of hot content.
11. The computer-implemented method of claim 9 , wherein the load factor prioritizes selection of a specific server from the set of servers to process the subset of hot content.
12. A computer-implemented method comprising:
obtaining a list of fully qualified domain names (FQDNs) comprising a different FQDN identifying each server of a set of servers;
producing a first 64-bit hash for each FQDN in the list of FQDNs;
receiving a request comprising a URL identifying content being requested;
producing a second 64-bit hash of the URL;
combining the second 64-bit hash with each first 64-bit hash produced for each FQDN in the list of FQDNs;
selecting a server from the set of servers to process the request based on a result of combining the second 64-bit hash with each first 64-bit hash; and
distributing the request to the selected server.
13. The computer-implemented method of claim 12 further comprising identifying the request as one for differentiated content or undifferentiated content based on said URL.
14. The computer-implemented method of claim 13 , wherein said combining comprises adjusting the result of combining the second 64-bit hash with each first 64-bit hash with a first set of load factor values when the request is for differentiated content and adjusting the result of combining the second 64-bit hash with each first 64-bit hash with a different second set of load factor values when the request is for undifferentiated content.
15. The computer-implemented method of claim 14 , wherein the first set of load factor values prioritizes a first subset of the set of servers for responding to requests for differentiated content, and wherein the second set of load factor values prioritizes a different second subset of the set of servers for responding to requests for undifferentiated content.
16. The computer-implemented method of claim 13 , wherein producing the first 64-bit hash for each FQDN in the list of FQDNs comprises adjusting the first 64-bit hash for each FQDN with a first load value associated with the FQDN when the request is for differentiated content and adjusting the first 64-bit hash for each FQDN with a second load value when the request is for undifferentiated content, wherein the first load value increases a likelihood of selecting a first subset of the set of servers for responding to requests for differentiated content and the second load value increases a likelihood of selecting a second subset of the set of servers for responding to requests for undifferentiated content.
17. The computer-implemented method of claim 16 further comprising processing each log to dynamically determine different content identified as one of the differentiated content and the undifferentiated content.
18. The computer-implemented method of claim 13 further comprising aggregating a log from each server of the set of servers.
19. The computer-implemented method of claim 12 , wherein selecting the server from the set of servers comprises invoking a first consistent distribution scheme that distributes the request to a first server from the set of servers when the request is for differentiated content, the first consistent distribution scheme providing an even distribution for requests of differentiated content across a first subset of the set of servers optimized for differentiated content delivery.
20. The computer-implemented method of claim 19 , wherein selecting the server from the set of servers further comprises invoking a second consistent distribution scheme that distributes the request to a second server of the set of servers when the request is for undifferentiated content, the second consistent distribution scheme providing an even distribution for requests of undifferentiated content across a different second subset of the set of servers optimized for undifferentiated content delivery, wherein the second subset comprises servers from the set of servers not in the first subset.
21. The computer-implemented method of claim 20 , wherein differentiated content comprises any one of hotly demanded content, content of a particular type, and content delivered with a particular quality of service.
22. A load distribution system for distributing content requests amongst a set of servers, the load distribution system comprising:
a memory storing computer-executable instructions; and
a computer processor in communication with the memory, the computer-executable instructions programming the computer processor in:
obtaining a list of identifiers comprising different identifiers identifying each server of the set of servers;
producing a first 64-bit hash for each identifier in the list of identifiers;
receiving a request comprising a URL identifying content being requested;
producing a second 64-bit hash of the URL;
combining the second 64-bit hash with each first 64-bit hash;
selecting a server from the set of servers to process the request based on a result of combining the second 64-bit hash with each first 64-bit hash; and
distributing the request to the selected server.