On Wed, May 28, 2008 at 7:04 PM, Matthew Toseland
<toad at amphibian.dyndns.org> wrote:
> On Wednesday 28 May 2008 01:22, Daniel Cheng wrote:
>> On 5/28/08, Matthew Toseland <toad at amphibian.dyndns.org> wrote:
>> > On Sunday 25 May 2008 12:46, Daniel Cheng wrote:
>> > > On Sat, May 24, 2008 at 7:40 AM, Matthew Toseland
>> > > <toad at amphibian.dyndns.org> wrote:
>> > > > On Friday 23 May 2008 15:20, j16sdiz at freenetproject.org wrote:
>> > > >> Author: j16sdiz
>> > > >> Date: 2008-05-23 14:20:31 +0000 (Fri, 23 May 2008)
>> > > >> New Revision: 20061
>> > > >>
>> > > >> Modified:
>> > > >>
>> > > >
>> >
> branches/saltedhashstore/freenet/src/freenet/store/SaltedHashFreenetStore.java
>> > > >> Log:
>> > > >> use bloom filter
>> > > >
>> > > > Can we be 100% sure of not adding the same key twice? The write code
> takes
>> > a
>> > > > lock, then checks every place it could be, then writes it, and updates
> the
>> > > > bloom filter, so we should never add the same key twice, right?
>> > > >
>> > >
>> > > Unless two threads trying to put the same entry at the same time.
>> >
>> > Locking...
>>
>> In the current implementation, the lock is not held long enough to
>> prevent this. Updating the bloom filter is slow, as it always fsync()
>> after each update. I don't think holding a lock that long is a good
>> idea.
>
> Can't you do the fsync outside the lock?
That's what we are doing:
1 check if the store already exist
2 write to bloom filter
3 fsync
4 write the store
If we want to prevent writing the bloom filter twice for the same key,
the lock have to be held until the block is written to the store.
If we swap step 3 and 4, there may be false negative if it crash in between
>>
>> > > > Is it possible to calculate how often we will need to regenerate the
>> > filter?
>> > > > We will need to do that in the background, and obviously turn off
> lookups
>> > > > during that period...
>> > >
>> > >
>> > > We can do this by keeping some statistics on false positives.
>> > > This is on my (private) todo list.
>> >
>> > Anything important could/should go to the bug tracker...
>> > >
>> > > >> Modified:
>> > > >
>> >
> branches/saltedhashstore/freenet/src/freenet/store/SaltedHashFreenetStore.java
>> > > >> ===================================================================
>> > > >> ---
>> > > >
>> >
> branches/saltedhashstore/freenet/src/freenet/store/SaltedHashFreenetStore.java
>> > > > 2008-05-23 14:20:21 UTC (rev 20060)
>> > > >> +++
>> > > >
>> >
> branches/saltedhashstore/freenet/src/freenet/store/SaltedHashFreenetStore.java
>> > > > 2008-05-23 14:20:31 UTC (rev 20061)
>> > > >> @@ -23,6 +23,7 @@
>> > > >> import freenet.crypt.ciphers.Rijndael;
>> > > >> import freenet.keys.KeyVerifyException;
>> > > >> import freenet.node.SemiOrderedShutdownHook;
>> > > >> +import freenet.support.BloomFilter;
>> > > >> import freenet.support.Fields;
>> > > >> import freenet.support.HexUtil;
>> > > >> import freenet.support.Logger;
>> > > >> @@ -39,6 +40,10 @@
>> > > >> private static final boolean OPTION_SAVE_PLAINKEY = true;
>> > > >> private static final int OPTION_MAX_PROBE = 4;
>> > > >>
>> > > >> + private static final boolean updateBloom = true;
>> > > >> + private static final boolean checkBloom = true;
>> > > >> + private BloomFilter bloomFilter;
>> > > >> +
>> > > >> private static final boolean logLOCK = false;
>> > > >> private static boolean logMINOR;
>> > > >> private static boolean logDEBUG;
>> > > >> @@ -88,6 +93,9 @@
>> > > >> loadConfigFile();
>> > > >>
>> > > >> openStoreFiles(baseDir, name);
>> > > >> +
>> > > >> + if (updateBloom || checkBloom)
>> > > >> + bloomFilter = new BloomFilter(new
>> > File(this.baseDir, name + ".bloom"),
>> > > > 0x100000, 5);
>> > > >>
>> > > >> callback.setStore(this);
>> > > >> shutdownHook.addEarlyJob(new Thread(new ShutdownDB()));
>> > > >> @@ -99,7 +107,7 @@
>> > > >> public StorableBlock fetch(byte[] routingKey, byte[] fullKey,
>> > boolean
>> > > > dontPromote) throws IOException {
>> > > >> if (logMINOR)
>> > > >> Logger.minor(this, "Fetch " +
>> > HexUtil.bytesToHex(routingKey) + " for " +
>> > > > callback);
>> > > >> -
>> > > >> +
>> > > >> Entry entry = probeEntry(routingKey);
>> > > >>
>> > > >> if (entry == null) {
>> > > >> @@ -112,6 +120,8 @@
>> > > >> try {
>> > > >> StorableBlock block =
>> > entry.getStorableBlock(routingKey, fullKey);
>> > > >> incHits();
>> > > >> + if (updateBloom && !checkBloom)
>> > > >> + bloomFilter.updateFilter(routingKey);
>> > > >> return block;
>> > > >> } catch (KeyVerifyException e) {
>> > > >> Logger.minor(this, "key verification
> exception",
>> > e);
>> > > >> @@ -129,6 +139,10 @@
>> > > >> * @throws IOException
>> > > >> */
>> > > >> private Entry probeEntry(byte[] routingKey) throws IOException
> {
>> > > >> + if (checkBloom)
>> > > >> + if (!bloomFilter.checkFilter(routingKey))
>> > > >> + return null;
>> > > >> +
>> > > >> Entry entry = probeEntry0(routingKey, storeSize);
>> > > >>
>> > > >> if (entry == null && prevStoreSize != 0)
>> > > >> @@ -190,8 +204,11 @@
>> > > >> }
>> > > >>
>> > > >> // Overwrite old offset
>> > > >> + if (updateBloom)
>> > > >> + bloomFilter.updateFilter(routingKey);
>> > > >> Entry entry = new Entry(routingKey, header,
> data);
>> > > >> writeEntry(entry, oldOffset);
>> > > >> + incWrites();
>> > > >> return;
>> > > >> } finally {
>> > > >> unlockEntry(oldOffset);
>> > > >> @@ -210,6 +227,8 @@
>> > > >> if (isFree(offset[i])) {
>> > > >> if (logDEBUG)
>> > > >>
>> > Logger.debug(this, "probing, write to i=" + i + ", offset=" +
>> > > > offset[i]);
>> > > >> + if (updateBloom)
>> > > >> +
>> > bloomFilter.updateFilter(routingKey);
>> > > >> writeEntry(entry, offset[i]);
>> > > >> incWrites();
>> > > >> return;
>> > > >> @@ -227,7 +246,9 @@
>> > > >> try {
>> > > >> if (logDEBUG)
>> > > >> Logger.debug(this, "collision, write to
>> > i=0, offset=" + offset[0]);
>> > > >> - writeEntry(entry, offset[0]);
>> > > >> + if (updateBloom)
>> > > >> + bloomFilter.updateFilter(routingKey);
>> > > >> + writeEntry(entry, offset[0]);
>> > > >> incWrites();
>> > > >> } finally {
>> > > >> unlockEntry(offset[0]);
>> > > >>
>> > > >> _______________________________________________
>> > > >> cvs mailing list
>> > > >> cvs at freenetproject.org
>> > > >> http://emu.freenetproject.org/cgi-bin/mailman/listinfo/cvs
>> > > >>
>> > > >>
>> > > >
>> > > > _______________________________________________
>> > > > Devl mailing list
>> > > > Devl at freenetproject.org
>> > > > http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
>> > > >
>> > > _______________________________________________
>> > > Devl mailing list
>> > > Devl at freenetproject.org
>> > > http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
>> > >
>> > >
>> >
>> > _______________________________________________
>> > Devl mailing list
>> > Devl at freenetproject.org
>> > http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
>> >
>> >
>> _______________________________________________
>> Devl mailing list
>> Devl at freenetproject.org
>> http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
>>
>>
>
> _______________________________________________
> Devl mailing list
> Devl at freenetproject.org
> http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
>
