On Wednesday 07 Nov 2012 11:34:09 Matthew Toseland wrote: > On Tuesday 06 Nov 2012 21:58:49 Matthew Toseland wrote: > > On Tuesday 06 Nov 2012 20:38:32 xor wrote: > > > On Tuesday, November 06, 2012 05:24:20 PM Matthew Toseland wrote: > > > > However for forum posts, messages can be quite big especially if they > > > > quote > > > > lots of prior messages, or include lots of hints. So it may be better to > > > > have fairly big SSKs - 4KB or even 32KB? > > > > > > A Freetalk message list right now can only link to 5 messages when trying > > > to fit into the 1KiB SSK. This is clearly not enough. > > > > > > Sample XML files can be seen in the XML-Test sourcecode: > > > > > > https://github.com/freenet/plugin-Freetalk-staging/blob/master/test/plugins/Freetalk/WoT/WoTMessageListXMLTest.java > > > > So how many kB would be ideal? Obviously if it's very big that will slow > > things down... 2K or 4K we could probably send as a single message, much > > bigger than that and that gets problematic, although I'm guessing here. > > Also bigger means we are more likely to need to verify it *after we've > > transferred it all the way*, at least in the low latency case, which is > > troublesome too. If you're using bulk mode then I guess that's less > > important... > > > Hmmm, what would be easy in terms of avoiding new storage requirements, and > keeping similar network protocols: > - ~885 bytes: Slightly smaller than a current SSK, fits comfortably in one > packet and one datastore slot. (1120 bytes total inc headers/pubkey) > - ~32KB: Stick it in a CHK slot. > > If we want anything in between we likely need a new store. Allocating that on > existing users' nodes would be problematic. We can't get rid of the pubkey > store just yet. Using CHK slots to store smaller keys would be rather sad. > Subdividing them would be problematic as one CHK would evict many smaller > keys, and do we really want one smaller key to evict one CHK? > > It looks like this would be fine for FLIP. But FMS/Freetalk probably want > something medium sized, like 2KB or 4KB? > Storage problems for 2KB keys are *possible* to solve, and we get rid of the pubkey store at the same time:
High level goals: - COMBINE THE SSK AND PUBKEY STORES INTO A SINGLE STORE. - First by mapping the pubkeys into the same slots as SSKs, and then by combining the files into one. - Don't use any additional disk space in the conversion. - Result: In any slot, we can put either: An old SSK (1KB payload, headers, 1KB pubkey) A small new SSK (one packet / 1120 bytes inc pubkey and headers) A large new SSK (two packets, ~ 2KB inc pubkey and headers) DETAILS: - *Convert one SSK store at a time*. Memory requirements are slightly higher than normal, but if the other one isn't online, that's okay. - Create a bitmap for what pubkey slots are in use. - Create an integer array for the pubkey slot to be used by any given SSK slot. - Create an integer array for the pubkey slot containing the pubkey that was previously in the pubkey slot index. Initialise it to 0..N-1 - Go over the SSKs linearly, i = SSK slot: -- Look up the pubkey. If we can't find it, continue. -- Mark the slot as occupied in the pubkey slots bitmap. -- Mark the pubkey slot to use in the pubkeySlotForSSKSlot array. - Go over the SSKs linearly: sskSlot = current counter -- Check the pubkeySlotForSSKSlot array for the original slot used by the SSK. -- If there is nothing, that means the SSK isn't usable, clear it and continue. (The pubkey slot should already be marked as free) -- Look up the slot we just fetched in the pubkeySlotForOldPubkeySlot array. -- Fetch the pubkey from the slot specified. -- If the pubkey is not valid, something is wrong, probably data corruption. Log an error and continue, and free the slot. -- If sskSlot == the pubkey slot, we're done, continue. -- Read the old pubkey from the sskSlot (if the bitmap says it's not in use then we don't need to read and there is no pubkey). -- Write the new pubkey to sskSlot. -- If there is no pubkey in the sskSlot, continue, we're done. -- The old pubkey needs to be moved. -- Find a free slot to put the old pubkey in. -- If no free slots available, log and count an error. -- Write the old pubkey to the free slot. -- Record it in the pubkeySlotForOldPubkeySlot array. Now, how do we ensure that we don't lose too much data? - We need to free a slot when we allocate a slot. - The SSK pubkey gets written to the SSK slot. - The old pubkey gets moved to a new slot. - What happens to the pubkey we fetched for the SSK? -- We could mark it as free. -- The complication is it may be used by many keys. -- So we mark it as free, and update the pubkeySlotForOldPubkeySlot pointer (for the pubkey slot) to point to the sskSlot, where we can be confident that the pubkey will remain. - At this point, the pubkeys should all be ordered by the SSKs. Given the above, we should not lose more than one key. THIS MUST BE TESTED! - MAKE IT RESTARTABLE: Keep the pubkeySlotForOldPubkeySlot array on disk, i.e. use spare space in the slots to store it. On restarting, we first read the pubkeySlotForOldPubkeySlot array, which we then use in the first pass as an extra possible location for the pubkeys. Hence we should lose no data on a clean restart. THIS MUST BE TESTED TOO! - CAN WE DO THIS ONLINE? Memory may be an issue, and it's complicated ... may be best not to ... However it is certainly possible to do it online, if the extra memory and disk I/O isn't an issue; I don't think it makes sense to though. - DO WE WANT TO START UP THE NODE WITHOUT AN SSK/PUBKEY STORE? That might be bad ... but prolonged downtime might be bad too (e.g. for opennet) ... Maybe we want to do it staggered, one at a time (store then cache), offline, not necessarily on upgrade/startup? On the other hand on most nodes it will probably complete quickly. - At this point, everything is ordered by the SSK slots rather than the pubkeys. But it's still two files. It is usable as-is, but it'd be better to complete the transition first. - We mark the first stage as completed, by e.g. renaming the files. We no longer need the temporary bitmaps/int arrays. - We move a chunk at a time (1MB?) from the end of both the pubkey and SSK files, into a new file. We interlace them into a single entry per SSK, and order the entries backwards. We chop the original files after each copy operation, so as to use (roughly) fixed disk space. - The outcome is we have a single file with the SSK and pubkey in each slot, with ordering reversed relative to that which we previously used. - SaltedHashFreenetStore can now use this single file. A flag is set to invert the slot lookups, since it's "backwards".
signature.asc
Description: This is a digitally signed message part.
_______________________________________________ Devl mailing list Devl@freenetproject.org https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
