This is somewhat long and mathy. If it's not explained well, please ask! Executive summary: by using better encoding schemes than our present splitfile segmentation, we can dramatically improve splitfile success rates in a variety of situations, while keeping the same basic FEC code and 2x redundancy rate.
Introduction Our current splitfile scheme has a number of problems when it comes to data retention. On some files (mostly large ones) the success rates for the whole file will be low, despite a reasonably large fraction of the blocks being available. There are a variety of ways we can improve this (without increasing the number of check blocks); the most promising is a two-layered interleaved scheme similar to that used by CDs (CIRC). I've written a monte-carlo simulator to give expected success rates for a file based on file size, encoding scheme, and block-level success rate. This entire email is concerned with problems that happen at the bottom (data) layer of the splitfile only. Problems that stem from top blocks and upper layers and such are not addressed. (In other words: everything here assumes that all of the non-data layers have already been successfully downloaded.) Splitfiles as they are now Freenet splitfiles have 2x redundancy. A number of check blocks are created for each file, equal in number to the data blocks. If we had a theoretically perfect coding scheme, to download a file with n data blocks, any combination of n data and check blocks would suffice. For large files, that presents practical problems. The solution is segmented splitfiles. We group up to 128 data blocks together, and then use a Reed-Solomon code to generate an equal number of check blocks to make up a segment of up to 256 blocks total. (Since we use 32 KiB blocks, each segment is up to 4 MiB of data, or 8 MiB total.) The result is that each segment is independent: if one segment fails to download, there is no way to recover from that. This is the first cause of problems. A file with many segments, that has had a moderate number of blocks drop off the network, can have a low probability of success despite having plenty of blocks available. As the number of segments gets large, it becomes likely that somewhere the failed blocks will clump into one segment enough to make it fail. For example, if each individual block succeeds with probability p=0.58, then a single segment will succeed with p=0.99588, which is fairly good. But, by four segments, the file success rate has dropped to 0.984, and by 8 to 0.967. 3.3% failure isn't that high, but we've only reached a 32 MiB file. For a 700 MiB file, it's down to only a 48% chance of success. Even at block success rate of 0.60 (segment success rate of 0.99951), the file success rate is only 92%. As the file size gets larger, we require a steadily higher block success rate to achieve high reliability. The second cause of problems is that we don't split the segments up evenly. In the worst case, a file with 129 data blocks becomes two segments, one of 128 data + 128 check blocks, and one with 1 data and 1 check blocks. I've made some diagrams of this. For clarity, the diagrams are drawn with a maximum of only 16 blocks per segment. Here's how a splitfile with 34 blocks would look with such segments: http://www.miranda.org/~evand/freenet/single_layer_1.svg Simple improvements The second problem is obviously much easier to solve than the first. We simply split the blocks evenly amongst the segments. Here's the analogous diagram: http://www.miranda.org/~evand/freenet/single_layer_2.svg This significantly improves retrievability, in the case of files that have only slightly more than a multiple of 128 data blocks, because larger segments are more reliable than smaller ones at the same success rate. In fact, this effect is strong enough (when combined with segments being independent) that in some cases it is advantageous to use slightly lower redundancy in order to reduce the segment count. For example, at p=0.6, for a file with 134 data blocks, the two-segment splitfile (67 + 67 blocks in each segment) will fail 1.5% of the time. But, if it is instead encoded as a single larger segment with reduced total redundancy (that is, 134 data and 122 check blocks) the failure rate falls to only 0.5% -- it's three times less likely to fail, despite using up 5% less storage space. See https://bugs.freenetproject.org/view.php?id=2931 for some more discussion and lots of numbers. Multi-layer interleaving For large files, there are more sophisticated techniques than our simple segments, that don't require larger encoding groups (and associated increase in memory usage and disk seeks). Roughly speaking, the odds are very, very good that most segments can fetch at least one more block than is strictly required (ie 129 of 256 instead of only 128 of 256). At the same time, the odds are also high that *some* segment won't be able to fetch the required 128 blocks. So, we do a two-layer scheme: outer segments that require 129 blocks to decode, and then those groups of 129 blocks are regrouped into a second layer of segments that have 128 data blocks and 1 check block. That means that if one outer segment gets very unlucky, but the others can download 129 blocks, then all the missing blocks from the one outer segment are dispersed, each showing up as the only missing block in some inner segment. Again, a diagram to illustrate. With 16-block segments, and 40 data blocks (5 full segments of 8+8), our current single-layer scheme looks like this: http://www.miranda.org/~evand/freenet/single_layer.svg The two layer scheme keeps the same total number of check blocks, but instead computes some of them from the inner segments: http://www.miranda.org/~evand/freenet/double_layer.svg (In this diagram, outer segments require 9 of 16 blocks to decode, and inner segments require 8 of 9. Again, these diagrams are merely intended to illustrate. The file shown is actually small enough that the single-layer scheme performs better. It's only as the files get large that the double-layer scheme becomes important.) Returning to our hypothetical 700 MiB file (22400 blocks in 175 segments by the current scheme), with a block success rate of 0.6 we have a file success rate of only 92%: it fails about 1 in 12 times. If instead we encode it as 175 outer segments (with 129 of 256 blocks required), and a second interleaved layer of 175 inner segments (with 128 of 129 blocks required), the success rate was 1000 out of 1000 monte-carlo runs: a perfect record. Even at the lower p=0.58 (where over half of simple segmented files fail) the double-layer success rate is still 1000/1000. At p=0.56, where the simple segmented file only succeeds 1.64% of the time, the double-layered structure manages a success rate of 978/1000. There is some more discussion of this at https://bugs.freenetproject.org/view.php?id=3370 . I'll be adding an update there with more numbers soon. Proposal We should make several changes. The problems and solutions are different for very small, medium, and large files. First, for very tiny files, achieving reasonable success rates simply requires more check blocks (on single-segment files, our coding is already perfect). I somewhat arbitrarily propose that all splitfiles with less than 8 data blocks be given 1 additional check block. So, a file with 3 data blocks is given 4 check blocks, for 7 total blocks. With 7 data blocks, it gets 8 check blocks. At 8 or more we use our usual 2x redundancy. For files of moderate size, we keep our current segmenting system, but with modifications. First, the segments should always be the same size (some having 1 more data and 1 more check block when the data blocks don't divide evenly). Additionally, splitfiles of up to 136 data blocks should use only one segment. Splitfiles up to 266 blocks should be two segments, up to 393 should be 3 segments, up to 520 blocks should be 4 segments. Beyond that, the differences between different split points become rather small; simply splitting to limit the maximum segment size to 128 data blocks is fine. For files of 20 segments (80 MiB) or more, we move to the double-layered interleaved scheme. I'm working on the interleaving code still (it isn't optimal for all numbers of data blocks yet). The simple segmenting scheme is better for smaller files, and the interleaved scheme for large ones. At 18 segments, the segmentation does better. By 20 segments, the interleaved code is slightly better. By 25 segments, the difference is approaching a 1.5x reduction in failure rates. (Details depend on block success rate. I'll post them on the bug report shortly.) Evan Daniel
