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?
>
> > > > 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
>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL:
<https://emu.freenetproject.org/pipermail/devl/attachments/20080528/10b4412e/attachment.pgp>
