# US 10,481,803 B2 · Low write overhead consensus protocol for distributed storage > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,481,803 B2 - Document ID: US10481803B2 - Status: Granted - Kind: B2 - Application number: 15/626,061 - Filed: 2017-06-16 - Published: 2018-12-20 - Granted: 2019-11-19 - Earliest claimed: 2017-06-16 - Assignees: Western Digital Technologies, Inc. - Applicants: Western Digital Technologies, Inc. - Inventors: Arman Fazeli Chaghooshi; Lluis Pamies-Juarez; Cyril Guyot - Web page: https://patentgrep.com/patent/US10481803B2 ## CPC - G06F 3/0613: {in relation to throughput} - G06F 3/0619: {in relation to data integrity, e.g. data losses, bit errors} - G06F 3/065: {Replication mechanisms} - G06F 3/0659: {Command handling arrangements, e.g. command buffers, queues, command scheduling} - G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]} - G06F 16/273: {Asynchronous replication or reconciliation} - H04L 67/1097: for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS] - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract Technology is provided for updating a data set in a data storage system. In an example data storage system, the system stores a separate copy of an initial data set on each one of a plurality of storage devices, one of which is designated as a leader storage device. The system receives update data and transmits it to each other one of the plurality of replica storage devices. The system updates the copy of the initial data set stored on a replica storage device based on the updated data, resulting in an updated data set and adds a provisional marker to the updated data set. The system transmits an update notification to each of the other replica storage devices. Responsive to determining that update notifications have been received from a threshold number of replica storage, the system removes the provisional marker from the updated data set. ## Claims ### Claim 1 A computer-implemented method 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. ### Claim 2 (depends on 1) The computer-implemented method of claim 1, wherein the threshold number of replica storage devices is based on a total number of replica storage devices in the plurality of replica storage devices. ### Claim 3 (depends on 1) The computer-implemented method of claim 1, wherein the threshold number of replica storage devices is a majority of replica storage devices in the plurality of replica storage devices. ### Claim 4 (depends on 1) The computer-implemented method of claim 1, further comprising: determining that the leader storage device has failed; selecting a candidate replica storage device from the plurality of replica storage devices; and designating the candidate replica storage device as a new leader storage device. ### Claim 5 (depends on 4) The computer-implemented method of claim 4, wherein the candidate replica storage device is selected from replica storage devices in the plurality of replica storage devices that have been updated and do not include the provisional marker. ### Claim 6 (depends on 4) The computer-implemented method of claim 4, wherein the candidate replica storage device is selected from replica storage devices in the plurality of replica storage devices that have not been updated and do not include the provisional marker. ### Claim 7 (depends on 4) The computer-implemented method of claim 4, further comprising: determining that all replica devices in the plurality of replica storage devices include the provisional marker; and selecting the candidate replica storage device from the replica devices in the plurality of replica storage devices that include the provisional marker. ### Claim 8 (depends on 1) The computer-implemented method of claim 1, wherein the leader storage device is predetermined. ### Claim 9 (depends on 1) The computer-implemented method of claim 1, wherein the leader storage device is designated based at least in part on one of: a location of at least one client system, a portion of the initial data set being updated, and a workload associated with the plurality of replica storage devices. ### Claim 10 (depends on 1) The computer-implemented method of claim 1, wherein the update data is included as part of a requested write operation. ### Claim 11 (depends on 1) The computer-implemented method of claim 1, wherein the method does not use update logs while updating data stored on the plurality of replica storage devices. ### Claim 12 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. ### Claim 13 (depends on 12) The data storage system of claim 12, wherein the threshold number of replica storage devices is based on a total number of replica storage devices in the plurality of replica storage devices. ### Claim 14 (depends on 12) The data storage system of claim 12, wherein the threshold number of replica storage devices is a majority of replica storage devices in the plurality of replica storage devices. ### Claim 15 (depends on 12) The data storage system of claim 12, wherein the operations further comprise: determining that the designated leader storage device has failed; selecting a candidate replica storage device in the plurality of replica storage devices; and designating the candidate replica storage device as a new leader storage device. ### Claim 16 (depends on 15) The data storage system of claim 15, wherein the candidate replica storage device is selected from replica storage devices in the plurality of replica storage devices that have been updated and do not include a provisional marker. ### Claim 17 (depends on 12) The data storage system of claim 12, wherein the leader storage device is predetermined. ### Claim 18 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. ### Claim 19 (depends on 18) The system of claim 18, wherein the threshold number of replica storage devices is based on a total number of replica storage devices in the plurality of replica storage devices. ### Claim 20 (depends on 18) The system of claim 18, wherein the threshold number of replica storage devices is a majority of replica storage devices in the plurality of replica storage devices.