Distributed erasure coded virtual file system
First Claim
1. A system comprising:
- a plurality of computing devices communicatively coupled to each other via a network, wherein;
each of said plurality of computing devices comprises one or more of a plurality of storage devices;
a plurality of failure resilient address spaces are distributed across said plurality of storage devices such that each of said plurality of failure resilient address spaces spans a plurality of said storage devices;
each one of said plurality of failure resilient address spaces is organized into a plurality of stripes; and
each one or more stripes of said plurality of stripes is part of a respective one of a plurality of forward error correction (FEC) protection domains, wherein said plurality of computing devices are operable to rank said plurality of stripes, wherein said rank is used for selection of which of said plurality of stripes to use for a next commit to said particular one of said plurality of failure resilient address spaces.
3 Assignments
0 Petitions
Accused Products
Abstract
A plurality of computing devices are communicatively coupled to each other via a network, and each of the plurality of computing devices comprises one or more of a plurality of storage devices. A plurality of failure resilient address spaces are distributed across the plurality of storage devices such that each of the plurality of failure resilient address spaces spans a plurality of the storage devices. Each one of the plurality of failure resilient address spaces is organized into a plurality of stripes. Each one or more stripes of the plurality of stripes is part of a respective one of a plurality of forward error correction (FEC) protection domains. Each of the plurality of stripes may comprise a plurality of storage blocks. Each block of a particular one of the plurality of stripes may reside on a different one of the plurality of storage devices.
-
Citations
229 Claims
-
1. A system comprising:
a plurality of computing devices communicatively coupled to each other via a network, wherein; each of said plurality of computing devices comprises one or more of a plurality of storage devices; a plurality of failure resilient address spaces are distributed across said plurality of storage devices such that each of said plurality of failure resilient address spaces spans a plurality of said storage devices; each one of said plurality of failure resilient address spaces is organized into a plurality of stripes; and each one or more stripes of said plurality of stripes is part of a respective one of a plurality of forward error correction (FEC) protection domains, wherein said plurality of computing devices are operable to rank said plurality of stripes, wherein said rank is used for selection of which of said plurality of stripes to use for a next commit to said particular one of said plurality of failure resilient address spaces. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 191, 192, 193)
-
26. A system comprising:
a plurality of computing devices communicatively coupled to each other via a network, wherein; each of said plurality of computing devices comprises one or more of a plurality of storage devices; a plurality of failure resilient address spaces are distributed across said plurality of storage devices such that each of said plurality of failure resilient address spaces spans a plurality of said storage devices; each one of said plurality of failure resilient address spaces is organized into a plurality of stripes; each one or more stripes of said plurality of stripes is part of a respective one of a plurality of forward error correction (FEC) protection domains; said plurality of stripes are organized into a plurality of groups; each of said plurality of groups comprises one or more of said plurality of stripes; and for each of said groups, said plurality of computing devices are operable to rank said one or more of said plurality of stripes. - View Dependent Claims (27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49)
-
50. A system comprising:
a plurality of computing devices communicatively coupled to each other via a network, wherein; each of said plurality of computing devices comprises one or more of a plurality of storage devices; a plurality of failure resilient address spaces are distributed across said plurality of storage devices such that each of said plurality of failure resilient address spaces spans a plurality of said storage devices; each one of said plurality of failure resilient address spaces is organized into a plurality of stripes; each one or more stripes of said plurality of stripes is part of a respective one of a plurality of forward error correction (FEC) protection domains; and said plurality of computing devices are operable to; perform successive commit operations to a selected one of said plurality of groups until said one or more of said plurality of stripes of said group no longer meets a determined criterion; and upon said selected one of said plurality of groups no longer meeting said determined criterion, select a different one of said plurality of groups. - View Dependent Claims (51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72)
-
73. A system comprising:
a plurality of computing devices communicatively coupled to each other via a network, wherein; each of said plurality of computing devices comprises one or more of a plurality of storage devices; a plurality of failure resilient address spaces are distributed across said plurality of storage devices such that each of said plurality of failure resilient address spaces spans a plurality of said storage devices; each one of said plurality of failure resilient address spaces is organized into a plurality of stripes; each one or more stripes of said plurality of stripes is part of a respective one of a plurality of forward error correction (FEC) protection domains; and said plurality of computing devices are operable to buffer multiple unrelated portions of data from multiple client application write operations, and commit said multiple unrelated portions of data to a single one of said plurality of stripes. - View Dependent Claims (74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94)
-
95. A system comprising:
a plurality of computing devices communicatively coupled to each other via a network, wherein; each of said plurality of computing devices comprises one or more of a plurality of storage devices; a plurality of failure resilient address spaces are distributed across said plurality of storage devices such that each of said plurality of failure resilient address spaces spans a plurality of said storage devices; each one of said plurality of failure resilient address spaces is organized into a plurality of stripes; and each one or more stripes of said plurality of stripes is part of a respective one of a plurality of forward error correction (FEC) protection domains; one of said plurality of FEC correction domains comprises a plurality of data storage blocks, a first protection storage block, and a second protection storage block; digits stored in said first protection storage block are calculated based on contents of a subset of said plurality of data storage blocks; and digits stored in said second protection storage block are calculated based on contents of at least a subset of said plurality of data storage blocks, and said first protection storage block. - View Dependent Claims (96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115)
-
116. A system comprising:
a plurality of computing devices communicatively coupled to each other via a network, wherein; each of said plurality of computing devices comprises one or more of a plurality of storage devices; a plurality of failure resilient address spaces are distributed across said plurality of storage devices such that each of said plurality of failure resilient address spaces spans a plurality of said storage devices; each one of said plurality of failure resilient address spaces is organized into a plurality of stripes; each one or more stripes of said plurality of stripes is part of a respective one of a plurality of forward error correction (FEC) protection domains; and said plurality of computing devices are operable to; calculate a first protection portion based on a plurality of data portions; replicate said plurality of data portions and said first protection portion, said replication resulting in a first set comprising said plurality of data portions, one or more replicas of said plurality of data portions, said first protection portion, and one or more replicas of said first protection portion; calculate a second protection portion based on all of said data portions and all of said first protection portions of said first set; and commit said first set and said second protection portion to one of said plurality of FEC protection domains. - View Dependent Claims (117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135)
-
136. A system comprising:
a plurality of computing devices communicatively coupled to each other via a network, wherein; each of said plurality of computing devices comprises one or more of a plurality of storage devices; a plurality of failure resilient address spaces are distributed across said plurality of storage devices such that each of said plurality of failure resilient address spaces spans a plurality of said storage devices; each one of said plurality of failure resilient address spaces is organized into a plurality of stripes; each one or more stripes of said plurality of stripes is part of a respective one of a plurality of forward error correction (FEC) protection domains; of said plurality of FEC protection domains comprises a plurality of first storage blocks and a second storage block; stored in each of said plurality of first storage blocks is either;
one of a plurality of data portions, or protection digits calculated based on said plurality of data portions; andstored in said second storage block is a protection portion calculated based on contents of said plurality of first storage blocks. - View Dependent Claims (137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 158, 159)
-
155. A system comprising:
a plurality of computing devices communicatively coupled to each other via a network, wherein; each of said plurality of computing devices comprises one or more of a plurality of storage devices; a plurality of failure resilient address spaces are distributed across said plurality of storage devices such that each of said plurality of failure resilient address spaces spans a plurality of said storage devices; each one of said plurality of failure resilient address spaces is organized into a plurality of stripes; and each one or more stripes of said plurality of stripes is part of a respective one of a plurality of forward error correction (FEC) protection domains; and said plurality of computing devices are operable to; calculate a first protection portion based on a plurality of data portions; calculate a second protection portion based on a first subset of said first protection portion and said plurality of data portions; commit said first subset of said first protection portion and said plurality of data portions and said first protection portion to a first one of said plurality of FEC protection domains; calculate a second protection portion based on a second subset of said first protection portion and said plurality of data portions; and commit said second subset of said first protection portion and said plurality of data portions and said second protection portion to a second one of said plurality of FEC protection domains. - View Dependent Claims (156, 157, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172)
-
173. A system comprising:
a plurality of computing devices communicatively coupled to each other via a network, wherein; each of said plurality of computing devices comprises one or more of a plurality of storage devices; a plurality of failure resilient address spaces are distributed across said plurality of storage devices such that each of said plurality of failure resilient address spaces spans a plurality of said storage devices; each one of said plurality of failure resilient address spaces is organized into a plurality of stripes; each one or more stripes of said plurality of stripes is part of a respective one of a plurality of forward error correction (FEC) protection domains; said plurality of storage devices are organized into a plurality of failure domains; and each of said failure resilient address spaces spans all of said plurality of failure domains, such that upon failure of any particular one of said plurality of failure domains, a workload for reconstructing the lost data is distributed among each of the others of said plurality of failure domains. - View Dependent Claims (174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188)
-
189. A system comprising:
a plurality of computing devices communicatively coupled to each other via a network, wherein; each of said plurality of computing devices comprises one or more of a plurality of storage devices; a plurality of failure resilient address spaces are distributed across said plurality of storage devices such that each of said plurality of failure resilient address spaces spans a plurality of said storage devices; each one of said plurality of failure resilient address spaces is organized into a plurality of stripes; each one or more stripes of said plurality of stripes is part of a respective one of a plurality of forward error correction (FEC) protection domains; said plurality of storage devices are organized into a plurality of failure domains; and in an instance when multiple of said plurality of stripes have one or more failed blocks, said plurality of computing devices are operable to prioritize reconstruction of said multiple of said plurality of stripes in descending order of number of failed blocks in each of said multiple of said plurality of stripes. - View Dependent Claims (190, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 217)
-
204. A system comprising:
a plurality of computing devices communicatively coupled to each other via a network, wherein; each of said plurality of computing devices comprises one or more of a plurality of storage devices; a plurality of failure resilient address spaces are distributed across said plurality of storage devices such that each of said plurality of failure resilient address spaces spans a plurality of said storage devices; each one of said plurality of failure resilient address spaces is organized into a plurality of stripes; each one or more stripes of said plurality of stripes is part of a respective one of a plurality of forward error correction (FEC) protection domains; said plurality of storage devices are organized into a plurality of failure domains; and said plurality of computing devices are operable to, in the event of a failure of one or more of said failure domains, determine a rate at which any particular lost block is reconstructed based on how many other blocks of a same one of said plurality of stripes have also been lost. - View Dependent Claims (205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216)
-
218. A system comprising:
a plurality of computing devices communicatively coupled to each other via a network, wherein; each of said plurality of computing devices comprises one or more of a plurality of storage devices; a plurality of failure resilient address spaces are distributed across said plurality of storage devices such that each of said plurality of failure resilient address spaces spans a plurality of said storage devices; each one of said plurality of failure resilient address spaces is organized into a plurality of stripes; each one or more stripes of said plurality of stripes is part of a respective one of a plurality of forward error correction (FEC) protection domains; and said plurality of computing devices are operable to; perform successive commit operations to a selected one of said plurality of groups until said one or more of said plurality of stripes of said group no longer meets a determined criterion; and upon said selected one of said plurality of groups no longer meeting said determined criterion, select a different one of said plurality of groups; and said criterion is based on how many blocks are available for new data to be written to. - View Dependent Claims (219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229)
Specification