search

klauspost / reedsolomon

Reed-Solomon Erasure Coding in Go
MIT License
1.86k stars 244 forks source link

matrix is singular error #16

Closed hedwigz closed 8 years ago

hedwigz commented 8 years ago

Hi, I am using the example's files to test the code. When I take a 100MB file with 250 data shards and 125 pairity shards and then delete shards 0-49 and 270-279 reconstruction fails with matrix is singular error. Is this suppose to happen? Cause I thought I can lose up to 125 shards and still recover the data. What am I missing? Thanks, Amit

hedwigz commented 8 years ago

Also happens for random 40kb buffer and some other files. For fewer pairity/shards (e.g 50/20) error doesn't occur. Is the likelihood of singularity rises when the size of the matrix rises?

xiaost commented 8 years ago

it seems the rows/cols idx exceeds byte len when generating Vandermonde matrix within Galois Field

https://github.com/klauspost/reedsolomon/blob/master/matrix.go#L271

klauspost commented 8 years ago

It would seem that to be safe from this the number of data+parity shards should not exceed 255.

I did some tests, which only seemed to fail if the number of data shards where >255, but it seems like there is another limitation that kicks in when reconstructing.

hedwigz commented 8 years ago

Hi, Thanks for the answer. I think I missed the point of how to avoid this or that maybe it's a bug? Are you saying that shards+parity cannot excced 255? Cause I didn't infer that from the documentation. (And also there's no error for those dimensions) Sorry for my lack of understanding. On Apr 10, 2016 21:30, "Klaus Post" notifications@github.com wrote:

It would seem that to be safe from this the number of data+parity shards should not exceed 255.

I did some tests, which only seemed to fail if the number of data shards where >255, but it seems like there is another limitation that kicks in when reconstructing.

— You are receiving this because you authored the thread. Reply to this email directly or view it on GitHub https://github.com/klauspost/reedsolomon/issues/16#issuecomment-208041209

klauspost commented 8 years ago

Are you saying that shards+parity cannot excced 255?

That would be my recommendation. I will do some more tests, but for now, I would stick to that.

hedwigz commented 8 years ago

Thank you very much On Apr 10, 2016 21:50, "Klaus Post" notifications@github.com wrote:

Are you saying that shards+parity cannot excced 255?

That would be my recommendation. I will do some more tests, but for now, I would stick to that.

— You are receiving this because you authored the thread. Reply to this email directly or view it on GitHub https://github.com/klauspost/reedsolomon/issues/16#issuecomment-208042959

harshavardhana commented 8 years ago

AFAIK - (k + m) cannot be bigger than Galois field GF(2^8) - 1

hedwigz commented 8 years ago

ok so shouldn't we add a check at the constructor?

klauspost commented 8 years ago

That would make sense, yes - as well as updating the documentation