On Thu, May 15, 2008 at 7:08 AM, Matthew Toseland <toad at amphibian.dyndns.org> wrote: > On Sunday 11 May 2008 11:24, j16sdiz at freenetproject.org wrote: >> Author: j16sdiz >> Date: 2008-05-11 10:24:22 +0000 (Sun, 11 May 2008) >> New Revision: 19891 >> >> Modified: >> > branches/saltedhashstore/freenet/src/freenet/store/SaltedHashFreenetStore.java >> Log: >> Quadratic Probing (datastore resize disabled) > > Cool! Any test results yet?
It is working better then the previous code.. The store can grow ~70% full with no much resistant. >> Modified: > branches/saltedhashstore/freenet/src/freenet/store/SaltedHashFreenetStore.java >> =================================================================== >> --- > branches/saltedhashstore/freenet/src/freenet/store/SaltedHashFreenetStore.java > 2008-05-11 09:08:40 UTC (rev 19890) >> +++ > branches/saltedhashstore/freenet/src/freenet/store/SaltedHashFreenetStore.java > 2008-05-11 10:24:22 UTC (rev 19891) >> @@ -126,22 +126,29 @@ >> >> private Entry probeEntry0(byte[] routingKey, long probeStoreSize) >> throws > IOException { >> Entry entry; >> - long offset = getOffsetFromPlainKey(routingKey, >> probeStoreSize); >> + long[] offset = getOffsetFromPlainKey(routingKey, >> probeStoreSize); >> >> - if (!lockEntry(offset)) { >> - Logger.error(this, "can't lock entry: " + offset); >> - return null; >> + for (int i = 0; i < offset.length; i++) { >> + if (logDEBUG) >> + Logger.debug(this, "probing for i=" + i + ", >> offset=" + offset[i]); >> + >> + if (!lockEntry(offset[i])) { >> + Logger.error(this, "can't lock entry: " + >> offset[i]); >> + continue; >> + } >> + try { >> + entry = readEntry(offset[i], routingKey); >> + } catch (EOFException e) { >> + // may occur on resize, silent it a bit >> + Logger.error(this, "EOFException on >> probeEntry", e); >> + return null; > > Shouldn't we go around the loop here? Or are the offsets strictly increasing? Fixed in my local repository. >> + } finally { >> + unlockEntry(offset[i]); >> + } >> + if (entry != null) >> + return entry; >> } >> - try { >> - entry = readEntry(offset, routingKey); >> - } catch (EOFException e) { >> - // may occur on resize, silent it a bit >> - Logger.error(this, "EOFException on probeEntry", e); >> - return null; >> - } finally { >> - unlockEntry(offset); >> - } >> - return entry; >> + return null; >> } >> >> public void put(StorableBlock block, byte[] routingKey, byte[] fullKey, > byte[] data, byte[] header, >> @@ -163,16 +170,39 @@ >> } >> >> Entry entry = new Entry(routingKey, header, data); >> - if (!lockEntry(entry.getOffset())) { >> + long[] offset = entry.getOffset(); >> + >> + for (int i = 0; i < offset.length; i++) { >> + if (!lockEntry(offset[i])) { >> + Logger.error(this, "can't lock entry: " + >> offset[i]); >> + return; >> + } >> + try { >> + if (isFree(offset[i], entry)) { >> + if (logDEBUG) >> + Logger.debug(this, "probing, >> write to i=" + i + ", offset=" + > offset[i]); >> + writeEntry(entry, offset[i]); >> + incWrites(); >> + return; >> + } >> + } finally { >> + unlockEntry(offset[i]); >> + } >> + } >> + >> + // no free blocks? >> + int i = random.nextInt(offset.length); > > You should try to write to an empty slot, of course... if all are full, is it > better to overwrite an empty slot rather than the first one? All slot in offset[] are occupied when we reach this code. Have to pick a random one to overwrite >> + if (!lockEntry(offset[i])) { >> Logger.error(this, "can't lock entry: " + >> entry.getOffset()); >> - incMisses(); >> return; >> } >> try { >> - writeEntry(entry); >> + if (logDEBUG) >> + Logger.debug(this, "collision, write to i=" + >> i + ", offset=" + > offset[i]); >> + writeEntry(entry, offset[i]); >> incWrites(); >> } finally { >> - unlockEntry(entry.getOffset()); >> + unlockEntry(offset[i]); >> } >> } >> >> @@ -235,6 +265,7 @@ >> private byte[] data; >> >> private boolean isEncrypted; >> + public long curOffset; >> >> /** >> * Create a new entry >> @@ -352,7 +383,7 @@ >> return block; >> } >> >> - public long getOffset() { >> + public long[] getOffset() { >> if (digestedRoutingKey != null) >> return >> getOffsetFromDigestedKey(digestedRoutingKey, storeSize); >> else >> @@ -382,7 +413,8 @@ >> } >> } else { >> // we do not know the plain key, let's check >> the digest >> - if (!Arrays.equals(this.digestedRoutingKey, > getDigestedRoutingKey(routingKey))) >> + if (!Arrays.equals(this.digestedRoutingKey, >> SaltedHashFreenetStore.this >> + .getDigestedRoutingKey(routingKey))) >> return false; >> } >> >> @@ -411,7 +443,7 @@ >> header = cipher.blockEncipher(header, 0, >> header.length); >> data = cipher.blockEncipher(data, 0, data.length); >> >> - digestedRoutingKey = >> getDigestedRoutingKey(plainRoutingKey); >> + getDigestedRoutingKey(); >> isEncrypted = true; >> } >> >> @@ -438,6 +470,13 @@ >> public boolean isFree() { >> return (flag & ENTRY_FLAG_OCCUPIED) == 0; >> } >> + >> + public byte[] getDigestedRoutingKey() { >> + if (digestedRoutingKey != null) >> + return digestedRoutingKey; >> + else >> + return > SaltedHashFreenetStore.this.getDigestedRoutingKey(this.plainRoutingKey); >> + } > > So where does digestedRoutingKey get set? fixed in r19892. >> } >> >> /** >> @@ -504,6 +543,7 @@ >> return null; >> } >> >> + entry.curOffset = offset; >> return entry; >> } >> >> @@ -516,17 +556,12 @@ >> * <li>update the entry with latest store size</li> >> * </ul> >> */ >> - private void writeEntry(Entry entry) throws IOException { >> + private void writeEntry(Entry entry, long offset) throws IOException { >> entry.encrypt(); >> >> - long offset = entry.getOffset(); >> int split = (int) (offset % FILE_SPLIT); >> long rawOffset = (offset / FILE_SPLIT) * entryTotalLength; >> >> - if (logMINOR && !isFree(offset)) { >> - Logger.minor(this, "collision, overwritting an entry"); >> - } >> - >> ByteBuffer bf = entry.toByteBuffer(); >> do { >> int status = storeFC[split].write(bf, rawOffset + >> bf.position()); >> @@ -554,16 +589,18 @@ >> } >> >> /** >> - * Check if a block is free >> + * Check if a block is free or occupied by a specific routing key >> * >> * @param offset >> + * @param entry >> + * entry, maybe <code>null</code> >> * @throws IOException >> */ >> - private boolean isFree(long offset) throws IOException { >> + private boolean isFree(long offset, Entry entry) throws IOException { >> int split = (int) (offset % FILE_SPLIT); >> long rawOffset = (offset / FILE_SPLIT) * entryTotalLength; >> >> - ByteBuffer bf = ByteBuffer.allocate(0x30 + 0x08); >> + ByteBuffer bf = ByteBuffer.allocate((int) ENTRY_HEADER_LENGTH); >> >> do { >> int status = storeFC[split].read(bf, rawOffset + >> bf.position()); >> @@ -571,7 +608,17 @@ >> throw new EOFException(); >> } while (bf.hasRemaining()); >> >> - return (bf.getLong(0x30) & ENTRY_FLAG_OCCUPIED) == 0; >> + if ((bf.getLong(0x30) & ENTRY_FLAG_OCCUPIED) == 0) { >> + // free >> + return true; >> + } else if (entry != null) { >> + // check digested key >> + byte[] digestedRoutingKey = new byte[0x20]; >> + bf.position(0); >> + bf.get(digestedRoutingKey); >> + return Arrays.equals(digestedRoutingKey, >> entry.getDigestedRoutingKey()); >> + } >> + return false; >> } >> >> private void flushAndClose() { >> @@ -689,7 +736,7 @@ >> while (!shutdown) { >> synchronized (cleanerLock) { >> if (prevStoreSize != 0) >> - resizeStore(); >> + ; //resizeStore(); >> else >> estimateStoreSize(); >> >> @@ -728,9 +775,11 @@ >> */ >> private int resizeRound; >> >> - /** >> + /*- >> + * >> + * >> * Move old entries to new location and resize store >> - */ >> + * >> private void resizeStore() { >> ++resizeRound; >> Logger.normal(this, "Starting datastore resize (round >> " + resizeRound > + ")"); >> @@ -773,7 +822,7 @@ >> >> /** >> * Scan all entries and try to move them >> - */ >> + * >> private void moveOldEntry0(boolean queueItem) { >> newEntries = 0; >> oldEntries = 0; >> @@ -827,7 +876,7 @@ >> long newOffset = >> entry.getOffset(); >> >> if (newOffset == offset) { // >> lucky! >> - writeEntry(entry); // >> write back entry storeSize >> + lockAndWrite(entry); >> // write back entry storeSize >> resolvedEntries++; >> continue; >> } >> @@ -840,7 +889,7 @@ >> >> if >> (newOffsetEntry.isFree()) { >> // the new >> offset is freeeeeeee.. >> - >> writeEntry(entry); >> + >> lockAndWrite(entry); >> >> freeOffset(offset); >> >> resolvedEntries++; >> } else if >> (newOffsetEntry.getStoreSize() == storeSize) { >> @@ -862,7 +911,7 @@ >> >> oldEntries++; // newOffset wasn't counted count it >> } >> >> - >> writeEntry(entry); >> + >> lockAndWrite(entry); >> >> freeOffset(offset); >> >> resolvedEntries++; >> } >> @@ -896,7 +945,7 @@ >> * Put back oldItems with best effort >> * >> * @throws IOException >> - */ >> + * >> private void putBackOldItems(FileChannel oldItems) throws >> IOException { >> while (true) { >> Entry entry = readOldItem(oldItems); >> @@ -914,7 +963,7 @@ >> if (isFree(newOffset)) { >> if (logDEBUG) >> Logger.debug(this, >> "Put back old item: " + > HexUtil.bytesToHex(entry.digestedRoutingKey)); >> - writeEntry(entry); >> + lockAndWrite(entry); >> done = true; >> } else { >> if (logDEBUG) >> @@ -948,6 +997,7 @@ >> bf.flip(); >> return new Entry(bf); >> } >> + */ >> >> /** >> * Samples to take on key count estimation >> @@ -972,7 +1022,7 @@ >> long occupied = 0; >> while (sampled < numSample) { >> try { >> - if (!isFree(samplePos)) { >> + if (!isFree(samplePos, null)) { >> occupied++; >> } >> sampled++; >> @@ -1173,7 +1223,7 @@ >> * @param storeSize >> * @return >> */ >> - public long getOffsetFromPlainKey(byte[] plainKey, long storeSize) { >> + public long[] getOffsetFromPlainKey(byte[] plainKey, long storeSize) { >> return >> getOffsetFromDigestedKey(getDigestedRoutingKey(plainKey), > storeSize); >> } >> >> @@ -1184,18 +1234,27 @@ >> * @param storeSize >> * @return >> */ >> - public long getOffsetFromDigestedKey(byte[] digestedKey, long >> storeSize) { >> - long keyValue = (((long) (digestedKey[0]) << 0) + // >> - (((long) digestedKey[1]) << 8) + // >> - (((long) digestedKey[3]) << 16) + // >> - (((long) digestedKey[4]) << 24) + // >> - (((long) digestedKey[5]) << 32) + // >> - (((long) digestedKey[6]) << 40) + // >> - (((long) digestedKey[7]) << 48)) >> - & Long.MAX_VALUE; >> - return keyValue % storeSize; >> + public long[] getOffsetFromDigestedKey(byte[] digestedKey, long >> storeSize) > { >> + long keyValue = keyToLong(digestedKey); >> + // h + 141 i^2 + 13 i >> + return new long[] {// >> + ((keyValue + 141 * (0 * 0) + 13 * 0) & Long.MAX_VALUE) % >> storeSize, // i > = 0 >> + ((keyValue + 141 * (1 * 1) + 13 * 1) & Long.MAX_VALUE) >> % > storeSize, // i = 1 >> + ((keyValue + 141 * (2 * 2) + 13 * 2) & Long.MAX_VALUE) >> % > storeSize, // i = 2 >> + ((keyValue + 141 * (3 * 3) + 13 * 3) & Long.MAX_VALUE) >> % > storeSize, // i = 3 >> + }; > > These are all going to be quite close to keyValue, no? Is this intentional? Quite close, but never a problem. The keys is random distributed. I was considering to make it even closer (to take advantage of the read-a-head cache in linux), but i don't have any idea with spitted files enabled. >> } >> >> + private long keyToLong(byte[] key) { >> + return (((long) (key[0]) << 0) + // >> + (((long) key[1]) << 8) + // >> + (((long) key[3]) << 16) + // >> + (((long) key[4]) << 24) + // >> + (((long) key[5]) << 32) + // >> + (((long) key[6]) << 40) + // >> + (((long) key[7]) << 48)); > > What about 56? hmm.. yes. fixed. >> + } >> + >> // ------------- Statistics (a.k.a. lies) >> private final Object statLock = new Object(); >> private long hits; > > _______________________________________________ > Devl mailing list > Devl at freenetproject.org > http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl >