Low-latency high-throughput scalable data caching

• US 10,063,632 B1
• Filed: 12/22/2017
• Issued: 08/28/2018
• 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
• Application Number:
  US15/853,366
• Time in Patent Office: 249 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 data source comprising a processor communicatively coupled with a memory connected over a network to a plurality of load balancer servers including a first load balancer server and a second load balancer server, wherein each load balancer server of the plurality of load balancer servers has a respective data cache, including a first data cache of the first load balancer server and a second data cache of the second load balancer server; and

a load balancer service and a data cache service executing on one or more processors on the first load balancer server to;

receive, by the load balancer service, a first request from a first client device over the network;

request, by the load balancer service, a first data entry associated with the first request from the data cache service;

retrieve, by the data cache service, the first data entry from the first data cache, wherein the first data cache stores a first plurality of data entries that is a first subset of a second plurality of data entries stored in the data source;

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

send, by the load balancer service, the modified first request to a plurality of receivers; and

reject, by the load balancer service, a second request from a second client device based on the data cache service failing to locate a second data entry associated with the second request in the first data cache and also failing to locate the second data entry in the data source.

2. The system of claim 1, wherein the second data cache stores a third plurality of data entries that is a second subset of the second plurality of data entries, and the first plurality of data entries is different from the third plurality of data entries.

3. The system of claim 2, wherein the first load balancer server, the second load balancer server, and the data source are all located in a same data center.

4. The system of claim 3, wherein a master data source stores a fourth plurality of data entries, the second plurality of data entries is a third subset of the fourth plurality of data entries, and the master data source is located in a separate geographical region from the data source.

5. The system of claim 4, wherein the master data source is a backup array updated periodically from the data source.

6. The system of claim 1, wherein the first data entry is updated in the data source based on a first update request from the first client device.

7. The system of claim 6, wherein the first update request is generated by the first client device in response to a reply to the first modified request.

8. The system of claim 6, wherein the first data entry in the first data cache is updated based on one of a data request from the first data cache to the data store and a update push by the data store.

9. The system of claim 6, wherein the first update request includes a cookie.

10. The system of claim 1, wherein the data cache service retrieves the first data entry from the data source.

11. The system of claim 1, wherein the data source retrieves the second data entry from a master data source based on the second request, and the data source sends the second data entry to the first data cache.

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

13. The system of claim 1, wherein the data source is configured to execute to a backup of the second plurality of data entries on the data source while the data source responds to the data cache service.

14. The system of claim 13, wherein the backup is taken in a binary form.

15. The system of claim 14, wherein the backup is converted to a format compatible with a relational database and uploaded to a master data source.

16. The system of claim 1, wherein the first plurality of data entries and the second plurality of data entries are stored in random access memory.

17. The system of claim 1, wherein each new request during an extended time interval from the first client device is processed by the load balancer service instead of any other load balancer service on the plurality of load balancer servers.

18. The system of claim 1, wherein upon failure of the data source, a replacement data source is initialized with a third plurality of data entries based on respective pluralities of data entries on respective data caches on the plurality of load balancer servers.

19. The system of claim 1, wherein upon failure of the first load balancer server, a third load balancer server is initialized and the first plurality of data entries is loaded to a third data cache in the third load balancer server.

20. The system of claim 1, wherein the first request is generated by the first client device in response to an advertisement impression and the data entry is a profile associated with the first client device.

21. The system of claim 20, wherein the modified first request is a solicitation for bids for the advertisement impression and a first receiver of the plurality of receivers is an advertiser.

22. The system of claim 21, wherein the advertiser serves an advertisement on the first client device.

23. A method comprising:

receiving, by a load balancer service, a first request from a first client device over a network;

requesting a first data entry associated with the first request from a first data cache, wherein the first data cache is hosted on a same server as the load balancer service;

retrieving the first data entry from the first data cache, wherein the first data cache stores a first plurality of data entries that is a first subset of a second plurality of data entries stored in a data source;

modifying the first request with the first data entry;

sending the modified first request to a plurality of receivers; and

rejecting, by the load balancer service, a second request from a second client device based on failing to locate a second data entry associated with the second request in the first data cache and also failing to locate the second data entry in the data source.

24. The method of claim 23, wherein a master data source stores a third plurality of data entries, the second plurality of data entries is a third subset of the third plurality of data entries, and the master data source is located in a separate geographical region from the data source and the first data cache.

25. The method of claim 23,

wherein the data source retrieves the second data entry from a master data source based on the second request, and the data source sends the second data entry to the first data cache.

26. The method of claim 23, wherein the first data entry is updated in the data source based on a first update request from the first client device and an updated first data entry is later sent to the first data cache.

27. The method of claim 23, wherein the first data cache retrieves the first data entry from the data source.

28. The method of claim 23, wherein upon failure of the data source, a replacement data source is initialized with a third plurality of data entries based on respective pluralities of data entries on respective data caches on a plurality of load balancer servers associated with the data source.

29. 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 over a network;

request a first data entry associated with the first request from a first data cache, wherein the first data cache is hosted on a same server as the load balancer service;

retrieve the first data entry from the first data cache, wherein the first data cache stores a first plurality of data entries that is a first subset of a second plurality of data entries stored in a data source;

modify the first request with the first data entry;

send the modified first request to a plurality of receivers; and

reject, by the load balancer service, a second request from a second client device based on failing to locate a second data entry associated with the second request in the first data cache and also failing to locate the second data entry in the data source.