3 ms·

How could any approach involving n copies of data mitigate against loss of n devices? What is the superior approach that avoids this pitfall?

by jl6 5y ago

toast0 5y ago
If you store three copies of all your files, with copies uniformly distributed over the disks, and three disks fail simultaneously [1], you are guaranteed to lose data. If instead, you break your disks into N/3 groups of three, and store each file three times in one group, you only lose data when all three disks in one group fail simultaneously. If you're lucky, you can lose 2/3rds of your disks before you lose data. Edit to add: If you're using mirroring, it's low cost to do mirroring by groups although uniform distribution can help with hotspots. With uniform distribution, even if one device has two popular files, the other copies of those files are likely to be on devices with only one popular file. With grouping, if one group gets two popular files, all devices in the group have two popular files and therefore elevated use. If you're using a parity scheme (raid6/raidz2/some other erasure coding), the cost to do grouping is more apparent. Each group has the +X parity cost; If you did raidz2, and had 45 drives in a case, you could do one set of 45, and get 43 drives worth of storage, or three sets of 15 and get 39 drives worth of storage, or five sets of 9 to get 35 drives worth of storage, etc. In each of the smaller sets, you still can lose data with the first three failures, but you need an increasingly large number of failures to guarantee data loss. Also, the size of the data lost when there's a loss is smaller. [1] or at least, the third disk fails before either of the first two failures is repaired
- jl6 5y ago
  Intuitively, it feels as though grouping is a tradeoff that lowers the probability of a data loss event, at the expense of increasing the amount of data lost in a data loss event? Edit: “proof” by example… 9 disks, replication factor of 3. 9 choose 3 = 84 ways to allocate a file’s replicas across the disks. If 3 disks fail, on average 1/84 of the total data is lost (assuming >>84 files). Versus… 3 groups of 3 disks. If 3 disks fail, the probability of the second disk failure being in the same group as the first disk failure is 2/8, and then 1/7 that the third failure is also in the same group. (2/8)*(1/7)=1/28. So a 100% chance of losing 1/84 of the data versus a 1/28 chance of losing 1/3 of the data. Same total expected amount of data lost.
  - jerf 5y ago
    You begin to see why this is a subtle problem, and why I think it catches so many people. Naive statistics, and perhaps "intuitive" statistics, say it's no different. In reality it's hugely different. It is generally preferable in reality to take the second choice because additional realities intervene to give you time to deal with the problem, allowing the existence of fairly highly-reliable systems, whereas those same additional realities mean that in practice, you will lose data with some frequency if you select the uniformly random result. Sometimes the better systems still catastrophically lose data, that is indeed inevitable as you point out, but what it takes to knock out that system would have result in lost data in the bad uniformly-random system, too, so in practice it's not much of a tradeoff.

How could any approach involving n copies of data mitigate against loss of n devices? What is the superior approach that avoids this pitfall?

by jl6 5y ago

How could any approach involving n copies of data mitigate against loss of n devices? What is the superior approach that avoids this pitfall?

toast0 5y ago

If you store three copies of all your files, with copies uniformly distributed over the disks, and three disks fail simultaneously [1], you are guaranteed to lose data. If instead, you break your disks into N/3 groups of three, and store each file three times in one group, you only lose data when all three disks in one group fail simultaneously. If you're lucky, you can lose 2/3rds of your disks before you lose data. Edit to add: If you're using mirroring, it's low cost to do mirroring by groups although uniform distribution can help with hotspots. With uniform distribution, even if one device has two popular files, the other copies of those files are likely to be on devices with only one popular file. With grouping, if one group gets two popular files, all devices in the group have two popular files and therefore elevated use. If you're using a parity scheme (raid6/raidz2/some other erasure coding), the cost to do grouping is more apparent. Each group has the +X parity cost; If you did raidz2, and had 45 drives in a case, you could do one set of 45, and get 43 drives worth of storage, or three sets of 15 and get 39 drives worth of storage, or five sets of 9 to get 35 drives worth of storage, etc. In each of the smaller sets, you still can lose data with the first three failures, but you need an increasingly large number of failures to guarantee data loss. Also, the size of the data lost when there's a loss is smaller. [1] or at least, the third disk fails before either of the first two failures is repaired

jl6 5y ago
Intuitively, it feels as though grouping is a tradeoff that lowers the probability of a data loss event, at the expense of increasing the amount of data lost in a data loss event? Edit: “proof” by example… 9 disks, replication factor of 3. 9 choose 3 = 84 ways to allocate a file’s replicas across the disks. If 3 disks fail, on average 1/84 of the total data is lost (assuming >>84 files). Versus… 3 groups of 3 disks. If 3 disks fail, the probability of the second disk failure being in the same group as the first disk failure is 2/8, and then 1/7 that the third failure is also in the same group. (2/8)*(1/7)=1/28. So a 100% chance of losing 1/84 of the data versus a 1/28 chance of losing 1/3 of the data. Same total expected amount of data lost.
- jerf 5y ago
  You begin to see why this is a subtle problem, and why I think it catches so many people. Naive statistics, and perhaps "intuitive" statistics, say it's no different. In reality it's hugely different. It is generally preferable in reality to take the second choice because additional realities intervene to give you time to deal with the problem, allowing the existence of fairly highly-reliable systems, whereas those same additional realities mean that in practice, you will lose data with some frequency if you select the uniformly random result. Sometimes the better systems still catastrophically lose data, that is indeed inevitable as you point out, but what it takes to knock out that system would have result in lost data in the bad uniformly-random system, too, so in practice it's not much of a tradeoff.