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 10:08:12 UTC
svn commit: r754636 - in /labs/bananadb/trunk: CHANGES.txt FILES.txt
src/main/java/org/apache/labs/bananadb/hashtable/Hashtable.java
src/test/java/org/apache/labs/bananadb/hashtable/TestHashtable.java
Author: kalle
Date: Sun Mar 15 09:08:10 2009
New Revision: 754636
URL: http://svn.apache.org/viewvc?rev=754636&view=rev
Log:
BananaDB
1. Automatic growing capacity of the hashtable.
Increased the capacity with factor 1.7 when the the key posting space use at least 20%
of the available space in the key postings file.
2. Read methods of key postings compares using keyhash before unmarshalling key.
A fairly obvious way to save clock ticks when iterating though large key posting lists
that are associated with the same hash posting.
Modified:
labs/bananadb/trunk/CHANGES.txt
labs/bananadb/trunk/FILES.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/TestHashtable.java
Modified: labs/bananadb/trunk/CHANGES.txt
URL: http://svn.apache.org/viewvc/labs/bananadb/trunk/CHANGES.txt?rev=754636&r1=754635&r2=754636&view=diff
==============================================================================
--- labs/bananadb/trunk/CHANGES.txt (original)
+++ labs/bananadb/trunk/CHANGES.txt Sun Mar 15 09:08:10 2009
@@ -31,24 +31,24 @@
New features
- 1. Rehashing, growing hashtable capacity.
- (Karl Wettin)
+ 1. Rehashing, growing hashtable capacity.
+ (Karl Wettin)
- Hashtable and Key postings file now both got a header of 1024 bytes
- that contains start and end offset. On rehash a write lock is set
- and the hashtable and key postings files are appended with null data
- on which the rehashed postings are written.
+ Hashtable and Key postings file now both got a header of 1024 bytes
+ that contains start and end offset. On rehash a write lock is set
+ and the hashtable and key postings files are appended with null data
+ on which the rehashed postings are written.
- When rehash finish, the start- and end offset in the file headers are updated
- and thus any JVM running using the DB will start reading from the rehashed data.
+ When rehash finish, the start- and end offset in the file headers are updated
+ and thus any JVM running using the DB will start reading from the rehashed data.
- 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.
+ 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.
- CAVEAT!
- Cursors iterating values will throw an exception in case there has been a rehash.
+ CAVEAT!
+ Cursors iterating values will throw an exception in case there has been a rehash.
2. Transactions.
@@ -62,8 +62,21 @@
3. Last commit wins, will override any changes made to the entities in the hashtable since txn was created.
+ 3. Automatic growing capacity of the hashtable.
+ (Karl Wettin)
+
+ Increased the capacity with factor 1.7 when the the key posting space use at least 20%
+ of the available space in the key postings file.
+
+
Optimizations
+ 1. Read methods of key postings compares using keyhash before unmarshalling key.
+ (Karl Wettin)
+
+ A fairly obvious way to save clock ticks when iterating though large key posting lists
+ that are associated with the same hash posting.
+
Documentation
Modified: labs/bananadb/trunk/FILES.txt
URL: http://svn.apache.org/viewvc/labs/bananadb/trunk/FILES.txt?rev=754636&r1=754635&r2=754636&view=diff
==============================================================================
--- labs/bananadb/trunk/FILES.txt (original)
+++ labs/bananadb/trunk/FILES.txt Sun Mar 15 09:08:10 2009
@@ -35,6 +35,8 @@
int entity count
int postings start offset -- will change after rehash
int postings end offset -- will change after rehash
+int capacity
+long version -- increased by 1 after each change to the database
}}}
@@ -44,11 +46,12 @@
deleted key posting values are all set to -2.
int offset position in this file to the next entry with the same hash, -1 = null
+int key hash
int value partition number, -1 = null value
int offset position in value partition, -1 = null
int key length in bytes, 0 = null // todo remove
byte[] serialized key (if not null)
-int key hash, will be used for future rehashing
+
}}}
@@ -57,11 +60,22 @@
The actual key entity hashtable, points at the first position in entities-file for the given hash.
The position for any given key is calculated with: hash & (capacity - 1);
+
+Header: 1024 bytes
+{{{
+
+int postings start offset
+int bytes left
+
+}}}
+
+
Posting data:
{{{
byte 0 = no posting. Any other value means there is a posting.
-int offset position to first entity with this hash
+int offset position in key postings to first entity with this hash
+int offset position in key postings to last entity with this hash (used at rehash time)
}}}
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=754636&r1=754635&r2=754636&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 09:08:10 2009
@@ -33,8 +33,7 @@
* <p/>
* It does not handle null keys but allows null values.
* <p/>
- * todo: optimize
- * todo: overwrite old value in data file if possible when replacing a value. keep track of unused positions
+ * todo: optimize/cleanup method
*/
public class Hashtable<K, V> {
@@ -389,6 +388,67 @@
}
}
+
+ public class ValuePostingsFileHeader {
+ private int nextOffset;
+ private int bytesLeft;
+
+ public ValuePostingsFileHeader(int nextOffset, int bytesLeft) {
+ this.nextOffset = nextOffset;
+ this.bytesLeft = bytesLeft;
+ }
+
+ public ValuePostingsFileHeader(RandomAccessFile raf) throws IOException {
+ load(raf);
+ }
+
+ public void load(RandomAccessFile raf) throws IOException {
+ raf.seek(0);
+ nextOffset = raf.readInt();
+ bytesLeft = raf.readInt();
+ }
+
+ private void save(RandomAccessFile raf) throws IOException {
+ raf.seek(0);
+ raf.writeInt(nextOffset);
+ raf.writeInt(bytesLeft);
+ }
+
+ public int getNextOffset() {
+ return nextOffset;
+ }
+
+ private void setNextOffset(int nextOffset) {
+ this.nextOffset = nextOffset;
+ }
+
+ private int increaseNextOffset(int value) {
+ nextOffset += value;
+ return nextOffset;
+ }
+
+ public int getBytesLeft() {
+ return bytesLeft;
+ }
+
+ private void setBytesLeft(int bytesLeft) {
+ this.bytesLeft = bytesLeft;
+ }
+
+ private void decreaseBytesLeft(int value) {
+ bytesLeft -= value;
+ }
+
+ @Override
+ public String toString() {
+ return "ValuePostingsFileHeader{" +
+ "nextOffset=" + nextOffset +
+ ", bytesLeft=" + bytesLeft +
+ '}';
+ }
+ }
+
+
/**
* @param accessor
* @param key
@@ -405,6 +465,7 @@
return with.run();
}
+
private boolean automaticGrowing = true;
private double automaticGrowingCapacityFactor = 1.7d;
private double automaticGrowingThreadshold = 0.8d;
@@ -491,6 +552,11 @@
accessor.getKeyPostingsRAF().seek(keyPostingOffset);
nextKeyPostingOffset = accessor.getKeyPostingsRAF().readInt();
+ int keyHashIn = accessor.getKeyPostingsRAF().readInt();
+ if (keyHash != keyHashIn) {
+ previousKeyPostingOffset = keyPostingOffset;
+ continue;
+ }
int partitionNumber = accessor.getKeyPostingsRAF().readInt();
int partitionOffset = accessor.getKeyPostingsRAF().readInt();
int keySize = accessor.getKeyPostingsRAF().readInt();
@@ -540,6 +606,16 @@
}
+ /**
+ * keypostings raf needs to be queued up when this method is called
+ *
+ * @param accessor
+ * @param nextKeyPostingOffset
+ * @param keyBuf
+ * @param valueBuf
+ * @param keyHashCode
+ * @throws IOException
+ */
private void writePostings(HashtableAccessor accessor, int nextKeyPostingOffset, byte[] keyBuf, byte[] valueBuf, int keyHashCode) throws IOException {
int partitionNumber = -1;
@@ -563,6 +639,9 @@
// int offset position in this file to the next key posting with the same hash, -1 = null
accessor.getKeyPostingsRAF().writeInt(nextKeyPostingOffset);
+ // key hash
+ accessor.getKeyPostingsRAF().writeInt(keyHashCode);
+
// int value partition number, -1 == null
accessor.getKeyPostingsRAF().writeInt(partitionNumber);
@@ -575,8 +654,6 @@
// key writable key
accessor.getKeyPostingsRAF().write(keyBuf);
- // key hash
- accessor.getKeyPostingsRAF().writeInt(keyHashCode);
}
@@ -618,6 +695,12 @@
previousKeyPostingOffset = keyPostingOffset;
nextKeyPostingOffset = accessor.getKeyPostingsRAF().readInt();
+ int keyHashIn = accessor.getKeyPostingsRAF().readInt();
+
+ if (keyHash != keyHashIn) {
+ continue;
+ }
+
int partitionNumber = accessor.getKeyPostingsRAF().readInt();
int partitionOffset = accessor.getKeyPostingsRAF().readInt();
@@ -664,6 +747,12 @@
previousKeyPostingOffset = keyPostingOffset;
nextKeyPostingOffset = accessor.getKeyPostingsRAF().readInt();
+ int keyHashIn = accessor.getKeyPostingsRAF().readInt();
+
+ if (keyHash != keyHashIn) {
+ continue;
+ }
+
int partitionNumber = accessor.getKeyPostingsRAF().readInt();
if (partitionNumber == -1) {
@@ -746,6 +835,11 @@
accessor.getKeyPostingsRAF().seek(keyPostingOffset);
nextKeyPostingOffset = accessor.getKeyPostingsRAF().readInt();
+ int keyHashIn = accessor.getKeyPostingsRAF().readInt();
+ if (keyHash != keyHashIn) {
+ previousKeyPostingOffset = keyPostingOffset;
+ continue;
+ }
int partitionNumber = accessor.getKeyPostingsRAF().readInt();
int partitionOffset = accessor.getKeyPostingsRAF().readInt();
int keySize = accessor.getKeyPostingsRAF().readInt();
@@ -777,13 +871,13 @@
// remove posting in key file
accessor.getKeyPostingsRAF().seek(keyPostingOffset);
accessor.getKeyPostingsRAF().writeInt(-2); // int next key posting offset at same hash position
+ accessor.getKeyPostingsRAF().writeInt(-2); // int key hash
accessor.getKeyPostingsRAF().writeInt(-2); // int value partition
accessor.getKeyPostingsRAF().writeInt(-2); // int value partition offset
accessor.getKeyPostingsRAF().writeInt(-2); // int key length // todo remove
- for (int i=0; i<keyClassHandler.getByteSize(); i++) {
+ for (int i = 0; i < keyClassHandler.getByteSize(); i++) {
accessor.getKeyPostingsRAF().writeByte(-2); // key
}
- accessor.getKeyPostingsRAF().writeInt(-2); // key hash
// update key file headers
@@ -863,7 +957,7 @@
byte[] keyBuf = new byte[keyClassHandler.getByteSize()];
int keyHash;
- for (int inputKeyPostingOffset = inputKeyPostingsFileHeader.getStartOffset(); inputKeyPostingOffset < inputKeyPostingsFileHeader.getNextOffset(); inputKeyPostingOffset+=keyPostingByteSize) {
+ 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();
@@ -873,6 +967,8 @@
continue;
}
+ // int key hash
+ keyHash = keyPostingsInput.readInt();
// int value partition number, -1 = null value
valuePartition = keyPostingsInput.readInt();
// int offset position in value partition, -1 = null
@@ -881,8 +977,6 @@
keyPostingsInput.readInt();
// byte[] serialized key (if not null)
keyPostingsInput.read(keyBuf);
- // int key hash, will be used for future rehashing
- keyHash = keyPostingsInput.readInt();
int outputHashtableOffset = outputHashtableFileHeader.getHashCodeTableOffset(keyHash);
@@ -897,6 +991,9 @@
// int offset position in this file to the next key posting with the same hash, -1 = null
keyPostingsOutput.writeInt(-1);
+ // key hash
+ keyPostingsOutput.writeInt(keyHash);
+
// int value partition number, -1 == null
keyPostingsOutput.writeInt(valuePartition);
@@ -909,8 +1006,6 @@
// key writable key
keyPostingsOutput.write(keyBuf);
- // key hash
- keyPostingsOutput.writeInt(keyHash);
hashtableOutput.seek(outputHashtableOffset);
hashtableOutput.writeByte(1);
@@ -931,9 +1026,6 @@
keyPostingsOutput.seek(keyPostingOffset);
nextKeyPostingOffset = keyPostingsOutput.readInt();
- int partitionNumber = keyPostingsOutput.readInt();
- int partitionOffset = keyPostingsOutput.readInt();
- int keySize = keyPostingsOutput.readInt();
previousKeyPostingOffset = keyPostingOffset;
depth++;
@@ -956,6 +1048,9 @@
// int offset position in this file to the next key posting with the same hash, -1 = null
keyPostingsOutput.writeInt(-1);
+ // key hash
+ keyPostingsOutput.writeInt(keyHash);
+
// int value partition number, -1 == null
keyPostingsOutput.writeInt(valuePartition);
@@ -968,8 +1063,6 @@
// key writable key
keyPostingsOutput.write(keyBuf);
- // key hash
- keyPostingsOutput.writeInt(keyHash);
keyPostingsOutput.seek(previousKeyPostingOffset);
keyPostingsOutput.writeInt(keyPostingOffset);
@@ -1258,7 +1351,7 @@
accessor.getKeyPostingsRAF().seek(keyPostingsCursor);
keyPostingsCursor = accessor.getKeyPostingsRAF().readInt(); // next entity
if (keyPostingsCursor != -1) {
- accessor.getKeyPostingsRAF().seek(keyPostingsCursor + 4);
+ accessor.getKeyPostingsRAF().seek(keyPostingsCursor + 8);
set();
return true;
}
@@ -1276,7 +1369,7 @@
byte isnull = accessor.getHashtableRAF().readByte();
if (isnull != 0) {
keyPostingsCursor = accessor.getHashtableRAF().readInt();
- accessor.getKeyPostingsRAF().seek(keyPostingsCursor + 4);
+ accessor.getKeyPostingsRAF().seek(keyPostingsCursor + 8);
set();
return true;
Modified: labs/bananadb/trunk/src/test/java/org/apache/labs/bananadb/hashtable/TestHashtable.java
URL: http://svn.apache.org/viewvc/labs/bananadb/trunk/src/test/java/org/apache/labs/bananadb/hashtable/TestHashtable.java?rev=754636&r1=754635&r2=754636&view=diff
==============================================================================
--- labs/bananadb/trunk/src/test/java/org/apache/labs/bananadb/hashtable/TestHashtable.java (original)
+++ labs/bananadb/trunk/src/test/java/org/apache/labs/bananadb/hashtable/TestHashtable.java Sun Mar 15 09:08:10 2009
@@ -56,6 +56,8 @@
String v2 = map.get(accessor, 1);
assertEquals(v, v2);
+ accessor.close();
+
// test cursor
accessor = map.createAccessor(false);
Hashtable<Integer, String>.Cursor cursor = map.new Cursor(accessor);
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@labs.apache.org
For additional commands, e-mail: commits-help@labs.apache.org