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