[Gluster-devel] Why vandermonde matrix is used in EC?

[Xavier Hernandez]

Hi Han,

On 11/24/2016 04:25 AM, 한우형 wrote:
> Hi,
>
> I'm working on dispersed volume(ec) and I found ec encode/decode
> algorithm is using non-systematic vandermonde matrix.
>
> My question is this: why non-systematic algorithm is used?

Non-systematic encoding/decoding doesn't alter performance when one or 
more bricks are down. This means that you won't have service degradation 
when you are having troubles with one brick or you are doing maintenance.

 From the implementation perspective, a systematic approach would need 
to talk to all bricks anyway to check for critical metadata (gluster 
doesn't have a centralized metadata server). This means that the 
theoretical benefit of a systematic decoding for reads would be masked 
by the overhead needed for metadata operations (involving additional 
network round-trips).

That said, it's true that a systematic approach would have some 
benefits, like a little less CPU overhead. Not sure if the performance 
would benefit significantly though.

> If we use
> systematic algorithm(not systematic vandermonde, It's not MDS)

A non-systematic Vandermonde matrix *IS* MDS. In fact, pure Vandermonde 
matrices are non-systematic by definition. Some alterations need to be 
done to make them systematic, and these transformations can lead to a 
non MDS matrix if not made with care.

> we can
> boost read performance. (no need to decode step in read)

Though it would probably have some benefits, I'm not so sure that 
performance would improve significantly.

Current implementation of ec decoding can process 1GB/s of data per CPU 
core on low end processors (Intel Atoms with SSE2) using block sizes of 
128KB and a 4+2 configuration. Currently this is much faster than what a 
pure distributed volume on same hardware can read for a single 
client/single thread.

So, for now, the non-systematic approach doesn't seem a bottle-neck for 
gluster. Anyway there are plans to provide a systematic version, but 
it's not a priority as of now.

Best regards,

Xavi

>
> Best regards,
> Han
>
>
>
> _______________________________________________
> Gluster-devel mailing list
> Gluster-devel at gluster.org
> http://www.gluster.org/mailman/listinfo/gluster-devel
>