On Thursday 20 August 2009 18:40:26 Evan Daniel wrote: > On Thu, Aug 20, 2009 at 12:55 PM, Matthew > Toseland<toad at amphibian.dyndns.org> wrote: > > I have CC'ed devl. > > > > On Saturday 15 August 2009 04:39:13 Evan Daniel wrote: > >> On Fri, Aug 14, 2009 at 2:36 PM, Matthew > >> Toseland<toad at amphibian.dyndns.org> wrote: > >> > On Tuesday 11 August 2009 19:19:51 Evan Daniel wrote: > >> >> On Tue, Aug 11, 2009 at 9:37 AM, Matthew > >> >> Toseland<toad at amphibian.dyndns.org> wrote: > >> >> > On Sunday 09 August 2009 06:17:13 Evan Daniel wrote: > >> >> >> On Sat, Aug 8, 2009 at 9:06 PM, Matthew > >> >> >> Toseland<toad at amphibian.dyndns.org> wrote: > >> >> >> > On Thursday 06 August 2009 22:07:49 Evan Daniel wrote: > >> >> >> >> On Thu, Aug 6, 2009 at 3:27 PM, Matthew > >> >> >> >> Toseland<toad at amphibian.dyndns.org> wrote: > >> >> >> >> >> - A few specific bugs: 3295 (percent encoding is horribly, > >> >> >> >> >> embarrassingly broken -- in at least 5 different ways), 2931 > >> >> >> >> >> (split > >> >> >> >> >> blocks evenly between splitfile segments -- should help > >> >> >> >> >> dramatically > >> >> >> >> >> with availability), fixing top block healing on splitfiles > >> >> >> >> >> (discussed > >> >> >> >> >> in 3358). > >> >> >> >> > > >> >> >> >> > Skeptical on priority re 3295, but I guess I should look into > >> >> >> >> > it. IMHO it is critical that the top block be redundant, hence > >> >> >> >> > MHKs. Dunno re relative priority with f2f web proxy though. > >> >> >> >> > >> >> >> >> I've said this before, but not yet heard a specific response, so > >> >> >> >> I'll > >> >> >> >> repeat it. ?On both the initial insert and later downloads we > >> >> >> >> expend > >> >> >> >> more effort on the redundant information than the non-redundant > >> >> >> >> information; this is silly and should be fixed, whether or not we > >> >> >> >> implement MHKs. ?We don't know how big a problem non-redundant top > >> >> >> >> blocks would be if we fixed this discrepancy. ?It would be > >> >> >> >> premature > >> >> >> >> to implement a new keytype before we knew whether that change > >> >> >> >> plus a > >> >> >> >> more aggressive insert on the initial insert solved the problem > >> >> >> >> completely, partially, or not at all (my personal bet would be on > >> >> >> >> "almost but not quite completely"). ?Deciding to implement MHKs > >> >> >> >> without being able to answer this question would be pure alchemy. > >> >> >> > > >> >> >> > Everything below is redundant. Non-redundant blocks are likely to > >> >> >> > be on 3 nodes' datastores and that's it, after a reasonable > >> >> >> > period. And some of those 3 nodes will be offline. IMHO that is > >> >> >> > enough reason by itself. > >> >> >> > > >> >> >> > >> >> >> (Was this intended to be off-list? ?I've left my reply off-list, but > >> >> >> have no objection to either.) > >> >> >> > >> >> >> At present, we selectively apply *less* healing to the > >> >> >> *non-redundant* > >> >> >> data. ?Do you believe this is the right way to do things, and if so, > >> >> >> why? > >> >> > > >> >> > Yes, because that is how healing works. We have just fetched the > >> >> > data, why reinsert it? We only ever reinsert stuff that we know does > >> >> > not exist - that we have tried to fetch and failed. > >> >> > >> >> The current healing policy does not only heal things that "don't > >> >> exist". ?It heals things that were harder to fetch. > >> > > >> > Right. > >> > > >> >> Most fetches for > >> >> old or hard to find data take several attempts. ?For a splitfile, some > >> >> of the data blocks fetch before others, purely by luck. ?Suppose we > >> >> send repeated requests for the top block, and on the 20th retry we > >> >> find it. ?Then, on the data blocks, we start trying, and some blocks > >> >> come in quickly, but most fail at least once. ?Eventually we collect > >> >> all the data, with the last blocks coming in on the fifth retry, and > >> >> some of the missing blocks having 4 failed fetches and some 5. ?Making > >> >> some assumptions about randomness and the distribution of retries and > >> >> such, our best estimate is that the remaining blocks would have taken > >> >> another 4-5 retries to find, on average, for a total of 8-10 tries. > >> >> That suggests that they would be easier to find than the top block was > >> >> (at 20 retries). ?The behavior of the current code amounts to > >> >> concluding that, despite the fact that the top block was harder to > >> >> find, the redundant data is in greater need of healing. ?The act of > >> >> fetching the top block spread it to a few extra caches; the same is > >> >> true of the successfully fetched data blocks. ?However, the healing > >> >> reinserts spread the data to extra *stores*, which are longer lived > >> >> (and on average the insert gets cached more places than the fetch, > >> >> since the average successful fetch doesn't use up its htl). > >> > > >> > Okay so your theory is because it took a long time to fetch the top > >> > block, it is in the wrong place, and would therefore benefit > >> > significantly from reinsertion - more than a random key does. This makes > >> > sense. > >> > >> In the wrong place, or not common enough, or... > > > > "Not common enough" is bogus. It shouldn't need to be common. In the long > > term every key is stored on 3 stores and no caches, and this should be > > enough. It isn't enough for top blocks because of uptime issues... > > If nodes aren't up all the time, have backoff, don't get routed to > because of transient topology effects from connection churn, etc, then > we want the block to be on several nodes. It could be on a perfectly > reasonable node but still temporarily unavailable due to such effects; > imho that represents a block that is "not common enough" on the > network. > > Can routing really find *the* correct node on a reasonably large > network? Do you have simulation data that suggests it can?
"not common enough" = we need 1% of the network to cache it so we will always be able to find it. This assumes that routing and storage is hopelessly broken and in doing so makes the situation worse. > > My limited empirical data says otherwise. I have a file that was > inserted long ago and has mostly disappeared. It's been sitting in my > download queue for months. When I first started downloading it, it > had 30 or so blocks. After several days, it was in the 40s. Now it > has 79; it seems to still be finding blocks, though only very, very > slowly. I think that blocks in hard to find places is a more likely > explanation than ancient nodes returning to the network with the > blocks in their stores. Why does this happen now? When we were swapping on opennet, stuff would end up in the wrong place because node locations changed. But now locations don't change. So what are we left with? Inserts that never reached the ideal cluster, and inserts that did reach it, but the sink nodes have gone offline. So we find the data from the wrong place, in somebody's cache, or in one of the earlier sinks, by means of repeatedly hammering at it. Whereas if we duplicate it in the first place, there's a good chance that a node with a location close to the key's will still be online and findable. > > >> >> Currently, we only heal data blocks that are "hard" to find, defined > >> >> as those we didn't find on the first attempt. ?Similarly, I don't > >> >> think we should always heal the top block -- merely heal it if it was > >> >> hard to find, for some appropriate definition of hard (failed at least > >> >> n times); I don't know how to define the exact healing rate without > >> >> alchemy involved, but the healing rate parameters already have a fair > >> >> bit of that already. ?I suggest n = 3, without any particular > >> >> rationale beyond it feels about right. > >> > > >> > And you want to heal it after the rest of the splitfile completes? This > >> > requires that we store the block, especially if it's an SSK. Nonetheless > >> > it seems a reasonable idea, file a bug. > >> > >> I think we should heal it immediately on download (if it took at least > >> a certain number of retries), regardless of whether the whole file > >> completes. ?(That's what we do for the higher levels of a multi-layer > >> splitfile, right? ?Conceptually a top block is the same, it's a higher > >> level out of several, it's just one block instead of many.) > > > > We add to the healing queue after a segment completes. If we heal the top > > block immediately, won't it go back to where it was? > > Only if we insert from the same place as the original inserter, right? > If we start an insert and a request on two nodes in different > portions of the network, presumably they travel some distance before > intersecting. Any sinks along the reinsert path (presumed to be the > same as the request path, though in practice it won't be, due to > pInstantReject and backoff, even if the topology hasn't changed) > before the intersection are new stores the block goes to. Also, if > the original insert was old, and two of the three nodes with the block > in their stores have left the network, then it will find new stores. Right, but again we are using 0.5 logic, assuming the system is broken and making it worse by doing so. The sinks which are not common with the original sinks, or at least close to the original sinks location-wise, are far from where the data should be, and will not be findable except by nodes close to the inserter. > > >> >> >> I believe this is a bug, not a feature. ?Furthermore, in the > >> >> >> case of freesites, the problem applies to both the SSK redirect and > >> >> >> the CHK top block of the splitfile, but the MHK solution does not > >> >> >> address the SSK problem. > >> >> > > >> >> > SSKs are a problem yes, but freesites are more popular. Also, > >> >> > redundant SSK top blocks are probably easier than redundant CHK top > >> >> > blocks. > >> >> > >> >> I think the actual difference has more to do with the relative number > >> >> of SSK vs CHK blocks on the network. ?(What's the ratio? I don't know. > >> >> ?See bugs 3291 and 3347.) ?For example, try retrieving the old > >> >> auto-update jars. ?I picked a few at random from build 1150 to > >> >> present. ?On *all* of them, the SSK block returned almost immediately, > >> >> and the top CHK block took some time (several retries; several still > >> >> haven't been found after many hours). ?So perhaps we don't need MHKs > >> >> for SSK keys, simply because they have a much longer lifespan. > >> > > >> > Which suggests filesharers might do better by using SSKs. Unfortunately > >> > they love the reinsertion thing way too much. > >> > >> Reinserting to an SSK shouldn't be hard as long as the SSK block is > >> fetchable; the CHKs don't need to be. ?If the SSK isn't fetchable, > >> we'd need a stored binary blob, which is awkward from a UI standpoint > >> if nothing else. ?My testing suggests that the SSK being fetchable but > >> the file needing a reinsert is likely the norm. > > > > Right, unless we change the convergence behaviour, they can just reinsert > > to a CHK and it should make the SSK work, unless the file is very old. Thus the problem here is UI. > >> > >> >> If that's the case, we could consider instead the changes I propose in > >> >> 3359 / 3371 (combined with a recommendation that client apps insert > >> >> uploaded files to SSK keys, with the SSK keypair used for many files > >> >> or only one, as appropriate). ?If SSKs are really that much > >> >> longer-lived, they would provide a more reliable solution the > >> >> multiple-CHK style MHKs. > >> > > >> > 3359: this is a bug, unless a MIME type has been set. We can fix it even > >> > when there is a MIME type by making ?type= a proper part of FreenetURI's. > >> > >> My point with 3359 is that this is a good idea even if the MIME type > >> has been set, and even for manifests etc. ?Ideally it would be > >> combined with some other changes, and the SSK block would just hold > >> splitfile metadata for a layer with 15 data + 15 check blocks, and the > >> MIME type and manifest and such would be in a redundant layer to leave > >> the most space in the SSK block so the top splitfile layer would be as > >> large as possible. > > > > Yes, and I was under the impression that we already put the splitfile > > metadata in the top SSK block if it fits. If we don't that is definitely a > > bug. Not sure what you're talking about with manifests - if it's a normal > > manifest the data should go in the top block, if it's a container then the > > splitfile for the container should go in the top block. > > I'll check this. > > >> > 3371 is a good idea but probably less urgent - is it the *top block* or > >> > the *top metadata splitfile* (multiple blocks) which is more common? > >> > >> I'm not quite sure what you're asking here. > > > > Me neither. > >> > >> >> >> Assuming you intend to address the lack of > >> >> >> healing issue (which I hope you do, entirely independent of MHKs), is > >> >> >> there harm in trying it and seeing whether it fixes the problem > >> >> >> partially, completely, or not at all before making a decision to add > >> >> >> a > >> >> >> new keytype (which I'd guess would be more work for you, and know > >> >> >> would be more work for client apps)? > >> >> > > >> >> > I would be amazed if it made any significant difference. > >> >> > >> >> I wouldn't. ?Try downloading some old but popular files like the > >> >> autoupdate jars. ?The top blocks take forever to find, but the data > >> >> blocks come in reasonably rapidly after that. ?The only thing I can > >> >> think of to attribute this to is the splitfile healing algorithm. > >> > > >> > I attribute it to the top block being stored on 3 nodes and all of them > >> > being offline. > >> > >> Whatever the exact reason, the data blocks are individually more fetchable. > >> > >> If you do an initial insert, the block lands in 3 stores. ?If you > >> reinsert from a random different node on the network, presumably it > >> lands in 3 stores that time as well. ?How much overlap is there? ?I > >> suspect that after the reinsert, it is on average in 4-5 stores, not > >> 3. ?That is, I suspect that the second set of 3 stores is not > >> precisely the same, even if all nodes are still online. ?So healing > >> the same top block from different points on the network would help > >> availability. > > > > Maybe but that's a kludge. In the long term it will only be on the most > > specialised nodes for that key. Of which there may only be one. Our > > objective is to maximise the long term retrievability of as large a set of > > data as possible, no? Even if they are not requested for a while? > > How is storing in more stores under the same key any more or less of a > kludge than storing under more stores with different keys? Why is it > more of a kludge to do it for top blocks than for redundant blocks? Because each of the redundant blocks will be stored on 3 sinks, one of which (typically) will be close enough to the target location to be findable by anywhere on the network. Thus after a long period, we have 1 globally findable sink for current CHKs, or we have 3 with MHKs. Right now, when we get to this point (data only in stores), Freenet generally can't find the data, at least not quickly and for top blocks. But hopefully we can improve on that. Caches do tend to be somewhat specialised, so maybe I am oversimplifying - but they also have a lot faster turnover rate, and a lot more duplication of very popular content, so I am not convinced. > > >> >> My guess (more a hunch than anything backed by evidence) is that MHKs > >> >> would be *more* reliable, but that changing the healing algorithm > >> >> could capture most of the available benefit. ?Making MHKs so reliable > >> >> that the normal failure more for old files is that the MHK top blocks > >> >> work and the data blocks don't would in practice be no better than > >> >> merely making the top block somewhat more reliable than the data > >> >> blocks. > >> >> > >> >> Fundamentally, MHKs are an attempt to get more copies of the top block > >> >> out on the network. ?I think we need to do that. ?Changing the healing > >> >> algorithm does the same thing. ?I don't know whether it would help to > >> >> have those copies in different parts of the keyspace; I suspect it > >> >> doesn't matter more than a tiny bit either way. ?MHKs might be > >> >> slightly more reliable, but I think improved healing policy changes > >> >> could be reliable enough that the limiting factor was data block > >> >> retrieval rather than top blocks. ?If I'm right about that, I think it > >> >> is kinder to users and client app developers to avoid adding a new > >> >> keytype, especially one that's even longer than the current keys > >> >> (though that's a fairly minor issue). > >> > > >> > MHKs would be significantly more reliable IMHO, because there would be > >> > more copies on the network, in stores as opposed to caches, over the > >> > long term. However your proposal may also be worthwhile - if there is a > >> > single top block it might be worth reinserting it. > >> > >> My objection to MHKs is that 1) I think the changes I've suggested wrt > >> top block healing are important, and will help the problem to some > >> unknown but significant degree, and 2) until we test said changes, all > >> our arguments either way about MHKs are based on hunches and > >> intuition, not empirical data or even simulation data. ?That is, I > >> think it's premature to implement MHKs before addressing the top block > >> healing issue and gathering data on what happens as best we're able. > >> My hunch is that we won't need MHKs, but that's only a hunch; it will > >> be shown to be correct or not only when we have data about how big the > >> problem is after fix the top block healing issue. > > > > Okay so go implement top block healing. When the top block comes in, over > > some threshold, start a transient insert with the > > freenet.node.SimpleSendableInsert. > > OK, I'll look into it. Great. > > >> I note that the natural way to implement MHK healing (if unable to > >> download some of the top blocks, but we eventually get one, reinsert > >> some / all of the others, ie exactly analogous to current splitfile > >> healing) would have the consequence of changing the top block healing > >> rate in line with my suggestions above. ?Good scientific practice is > >> to change one thing at once; implementing MHKs without first changing > >> the healing policy would make both changes at the same time, making it > >> impossible to tell which one fixed the problem. > > > > How do you propose to track what the impact is? At the moment we don't have > > any published results for retrievability. I could run them here ... how > > important is this? > > I think having some sort of data gathering mechanism is a prerequisite > to these changes. At present, the best suggestion I have is to look > at reports on Frost / FMS of how often reinserts are needed on files > because the top block is unavailable. Data for this would take some > sophistication to collect reliably; we would need to insert a file, > and then download it repeatedly from different nodes with increasing > intervals between downloads, or something similar. (The healing > effects, whether due to changes in top block policy or MHKs, aren't > going to be visible if it doesn't get downloaded several times.) sdiz's automated tests (with 2^n days for 0 to 8) are running here since yesterday, I am not 100% sure they are working yet but they should be of interest. > > Evan Daniel -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 835 bytes Desc: This is a digitally signed message part. URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20090826/caf26793/attachment.pgp>
