Low-latency high-throughput scalable data caching

• US 10,432,706 B2
• Filed: 08/24/2018
• Issued: 10/01/2019
• Est. Priority Date: 12/22/2017
• Status: Active Grant

• Current Assignee: Cadent LLC
• Original Assignee: Engine Media, LLC
• Inventors: Ashner, Louis Clayton, Schwab, Mickey Alexander, Zacharski, Michael, Roach, John Patrick
• Primary Examiner(s): Hoang, Hieu T
• Application Number:
  US16/111,430
• Publication Number:
  US 20190199784A1
• Time in Patent Office: 403 Days
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects
• CPC Class Codes: G06Q 30/08 Auctions
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching

Abstract

Low-latency high-throughput scalable data caching is disclosed. For example, a data source is connected over a network to a load balancer server with data cache. A load balancer service and a data cache service execute on processors on the first load balancer server to receive, by the load balancer service, a request from a client device over the network. The load balancer service requests a data entry associated with the request from the first data cache service. The data cache service retrieves the first data entry from the first data cache, which stores a first plurality of data entries that is a subset of a second plurality of data entries stored in the data source. The load balancer service modifies the request with the data entry. The load balancer service sends a modified request to a plurality of receivers.

Claims

1. A system comprising:

a first data source comprising a processor and a first memory, the first data source connected to a first data cache over a network, wherein the first data source is located in a same geographical region as the first data cache, and wherein the first data source stores a plurality of data entries selected based on a first geolocation of the first data source;

a master data source connected to the first data source over the network;

a second memory storing the first data cache; and

a load balancer service and a data cache service executing on one or more processors communicatively coupled with the memory to;

receive, by the load balancer service, a first request from a client device based on the client device being located in a second geolocation in close proximity to the first geolocation of the first data source;

request, by the load balancer service, a first data entry associated with the first request from the data cache service, wherein the first data entry is available from the master data source;

determine, by the data cache service, that the first data entry is unavailable in both the first data cache and the first data source; and

responsive to determining that the first data entry is unavailable, reject, by the load balancer service, the first request, wherein the first data source retrieves the first data entry from the master data source after the first request is rejected.

2. The system of claim 1, wherein subsequent requests for data entries from the client device during a networking session established between the load balancer service and the client device by the first request are directed to the first data cache.

3. The system of claim 1, wherein each new data request during an extended time interval associated with the client device is processed by the data cache service and the first data cache instead of any other data cache.

4. The system of claim 1, wherein the same geographical region of the data source is located in one of a same data center, a same city, and a same state as the first data cache.

5. The system of claim 4, wherein a second data cache located in the proximate geolocation stores different data entries from the first data cache.

6. The system of claim 1, wherein rejecting the first request comprises one of allowing the first request to time out and responding to the first request with a termination request.

7. The system of claim 1, wherein the master data source is located in a separate geographical region from the first data source and the first data cache.

8. The system of claim 1, wherein the load balancer service and the data cache service further execute to:

receive, by the load balancer service, a second request for the first data entry;

retrieve, by the data cache service, the first data entry from the first data cache, wherein the first data cache received the first data entry from the first data source after the first request was rejected;

modify, by the load balancer service, the second request with the first data entry; and

send, by the load balancer service, the modified second request to a plurality of receivers.

9. The system of claim 8, wherein the modified second request is a solicitation for bids for an advertisement impression and a first receiver of the plurality of receivers is an advertiser that serves an advertisement to the client device.

10. The system of claim 8, wherein the first data entry is updated in the first data source based on a first update request from the client device generated in response to the client device receiving a reply to the modified second request.

11. The system of claim 1, wherein the master data source is updated from one of the first data cache and the first data source.

12. The system of claim 1, wherein the data cache service retrieves a second data entry from the data source.

13. The system of claim 1, wherein the first load balancer service receives a second request and the first data cache is queried for a second data entry while executing a first query for the first data entry.

14. The system of claim 1, wherein the data source is configured to create a backup of a plurality of data entries on the data source while the data source is queried for the first data entry.

15. The system of claim 1, wherein prior to sending the first request to the load balancer service, the client device previously requested the first data entry from a third geolocation resulting in the first data entry being retrieved from at least one of a second data cache and a second data source located in a fourth geolocation in close proximity to the third geolocation.

16. A method comprising:

receiving, by a load balancer service, a first request from a client device based on the client device being located in a first geolocation in close proximity to a second geolocation of a first data source, wherein the first data source is connected to a first data cache located in a same geographical region as the first data source over a network and the first data source stores a plurality of data entries selected based on the second geolocation;

requesting, by the load balancer service, a first data entry associated with the first request from a data cache service, wherein the first data entry is available from a master data source connected to the first data source over the network;

determining, by the data cache service, that the first data entry is unavailable in both the first data cache and the first data source; and

responsive to determining that the first data entry is unavailable, rejecting, by the load balancer service, the first request, wherein the first data source retrieves the first data entry from the master data source after the first request is rejected.

17. The method of claim 16, further comprising:

directing subsequent requests for data entries from the first client device during a networking session established between the load balancer service and the first client device by the first request to the first data cache.

18. The method of claim 16, wherein each new data request during an extended time interval associated with the first client device is processed by the data cache service and the first data cache instead of any other data cache.

19. The method of claim 16, wherein the same geographical region of the data source is located in one of a same data center, a same city, and a same state as the first data cache.

20. The method of claim 19, wherein a second data cache located in the proximate geolocation stores different data entries from the first data cache.

21. The method of claim 16, wherein rejecting the first request comprises one of allowing the first request to time out and responding to the first request with a termination request.

22. The method of claim 16, wherein the master data source is located in a separate geographical region from the first data source and the first data cache.

23. The method of claim 16, further comprising:

receiving, by the load balancer service, a second request for the first data entry;

retrieving, by the data cache service, the first data entry from the first data cache, wherein the first data cache received the first data entry from the first data source after the first request was rejected;

modifying, by the load balancer service, the second request with the first data entry; and

sending, by the load balancer service, the modified second request to a plurality of receivers.

24. The method of claim 23, wherein the modified second request is a solicitation for bids for an advertisement impression and a first receiver of the plurality of receivers is an advertiser that serves an advertisement to the first client device.

25. The method of claim 23, wherein the first data entry is updated in the first data source based on a first update request from the first client device generated in response to the first client device receiving a reply to the modified second request.

26. The method of claim 16, wherein the master data source is updated from one of the first data cache and the first data source.

27. The method of claim 16, further comprising:

retrieving, by the data cache service, a second data entry from the data source.

28. The method of claim 16, wherein the first load balancer service receives a second request and the first data cache is queried for a second data entry while executing a first query for the first data entry.

29. The method of claim 16, wherein prior to sending the first request to the load balancer service, the client device previously requested the first data entry from a third geolocation resulting in the first data entry being retrieved from at least one of a second data cache and a second data source located in a fourth geolocation in close proximity to the third geolocation.

30. A computer-readable non-transitory storage medium storing executable instructions, which when executed by a computer system, cause the computer system to:

receive, by a load balancer service, a first request from a client device based on the client device being located in a first geolocation in close proximity to a second geolocation of a first data source, wherein the first data source is connected to a first data cache located in a same geographical region as the first data source over a network and the first data source stores a plurality of data entries selected based on the second geolocation;

request, by the load balancer service, a first data entry associated with the first request from a data cache service, wherein the first data entry is available from a master data source connected to the first data source over the network;

determine, by the data cache service, that the first data entry is unavailable in both the first data cache and the first data source; and

responsive to determining that the first data entry is unavailable, reject, by the load balancer service, the first request, wherein the first data source retrieves the first data entry from the master data source after the first request is rejected.