TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

Erasure Coding for Distributed Systems

284 点作者 eatonphil9 个月前

11 条评论

jcalvinowens9 个月前
I&#x27;m surprised rateless fountain codes aren&#x27;t mentioned! If you enjoy this sort of thing, you&#x27;ll find the Luby Transform Code fascinating: <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Luby_transform_code" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Luby_transform_code</a><p>This paper is a really nice overview with more detail: <a href="https:&#x2F;&#x2F;switzernet.com&#x2F;people&#x2F;emin-gabrielyan&#x2F;060112-capillary-references&#x2F;ref&#x2F;MacKay05.pdf" rel="nofollow">https:&#x2F;&#x2F;switzernet.com&#x2F;people&#x2F;emin-gabrielyan&#x2F;060112-capilla...</a><p>LT codes are used as the &quot;outer code&quot; in the linear time RaptorQ encoding specified in RFC6330: <a href="https:&#x2F;&#x2F;www.rfc-editor.org&#x2F;rfc&#x2F;rfc6330" rel="nofollow">https:&#x2F;&#x2F;www.rfc-editor.org&#x2F;rfc&#x2F;rfc6330</a>
评论 #41365185 未加载
评论 #41365232 未加载
评论 #41364473 未加载
hinkley9 个月前
Years back someone proposed a cute algorithm for erasure codes that depended not on spinning rust but on multipath networking.<p>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.
评论 #41363714 未加载
评论 #41363214 未加载
评论 #41363536 未加载
评论 #41363339 未加载
otterley9 个月前
Erasure coding has been around for a very long time. Remember PAR2 files on Usenet? <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Parchive" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Parchive</a>
评论 #41365009 未加载
评论 #41363154 未加载
评论 #41364409 未加载
donavanm9 个月前
If youre interested in EC you might want to consider larger multi dimensional cases. Think of encoding not just across spindles, but another failure domain like rack, room, DC, or region. The goal being to tolerate common component failures, and larger system failures (or partitions) as well. A nice intro <a href="https:&#x2F;&#x2F;chameleoncloud.org&#x2F;blog&#x2F;2023&#x2F;12&#x2F;12&#x2F;design-considerations-and-analysis-of-multi-level-erasure-coding-in-large-scale-data-centers&#x2F;" rel="nofollow">https:&#x2F;&#x2F;chameleoncloud.org&#x2F;blog&#x2F;2023&#x2F;12&#x2F;12&#x2F;design-considerat...</a>
评论 #41364923 未加载
wahern9 个月前
Has anybody used Wirehair in a project? <a href="https:&#x2F;&#x2F;github.com&#x2F;catid&#x2F;wirehair">https:&#x2F;&#x2F;github.com&#x2F;catid&#x2F;wirehair</a><p>I&#x27;m curious if it&#x27;s well-defined enough to base a standard around--informally if not formally--for building a large file archiving&#x2F;data recovery project I&#x27;ve been mulling over for nearly 10 years. It&#x27;s the only large block erasure code I&#x27;ve found that has both the ideal (or nearly ideal) algorithmic performance <i>and</i> API. That makes it a nice blackbox for my use case, unlike something like RaptorQ, which leaks little details all over the place, driving up the complexity and rigidness of the rest of the stack. But Wirehair isn&#x27;t a spec, it&#x27;s an (experimental?) implementation of an idea. It seems stable, but unless&#x2F;until I try writing a second implementation, or it&#x27;s seen substantial use (exposing any sharp edges in the algorithm) I worry how easily it would translate to a reliable specification or second implementation.
评论 #41363192 未加载
stevefan19999 个月前
Yep, this is the key tech behind Ceph&#x27;s Erasure Code pool: <a href="https:&#x2F;&#x2F;docs.ceph.com&#x2F;en&#x2F;latest&#x2F;rados&#x2F;operations&#x2F;erasure-code&#x2F;" rel="nofollow">https:&#x2F;&#x2F;docs.ceph.com&#x2F;en&#x2F;latest&#x2F;rados&#x2F;operations&#x2F;erasure-cod...</a><p>This does not come without trade-offs though, you cannot update the coding parameters (k, m) afterwards, so you either have to be very sure that those parameters are going to work in a long time, or you have to start from scratch. This inelasticity is also the reason why replicas are still the dominant choice for HA fault tolerant data storage.
评论 #41364738 未加载
评论 #41364373 未加载
ggm9 个月前
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 &quot;needs to be re-encoded when the N is restored&quot; or else you have some files with less than stellar recovery for a random loss in the N set.
评论 #41363494 未加载
akww9 个月前
Reminds me also of Rabin’s Information Dispersal Algorithm, described in a paper here:<p><a href="https:&#x2F;&#x2F;dl.acm.org&#x2F;doi&#x2F;10.1145&#x2F;62044.62050" rel="nofollow">https:&#x2F;&#x2F;dl.acm.org&#x2F;doi&#x2F;10.1145&#x2F;62044.62050</a>
anonymousDan9 个月前
Is it the case that it&#x27;s really only practical for read-only or very read intensive workloads?
from-nibly9 个月前
This is one of the replication strategies that ceph uses for its distributed blob stores
nullc9 个月前
unfortunately modern cpus are still pretty sparse on tools to make erasure codes extremely fast. E.g. no vector clmuls.
评论 #41365551 未加载