Systems and methods for cache streams

• US 9,781,225 B1
• Filed: 02/03/2015
• Issued: 10/03/2017
• Est. Priority Date: 12/09/2014
• Status: Active Grant

• Current Assignee: DataRobot, Inc.
• Original Assignee: Parallel Machines Ltd.
• Inventors: Braverman, Avner, Adda, Michael, Amar, Lior, Khermosh, Lior, Zuckerman, Gal
• Primary Examiner(s): Phan, Raymond
• Application Number:
  US14/612,533
• Time in Patent Office: 973 Days
• Field of Search: 710104-110, 710305-311, 709201-203, 709217-219, 709226-229
• CPC Class Codes: G06F 12/0623 for memory modules
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 12/1081 for peripheral access to main memory, e.g. direct memory access [DMA]
• CPC Class Codes: G06F 13/28 using burst mode transfer, e.g. direct memory access DMA, cycle steal G06F13/32 takes precedence
• CPC Class Codes: G06F 13/4022 using switching circuits, e.g. switching matrix, connection or expansion network G06F13/4009 takes precedence
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/154 Networked environment
• CPC Class Codes: G06F 2212/2532 comprising a plurality of modules
• CPC Class Codes: G06F 2212/452 Instruction code
• CPC Class Codes: G06F 2212/621 Coherency control relating to peripheral accessing, e.g. from DMA or I/O device
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching

Abstract

Various embodiments of systems and methods to efficiently use a compute element to process a plurality of values distributed over a plurality of servers using a plurality of keys. In various embodiments, a system is configured to identify (or “derive”) the various server locations of various data values, to send requests to the various servers for the needed data values, to receive the data values from the various servers, and to process the various data values received. In various embodiments, requests are sent and data values are received via a switching network. In various embodiments, the servers are organized in a key value store, which may optionally be a shared memory pool. Various embodiments are systems and methods with a small number of compute elements and servers, but in alternative embodiments the elements may be expanded to hundreds or thousands of compute elements and servers.

Claims

1. A system operative to efficiently use a compute element to process a plurality of values distributed over a plurality of servers using a plurality of keys, comprising:

a first compute element associated with a first cache memory; and

a distributed key-value-store (KVS) comprising a plurality of servers configured to store a plurality of values associated with a plurality of keys, said plurality of servers communicatively connected with said first cache memory via a switching network;

wherein said system is configured to;

send, from said first compute element, to a second server of said plurality of servers identified using a second key of said plurality of keys, via said switching network, a new request to receive a second value of said plurality of values associated with said second key; and

receive, via said switching network, from a first server of said plurality of servers, into said first cache memory, a first value of said plurality of values previously requested in conjunction with a first key of said plurality of keys; and

wherein the system is configured to then;

process, in said first compute element, in conjunction with said first cache memory, said first value received, simultaneously with said second server and switching network handling of said new request; and

derive, in said first compute element, from a third key of said plurality of keys, during a first period prior to receiving and processing said second value and simultaneously with said second server and switching network handling of said new request, an identity of a third server of said plurality of servers into which to send a future request for a third value of said plurality of values, thereby facilitating said efficient usage.

2. The system of claim 1, wherein said derivation is done by applying on said third key a technique selected from a group consisting of:

(i) hashing, (ii) table-based mapping, and (iii) any mapping technique either analytical or using look-up tables.

3. A system operative to efficiently use a compute element to process a plurality of values distributed over a plurality of servers using a plurality of keys, comprising:

a first compute element associated with a first cache memory; and

a distributed key-value-store (KVS) comprising a plurality of servers configured to store a plurality of values associated with a plurality of keys, said plurality of servers communicatively connected with said first cache memory via a switching network;

wherein said system is configured to;

send, from said first compute element, to a second server of said plurality of servers identified using a second key of said plurality of keys, via said switching network, a new request to receive a second value of said plurality of values associated with said second key; and

receive, via said switching network, from a first server of said plurality of servers, into said first cache memory, a first value of said plurality of values previously requested in conjunction with a first key of said plurality of keys; and

wherein the system is configured to then;

process, in said first compute element, in conjunction with said first cache memory, said first value received, simultaneously with said second server and switching network handling of said new request; and

derive, in said first compute element, from a third key of said plurality of keys, during a first period prior to receiving and processing said second value, an identity of a third server of said plurality of servers into which to send a future request for a third value of said plurality of values, thereby facilitating said efficient usage;

wherein;

said system is configured to dedicate said first compute element for;

(i) sending any one of said requests to receive respectively any one of said plurality of values,

(ii) processing any one of said plurality of values, and

(iii) deriving identities of any one of said plurality of servers using respectively any one of said plurality of keys;

thereby minimizing at least;

(i) a second period between said receiving and said processing, and

(ii) a third period between said processing and said deriving, thereby facilitating said efficient usage.

4. The system of claim 3, further comprising:

a second compute element, together with said first compute element belonging to a first central-processing-unit (CPU); and

an operating-system (OS) configured to control and manage said first and second compute element;

wherein said operating-system is further configured to manage a plurality of processes comprising;

(i) said sending, receiving, processing, and deriving, and

(ii) other unrelated processes, and

wherein said operating-system is further configured to achieve said dedication by blocking said other unrelated processes from running on said first compute element, and by causing said other unrelated processes to run on said second compute element.

5. The system of claim 3, wherein as a result of said dedication and said simultaneity and said first cache memory, said derivation and processing together account for at least 50 (fifty) per-cent of time spent by said first compute element over a period extending from a beginning of said sending to an end of said deriving, thereby achieving a high computational duty-cycle, thereby allowing said first compute element to process said plurality of keys and values at an increased rate.

6. The system of claim 5, wherein said period extending from said beginning of said sending to said end of said deriving is less than 10 (ten) microseconds.

7. The system of claim 5, wherein said increased rate facilitates a sustained transaction rate of at least 100,000 (one hundred thousand) of said plurality of keys and values per second.

8. A system operative to efficiently use a compute element to process a plurality of values distributed over a plurality of servers using a plurality of keys, comprising:

a first compute element associated with a first cache memory; and

a distributed key-value-store (KVS) comprising a plurality of servers configured to store a plurality of values associated with a plurality of keys, said plurality of servers communicatively connected with said first cache memory via a switching network;

wherein said system is configured to;

send, from said first compute element, to a second server of said plurality of servers identified using a second key of said plurality of keys, via said switching network, a new request to receive a second value of said plurality of values associated with said second key; and

receive, via said switching network, from a first server of said plurality of servers, into said first cache memory, a first value of said plurality of values previously requested in conjunction with a first key of said plurality of keys; and

wherein the system is configured to then;

process, in said first compute element, in conjunction with said first cache memory, said first value received, simultaneously with said second server and switching network handling of said new request; and

derive, in said first compute element, from a third key of said plurality of keys, during a first period prior to receiving and processing said second value, an identity of a third server of said plurality of servers into which to send a future request for a third value of said plurality of values, thereby facilitating said efficient usage;

wherein said first compute element and said first cache memory belong to a first central-processing-unit (CPU), such that the first compute element has a high bandwidth access to the first cache memory, thereby allowing said processing to conclude in less than 5 (five) microseconds.

9. A system operative to efficiently use a compute element to process a plurality of values distributed over a plurality of servers using a plurality of keys, comprising:

a first compute element associated with a first cache memory;

a direct-memory-access (DMA) controller; and

a distributed key-value-store (KVS) comprising a plurality of servers configured to store a plurality of values associated with a plurality of keys, said plurality of servers communicatively connected with said first cache memory via a switching network;

wherein said system is configured to;

send, from said first compute element, to a second server of said plurality of servers identified using a second key of said plurality of keys, via said switching network, a new request to receive a second value of said plurality of values associated with said second key; and

receive, via said switching network, from a first server of said plurality of servers, into said first cache memory, a first value of said plurality of values previously requested in conjunction with a first key of said plurality of keys; and

wherein the system is configured to then;

process, in said first compute element, in conjunction with said first cache memory, said first value received, simultaneously with said second server and switching network handling of said new request; and

derive, in said first compute element, from a third key of said plurality of keys, during a first period prior to receiving and processing said second value, an identity of a third server of said plurality of servers into which to send a future request for a third value of said plurality of values, thereby facilitating said efficient usage;

wherein the direct-memory-access (DMA) controller is configured to receive said first value via said switching network directly into said first cache memory.

10. The system of claim 9, wherein said direct-memory-access controller frees the first compute element to perform said identification of said second server simultaneously with said receiving of said first value, thereby facilitating said efficient usage.

11. A system operative to efficiently use a compute element to process a plurality of values distributed over a plurality of servers using a plurality of keys, comprising:

a first compute element associated with a first cache memory; and

a distributed key-value-store (KVS) comprising a plurality of servers configured to store a plurality of values associated with a plurality of keys, said plurality of servers communicatively connected with said first cache memory via a switching network;

wherein said system is configured to;

send, from said first compute element, to a second server of said plurality of servers identified using a second key of said plurality of keys, via said switching network, a new request to receive a second value of said plurality of values associated with said second key; and

receive, via said switching network, from a first server of said plurality of servers, into said first cache memory, a first value of said plurality of values previously requested in conjunction with a first key of said plurality of keys; and

wherein the system is configured to then;

process, in said first compute element, in conjunction with said first cache memory, said first value received, simultaneously with said second server and switching network handling of said new request; and

derive, in said first compute element, from a third key of said plurality of keys, during a first period prior to receiving and processing said second value, an identity of a third server of said plurality of servers into which to send a future request for a third value of said plurality of values, thereby facilitating said efficient usage;

wherein the system is further configured to;

send to the third server of said plurality of servers identified, via said switching network, said future request to receive said third value; and

receive, via said switching network, from said second server, into said first cache memory, said second value; and

then

process said second value received, simultaneously with said third server and switching network handling of said future request.

12. A system operative to efficiently use a compute element to process a plurality of values distributed over a plurality of servers using a plurality of keys, comprising:

a first compute element associated with a first cache memory;

a network-interface-card (NIC); and

a distributed key-value-store (KVS) comprising a plurality of servers configured to store a plurality of values associated with a plurality of keys, said plurality of servers communicatively connected with said first cache memory via a switching network;

wherein said system is configured to;

send, from said first compute element, to a second server of said plurality of servers identified using a second key of said plurality of keys, via said switching network, a new request to receive a second value of said plurality of values associated with said second key; and

receive, via said switching network, from a first server of said plurality of servers, into said first cache memory, a first value of said plurality of values previously requested in conjunction with a first key of said plurality of keys; and

wherein the system is configured to then;

process, in said first compute element, in conjunction with said first cache memory, said first value received, simultaneously with said second server and switching network handling of said new request; and

derive, in said first compute element, from a third key of said plurality of keys, during a first period prior to receiving and processing said second value, an identity of a third server of said plurality of servers into which to send a future request for a third value of said plurality of values, thereby facilitating said efficient usage;

wherein the network-interface-card (NIC) is configured to associate said first compute element and said first cache memory with said switching network,

and wherein said network-interface-card is further configured to block or delay any communication currently preventing the network-interface-card from immediately performing said sending, thereby preventing said first compute element from waiting before performing said sending, thereby facilitating said efficient usage.

13. A system operative to efficiently use a compute element to process a plurality of values distributed over a plurality of servers using a plurality of keys, comprising:

a first compute element associated with a first cache memory;

a direct-memory-access (DMA) controller; and

a distributed key-value-store (KVS) comprising a plurality of servers configured to store a plurality of values associated with a plurality of keys, said plurality of servers communicatively connected with said first cache memory via a switching network;

wherein said system is configured to;

send, from said first compute element, to a second server of said plurality of servers identified using a second key of said plurality of keys, via said switching network, a new request to receive a second value of said plurality of values associated with said second key; and

receive, via said switching network, from a first server of said plurality of servers, into said first cache memory, a first value of said plurality of values previously requested in conjunction with a first key of said plurality of keys; and

wherein the system is configured to then;

process, in said first compute element, in conjunction with said first cache memory, said first value received, simultaneously with said second server and switching network handling of said new request; and

derive, in said first compute element, from a third key of said plurality of keys, during a first period prior to receiving and processing said second value, an identity of a third server of said plurality of servers into which to send a future request for a third value of said plurality of values, thereby facilitating said efficient usage;

wherein the direct-memory-access (DMA) controller is configured to receive said second value via said switching network directly into said first cache memory, and wherein said direct-memory-access controller frees the first compute element to perform said processing simultaneously with said receiving of said second value, thereby facilitating said efficient usage.

14. A method for efficiently mixing and timing at least two key-value transactions in conjunction with a distributed key-value-store (KVS), comprising:

starting, by a direct-memory-access (DMA) controller, a first process of receiving via a switching network, from a first server of a plurality of servers, directly into a first cache memory associated with a first compute element, a first value of a plurality of values previously requested and associated with a first key of a plurality of keys;

deriving in said first compute element, from a second key of said plurality of keys, simultaneously with at least one part of said first process, an identity of a second server of said plurality of servers into which to send a new request for a second value of said plurality of values;

sending, via said switching network from said first compute element to said second server identified, said new request;

finishing, by said direct-memory-access controller, said first process of receiving; and

then

processing said first value received, in said first compute element, simultaneously with said second server and switching network handling of said new request.

15. The method of claim 14, further comprising:

deriving, in said first compute element, from a third of said plurality of keys, during a first period prior to receiving and processing said second value, an identity of a third of said plurality of servers into which to send a future request for a third of said plurality of values.