Am I right in thinking that products made during an M of N incident are coded differently to when all N are available? If so, you might want a bitflag to denote "needs to be re-encoded when the N is restored" or else you have some files with less than stellar recovery for a random loss in the N set.
Erasure Coding for Distributed Systems
11–20 of 61 posts
Re: Erasure Coding for Distributed Systems
#12Am I right in thinking that products made during an M of N incident are coded differently to when all N are available? If so, you might want a bitflag to denote "needs to be re-encoded when the N is restored" or else you have some files with less than stellar recovery for a random loss in the N set.
Whenever you have a stripe with missing chunks they need to be re-encoded ASAP because those stripes will be lost if they lose enough chunks. Every distributed storage system needs some kind of librarian to go around grooming the stripes to keep them out of danger.
Re: Erasure Coding for Distributed Systems
#13Erasure coding has been around for a very long time. Remember PAR2 files on Usenet? https://en.wikipedia.org/wiki/Parchive
When I was younger, I literally thought PAR's were magic files. I had no idea how they worked, and from a distance it was magic.
"Any sufficiently advanced technology is indistinguishable from magic." -- Arthur C. Clarke
I thought the same thing when using PAR files. They're still useful today if you save things on media that can be damaged (CD, DVD, Blue-Ray) or across multiple multiple media.
Eventually, I decided to dig into the math behind it. It is a surprisingly simple principle:
Given polynomial of a degree X and an array of data points of size X, there is one and only one solution to the polynomial's coefficients such that it will pass through those data points.
So, stripe the data into bands of arrays, compute the polynomial, and compute additional data points of the curve, and save it with the original data. If you have at least the array's size of data points ( original array and/or parity values) and know the place in the list for each data point (thus which data is missing), there is one and only one solution to the polynomial equation. Once you solve the polynomial again, you can compute any point, including the missing ones. Again, because there is one and only one solution for the curve.
The devil is the math necessary solve the polynomials, which is why it is so computationally intensive.
Re: Erasure Coding for Distributed Systems
#14Years back someone proposed a cute algorithm for erasure codes that depended not on spinning rust but on multipath networking. I believe they called it network coding and the idea was in a network with multiple routes I might get a file faster by pulling an erasure code that used two parts of the file or even two files from one upstream instead of waiting for the entire file from the primary server.
I thought about something like that to make video calls more stable. For example I'll get completely different routes (sometimes noticeably lower/more predictable latency) when I use a VPN to connect to some peer in the US (from Europe.) Would be cool to combine different routes.
Re: Erasure Coding for Distributed Systems
#15Years back someone proposed a cute algorithm for erasure codes that depended not on spinning rust but on multipath networking. I believe they called it network coding and the idea was in a network with multiple routes I might get a file faster by pulling an erasure code that used two parts of the file or even two files from one upstream instead of waiting for the entire file from the primary server.
Network coding is more than that, participants in the graph can synthesize new parts on the fly from parts they just got without having the whole thing. FWIW, freenet at least uses fec-coded files so that you can have some flexibility in what parts you get and durability against a file becoming broken just because a single part gets lost.
and usenet binaries with https://en.wikipedia.org/wiki/Parchive and even earlier with RAR's recovery block, and probably even earlier with BBSes, but my memory is failing me what I was using before it in the 1990s.
edit: I see immediately below while I was composing this, someone mentioned pararchive..
Re: Erasure Coding for Distributed Systems
#16Is it the case that it's really only practical for read-only or very read intensive workloads?
Re: Erasure Coding for Distributed Systems
#17Am I right in thinking that products made during an M of N incident are coded differently to when all N are available? If so, you might want a bitflag to denote "needs to be re-encoded when the N is restored" or else you have some files with less than stellar recovery for a random loss in the N set.
Whenever you have a stripe with missing chunks they need to be re-encoded ASAP because those stripes will be lost if they lose enough chunks. Every distributed storage system needs some kind of librarian to go around grooming the stripes to keep them out of danger.
My point was specifically to new things created during the period. Resilvering happens on addition of a replacement drive in ZFS. I am less sure that otherwise valid, complete checksum states of files made during the loss period get uplifted to the wider stripe count when that is done.
I say that because I have seen some stuff which suggests when you grow the FS with new VDEV in ZFS there are circumstances where the balance is not fixed and you can have persisting unbalanced IO state.
Re: Erasure Coding for Distributed Systems
#18Earlier quoted context omitted.
Whenever you have a stripe with missing chunks they need to be re-encoded ASAP because those stripes will be lost if they lose enough chunks. Every distributed storage system needs some kind of librarian to go around grooming the stripes to keep them out of danger.
My point was specifically to new things created during the period. Resilvering happens on addition of a replacement drive in ZFS. I am less sure that otherwise valid, complete checksum states of files made during the loss period get uplifted to the wider stripe count when that is done. I say that because I have seen some stuff which suggests when you grow the FS with new VDEV in ZFS there are circumstances where the…
In distributed systems you don't need to be constrained to writing to a set of devices one of which is not available. You can just write anywhere, and remember where.
Re: Erasure Coding for Distributed Systems
#19Years back someone proposed a cute algorithm for erasure codes that depended not on spinning rust but on multipath networking. I believe they called it network coding and the idea was in a network with multiple routes I might get a file faster by pulling an erasure code that used two parts of the file or even two files from one upstream instead of waiting for the entire file from the primary server.
This has been used in Ceph for a long time:
https://docs.ceph.com/en/latest/rados/operations/erasure-cod...
I would not be surprised if there was a lot of stuff like this behind S3 and other cloud storage systems too, at least in the lower-access tiers of storage, but I have no actual knowledge of AWS or GCP systems.
Re: Erasure Coding for Distributed Systems
#20Am I right in thinking that products made during an M of N incident are coded differently to when all N are available? If so, you might want a bitflag to denote "needs to be re-encoded when the N is restored" or else you have some files with less than stellar recovery for a random loss in the N set.
Whenever you have a stripe with missing chunks they need to be re-encoded ASAP because those stripes will be lost if they lose enough chunks. Every distributed storage system needs some kind of librarian to go around grooming the stripes to keep them out of danger.
just a suggestion: let the curator's activity be called "preening" rather than "grooming"...