Systems and methods for key-value transactions

• US 9,753,873 B1
• Filed: 02/03/2015
• Issued: 09/05/2017
• Est. Priority Date: 12/09/2014
• Status: Active Grant

• Current Assignee: DataRobot, Inc.
• Original Assignee: Parallel Machines Ltd.
• Inventors: Khermosh, Lior, Braverman, Avner, Zuckerman, Gal
• Primary Examiner(s): Thai, Tuan
• Application Number:
  US14/612,595
• Time in Patent Office: 945 Days
• Field of Search: 711100, 711105, 711154, 711127
• CPC Class Codes: G06F 13/26 with priority control
• 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/423 with synchronous protocol
• CPC Class Codes: G06F 2213/0026 PCI express

Abstract

Various embodiments of systems and methods to interleave high priority key-value transactions together with lower priority transactions, in which both types of transactions are communicated over a shared input-output medium. In various embodiments, a central-processing-unit (CPU) initiates high priority key-value transactions by communicating via the shared input-output medium to a key-value-store. In various embodiments, a medium controller blocks or delays lower priority transactions such that the high priority transactions may proceed without interruption. In various embodiments, both of the types of transactions are packet-based, and the system interrupts a lower priority transaction at a particular packet, then completes the high priority transaction, then completes the lower priority transaction. In various embodiments, a network-interface-card (NIC) reduces latency of key-value transactions in a distributed data store by delaying any packet or transaction that may interrupt or prevent immediate delivery of a key to a destination server holding a key value.

Claims

1. A system configured to interleave high priority key-value transactions together with lower priority transactions over a shared input-output medium, comprising:

a shared input-output medium associated with a medium controller;

a central-processing-unit (CPU) comprising a first compute element and a first cache memory; and

a key-value-store communicatively connected with said central-processing-unit via said shared input-output medium,

wherein the central-processing-unit is configured to initiate high priority key-value transactions in conjunction with said key-value-store via said shared input-output medium; and

the medium controller is configured to block lower priority transactions via said shared input-output medium during at least parts of said high priority key-value transactions, thereby achieving said interleaving without delaying said high priority key-value transactions.

2. The system of claim 1, wherein said key-value-store is configured to store a first value associated with a first key, and wherein said high priority key-value transactions comprise at least a new request for said first value, said new request sent from said first compute element to said key-value-store via said shared input-output medium, and said new request conveying said first key to said key-value-store.

3. The system of claim 1, wherein said high priority key-value transactions are latency-critical key-value transactions;

and

said medium controller is configured to interrupt any of said lower priority transactions and immediately commence at least one of said high priority key-value transactions, thereby facilitating said latency criticality.

4. The system of claim 3, wherein both said high priority key-value transactions and lower priority transactions are packet-based transactions performed via said medium controller in conjunction with said shared input-output medium, and said medium controller is configured to stop on-going communication of a first packet belonging to said lower priority transactions via said shared input-output medium, and immediately commence communication of a second packet belonging to said high priority key-value transactions via said shared input-output medium instead, thereby achieving said interruption at the packet level.

5. The system of claim 4, wherein said medium controller is configured to resume communication of said first packet after said second packet has finished communicating, thereby facilitating packet fragmentation.

6. The system of claim 1, wherein said shared input-output medium is based on an interconnect element selected from a group consisting of:

(i) peripheral-component-interconnect-express (PCIE) computer expansion bus, (ii) Ethernet, and (iii) a network-interface-card (NIC).

7. The system of claim 1, wherein both said high priority key-value transactions and lower priority transactions are packet-based transactions performed via said medium controller in conjunction with said shared input-output medium, and said medium controller is configured to deny access to said shared input-output medium from a first packet belonging to said lower priority transactions, and instead grant access to said shared input-output medium to a second packet belonging to said high priority key-value transactions, thereby giving higher priority to said high priority key-value transactions over said lower priority transactions.

8. The system of claim 1, wherein said key-value-store is configured to store a first value associated with a first key, and wherein said high priority key-value transactions comprise at least sending of said first value from said key-value-store to said central-processing-unit via said shared input-output medium.

9. The system of claim 8, further comprising a direct-memory-access (DMA) controller configured to receive said first value via said shared input-output medium directly into said first cache memory.

10. The system of claim 1, wherein said shared input-output medium comprises an electro-optical interface and an optical fiber operative to transport said high priority key-value transactions and said lower priority transactions.

11. A method for interleaving high priority key-value transactions together with lower priority transactions over a shared input-output medium, comprising:

detecting, by a medium controller associated with a shared input-output medium, that a second packet associated with high priority key-value transactions is pending;

stopping, as a result of said detection, by said medium controller, handling of a first packet associated with a lower priority transactions via said shared input-output medium; and

commencing, by said medium controller, transmission of said second packet via said shared input-output medium,

thereby preventing said lower priority transactions from delaying said high priority key-value transactions and thereby interleaving the high priority key-value transactions with the lower priority transactions.

12. The method of claim 11, wherein said prevention leads to a preservation of timing performance of said high priority key-value transactions, wherein said timing performance is selected from a group consisting of:

(i) latency of said high priority key-value transactions, and (ii) bandwidth of said high priority key-value transactions.

13. The method of claim 11, wherein:

said prevention leads to a preservation of latency of said high priority key-value transactions; and

as a result,

said latency is shorter than a time required to transmit a shortest packet belonging to said lower priority transactions.

14. A method for interleave high priority key-value transactions together with lower priority transactions over a shared input-output medium, comprising:

detecting, in a medium controller associated with a shared input-output medium, that a second packet associated with high priority key-value transactions is pending;

delaying, as a result of said detection, by said medium controller, handling of a first packet associated with a lower priority transactions via said shared input-output medium; and

transmitting instead, by said medium controller, said second packet via said shared input-output medium,

thereby preventing said lower priority transactions from delaying said high priority key-value transactions and thereby interleaving the high priority key-value transactions with the lower priority transactions.

15. The method of claim 14, wherein said prevention leads to a preservation of timing performance of said high priority key-value transactions, said timing performance is selected from a group consisting of:

(i) latency of said high priority key-value transactions, and (ii) bandwidth of said high priority key-value transactions.

16. The method of claim 14, wherein:

said prevention leads to a preservation of latency of said high priority key-value transactions; and

as a result,

said latency is shorter than a time required to transmit a shortest packet belonging to said lower priority transactions.

17. A method for interleaving high priority key-value transactions together with lower priority transactions over a network-interface-card, comprising:

receiving, in a first network-interface-card (NIC), from a first compute element, a new request to extract with high priority a first value associated with a first key, in which the new request is associated with a high priority key-value transaction;

consequently

delaying, in said first network-interface-card, a lower priority transaction or other network-related activity—

that prevents said first network-interface-card from immediately communicating said first key to a destination server storing said first value and belonging to a key-value-store comprising a plurality of servers; and

communicating the first key immediately, as a result of said delaying, from said first network-interface-card to said destination server, thereby allowing said destination server to start immediately processing of said first key as required for locating, within said destination server, said first value in conjunction with said new request and thereby interleaving the high priority key-value transaction with the lower priority transaction.

18. The method of claim 17, wherein said delaying comprises prioritizing said new request ahead of said lower priority transaction or other network-related activity, such that said lower priority transaction or other network related activity starts only after said communicating of said first key.