# US 8,751,897 B2 · Distributed system for fault-tolerant data storage > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,751,897 B2 - Document ID: US8751897B2 - Status: Granted - Kind: B2 - Application number: 14/057,394 - Filed: 2013-10-18 - Published: 2014-02-13 - Granted: 2014-06-10 - Earliest claimed: 2012-04-25 - Assignees: Facebook, Inc. - Applicants: Facebook, Inc. - Inventors: Dhrubajyoti Borthakur; Per Brashers; Jason Matthew Taylor - Web page: https://patentgrep.com/patent/US8751897B2 ## CPC - G06F 11/2053: {where persistent mass storage functionality or persistent mass storage control functionality is redundant (error detection or correction in information storage based on relative movement between record carrier and transducer G11B20/18)} - G06F 11/1076: {Parity data used in redundant arrays of independent storages, e.g. in RAID systems} - G06F 2211/1028: Distributed, i.e. distributed RAID systems with parity - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Fault-tolerant storage is provided using a distributed data storage system that receives input data from clients and divides that data into data blocks for storage. The data blocks are processed using a coding scheme that generates redundant level one error correction blocks (L1EC Blocks). The L1EC blocks enable the reconstruction of one or more damaged or inaccessible data blocks, and the L1EC blocks and the data blocks are divided into distribution sets and stored at a plurality of data storage locations. At each data storage location additional level two error correction blocks (L2EC blocks) are generated that provide local data redundancy. Upon detecting a data disruption event, an inaccessible data storage location is identified and the elements that were stored at the inaccessible data storage location are reconstructed. ## Claims ### Claim 1 A method comprising: storing each of a plurality of distribution sets at a different one of a plurality of data storage locations, each distribution set comprising one or more elements, each element selected from a plurality of data blocks comprising a portion of input data or a plurality of level one error correction blocks (L1EC blocks) generated from the plurality of data blocks, the L1EC blocks comprising recovery information so that a damaged one of the data blocks is recoverable from one or more of the L1EC blocks and one or more of the plurality of data blocks other than the damaged data block; detecting a data disruption event; identifying an inaccessible data storage location in the plurality of data storage locations; and reconstructing the elements that were stored at the inaccessible data storage location using the elements stored at one or more of the plurality of data storage locations other than the inaccessible data storage location. ### Claim 2 (depends on 1) The method of claim 1, wherein the inaccessible data storage location comprises an inaccessible local storage resource at the data storage location, and wherein the reconstructing the elements that were stored at the inaccessible data storage location comprises reconstructing the elements that were stored at the inaccessible local storage resource using the elements stored at one or more of the plurality of local storage resources other than the inaccessible local storage resource. ### Claim 3 (depends on 1) The method of claim 1, wherein reconstructing the elements further comprises: using a directory maintained by a system supervisor to determine the elements that were stored at the inaccessible data storage location. ### Claim 4 (depends on 1) The method of claim 1, wherein at least one of the plurality of data storage locations further comprises a plurality of local storage resources comprising elements stored at the at least one data storage location. ### Claim 5 (depends on 1) The method of claim 1, wherein no distribution set contains a critical amount of data. ### Claim 6 (depends on 1) The method of claim 1, further comprising: receiving the input data; dividing the input data into the plurality of data blocks; generating the plurality of L1EC blocks from the plurality of data blocks; and generating the plurality of distribution sets. ### Claim 7 (depends on 6) The method of claim 6, further comprising: generating, for each data storage location, a level two error correction block (L2EC block) from two or more of the elements stored at that data storage location, the L2EC blocks comprising recovery information so that a damaged one of the elements at that data storage location is recoverable from one or more of the L2EC blocks and one or more of the plurality of elements at that data storage location other than the damaged element. ### Claim 8 A system comprising: a computer processor; and a non-transitory computer-readable storage medium containing computer instructions executable by the computer processor for: storing each of a plurality of distribution sets at a different one of a plurality of data storage locations, each distribution set comprising one or more elements, each element selected from a plurality of data blocks comprising a portion of input data or a plurality of level one error correction blocks (L1EC blocks) generated from the plurality of data blocks, the L1EC blocks comprising recovery information so that a damaged one of the data blocks is recoverable from one or more of the L1EC blocks and one or more of the plurality of data blocks other than the damaged data block; detecting a data disruption event; identifying an inaccessible data storage location in the plurality of data storage locations; and reconstructing the elements that were stored at the inaccessible data storage location using the elements stored at one or more of the plurality of data storage locations other than the inaccessible data storage location. ### Claim 9 (depends on 8) The system of claim 8, wherein the inaccessible data storage location comprises an inaccessible local storage resource at the data storage location, and wherein the reconstructing the elements that were stored at the inaccessible data storage location comprises reconstructing the elements that were stored at the inaccessible local storage resource using the elements stored at one or more of the plurality of local storage resources other than the inaccessible local storage resource. ### Claim 10 (depends on 8) The system of claim 8, wherein reconstructing the elements further comprises: using a directory maintained by a system supervisor to determine the elements that were stored at the inaccessible data storage location. ### Claim 11 (depends on 8) The system of claim 8, wherein at least one of the plurality of data storage locations further comprises a plurality of local storage resources comprising elements stored at the at least one data storage location. ### Claim 12 (depends on 8) The system of claim 8, wherein no distribution set contains a critical amount of data. ### Claim 13 (depends on 8) The system of claim 8, further comprising computer instructions for: receiving the input data; dividing the input data into the plurality of data blocks; generating the plurality of L1EC blocks from the plurality of data blocks; and generating the plurality of distribution sets. ### Claim 14 (depends on 13) The system of claim 13, further comprising computer instructions for: generating, for each data storage location, a level two error correction block (L2EC block) from two or more of the elements stored at that data storage location, the L2EC blocks comprising recovery information so that a damaged one of the elements at that data storage location is recoverable from one or more of the L2EC blocks and one or more of the plurality of elements at that data storage location other than the damaged element. ### Claim 15 A system comprising: a processor; a system supervisor configured for storing each of a plurality of distribution sets at a different one of a plurality of data storage locations, each distribution set comprising one or more elements, each element selected from a plurality of data blocks comprising a portion of input data or a plurality of level one error correction blocks (L1EC blocks) generated from the plurality of data blocks, the L1EC blocks comprising recovery information so that a damaged one of the data blocks is recoverable from one or more of the L1EC blocks and one or more of the plurality of data blocks other than the damaged data block; the system supervisor further configured for detecting a data disruption event and identifying an inaccessible data storage location in the plurality of data storage locations; and a plurality of reconstructing decoders configured for reconstructing the elements that were stored at the inaccessible data storage location using the elements stored at one or more of the plurality of data storage locations other than the inaccessible data storage location. ### Claim 16 (depends on 15) The system of claim 15, wherein the inaccessible data storage location comprises an inaccessible local storage resource at the data storage location, and wherein the reconstructing the elements that were stored at the inaccessible data storage location comprises reconstructing the elements that were stored at the inaccessible local storage resource using the elements stored at one or more of the plurality of local storage resources other than the inaccessible local storage resource. ### Claim 17 (depends on 15) The system of claim 15, wherein the system supervisor is further configured for maintaining a directory used to determine the elements that were stored at the inaccessible data storage location. ### Claim 18 (depends on 15) The system of claim 15, wherein no distribution set contains a critical amount of data. ### Claim 19 (depends on 15) The system of claim 15, wherein: the processor is further configured for receiving the input data and dividing the input data into the plurality of data blocks; and the system supervisor is further configured for generating the plurality of distribution sets; and further comprising: a global code generator configured for generating the plurality of L1EC blocks from the plurality of data blocks. ### Claim 20 (depends on 19) The system of claim 19, further comprising: a local code generator configured for generating, for each data storage location, a level two error correction block (L2EC block) from two or more of the elements stored at that data storage location, the L2EC blocks comprising recovery information so that a damaged one of the elements at that data storage location is recoverable from one or more of the L2EC blocks and one or more of the plurality of elements at that data storage location other than the damaged element the system supervisor further configured for identifying an inaccessible data storage location in the plurality of data storage locations; and the plurality of reconstructing decoders further configured for reconstructing the elements that were stored at the inaccessible data storage location using the elements stored at one or more of the plurality of data storage locations other than the inaccessible data storage location.