[mnet-devel] Ickle me, pickle me, tickle me too...

[Zooko]

I just took a shower and thought about the issues with stale localblockstore 
indexes.

If there is an entry in the index which no longer exists in the store, then we 
can catch it by comparing the SHA-1 of the actual data found in the store.  
However, that is an expensive operation to perform every time you do a common 
operation like read_block(blockId) or even has_block(blockId)!

I was thinking we could do a fast CRC-32 for a check, and only if it matches 
do a full SHA-1, but just now I think there's an even better solution: the 
localblockstore could be required to have an unambiguous flag indicating 
whether a location is occupied, and deletion requires first unsetting that 
flag, then removing the index entry.  That way the common operations of 
has_block() and read_block() can simply check the flag and if it is unset, 
remove the index entry and return 'no block'.

Likewise on adding a block you first store the data in the location, then set 
the "occupied" flag, then add it to the index.


The converse problem of having a block absent from the index but present on 
the disk is trickier.  I agree with Jim's analysis that the worst that happens 
is a "localblockstore space leak" -- blocks that aren't marked in the index 
don't get used and never get deleted.  Also, those blocks disappear from the 
net.

One possible solution is to change the block replacement policy.  The block 
replacer could use the localblockstore itself rather than the index to find 
block to eject.  Here's one possible block replacer algorithm.  (Funny that 
writing actual Python code can be the shortest explanation.  Python is 
executable pseudo-code!)

class Replacer:
    def __init__(self):
        # in-memory-only list for the replacer to use
        self.replacertargets=[]

    def eject_a_block(self):
        while self.replacertargets < 128:
            blockdata = localblockstore.give_me_a_random_block()
            blockId = make_id(blockdata)
            if not localblockstore.has_block(blockId):
                # A-ha!  A leaked block.
                localblockstore.remove_block(blockId)
                return # done -- we've ejected a block
            self.replacertargets.append(blockId)

        # eject our least favorite block from these 128 randomly chosen blocks
        loser = choose_least_wanted_block(self.replacertargets)
        localblockstore.remove_block(loser)

        # give our favorite blocks a free pass out of death row
        for winner in choose_most_wanted_blocks(self.replacertargets)
            replacertargets.remove(winner)

        return # done -- we've ejected a block
        



-------------------------------------------------------
This SF.Net email sponsored by: Free pre-built ASP.NET sites including
Data Reports, E-commerce, Portals, and Forums are available now.
Download today and enter to win an XBOX or Visual Studio .NET.
http://aspnet.click-url.com/go/psa00100003ave/direct;at.aspnet_072303_01/01
_______________________________________________
mnet-devel mailing list
mnet-devel at lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mnet-devel