US 2014/0195686 A1 · Optimized Consistent Request Distribution for Balanced Load Distribution in a Content Delivery Network

Abstract

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.

Claims22

Dependent claims

A load distribution server for distributing content requests amongst a set of servers, the load distribution server performing a computer-implemented method comprising:

obtaining a list of identifiers comprising an identifier for 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 that identifies 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.

5 more elements

A load distribution server for distributing content requests amongst a set of servers, the load distribution server performing a computer-implemented method comprising:

configuring an identifier listing identifying differentiated content;
configuring a consistent hash function computing a first hash based on a URL identifying requested content and a set of second hashes based on an identifier identifying each server in the set of servers;
receiving a request comprising a URL identifying content that is requested;
analyzing the request to determine whether the request is for differentiated content or undifferentiated content based on whether the URL matches an entry in the identifier listing;
selecting a server from the set of servers to process the request by hashing the URL using the consistent hash when the incoming request is for undifferentiated content;
and
selecting a server from the set of servers to process the request by hashing the URL using the consistent hash and by adjusting at least one resulting value with a set of load factor values when the incoming request is for undifferentiated content;
and
passing the request to a selected server.

6 more elements

For a content delivery network point of presence (PoP) comprising a first tier distribution element and a plurality of second tier caching elements, a computer-implemented method performed by the first tier distribution element to distribute requests across the plurality of second tier caching elements, the computer-implemented method comprising:

configuring an identifier listing, the identifier listing identifying requests for differentiated content;
receiving an incoming request comprising a URL identifying content that is requested;
analyzing the request to determine whether the request is for differentiated content or undifferentiated content based on whether the URL matches an entry in the identifier listing;
invoking a first consistent distribution scheme that distributes the request to a first caching element of the plurality of second tier caching elements when the request is for differentiated content, the first consistent distribution scheme providing an even distribution for requests of differentiated content across the plurality of second tier caching elements;
and
invoking a second consistent distribution scheme that distributes the request to a second caching element of the plurality of second tier caching elements when the request is for undifferentiated content, wherein the second consistent distribution scheme provides an even distribution for requests of undifferentiated content across the plurality of second tier caching elements.

3 more elements

Dependencies are inferred from the claim text.

Optimized Consistent Request Distribution for Balanced Load Distribution in a Content Delivery Network

Life of this patent

Optimized Consistent Request Distribution for Balanced Load Distribution in a Content Delivery Network

Life of this patent

Abstract

Claims22