You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@labs.apache.org by ka...@apache.org on 2009/03/15 11:33:55 UTC
svn commit: r754647 - in /labs/bananadb/trunk: CHANGES.txt
src/main/java/org/apache/labs/bananadb/hashtable/Hashtable.java
src/test/java/org/apache/labs/bananadb/hashtable/TestValuePartitions.java
Author: kalle
Date: Sun Mar 15 10:33:55 2009
New Revision: 754647
URL: http://svn.apache.org/viewvc?rev=754647&view=rev
Log:
BananaDB
Speedier rehash by skipping to the last key posting in the chain.
Modified:
labs/bananadb/trunk/CHANGES.txt
labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/Hashtable.java
labs/bananadb/trunk/src/test/java/org/apache/labs/bananadb/hashtable/TestValuePartitions.java
Modified: labs/bananadb/trunk/CHANGES.txt
URL: http://svn.apache.org/viewvc/labs/bananadb/trunk/CHANGES.txt?rev=754647&r1=754646&r2=754647&view=diff
==============================================================================
--- labs/bananadb/trunk/CHANGES.txt (original)
+++ labs/bananadb/trunk/CHANGES.txt Sun Mar 15 10:33:55 2009
@@ -10,23 +10,31 @@
File format
- 1. Hashtable and Key postings 1024 bytes headers.
- (Karl Wettin)
+ 1. Hashtable and key postings 1024 bytes headers.
+ (Karl Wettin)
+
+ The headers contains data start offset (and more) that is read at every
+ access and thus made the way for rehashing on one JVM to "notify" other
+ JVMs to start accessing rehashed data.
+
- The headers contains data start offset (and more) that is read at every
- access and thus made the way for rehashing on one JVM to "notify" other
- JVMs to start accessing rehashed data.
+ 2. Key postings header now contains a version.
+ (Karl Wettin)
+
+ This long value is increased for each modification to the database.
- 2. Key postings header now contains a version.
- (Karl Wettin)
- This long value is increased for each modification to the database.
+ 3. Hashtable posting points now also points at last key posting offset.
+ (Karl Wettin)
+
+ This allows for speedier rehash as it can skip to the last key posting
+ rather than iterating all key postings associated with a hash posting.
Bug fixes
- 1. Write lock on remove.
- (Karl Wettin)
+ 1. Write lock on remove.
+ (Karl Wettin)
New features
@@ -44,8 +52,7 @@
In the future one should implement
1. A cleanup() method that removes old posting parts of the files.
- 2. Automatic rehasing when the next available offset hits a threadshold.
-
+ 2. Automatic rehasing when the next available offset hits a threadshold. (DONE! see #2)
CAVEAT!
Cursors iterating values will throw an exception in case there has been a rehash.
@@ -78,6 +85,9 @@
that are associated with the same hash posting.
+ 2. Speedier rehash by skipping to the last key posting in the chain.
+ (Karl Wettin)
+
Documentation
Modified: labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/Hashtable.java
URL: http://svn.apache.org/viewvc/labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/Hashtable.java?rev=754647&r1=754646&r2=754647&view=diff
==============================================================================
--- labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/Hashtable.java (original)
+++ labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/Hashtable.java Sun Mar 15 10:33:55 2009
@@ -41,7 +41,7 @@
private static final int HASHTABLE_HEADER_BYTE_SIZE = 1024;
- private static final int HASHTABLE_RECORD_BYTE_SIZE = 1 + 4;
+ private static final int HASHTABLE_RECORD_BYTE_SIZE = 1 + 4 + 4;
/**
* the header contains meta data such as number of records, et c.
@@ -512,9 +512,9 @@
V oldValue = null;
int keyHash = key.hashCode();
- int hashtableOffset = hashtableFileHeader.getHashCodeTableOffset(keyHash);
+ int hashPostingOffset = hashtableFileHeader.getHashCodeTableOffset(keyHash);
- accessor.getHashtableRAF().seek(hashtableOffset);
+ accessor.getHashtableRAF().seek(hashPostingOffset);
if (accessor.getHashtableRAF().readByte() == 0) {
// create inital posting for hash
@@ -528,9 +528,10 @@
accessor.getKeyPostingsRAF().seek(keyPostingOffset);
writePostings(accessor, -1, keyBuf, valueBuf, keyHash);
- accessor.getHashtableRAF().seek(hashtableOffset);
+ accessor.getHashtableRAF().seek(hashPostingOffset);
accessor.getHashtableRAF().writeByte(1);
accessor.getHashtableRAF().writeInt(keyPostingOffset);
+ accessor.getHashtableRAF().writeInt(keyPostingOffset);
return null;
@@ -599,6 +600,10 @@
accessor.getKeyPostingsRAF().seek(previousKeyPostingOffset);
accessor.getKeyPostingsRAF().writeInt(keyPostingOffset);
+ // update last key posting offset in hash posting
+ accessor.getHashtableRAF().seek(hashPostingOffset + 5);
+ accessor.getHashtableRAF().writeInt(keyPostingOffset);
+
return null;
}
@@ -617,7 +622,7 @@
private void writePostings(HashtableAccessor accessor, int nextKeyPostingOffset, byte[] keyBuf, byte[] valueBuf, int keyHashCode) throws IOException {
int partitionNumber = -1;
- long offset = -1;
+ long valuePostingOffset = -1;
if (valueBuf != null) {
Partition partition = partitions.get(partitions.size() - 1);
@@ -633,7 +638,7 @@
}
partitionNumber = partition.partitionNumber;
- offset = partition.append(accessor, valueBuf);
+ valuePostingOffset = partition.append(accessor, valueBuf);
}
// int offset position in this file to the next key posting with the same hash, -1 = null
@@ -646,7 +651,7 @@
accessor.getKeyPostingsRAF().writeInt(partitionNumber);
// int offset position in value partition, -1 == null
- accessor.getKeyPostingsRAF().writeInt((int) offset);
+ accessor.getKeyPostingsRAF().writeInt((int) valuePostingOffset);
// int key byte length todo: remove this from the file
accessor.getKeyPostingsRAF().writeInt(keyBuf.length);
@@ -671,16 +676,14 @@
int keyHash = key.hashCode();
int hashtableOffset = hashtableFileHeader.getHashCodeTableOffset(keyHash);
- byte[] hashtableRecordBuf = new byte[HASHTABLE_RECORD_BYTE_SIZE];
accessor.getHashtableRAF().seek(hashtableOffset);
- accessor.getHashtableRAF().read(hashtableRecordBuf);
- DataInput in = new DataInputStream(new ByteArrayInputStream(hashtableRecordBuf));
- byte isnull = in.readByte();
+
+ byte isnull = accessor.getHashtableRAF().readByte();
if (isnull == 0) {
return false;
}
- int firstKeyPostingOffset = in.readInt();
+ int firstKeyPostingOffset = accessor.getHashtableRAF().readInt();
K compareKey;
@@ -701,8 +704,9 @@
continue;
}
- int partitionNumber = accessor.getKeyPostingsRAF().readInt();
- int partitionOffset = accessor.getKeyPostingsRAF().readInt();
+ accessor.getKeyPostingsRAF().skipBytes(8);
+// int partitionNumber = accessor.getKeyPostingsRAF().readInt();
+// int partitionOffset = accessor.getKeyPostingsRAF().readInt();
int keySize = accessor.getKeyPostingsRAF().readInt();
if (keySize > 0) {
@@ -724,11 +728,11 @@
KeyPostingsFileHeader keyPostingsFileHeader = new KeyPostingsFileHeader(accessor);
int keyHash = key.hashCode();
- int hashtableOffset = hashtableFileHeader.getHashCodeTableOffset(keyHash);
- accessor.getHashtableRAF().seek(hashtableOffset);
+ int hashPostingOffset = hashtableFileHeader.getHashCodeTableOffset(keyHash);
+ accessor.getHashtableRAF().seek(hashPostingOffset);
- byte isnull = accessor.getHashtableRAF().readByte();
- if (isnull == 0) {
+ byte flag = accessor.getHashtableRAF().readByte();
+ if (flag == 0) {
return null;
}
@@ -818,12 +822,13 @@
int keyHash = key.hashCode();
- int hashtableOffset = hashtableFileHeader.getHashCodeTableOffset(keyHash);
- accessor.getHashtableRAF().seek(hashtableOffset);
+ int hashPostingOffset = hashtableFileHeader.getHashCodeTableOffset(keyHash);
+ accessor.getHashtableRAF().seek(hashPostingOffset);
byte isnull = accessor.getHashtableRAF().readByte();
int firstKeyPostingOffset = accessor.getHashtableRAF().readInt();
+ int lastKeyPostingOffset = accessor.getHashtableRAF().readInt();
K compareKey;
@@ -862,9 +867,16 @@
// update offset in previous key posting to point at next offset in removed key posting
accessor.getKeyPostingsRAF().seek(previousKeyPostingOffset);
accessor.getKeyPostingsRAF().writeInt(nextKeyPostingOffset);
+
+ // update last key posting offset in hash posting
+ if (keyPostingOffset == lastKeyPostingOffset) {
+ accessor.getHashtableRAF().seek(hashPostingOffset);
+ accessor.getHashtableRAF().writeInt(previousKeyPostingOffset);
+ }
+
} else {
// remove posting in hashtable
- accessor.getHashtableRAF().seek(hashtableOffset);
+ accessor.getHashtableRAF().seek(hashPostingOffset);
accessor.getHashtableRAF().writeByte(0);
}
@@ -934,22 +946,26 @@
log.info("Updating capacity from " + inputKeyPostingsFileHeader.getCapacity() + " to " + newCapacity + ".");
- HashtableFileHeader outputHashtableFileHeader = new HashtableFileHeader(inputHashtableFileHeader.getEndOffset() + 1, newCapacity);
- KeyPostingsFileHeader outputKeyPostingsFileHeader = new KeyPostingsFileHeader(inputKeyPostingsFileHeader.getNextOffset() + 1, inputKeyPostingsFileHeader.getEntityCount(), inputKeyPostingsFileHeader.getNextOffset() + 1, newCapacity, inputKeyPostingsFileHeader.getVersion() + 1);
+ HashtableFileHeader outputHashtableFileHeader = new HashtableFileHeader(
+ inputHashtableFileHeader.getEndOffset() + 1,
+ newCapacity);
+
+ KeyPostingsFileHeader outputKeyPostingsFileHeader = new KeyPostingsFileHeader(
+ inputKeyPostingsFileHeader.getEndOffset() + 1,
+ inputKeyPostingsFileHeader.getEntityCount(),
+ inputKeyPostingsFileHeader.getEndOffset() + 1,
+ newCapacity,
+ inputKeyPostingsFileHeader.getVersion() + 1);
- RandomAccessFile keyPostingsInput = accessor.getKeyPostingsRAF();
- keyPostingsInput.seek(inputKeyPostingsFileHeader.getStartOffset());
HashtableAccessor outputAccessor = createAccessor(false);
- RandomAccessFile hashtableOutput = outputAccessor.getHashtableRAF();
+ RandomAccessFile hashPostingsOutput = outputAccessor.getHashtableRAF();
RandomAccessFile keyPostingsOutput = outputAccessor.getKeyPostingsRAF();
// append formatted data to files
- formatAppend(hashtableOutput, newCapacity * HASHTABLE_RECORD_BYTE_SIZE);
+ formatAppend(hashPostingsOutput, newCapacity * HASHTABLE_RECORD_BYTE_SIZE);
formatAppend(keyPostingsOutput, newCapacity * keyPostingByteSize);
- int highScore = 0;
-
int nextKeyListPostingOffset;
int valuePartition;
int valuePartitionOffset;
@@ -957,12 +973,16 @@
byte[] keyBuf = new byte[keyClassHandler.getByteSize()];
int keyHash;
+ RandomAccessFile keyPostingsInput = accessor.getKeyPostingsRAF();
+ keyPostingsInput.seek(inputKeyPostingsFileHeader.getStartOffset());
+
for (int inputKeyPostingOffset = inputKeyPostingsFileHeader.getStartOffset(); inputKeyPostingOffset < inputKeyPostingsFileHeader.getNextOffset(); inputKeyPostingOffset += keyPostingByteSize) {
// int offset position in this file to the next entry with the same hash, -1 = null
nextKeyListPostingOffset = keyPostingsInput.readInt();
if (nextKeyListPostingOffset == -2) {
+ // deleted
keyPostingsInput.skipBytes(keyPostingByteSize - 4);
continue;
}
@@ -979,10 +999,10 @@
keyPostingsInput.read(keyBuf);
- int outputHashtableOffset = outputHashtableFileHeader.getHashCodeTableOffset(keyHash);
- hashtableOutput.seek(outputHashtableOffset);
+ int outputHashPostingOffset = outputHashtableFileHeader.getHashCodeTableOffset(keyHash);
+ hashPostingsOutput.seek(outputHashPostingOffset);
- if (hashtableOutput.readByte() == 0) {
+ if (hashPostingsOutput.readByte() == 0) {
// create inital posting for hash
int outputKeyPostingOffset = outputKeyPostingsFileHeader.getNextOffset();
outputKeyPostingsFileHeader.increaseNextOffset(keyPostingByteSize);
@@ -1007,44 +1027,25 @@
keyPostingsOutput.write(keyBuf);
- hashtableOutput.seek(outputHashtableOffset);
- hashtableOutput.writeByte(1);
- hashtableOutput.writeInt(outputKeyPostingOffset);
+ hashPostingsOutput.seek(outputHashPostingOffset);
+ hashPostingsOutput.writeByte(1);
+ hashPostingsOutput.writeInt(outputKeyPostingOffset);
+ hashPostingsOutput.writeInt(outputKeyPostingOffset);
} else {
// already contains a posting for the hash
- int firstKeyPostingOffset = hashtableOutput.readInt();
-
- int depth = 0;
-
- int previousKeyPostingOffset = -1;
- int nextKeyPostingOffset = firstKeyPostingOffset;
- while (nextKeyPostingOffset != -1) {
- int keyPostingOffset = nextKeyPostingOffset;
-
- keyPostingsOutput.seek(keyPostingOffset);
-
- nextKeyPostingOffset = keyPostingsOutput.readInt();
- previousKeyPostingOffset = keyPostingOffset;
-
- depth++;
-
- }
-
- if (depth > highScore) {
- highScore = depth;
- log.info("New depth high score: " + highScore);
- }
+ int firstKeyPostingOffset = hashPostingsOutput.readInt();
+ int lastKeyPostingsOffset = hashPostingsOutput.readInt();
// this key instance did not exist in entries
// although it shares hash with some other keys in there.
// create new key posting and point at it from the previous key posting
- int keyPostingOffset = outputKeyPostingsFileHeader.getNextOffset();
+ int outputKeyPostingOffset = outputKeyPostingsFileHeader.getNextOffset();
outputKeyPostingsFileHeader.increaseNextOffset(keyPostingByteSize);
- keyPostingsOutput.seek(keyPostingOffset);
+ keyPostingsOutput.seek(outputKeyPostingOffset);
// int offset position in this file to the next key posting with the same hash, -1 = null
keyPostingsOutput.writeInt(-1);
@@ -1064,8 +1065,15 @@
keyPostingsOutput.write(keyBuf);
- keyPostingsOutput.seek(previousKeyPostingOffset);
- keyPostingsOutput.writeInt(keyPostingOffset);
+ keyPostingsOutput.seek(lastKeyPostingsOffset);
+ keyPostingsOutput.writeInt(outputKeyPostingOffset);
+
+ // update last key posting offset in hash posting
+// hashPostingsOutput.seek(outputHashPostingOffset + 5);
+ hashPostingsOutput.seek(outputHashPostingOffset);
+ byte flag = hashPostingsOutput.readByte();
+ int first = hashPostingsOutput.readInt();
+ hashPostingsOutput.writeInt(outputKeyPostingOffset);
}
}
@@ -1107,11 +1115,11 @@
partitions.add(partitionNumber, this);
}
- public long append(HashtableAccessor accessor, byte[] bytes) throws IOException {
- return append(accessor, bytes, bytes.length);
+ public long append(HashtableAccessor accessor, byte[] value) throws IOException {
+ return append(accessor, value, value.length);
}
- public long append(HashtableAccessor accessor, byte[] bytes, int length) throws IOException {
+ public long append(HashtableAccessor accessor, byte[] value, int length) throws IOException {
RandomAccessFile raf = accessor.getPartitionRAF(this);
@@ -1125,7 +1133,7 @@
raf.seek(offset);
raf.writeInt(length);
- raf.write(bytes);
+ raf.write(value);
return offset;
}
Modified: labs/bananadb/trunk/src/test/java/org/apache/labs/bananadb/hashtable/TestValuePartitions.java
URL: http://svn.apache.org/viewvc/labs/bananadb/trunk/src/test/java/org/apache/labs/bananadb/hashtable/TestValuePartitions.java?rev=754647&r1=754646&r2=754647&view=diff
==============================================================================
--- labs/bananadb/trunk/src/test/java/org/apache/labs/bananadb/hashtable/TestValuePartitions.java (original)
+++ labs/bananadb/trunk/src/test/java/org/apache/labs/bananadb/hashtable/TestValuePartitions.java Sun Mar 15 10:33:55 2009
@@ -48,12 +48,14 @@
}
String str = sb.toString();
for (int i = 101; i < 5000; i++) {
- map.put(accessor, i, str + String.valueOf(i));
+ log.info(String.valueOf(i));
+ map.put(accessor, i, String.valueOf(i) + str);
+ assertEquals(String.valueOf(i) + str, map.get(accessor, i));
}
assertEquals(3, map.getPartitions().size());
for (int i = 101; i < 5000; i++) {
- assertEquals(str + String.valueOf(i), map.get(accessor, i));
+ assertEquals(String.valueOf(i) + str, map.get(accessor, i));
}
accessor.close();
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@labs.apache.org
For additional commands, e-mail: commits-help@labs.apache.org