Systems and methods for automatically aggregating write requests

• US 9,477,412 B1
• Filed: 07/23/2015
• Issued: 10/25/2016
• Est. Priority Date: 12/09/2014
• Status: Active Grant

• Current Assignee: DataRobot, Inc.
• Original Assignee: Parallel Machines Ltd.
• Inventors: Amar, Lior, Braverman, Avner, Zuckerman, Gal, Khermosh, Lior, Adda, Michael
• Primary Examiner(s): Unelus, Ernest
• Assistant Examiner(s): MODO, RONALD T
• Application Number:
  US14/806,835
• Time in Patent Office: 460 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• 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/0862 with prefetch
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 12/1081 for peripheral access to main memory, e.g. direct memory access [DMA]
• 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 16/244 Grouping and aggregation
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/2532 comprising a plurality of modules
• CPC Class Codes: G06F 2212/283 Plural cache memories
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Described herein are various systems and methods to automatically decide to aggregate data write requests in a distributed data store. A system initiates outgoing data write requests in synchronization with incoming data store commands, thereby facilitating low-latency read-back of the data. In response to an absence of data read requests, the system automatically changes such that each request includes two or more data sets, thereby breaking synchronization but consequently reducing traffic load on a switching network within the system. If the system later detects data read requests for previously stored data, the system will automatically change back to the original synchronized state, thereby decreasing the latency of accessing stored data. The system alternates between the modes of operation to achieve balance between low latency of data access and reduced traffic load on the switching network.

Claims

1. A system operative to automatically decide to aggregate data write requests in a distributed data store, comprising:

a plurality of memory modules constituting a distributed data store, in which said plurality of memory modules are associated respectively with a plurality of data interfaces;

a switching network; and

a first compute element configured to receive sequentially a sequence of store commands associated respectively with a sequence of data sets, in which each of the store commands instructs the first compute element to store the respective data set in said distributed data store, wherein;

the first compute element is further configured to initiate, as a result of the sequence, a series of data write requests respectively with some of the commands and in synchronization therewith, in which;

(i) each of the data write requests comprises one of the data sets to be conveyed, and (ii) each of the data write requests is sent via the switching network to one of the data interfaces that consequently stores, in the respective memory module, the data set conveyed;

each of the data interfaces is configured to detect a condition in which;

(i) at least a certain number of said data write requests have arrived at the data interface, while (ii) there has been no attempt to read any of the data sets conveyed to the data interface, thereby signifying that maintaining low latency through said synchronization is not critical; and

therefore the first compute element, as a response to one of the data interfaces signaling that said condition has been detected, is further configured to send at least one aggregated data write request to the data interface, in which said aggregated data write request conveys at least two of the data sets that have not yet been conveyed, thereby;

breaking said synchronization;

consequently increasing a latency associated with storage of the data sets conveyed;

but gaining a reduction of load on the switching network.

2. The system of claim 1, wherein:

each of the data interfaces is further configured to detect a departure from said condition, by identifying an attempt to read any of the data sets conveyed to the data interface, thereby signifying that maintaining low latency through a renewed synchronization with the sequence of store commands is now critical; and

the first compute element, as a response to one of the data interfaces signaling that said departure from the condition has been detected, is further configured to;

stop aggregation of data sets into a next aggregated data write request; and

send, as quickly as possible, said next aggregated data write request containing whatever data sets that have already been accumulated.

3. The system of claim 2, wherein the first compute element, as a further response to one of the data interfaces signaling that said departure from the condition has been detected, is further configured to initiate a second series of data write requests in a renewed synchronization with the store commands that are still being received, in which:

(i) each of the data write requests in the second series comprises one of the data sets that has been recently received in one of the store commands, and (ii) each of the data write requests in the second series is sent via the switching network to one of the data interfaces that consequently stores, in the respective memory module, the respective data set, thereby;

renewing said synchronization;

consequently

decreasing a latency associated with storage of the data sets conveyed;

but consequently increasing the load on the switching network.

4. The system of claim 3, wherein said renewed synchronization is done in conjunction with all of the data interfaces.

5. The system of claim 3, wherein said renewed synchronization is done in conjunction with only the data interface which has detected said departure.

6. The system of claim 1, wherein the first compute element, as a further response to one of the data interfaces signaling that said condition has been detected, is further configured to send at least another aggregated data write request to one of the data interfaces other than the data interface which has detected said condition, in which said another aggregated data write request conveys at least another two of the data sets that have not yet been conveyed.

7. The system of claim 6, wherein:

the at least two data sets conveyed by the aggregated data write request are selected for aggregation in said aggregated data write request according to a decision, by the first compute element, to store the at least two data sets in conjunction with one of the data interfaces; and

the at least another two data sets conveyed by the another aggregated data write request are selected for aggregation in said another aggregated data write request according to another decision, by the first compute element, to store the at least another two data sets in conjunction with another of the data interfaces.

8. The system of claim 1, wherein said breaking of synchronization is done in conjunction with all of the data interfaces.

9. The system of claim 1, wherein said breaking of synchronization is done in conjunction with only the data interface which has detected said condition.

10. The system of claim 1, wherein said first compute element decides, per each of the data write requests, according to an input, which of the data interfaces is the target of the data write request.

11. The system of claim 10, wherein:

the distributed data store is a key-value store (KVS);

said sequence of data sets is a sequence of values, in which each of the data sets is a value associated with a key; and

said input is the respective key.

12. The system of claim 1, wherein the sequence of store commands is sent to the first compute element from a second compute element, in which said second compute element is not aware to whether or not the data sets in the sequence of store commands are conveyed to the data interfaces using aggregated data write requests.

13. The system of claim 12, wherein the first compute element does not know when the second compute element will decide to read-back any of the data sets conveyed.

14. The system of claim 1, wherein:

the sequence of store commands is generated by an application layer running on said first compute element;

said sequence of store commands are received by an interface layer running on said first compute element; and

the series of data write requests and the at least one aggregated data write request are all sent by said interface layer, in which said application layer is not aware as to whether or not said interface layer sends the data sets to the data interfaces using aggregated data write requests.

15. The system of claim 14, wherein the interface layer does not know when the application layer will decide to read-back any of the data sets conveyed.

16. A method for signaling a compute element to start aggregating data write requests;

comprising;

receiving, in a data interface, from a compute element, a series of data write requests conveying respectively a series of data sets, in which each of the data sets conveyed is to be stored by the data interface;

storing, by the data interface, each of the data sets conveyed, as soon as the data set is conveyed, such that said storing is performed in synchronization with said reception of the data write requests, thereby facilitating low latency read-back of the data sets already conveyed;

detecting, by the data interface, a condition in which;

(i) at least a certain number of said data write requests have arrived at the data interface, while (ii) there has been essentially no attempt to read-back, from the data interface, any of the data sets conveyed to the data interface;

signaling, as a result of said detection, by the data interface, to the compute element, that said condition has been detected, thereby implying to said compute element that;

(i) it is not critical to maintain a low latency in conjunction with said storage of the data sets, and therefore that (ii) aggregation of data write requests is now possible; and

receiving, in the data interface, from a compute element, as a result of said signaling, at least one aggregated data write request, in which said aggregated data write request conveys at least two additional data sets to be stored by the data interface.

17. The method of claim 16, further comprising:

storing, eventually, by the data interface, in a memory module, the at least two additional data sets conveyed.

18. The method of claim 17, further comprising:

detecting, by the data interface, a departure from said condition, by identifying an attempt to read any of the data sets conveyed to the data interface, thereby signifying that maintaining the low latency in conjunction with the storage of said data sets is now critical; and

signaling, by the data interface, to the compute element, that the departure from said condition has been detected, thereby implying to said compute element that;

(i) it is now critical again to maintain the low latency in conjunction with said storage of the data sets, and therefore that (ii) aggregation of data write requests is not possible anymore.

19. The method of claim 16, wherein the storing of each of the data sets conveyed, which is performed in synchronization with the reception of the data write requests, is performed in conjunction with a memory module associated with the data interface.

20. The method of claim 16, wherein the storing of each of the data sets conveyed, which is performed in synchronization with the reception of the data write requests, is performed in conjunction with a data register belonging to the data interface.

21. The method of claim 20, further comprising:

transferring the data sets conveyed, from the data register to a memory module associated with the data interface.

22. The method of claim 16, wherein:

the condition detected is a condition in which;

(i) at least 10 (ten) of said data write requests have arrived at the data interface, while (ii) there has been absolutely no attempt to read any of the data sets conveyed to the data interface.

23. A method for signaling a compute element to start aggregating data write requests;

comprising;

receiving, in a data interface, from a compute element, a series of data write requests conveying respectively a series of data sets, in which each of the data sets conveyed is to be stored by the data interface;

storing, by the data interface, each of the data sets conveyed, as soon as the data set is conveyed, such that said storing is performed in synchronization with said reception of the data write requests, thereby facilitating low latency read-back of the data sets already conveyed;

detecting, by the data interface, a condition in which;

(i) at least a first quantity of said data write requests have arrived at the data interface, while (ii) there has been a second quantity of attempts to read-back, from the data interface, any of the data sets conveyed to the data interface, in which said first quantity is at least 10 (ten) times larger than said second quantity, thereby implying that there was essentially no attempt to read any of the data sets conveyed to the data interface;

signaling, as a result of said detection, by the data interface, to the compute element, that said condition has been detected, thereby implying to said compute element that;

(i) it is not critical to maintain a low latency in conjunction with said storage of the data sets, and therefore that (ii) aggregation of data write requests is now possible; and

receiving, in the data interface, from a compute element, as a result of said signaling, at least one aggregated data write request, in which said aggregated data write request conveys at least two additional data sets to be stored by the data interface.