# US 2014/0195574 A1 · Storing encoded data files on multiple file servers > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0195574 A1 - Document ID: US20140195574A1 - Status: Published application - Kind: A1 - Application number: 14/004,850 - Filed: 2012-08-16 - Published: 2014-07-10 - Earliest claimed: 2012-08-16 - Assignees: Empire Technology Development LLC - Inventors: Lei Zhang; Xuefeng Song - Web page: https://patentgrep.com/patent/US20140195574A1 ## CPC - G06F 16/182: Distributed file systems - G06F 11/1076: {Parity data used in redundant arrays of independent storages, e.g. in RAID systems} - G06F 11/1479: Generic software techniques for error detection or fault masking - G06F 11/2094: {Redundant storage or storage space (G06F11/2056 takes precedence)} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract In some examples, a method for encoding and storing data blocks of a data file on multiple file servers is described. The method may include selecting a data clip size S, selecting a number N of data clips to include in each data block, and dividing the data file into data blocks each having data size (S×N). The method may also include, for each data block, dividing the data block into N data clips, generating a random number R where 1≦R≦N, selecting a number K of redundant data clips where N≦K<2̂N, encoding K data clips using random linear coding by XORing R data clips K times, and storing the K encoded data clips on the multiple file servers. ## Claims ### Claim 1 A method for encoding and storing data blocks of a data file on multiple file servers, the method comprising: selecting a data clip size S; selecting a number N of data clips to include in each data block; dividing the data file into data blocks each having data size (S×N); and for each data block, dividing the data block into N data clips, generating a random number R where 1≦R≦N, selecting a number K of redundant data clips where N≦K<2̂N, encoding K data clips using random linear coding by XORing R data clips K times, and storing the K encoded data clips on the multiple file servers. ### Claim 2 (depends on 1) The method of claim 1, wherein the data clip size S is selected to match a system page size of the multiple file servers. ### Claim 3 (depends on 2) The method of claim 2, wherein the system page size is 4 kB. ### Claim 4 (depends on 2) The method of claim 2, wherein the system page size is 16 kB. ### Claim 5 (depends on 1) The method of claim 1, wherein the number N of data clips is selected as a random number. ### Claim 6 (depends on 1) The method of claim 1, wherein the number N of data clips is selected as a prime number. ### Claim 7 (depends on 1) The method of claim 1, wherein the number N of data clips is selected as 9973. ### Claim 8 (depends on 1) The method of claim 1, wherein a final data block is padded with zeros where the data block size (S×N) does not divide into the size of the data file evenly. ### Claim 9 (depends on 1) The method of claim 1, wherein the multiple file servers are configured to execute a Hadoop Distributed File System (HDFS). ### Claim 10 (depends on 1) A computer storage medium having computer-executable instructions stored thereon that are executable by a computing device to perform the method of claim 1. ### Claim 11 A method for retrieving and decoding encoded data blocks of a data file from multiple file servers, the method comprising: retrieving a data clip size S and a number N of data clips included in each data block; for each encoded data block, retrieving N linearly independent encoded data clips corresponding to the data block from the multiple file servers, decoding the N linearly independent encoded data clips using one or more linear equations, and assembling the N data clips each having the data clip size S into the data block; and assembling the data blocks into the data file. ### Claim 12 (depends on 11) The method of claim 11, wherein the data clip size S is selected to match a system page size of the multiple file servers. ### Claim 13 (depends on 11) The method of claim 11, wherein the system page size is 4 kB or 16 kB. ### Claim 14 (depends on 11) The method of claim 11, wherein the number N of data clips is selected as a random prime number. ### Claim 15 (depends on 11) The method of claim 11, wherein the number N of data clips is selected as 9973. ### Claim 16 (depends on 11) The method of claim 11, further comprising, prior to assembling the data blocks into the data file, removing zeros padded on a final data block if the data block size (S×N) does not divide into the size of the data file evenly. ### Claim 17 (depends on 11) The method of claim 11, wherein the multiple file servers are configured to execute a Hadoop Distributed File System (HDFS). ### Claim 18 (depends on 11) A computer storage medium having computer-executable instructions stored thereon that are executable by a computing device to perform the method of claim 11. ### Claim 19 A system for encoding and storing data blocks of a data file on multiple file servers and retrieving and decoding encoded data blocks of the data file from the multiple file servers, the system comprising: a primary file server and one or more secondary file servers, the primary file server being configured, during the storing of the data file, to: select a data clip size S; select a number N of data clips to include in each data block; divide the data file into data blocks each having data size (S×N); and for each data block, divide the data block into N data clips, generate a random number R where 1≦R≦N, select a number K of redundant data clips where N≦K<2̂N, encode K data clips using random linear coding by XORing R data clips K times, and store the K encoded data clips on one or more secondary file servers, and the primary file server being further configured, during the retrieving of the data file, to: for each encoded data block, retrieve N linearly independent encoded data clips corresponding to the data block from the one or more secondary file servers, decode the N linearly independent encoded data clips using one or more linear equations, and assemble the N data clips each having the data clip size S into the data block; and assemble the data blocks into the data file. ### Claim 20 (depends on 19) The system of claim 19, wherein the primary file server is configured as a NameNode and the one or more secondary file servers are each configured as a DataNode of a Hadoop Distributed File System (HDFS).