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.