Peer to peer code generator and decoder for digital systems and cluster storage system

• US 9,372,870 B1
• Filed: 01/06/2014
• Issued: 06/21/2016
• Est. Priority Date: 01/21/2003
• Status: Active Grant

• Current Assignee: PEER Fusion, Inc.
• Original Assignee: PEER Fusion, Inc.
• Inventors: Levy, Richard S.
• Primary Examiner(s): Park, Jeong S
• Application Number:
  US14/148,575
• Time in Patent Office: 897 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 16/1834 implemented based on peer-to-peer networks, e.g. gnutella p2p communication protocols H04L67/104
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: 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]

Abstract

A highly resilient, scalable, high-performance data storage system that stripes its content across a cluster of peer computers. Multiple peers can fail (up to the FEC level configured in the cluster) without disrupting the clients. Peer failures are detected by the cluster and all missing data is seamlessly generated so all I/O operations complete successfully.

Claims

1. A method for operating a cluster of peer systems supporting a filesystem common to all of the peers in the cluster, the filesystem including a plurality of files each divided into codewords striped across at least a subset of the peer systems, comprising the steps of:

each of the peers across which codewords of a particular one of the files are striped having a respective local copy of file metadata indicating both the identity of all the peers across which the codewords of the particular file are striped, and which portions of each of the codewords are assigned to which of the peers, the particular file being striped across more than one peer;

each given available one of the peers across which codewords of the particular file are striped, in response to receiving from a content requestor a first multicast request message which includes a request to read data from the particular file, the first request message identifying both the particular file and the range of data requested, determining in dependence upon both the file metadata copy local to the given peer and the file and data range identified in the first request message, which respective portion of the requested data (if any) is the responsibility of each of the available peers to provide and which respective portion of the requested data is the responsibility of each unavailable peer (if any) to provide; and

each of the given available peers multicasting, toward at least the content requestor and all of the available ones of the peers across which codewords of the particular file are striped, the data which is the responsibility of given peer to provide; and

each of the given peers including in conjunction with its multicast data an identification of both the particular file and the range of data requested by the first request message.

2. The method of claim 1, wherein the particular codeword includes a checksum symbol segment,

and wherein a first subject one of the peers across which codewords of the particular file are striped is unavailable, thereby rendering a first input symbol segment of the file missing,

the method comprising a second subject one of the peers across which codewords of the particular file are striped:

determining, in dependence upon both the file metadata copy local to the second subject peer and the file and data range identified in the first request message, that the second subject peer has a first checksum symbol segment applicable for regenerating the first missing input symbol segment; and

multicasting the first checksum symbol segment toward at least all of the available ones of the peers across which codewords of the particular file are striped.

3. The method of claim 2, further comprising a third subject one of the peers across which codewords of the particular file are striped:

determining in dependence upon both the file metadata copy local to the third subject peer and the file and data range identified in the first request message, that the third subject peer is responsible for regenerating the first missing input symbol segment;

regenerating the first missing input symbol segment in dependence upon the first checksum symbol segment received by multicast from the second subject peer and in further dependence upon data received from available ones of the peers responsively to the first request message; and

multicasting the regenerated first missing input symbol segment.

4. The method of claim 3, wherein the range of data identified in the first request message covers fewer than all input symbol segments of a particular codeword of the file, but does cover the first missing input symbol segment, further comprising a fourth subject one of the peers:

determining in dependence upon both the file metadata copy local to the fourth subject peer and the file and data range identified in the first request message, that the data range identified in the first request message excludes fourth data of the particular codeword held by the fourth subject peer; and

in dependence upon recognition that the first subject peer is unavailable, multicasting the fourth data of the particular codeword toward at least the third subject peer.

5. The method of claim 1, wherein a first subject one of the peers across which codewords of the particular file are striped is unavailable, thereby rendering a first input symbol segment of the file missing,

and wherein the particular codeword includes a checksum symbol segment applicable for regenerating the first missing input symbol segment,

the method comprising a third subject one of the peers across which codewords of the particular file are striped:

determining in dependence upon both the file metadata copy local to the third subject peer and the file and data range identified in the first request message, that the third subject peer is responsible for regenerating the first missing input symbol segment;

regenerating the first missing input symbol segment in dependence upon the checksum symbol segment and in further dependence upon data received from available ones of the peers responsively to the first request message; and

multicasting the regenerated first missing input symbol segment.

6. The method of claim 5, further comprising the third subject peer determining, in dependence upon both the file metadata copy local to the second subject peer and the file and data range identified in the first request message, that the third subject peer has the checksum symbol segment stored locally to the third subject peer.

7. The method of claim 1, wherein a particular one of the peers across which codewords of the particular file are striped fails to receive the first request message, further comprising the particular peer, in response to receiving a particular one of the multicasts sent by a peer responsively to the first request message, the particular multicast including in conjunction therewith the identification of both the particular file and the range of data requested, multicasting the data which is the responsibility of particular peer to provide.

8. The method of claim 7, wherein the first request message is one of a plurality of request messages sent by a data requestor, each of which further includes a unique request identifier,

wherein each of the multicasts sent by peers includes in conjunction therewith the unique identifier of the request identifier of the request message to which it is responsive,

further comprising the particular peer discovering its failure to receive the first request message at least in part by determining that the particular peer had not previously seen a request message having the same request identifier as the particular multicast.

9. The method of claim 1, wherein the filesystem common to all of the peers in the cluster includes a directory hierarchy which is replicated in all of the peers in the cluster.

10. The method of claim 1, wherein the identification of the particular file includes a directory path to the particular file and a name of the particular file.

11. The method of claim 1, wherein the file metadata copies local to each of the peers across which codewords of each subject one of the files is striped each indicate the identity of all the peers across which the codewords of the subject file are striped, including both available peers and any unavailable peers.

12. The method of claim 11, wherein the file metadata copies local to each of the peers across which codewords of each particular one of the files is striped each further indicate a total peer count across which the subject file was striped and a minimum available peer count necessary to open the particular file.

13. The method of claim 1, wherein the range of data identified by the first multicast request message begins with a block other than the first block of the particular file.