[mnet-devel] FEC parameters, backwards compatibility

[Jim McCoy]

Zooko wrote:
> Someone asked on IRC [1] if the GF(2^16) mode of Rizzo's FEC was a 
> good choice.
>
> First of all, I question whether a large number of erasure code shares 
> actually
> makes any difference.  It probably makes no difference to file 
> robustness.

I was the person who brought up the issue, and I think that it does 
have several different impacts, which I will outline.

The first issue is that you need to remember how the datastore is 
organized.  If you have a (400, 1600) scheme and a (4, 16) scheme with 
100 replicas out there you are going to find different characteristics 
given different sizes of networks. How long is a file expected to stick 
around?  Be sure to consider network growth here.  If I encode a file 
with (4,16) and push out 100 replicas (assuming there are that many 
hosts with that much overlap) then it will probably be fine for the 
moment.  But when the network grows larger or more data gets pushed 
into the storage mesh you are going to see different reliability for 
each file, the massive replica model assumes that you can try to 
influence the number or replicas kept by peers over time (which is not 
a valid assumption to make) while the large number of shares has a 
better reliability over the long term. A (4,16) file will fade into 
non-existence if the system becomes more than a research toy, while a 
400,1600) file can still maintain good long term viability. Keep the 
amount of guesswork on the part of the user low, don't force them to 
trust you when it comes to the long-term growth characteristics of the 
network.

> So I intend to do *both* GF(2^8) and GF(2^16), where we use the 
> fastest one of
> the two that is big enough to handle the current file.

Why bother with two encoding schemes?  The different between using 
GF(8) and GF(16) is that the former's math tables can be kept in memory 
while the latter will require more CPU time for encoding and decoding 
because it has to do a bit more math.  By all accounts, this is a 3-4x 
difference which is almost completely insignificant for this 
application.  The reason that GF(8) is used in preference for 
swarmcast/ocn and Freenet is that they are stuck with Java as a back 
end.  This has been noted as causing a _significant_ (almost 100x) 
slowdown for this application when run in the JavaVM compared to native 
C code, which makes the increased slowdown for using GF(16) a bit 
noticable.

The major practical difference between using GF(8) and GF(16) is that 
in the former you get to have a max of 256 shares, while the latter 
gives you up to 65536 shares.  This is a major difference, particularly 
when we are talking about large files. With GF(16) as the standard you 
have the option of using a lot of shares, but are not required to do 
so.  Win-win.

> My envisioned parameters
> make it so that "Zooko's decentralized filestore format" can handle 20 
> GB files
> before running out of FEC GF() space.  When this limit begins to 
> chafe, I might
> add support for GF(2^32).

Be prepared for a serious math hit for GF(32) unless we are running on 
64-bit machines as the standard, there is some serious matrix work 
involved with this option. GF(16) with 256K shares gets you close to 
16GB files, by upping the share size to 512K you are supporting some 
truly massive files. To those who would suggest that we need to be able 
to eventually support X GB files, think about how long it will take 
someone to upload or download this file -- by the time that sort of 
practical bandwidth is available it will be trivial to have 1M or 
larger share sized.

> Another topic I saw on IRC was backwards compatibility.  I'm pretty 
> sure we can
> achieve smooth backwards compatibility by denoting the version 
> somewhere early
> in the metadata.  I've worked out concrete formats that include this 
> feature.

Care to share them?  I am not sure that I see any benefit to backwards 
compatibility here given the fact that there is not too much that will 
be lost and the system reliability gain is rather significant. It is 
still easy to keep most of the original structure, just running a 
series of pieces that are a sequence in a single chunk (e.g. eliminate 
the chunk, just have pieces of the file listed in the sharemap.)  
Because the Vandermonde FEC is a structured erasure code, the first K 
shares are sequential parts of the original file which means that it is 
a win if you can get those K shares when you are downloading (no need 
to perform the error correction math).

I guess that I would suggest that "Jim's decentralized file format" is 
a short hop from the current one, with the downside being that it just 
burns the existing datastore for the sake of simplicity.  The 
encoder/decoder and the options associated with it remain simple (there 
are already too many tweak options available, let's limit a few) but it 
provides the sort of future  expansion that you want without the 
downside of trying to be too clever. It also means that you can abandon 
the old blockshares code and its associated cruft.

Jim



-------------------------------------------------------
This SF.NET email is sponsored by:
SourceForge Enterprise Edition + IBM + LinuxWorld = Something 2 See!
http://www.vasoftware.com
_______________________________________________
mnet-devel mailing list
mnet-devel at lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mnet-devel