Erasure Coding versus Tail Latency
brooker.co.za
brooker.co.za
Usually the codes used for erasure coding are in systematic form: there are k "preferential" parts out of M that are just literal fragments of the original blob, so if you get those you can just concatenate them to get the original data. If you get any other k-subset, you need to perform expensive reconstruction.
The first two codes (N of N+1 and N of N+2) are nearly trivial and can be done very fast indeed. On my hardware, the N of N+1 code (which is an XOR) can be arranged to be nearly as fast a memcpy (which obviously isn't free either). They can also be done in a streaming way which can save the memcpy if you're feeding a stream into a parser (e.g. JSON or something) or decryption.
> Usually the codes used for erasure coding are in systematic form: there are k "preferential" parts out of M that are just literal fragments of the original blob, so if you get those you can just concatenate them to get the original data.
Yeah, that's true. If you're CPU bound, it may be worth waiting a little longer for these 'diagonal' components to come back.
IIRC, Turbo Codes and LDPCs are less-perfect (they cannot offer strict guarantees like Reed-Solomon can), but as XOR-based simple operations, they are extremely extremely fast to implement.
LDPC has high-probabilities of fixing errors (near Reed-Solomon level), which is good enough in practice. Especially since LDPC's simple XOR-based operation is far faster and like O(n) instead of Reed-Solomon's matrix-multiplication (O(n^2)) algorithm.
The state of the art has moved forward. Reed Solomon is great for proving the practice and providing strict assurances (likely better for storage where you have strict size limits and need strong guarantees for MTBF or other such statistics). But for a "faster" algorithm (ie: trying to prevent repeated packets in a communication stream like TCP or similar protocol), LDPC and/or Turbo codes are likely a better solution.
-----
Reed Solomon is probably best for "smaller" codes where the matrix is smaller and O(n^2) hasn't gotten out of hand yet. But as codes increase in size, the O(n) "less than perfect" codes (such as Turbo codes or LDPC codes) become better-and-better ideas.
That being said: I can imagine some crazy GPU / SIMD algorithm where we have such cheap compute and low bandwidth where the O(n^2) operation might serve as a better basis than the cheap XOR operation. The future of computers is going to be more compute and less relative memory bandwidth after all, so the pendulum may swing the other way depending on how future machines end up.
Do they serve the same use case though? With Reed-Solomon the idea is to recover from complete loss of a fragment of data (erasure coding), isn't LPDC strictly for error correction/"noise" (e.g. certain bits flipping but the data overall exists)?
Reed Solomon traditionally is an error-correction code, for example. But has common implementations in its simplified erasure-only code. (Ex: fixing "lost data" is far easier than fixing "contradictory data").
I'm fairly certain that LDPC erasure codes is as simple as "Is there only one missing erasure in this particular code??" and "answer is LDPC XOR (other data) == missing-data".
EDIT: The "hard part" is the exact composition of (other data), of which there's many styles and different methodologies with tons of different tradeoffs.
There's a lot of names thrown out for practical LDPC erasure codes. Raptor Codes, Tornado Codes, and the like. Hopefully those names can give you a good starting point?
EDIT: I also remember reading a paper on a LDPC Fountain Code (ex: keep sending data + LDPC checkbits until the other side got enough to reconstruct the data), as a kind of "might as well keep sending data while waiting for the ACK", kind of thing, which should cut down on latency.
--------
I'm personally on the "Finished reading my book on Reed-Solomon codes. Figuring out what to study next" phase. There's a lot of codes out there, and LDPC is a huge class...
Then again, the project at work that I had that benefited from these error (erm... erasure) correcting codes was complete and my Reed-solomon implementation was good enough and doesn't really need to be touched anymore. So its not like I have a real reason to study this stuff anymore. Just a little bit of extra data that allowed the protocol to cut off some latency and reduce the number of resends in a very noisy channel we had. The good ol' "MVP into shelved code" situation, lol. Enough code to prove it works, made a nice demo that impressed the higher-ups, and then no one ended up caring for the idea.
If I were to productize the concept, I'd research these more modern, faster codes (like LDPC, Raptor, Tornado, etc. etc.) and implement a state-of-the-art erasure correction solution, ya know? But at this point, the projects just dead.
But honestly, the blog-post's situation (cut down on latency with forward error correction) is seemingly a common problem that's solved again and again in our industry. But at the same time, there's so much to learn in the world of Comp. Sci that sometimes its important to "be lazy" and "learn it when its clearly going to be useful" (and not learning it to hypothetically improve a dead project, lol).
It's unfortunate when a project I've worked on for a while is never used, but at least nice when I learned something from writing it.
Thanks!
I worked on a system that uses a variant of parity packet encoding. Basic parity packet encoding is very simple. You divide you data into N blocks, then send the XOR of all the blocks as an extra packet. Both sender and receiver maintain a running XOR of packets. As soon as the Nth packet has been received, they immidietly reconstruct the N+1th packet without any additional work. This ammounts to 1 extra XOR operation per unit of data, which is a trivial amount of overhead in almost any workload.
Of course, the above scheme is limited to N/N+1 recovery (and is probably as good as you can do for that particular use case).
However, it has a fairly simple extension to N/N+M recovery. Arrange the data in an NxM grid, and construct M sets of "extra" packets". The first set is constructed row wise, (effectivly devolving into the above case). For the second set, rotate each of the columns by their column index. So if R(x,y) is a redundant packet, and D(x,y) is a data packet at location (x,y) in the grid, you would have
* R(0,0) = D(0,0) ^ D(1,0) ^ D(2,0) ^ ... D(N,0)
* R(0,1) = D(0,1) ^ D(1,1) ^ D(2,1) ^ ... D(N,1)
...
* R(0,M-1) = D(0,M-1) ^ D(1,M-1) ^ D(2,M-1) ^ ... D(N,M-1)
* R(1,0) = D(0,0) ^ D(1,1) ^ D(2,2) ^ ... D(N,N%M)
* R(1,1) = D(0,1) ^ D(1,2) ^ D(2,3) ^ ... D(N,(N+1)%M)
* R(1,M-1) = D(0,M-1) ^ D(1,0) ^ D(2,1) ^ ... D(N,(N+1)%M)
...
* R(2,0) = D(0,0) ^ D(1,2) ^ D(2,4) ^ ... D(N,2N%M)
* R(3,0) = D(0,0) ^ D(1,3) ^ D(2,6) ^ ... D(N,3N%M)
Interestingly, the recovery algorithm I described is not optimal in the sense that there are times where it fails to recover data that is theoretically recoverable. Recovering data in all theoretically possible cases probably would be quite intensive.
Say 1 chunk lives in Germany, Ireland and the US each. Client races GETs to all 3 regions and cancels the request to the slowest to respond (which may also be down). Final client latency is equivalent to that of the 2nd slowest region, with substantially better availability due to the ability to tolerate any single region being down
Still wouldn't recommend using E2 for anything important, but ^ was one potential approach to dealing with its terribleness. It still doesn't address the reality of when E2 regions go down, it is often for days and reportedly sometimes weeks at a time. So reliable writing in this scenario would necessitate some kind of queue with capacity for weeks of storage
There are variants of this scheme where you could potentially balance the horrible reliability storage with some expensive reliable storage as part of the same system, but I never got that far in thinking about how it would work
Dropbox does this internally in magic pocket (see their eng blog)
If they aren't also failing at durability, then it wouldn't be any of the classical problems associated with running a storage cluster. Do they just... not bother with online maintenance / upgrades / hardware transitions?
one followup I was thinking of is whether this can generalize to queries other than key value point lookups. if I'm understanding correctly, the article is suggesting to take a key value store, and for every `(key, value)` in the system, split `value` into fragments that are stored on different shards with some `k` of `M` code. then at query time, we can split a query for `key` into `k` subqueries that we send to the relevant shards and reassemble the query results into `value`.
so, if we were to do the same business for an ordered map with range queries, we'd need to find a way to turn a query for `interval: [start, end]` into some number of subqueries that we could send to the different shards and reassemble into the final result. any ideas?
Dbs that are backed by s3-like-storage, the storage does this for you, but for blocks of, say, 1MB, and not per-kv (high overhead).
Think you use rocksdb in your db, and erasure-code the sstables.
For writing, triple-rep has to write 2x as much data or more, so it's going to be slower unless your CPUs are horribly slow compared to your drives.
If you're going to "nest" erasure codes, might as well make them XOR-based (fastest operation on modern CPUs and/or hardware), calculate a randomization scheme that has very-very high probability (99.9%+) of fixing errors, and other such benefits.
To provide assurances that you have enough LDPC, you then run LDPC on your LDPC-check bits. Then you run LDPC on your LDPC-LDPC-check bits. Then you run LDPC on your LPDC-LDPC-LDPC-check bits, until you've got the target probability / chance of fixing errors that you desire.
--------
LDPC's brilliance is that XOR-as-erasure-code is exceptionally fast, and this "repeated hierarchy" of error-correction codes leads to high-probabilities (99.9999%+) of successful correction of erasures.
AWS is such a big place that even after a bit of tenure you still got place to look to find interesting technical approaches and when I was introduced to this schema for Lambda storage I was surprised.
As Marc mentions it is such a simple and powerful idea that is definitely not mentioned enough.
A large number of RS erasure codes are over GF(2^8) which could allow individual byte updates to a stripe for e.g. Octane as storage. Generally, of course, most filesystems checksum at a block level and so byte-writes are rarely going to be implemented as such.