Granted Patent B2

US 10,681,120 · App. 16/045,665 · Granted Jun 9, 2020

Abstract

Claims (90)

1. A method, comprising:

receiving, by an intermediary node, from each of a set of servers, a broadcast wherein the broadcast includes a plurality of geohashes, wherein each geohash indicates a three-dimensional map tile repesenting a geographic area that is loaded into the server's memory as an encoding of the location coordinates indicating the geographic area into an interleaved alphanumeric string;

for each of the received geohashes, updating, by the intermediary node, an ordered list indexed by the geohash, wherein each ordered list includes one or more server identifiers each identifying a server of the set of servers that has loaded into its memory the three-dimensional map tile corresponding to the ordered list;

receiving, at the intermediary node, from a client device, a request to connect with a server, the request including location data indicating a location of the client device and a client identifier, the client identifier distinguishing the client device from other client devices;

generating, by the intermediary node, a client geohash based on the received location data;

identifying, by the intermediary node, the ordered list in the set of ordered lists indexed by the client geohash;

selecting, by the intermediary node, a server identifier from the identified ordered list based the client identifier; and

initiating, by the intermediary node, a network connection between the client device and the server of the set of servers associated with the selected server identifier.

2. The method of claim 1 , wherein selecting the server identifier from the identified ordered list based on the client identifier comprises at least one of rendezvous hashing the client identifier and consistent hashing the client identifier.

3. The method of claim 1 , wherein generating the client geohash based on the received location data comprises:

obtaining, by the intermediary node, a location estimate for the client device based on the received location data, wherein the location estimate comprises a set of coordinates; and

generating, by the intermediary node, the client geohash based on the set of coordinates.

4. The method of claim 1 , further comprising:

determining, by the intermediary node, a number of clients that are using a certain three-dimensional map tile;

determining, by the intermediary node, a number of servers that have loaded into memory the certain three-dimensional map tile;

determining, by the intermediary node, a score based on the determined number of clients and the determined number of servers; and

responsive to the determined score exceeding a threshold score:

identifying, by the intermediary node, a least used three-dimensional map tile;

identifying, by the intermediary node, a server of the set of servers that has in its memory the least used three-dimensional map tile; and

sending, by the intermediary node, to the identified server, a request to replace the least used three-dimensional map tile with the certain three-dimensional map tile.

5. The method of claim 1 , further comprising:

determining, by the intermediary node, based on at least one received broadcast, that a first server does not include a first three-dimensional map tile that is represented by a first geohash;

identifying an ordered list indexed by the first geohash; and

removing, from the identified ordered list, a first server identifier representing the first server.

6. The method of claim 5 , further comprising:

identifying, by the intermediary node, a first client device with an initiated network connection with the first server;

determining, by the intermediary node, that the first client device is associated with a first location estimate included in the first three-dimensional map tile;

selecting, by the intermediary node, a new server identifier from the identified ordered list other than the first server identifier; and

initiating, by the intermediary node, a network connection between the first client device and a server of the set of servers associated with the new server identifier.

7. The method of claim 1 , further comprising:

determining, by the intermediary node, that the client device is a high speed client device; and

sending, by the intermediary node, to the server associated with the selected server identifier, instructions to load into its memory three-dimensional map tiles contiguous with the three-dimensional map tile represented by the client geohash.

8. A non-transitory computer-readable storage medium storing computer program instructions executable by a processor to perform operations, the operations comprising:

receiving, by an intermediary node, from each of a set of servers, a broadcast wherein the broadcast includes a plurality of geohashes, wherein each geohash indicates a three-dimensional map tile representing a geographic area that is loaded into the server's memory as an encoding of location coordinates indicating the geographic area into an interleaved alphanumeric string;

for each of the received geohashes, updating, by the intermediary node, an ordered list indexed by the geohash, wherein each ordered list includes one or more server identifiers each identifying a server of the set of servers that has loaded into its memory the three-dimensional map tile corresponding to the ordered list;

receiving, at the intermediary node, from a client device, a request to connect with a server, the request including location data indicating a location of the client device and a client identifier, the client identifier distinguishing the client device from other client devices;

generating, by the intermediary node, a client geohash based on the received location data;

identifying, by the intermediary node, the ordered list in the set of ordered lists indexed by the client geohash;

selecting, by the intermediary node, a server identifier from the identified ordered list based the client identifier; and

initiating, by the intermediary node, a network connection between the client device and the server of the set of servers associated with the selected server identifier.

9. The non-transitory computer-readable storage medium of claim 8 , wherein selecting the server identifier from the identified ordered list based on the client identifier comprises at least one of rendezvous hashing the client identifier and consistent hashing the client identifier.

10. The non-transitory computer-readable storage medium of claim 8 , wherein generating the client geohash based on the received location data comprises:

obtaining, by the intermediary node, a location estimate for the client device based on the received location data, wherein the location estimate comprises a set of coordinates; and

generating, by the intermediary node, the client geohash based on the set of coordinates.

11. The non-transitory computer-readable storage medium of claim 8 , the operations further comprising:

determining, by the intermediary node, a number of clients that are using a certain three-dimensional map tile;

determining, by the intermediary node, a number of servers that have loaded into memory the certain three-dimensional map tile;

determining, by the intermediary node, a score based on the determined number of clients and the determined number of servers; and

responsive to the determined score exceeding a threshold score:

identifying, by the intermediary node, a least used three-dimensional map tile;

identifying, by the intermediary node, a server of the set of servers that has in its memory the least used three-dimensional map tile; and

sending, by the intermediary node, to the identified server, a request to replace the least used three-dimensional map tile with the certain three-dimensional map tile.

12. The non-transitory computer-readable storage medium of claim 8 , the operations further comprising:

determining, by the intermediary node, based on at least one received broadcast, that a first server does not include a first three-dimensional map tile that is represented by a first geohash;

identifying, by the intermediary node, an ordered list indexed by the first geohash; and

removing, by the intermediary node, from the identified ordered list, a first server identifier representing the first server.

13. The non-transitory computer-readable storage medium of claim 12 , the operations further comprising:

identifying, by the intermediary node, a first client device with initiated network connections with the first server;

determining, by the intermediary node, that the first client device is associated with a first location estimate included in the first three-dimensional map tile;

selecting, by the intermediary node, a new server identifier from the identified ordered list other than the first server identifier; and

initiating, by the intermediary node, a network connection between the first client device and a server of the set of servers associated with the new server identifier.

14. The non-transitory computer-readable storage medium of claim 8 , the operations further comprising:

determining, by the intermediary node, that the client device is a high speed client device; and

sending, by the intermediary node, to the server associated with the selected server identifier, instructions to load into its memory three-dimensional map tiles contiguous with the three-dimensional map tile represented by the client geohash.

15. A system comprising:

a processor for executing computer program instructions; and

a non-transitory computer-readable storage medium storing computer program instructions executable by the processor to perform operations, the operations comprising:

receiving, by an intermediary node, from each of a set of servers, a broadcast wherein the broadcast includes a plurality of geohashes, wherein each geohash indicates a three-dimensional map tile representing a geographic area that is loaded into the server's memory as an encoding of location coordinates indicating the geographic area into an interleaved alphanumeric string;

for each of the received geohashes, updating, by the intermediary node, an ordered list indexed by the geohash, wherein each ordered list includes one or more server identifiers each identifying a server of the set of servers that has loaded into its memory the three-dimensional map tile corresponding to the ordered list;

receiving, at the intermediary node, from a client device, a request to connect with a server, the request including location data indicating a location of the client device and a client identifier, the client identifier distinguishing the client device from other client devices;

generating, by the intermediary node, a client geohash based on the received location data;

identifying, by the intermediary node, the ordered list in the set of ordered lists indexed by the client geohash;

selecting, by the intermediary node, a server identifier from the identified ordered list based the client identifier; and

initiating, by the intermediary node, a network connection between the client device and the server of the set of servers associated with the selected server identifier.

16. The system of claim 15 , wherein selecting the server identifier from the identified ordered list based on the client identifier comprises at least one of rendezvous hashing the client identifier and consistent hashing the client identifier.

17. The system of claim 15 , wherein generating the client geohash based on the received location data comprises:

obtaining, by the intermediary node, a location estimate for the client device based on the received location data, wherein the location estimate comprises a set of coordinates; and

generating, by the intermediary node, the client geohash based on the set of coordinates.

18. The system of claim 15 , the operations further comprising:

determining, by the intermediary node, based on at least one received broadcast, that a first server does not include a first three-dimensional map tile that is represented by a first geohash;

identifying, by the intermediary node, an ordered list indexed by the first geohash; and

removing, by the intermediary node, from the identified ordered list, a first server identifier representing the first server.

19. The system of claim 18 , the operations further comprising:

identifying, by the intermediary node, a first client device with initiated network connections with the first server;

determining, by the intermediary node, that the first client device is associated with a first location estimate included in the first three-dimensional map tile;

selecting, by the intermediary node, a new server identifier from the identified ordered list other than the first server identifier; and

initiating, by the intermediary node, a network connection between the first client device and a server of the set of servers associated with the new server identifier.

20. The system of claim 15 , the operations further comprising:

determining, by the intermediary node, that the client device is a high speed client device; and

sending, by the intermediary node, to the server associated with the selected server identifier, instructions to load into its memory three-dimensional map tiles contiguous with the three-dimensional map tile represented by the client geohash.

Assignments (7)