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.
> > > 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
>
>
