Author: j16sdiz
Date: 2008-07-09 08:43:57 +0000 (Wed, 09 Jul 2008)
New Revision: 21010
Modified:
branches/saltedhashstore/freenet/src/freenet/store/saltedhash/SaltedHashFreenetStore.java
branches/saltedhashstore/freenet/src/freenet/support/BloomFilter.java
Log:
Use optimial K for filter
Modified:
branches/saltedhashstore/freenet/src/freenet/store/saltedhash/SaltedHashFreenetStore.java
===================================================================
---
branches/saltedhashstore/freenet/src/freenet/store/saltedhash/SaltedHashFreenetStore.java
2008-07-09 08:43:31 UTC (rev 21009)
+++
branches/saltedhashstore/freenet/src/freenet/store/saltedhash/SaltedHashFreenetStore.java
2008-07-09 08:43:57 UTC (rev 21010)
@@ -53,9 +53,9 @@
private static final byte FLAG_REBUILD_BLOOM = 0x2;
private static final int BLOOM_FILTER_SIZE = 0x8000000; // bits
- private static final int BLOOM_FILTER_K = 5;
private static final boolean updateBloom = true;
private static final boolean checkBloom = true;
+ private int bloomFilterK;
private BloomFilter bloomFilter;
private static boolean logMINOR;
@@ -111,7 +111,7 @@
File bloomFile = new File(this.baseDir, name +
".bloom");
if (!bloomFile.exists() || bloomFile.length() !=
BLOOM_FILTER_SIZE / 8)
flags |= FLAG_REBUILD_BLOOM;
- bloomFilter = new BloomFilter(bloomFile,
BLOOM_FILTER_SIZE, BLOOM_FILTER_K);
+ bloomFilter = new BloomFilter(bloomFile,
BLOOM_FILTER_SIZE, bloomFilterK);
}
if ((flags & FLAG_DIRTY) != 0)
@@ -727,9 +727,12 @@
* |0010| Store Size | prevStoreSize |
* +----+---------------+-------+-------+
* |0020| Est Key Count | Gen | Flags |
- * +----+---------------+-------+-------+
+ * +----+-------+-------+-------+-------+
+ * |0030| K | |
+ * +----+-------+-----------------------+
*
* Gen = Generation
+ * K = K for bloom filter
* </pre>
*/
private final File configFile;
@@ -763,6 +766,12 @@
if ((flags & FLAG_DIRTY) != 0)
flags |= FLAG_REBUILD_BLOOM;
+ try {
+ bloomFilterK = raf.readInt();
+ } catch (IOException e) {
+ flags |= FLAG_REBUILD_BLOOM;
+ }
+
raf.close();
}
@@ -784,6 +793,9 @@
raf.writeLong(keyCount.get());
raf.writeInt(generation);
raf.writeInt(flags);
+ raf.writeInt(bloomFilterK);
+ raf.writeInt(0);
+ raf.writeLong(0);
raf.close();
@@ -889,10 +901,11 @@
if (storeSize > _prevStoreSize)
setStoreFileSize(storeSize);
+ int optimialK =
BloomFilter.optimialK(BLOOM_FILTER_SIZE, storeSize);
configLock.writeLock().lock();
try {
generation++;
- bloomFilter.fork(BLOOM_FILTER_K);
+ bloomFilter.fork(optimialK);
keyCount.set(0);
} finally {
configLock.writeLock().unlock();
@@ -963,7 +976,9 @@
return;
bloomFilter.merge();
prevStoreSize = 0;
+
flags &= ~FLAG_REBUILD_BLOOM;
+ bloomFilterK = optimialK;
} finally {
configLock.writeLock().unlock();
}
@@ -978,11 +993,12 @@
Logger.normal(this, "Start rebuilding bloom filter (" +
name + ")");
long startTime = System.currentTimeMillis();
+ int optimialK =
BloomFilter.optimialK(BLOOM_FILTER_SIZE, storeSize);
configLock.writeLock().lock();
try {
generation++;
- bloomFilter.fork(BLOOM_FILTER_K);
+ bloomFilter.fork(bloomFilterK);
keyCount.set(0);
} finally {
configLock.writeLock().unlock();
@@ -1021,6 +1037,7 @@
configLock.writeLock().lock();
try {
flags &= ~FLAG_REBUILD_BLOOM;
+ bloomFilterK = optimialK;
} finally {
configLock.writeLock().unlock();
}
Modified: branches/saltedhashstore/freenet/src/freenet/support/BloomFilter.java
===================================================================
--- branches/saltedhashstore/freenet/src/freenet/support/BloomFilter.java
2008-07-09 08:43:31 UTC (rev 21009)
+++ branches/saltedhashstore/freenet/src/freenet/support/BloomFilter.java
2008-07-09 08:43:57 UTC (rev 21010)
@@ -29,7 +29,7 @@
* Constructor
*
* @param length
- * length in bits
+ * length in bits
*/
public BloomFilter(int length, int k) {
if (length % 8 != 0)
@@ -44,9 +44,9 @@
* Constructor
*
* @param file
- * disk file
+ * disk file
* @param length
- * length in bits
+ * length in bits
* @throws IOException
*/
public BloomFilter(File file, int length, int k) throws IOException {
@@ -70,7 +70,7 @@
} finally {
lock.writeLock().unlock();
}
-
+
if (forkedFilter != null)
forkedFilter.updateFilter(key);
}
@@ -94,7 +94,7 @@
MessageDigest md = SHA256.getMessageDigest();
try {
ByteBuffer bf = null;
-
+
for (int i = 0; i < k; i++) {
if (bf == null || bf.remaining() < 8) {
md.update(key);
@@ -126,7 +126,7 @@
((MappedByteBuffer) filter).force();
}
}
-
+
protected BloomFilter forkedFilter;
/**
@@ -150,7 +150,7 @@
lock.writeLock().unlock();
}
}
-
+
public void merge() {
lock.writeLock().lock();
try {
@@ -181,4 +181,23 @@
public int getK() {
return k;
}
+
+ /**
+ * Calculate optimal K value
+ *
+ * @param filterLength
+ * filter length in bits
+ * @param maxKey
+ * @return optimal K
+ */
+ public static int optimialK(int filterLength, long maxKey) {
+ long k = Math.round(Math.log(2) * maxKey / filterLength);
+
+ if (k < 1)
+ k = 1;
+ if (k > 128)
+ k = 128;
+
+ return (int) k;
+ }
}
