A system comprising a primary storage unit and one or more secondary storage units (224, 226), the primary storage unit comprising: a first non-volatile memory; a first memory storing processor-executable process steps; and a first processor to execute the processor-executable process steps to cause the primary storage unit to: receive a first write request from a client including a first key-value pair comprising a first key and a first value, wherein the key in a key-value pair is a number from a monotonically-increasing sequence and the value in a key-value pair is a transaction log fragment; persist the first value in the first non-volatile memory in association with the first key; broadcast the first write request and a first set of globally-durable keys to the one or more secondary storage units (224, 226), wherein a set of globally-durable keys includes all keys for which a value has been made durable in each storage unit (222, 224, 226) of the system; receive, from each of the one or more secondary storage units (224, 226), an acknowledgement of the first write request and a first set of locally-durable keys, each of the first sets of locally-durable keys including the first key, wherein the locally-durable keys are keys that are not globally-durable; in response to the reception of the acknowledgement of the first write request and the first set of locally-durable keys from each of the one or more secondary storage units, transmit an acknowledgement of the first write request to the client; receive a second write request from the client including a second key-value pair comprising a second key and a second value; persist the second value in the first non-volatile memory in association with the second key; and broadcast the second write request and a second set of globally-durable keys to the one or more secondary storage units, the second set of globally-durable keys including the first key. a first non-volatile memory; a first memory storing processor-executable process steps; and a first processor to execute the processor-executable process steps to cause the primary storage unit to: receive a first write request from a client including a first key-value pair comprising a first key and a first value, wherein the key in a key-value pair is a number from a monotonically-increasing sequence and the value in a key-value pair is a transaction log fragment; persist the first value in the first non-volatile memory in association with the first key; broadcast the first write request and a first set of globally-durable keys to the one or more secondary storage units (224, 226), wherein a set of globally-durable keys includes all keys for which a value has been made durable in each storage unit (222, 224, 226) of the system; receive, from each of the one or more secondary storage units (224, 226), an acknowledgement of the first write request and a first set of locally-durable keys, each of the first sets of locally-durable keys including the first key, wherein the locally-durable keys are keys that are not globally-durable; in response to the reception of the acknowledgement of the first write request and the first set of locally-durable keys from each of the one or more secondary storage units, transmit an acknowledgement of the first write request to the client; receive a second write request from the client including a second key-value pair comprising a second key and a second value; persist the second value in the first non-volatile memory in association with the second key; and broadcast the second write request and a second set of globally-durable keys to the one or more secondary storage units, the second set of globally-durable keys including the first key. receive a first write request from a client including a first key-value pair comprising a first key and a first value, wherein the key in a key-value pair is a number from a monotonically-increasing sequence and the value in a key-value pair is a transaction log fragment; persist the first value in the first non-volatile memory in association with the first key; broadcast the first write request and a first set of globally-durable keys to the one or more secondary storage units (224, 226), wherein a set of globally-durable keys includes all keys for which a value has been made durable in each storage unit (222, 224, 226) of the system; receive, from each of the one or more secondary storage units (224, 226), an acknowledgement of the first write request and a first set of locally-durable keys, each of the first sets of locally-durable keys including the first key, wherein the locally-durable keys are keys that are not globally-durable; in response to the reception of the acknowledgement of the first write request and the first set of locally-durable keys from each of the one or more secondary storage units, transmit an acknowledgement of the first write request to the client; receive a second write request from the client including a second key-value pair comprising a second key and a second value; persist the second value in the first non-volatile memory in association with the second key; and broadcast the second write request and a second set of globally-durable keys to the one or more secondary storage units, the second set of globally-durable keys including the first key.