Consistent distribution using jump table assisted hybrid hash

Patent metadata

Field	Value
Publication number	US-11528322-B1
Application number	US-202117407861-A
Country	US
Kind code	B1
Filing date	Aug 20, 2021
Priority date	Aug 20, 2021
Publication date	Dec 13, 2022
Grant date	Dec 13, 2022

Abstract

Improving load distribution and consistency is provided. A device intermediary to clients and servers can maintain bit values indicative of server availability stored in indices arranged in various levels. A lowest level comprises indices corresponding to a list of servers repeated multiple times. Each index in a higher level maps to a set of indices in a lower level. The device can receive a request from a client to access a server. The device can identify an index in a highest level. The device can determine a second index in the highest level that is after the index in the highest level and has a bit value indicating server availability. The device can identify an index in the lowest level mapping to the second index in the highest level. The device can select a server corresponding to the index in the lowest level.

First claim

What is claimed is:

1. A method, comprising:
maintaining, by a device intermediary to a plurality of clients and a plurality of servers, bit values indicative of server availability stored in indices arranged in a plurality of levels, wherein a lowest level of the plurality of levels comprises a plurality of indices corresponding to a list of servers repeated multiple times, and each index in a higher level in the plurality of levels maps to a set of indices in a lower level of the plurality of levels;
receiving, by the device, a request from a client of the plurality of clients to access one of the plurality of servers;
identifying, by the device based on at least a portion of the request, an index of a plurality of indices in a highest level of the plurality of levels;
determining, by the device, a second index in the plurality of indices in the highest level that is subsequent to the index in the highest level and has a bit value that indicates one or more servers associated with the second index is available to service the request;
identifying, by the device, an index of the plurality of indices in the lowest level of the plurality of levels that maps to the second index in the highest level; and
selecting, by the device to service the request, a server from the list of servers corresponding to the index in the lowest level.

2. The method of claim 1 , further comprising:
determining, by the device based on at least the portion of the request, a second index of the plurality of indices in the lowest level; and
identifying, by the device, the index of the plurality of indices in the highest level of the plurality of levels that maps to the second index in the lowest level.

3. The method of claim 1 , further comprising:
determining, by the device, a hash value based on the at least the portion of the request received from the client;
identifying, by the device using the hash value, a second index of the plurality of indices in the lowest level; and
iteratively mapping, by the device, the second index in the lowest level to the index in the highest level of the plurality of indices in the highest level.

4. The method of claim 1 , further comprising iteratively mapping, by the device, the second index from the highest level to the index of the plurality of indices in the lowest level with the bit value that indicates the one or more servers are available.

5. The method of claim 1 , further comprising:
identifying, by the device, a least significant bit of the second index in the plurality of indices in the highest level, the least significant bit having the bit value that indicates the one or more servers are available;
mapping, by the device, the least significant bit to the index of the plurality of indices in the lowest level;
identifying, by the device, a second least significant bit of the index in the plurality of indices in the lowest level, the second least significant bit having the bit value indicative of an available server; and
selecting, by the device to service the request, the server from the list of servers corresponding to the second least significant bit of the index in the lowest level.

6. The method of claim 1 , further comprising generating, by the device, a hash table with a plurality of indices that each correspond to lists of servers formed from multiple hashes of each of the plurality of servers, wherein the indices of the lowest level of the plurality of levels correspond to the plurality of indices in the hash table.

7. The method of claim 1 , further comprising:
setting, by the device, bit values of first indices in the plurality of levels to a non-zero value based on at least one server associated with the indices being ready to service requests from the plurality of clients; and
setting, by the device, bit values of second indices in the plurality of levels to zero based on none of the servers associated with the second indices being ready to service requests from the plurality of clients.

8. The method of claim 1 , further comprising identifying, by the device, the second index in the highest level by proceeding in a circular clockwise direction from the index in the highest level identified based on at least a portion of the request from the client.

9. The method of claim 1 , further comprising updating, by the device, the bit values stored in the indices in the plurality of levels responsive to a change in availability of any server of the plurality of servers.

10. A system, comprising:
a device comprising one or more processors and memory that is intermediary to a plurality of clients and a plurality of servers to:
maintain bit values indicative of server availability stored in indices arranged in a plurality of levels, wherein a lowest level of the plurality of levels comprises a plurality of indices corresponding to a list of servers repeated multiple times, and each index in a higher level in the plurality of levels maps to a set of indices in a lower level of the plurality of levels;
receive a request from a client of the plurality of clients to access one of the plurality of servers;
identify, based on at least a portion of the request, an index of a plurality of indices in a highest level of the plurality of levels;
determine a second index in the plurality of indices in the highest level that is subsequent to the index in the highest level and has a bit value that indicates one or more servers associated with the second index is available to service the request;
identify an index of the plurality of indices in the lowest level of the plurality of levels that maps to the second index in the highest level; and
select, to service the request, a server from the list of servers corresponding to the index in the lowest level.

11. The system of claim 10 , wherein the device is further configured to:
determine, based on at least the portion of the request, a second index of the plurality of indices in the lowest level; and
identify the index of the plurality of indices in the highest level of the plurality of levels that maps to the second index in the lowest level.

12. The system of claim 10 , wherein the device is further configured to:
determine a hash value based on the at least the portion of the request received from the client;
identify, using the hash value, a second index of the plurality of indices in the lowest level; and
iteratively map the second index in the lowest level to the index in the highest level of the plurality of indices in the highest level.

13. The system of claim 10 , wherein the device is further configured to iteratively map the second index from the highest level to the index of the plurality of indices in the lowest level with the bit value that indicates the one or more servers are available.

14. The system of claim 10 , wherein the device is further configured to:
identify a least significant bit of the second index in the plurality of indices in the highest level, the least significant bit having the bit value that indicates the one or more servers are available;
map the least significant bit to the index of the plurality of indices in the lowest level;
identify a second least significant bit of the index in the plurality of indices in the lowest level, the second least significant bit having the bit value indicative of an available server; and
select, to service the request, the server from the list of servers corresponding to the second least significant bit of the index in the lowest level.

15. The system of claim 10 , wherein the device is further configured to generate a hash table with a plurality of i

Assignees

• Citrix Systems Inc

Inventors

• Chaudhary Aman
• Narayana Raghav Somanahalli
• Abbigari Arunkanth
• Joshi Rajesh
• Srimithra Vemula
• Shivananda Vinay

Classifications

• H04L67/1008 Primary

  based on parameters of servers, e.g. available memory or workload (monitoring of computer activity G06F11/30) · CPC title

• H04L67/1023

  based on a hash applied to IP addresses or costs · CPC title

• H04L67/1014 Primary

  based on the content of a request · CPC title

• H04L67/56

  Provisioning of proxy services (store-and-forward switching systems in data switching networks H04L12/54) · CPC title

• H04L67/101

  based on network conditions · CPC title