Low write overhead consensus protocol for distributed storage

A data storage system comprising:

• one or more computer processors;
• and
• storage logic including a data manager that, when executed by the one or more computer processors, performs operations comprising:
• storing a separate copy of an initial data set on each one of a plurality of replica storage devices, one of which is designated as a leader storage device;
• receiving, at the leader storage device, update data from a client system;
• transmitting the update data from the leader storage device to each other one of the plurality of replica storage devices;
• at a plurality of particular replica storage devices other than the leader storage device in the plurality of replica storage devices:
• updating a copy of the initial data set stored on each particular replica storage device based on the update data, resulting in an updated data set;
• adding a provisional marker to the updated data set stored on each particular replica storage device;
• transmitting an update notification to each other one of the plurality of replica storage devices in the plurality of replica storage devices;
• determining, by each particular replica storage device, that update notifications have been received from at least a threshold number of replica storage devices in the plurality of replica storage devices;
• and
• responsive to each particular replica storage device determining that the update notifications have been received from at least the threshold number of replica storage devices in the plurality of replica storage devices, removing the provisional marker from the updated data set stored on each particular replica storage device;
• determining, at the leader storage device, that the update notifications have been received from at least the threshold number of replica storage devices in the plurality of replica storage devices;
• and
• updating the copy of the initial data set stored at the leader storage device to the updated data set.

A system comprising:

• means for storing a separate copy of an initial data set on each one of a plurality of replica storage devices, one of which is designated as a leader storage device;
• means for receiving, at the leader storage device, update data from a client system;
• means for transmitting the update data from the leader storage device to each other one of the plurality of replica storage devices;
• at a plurality of particular replica storage devices other than the leader storage device in the plurality of replica storage devices:
• means for updating a copy of the initial data set stored on each particular replica storage device based on the update data, resulting in an updated data set;
• means for adding a provisional marker to the updated data set stored on each particular replica storage device;
• means for transmitting an update notification to each other one of the plurality of replica storage devices in the plurality of replica storage devices;
• means for determining, by each particular replica storage device, that update notifications have been received from at least a threshold number of replica storage devices in the plurality of replica storage devices;
• and
• means for, responsive to each particular replica storage device determining that the update notifications have been received from at least the threshold number of replica storage devices in the plurality of replica storage devices, removing the provisional marker from the updated data set stored on each particular replica storage device;
• means for determining, at the leader storage device, that the update notifications have been received from at least the threshold number of replica storage devices in the plurality of replica storage devices;
• and
• means for updating the copy of the initial data set stored at the leader storage device to the updated data set.