Author: elecharny
Date: Fri Jun 14 21:12:08 2013
New Revision: 1493248
URL: http://svn.apache.org/r1493248
Log:
o Added the lastOffset pointer in the Page
o Store the lastOffset in page referenceHolder
o Added some javadoc
o Improved the way we pdate the free page, leading to a gain of 25% n speed
o Improved the output of some tests to provide more realistic numbers
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/RecordManager.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ReferenceHolder.java
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/InMemoryBTreeTest.java
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java?rev=1493248&r1=1493247&r2=1493248&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java
Fri Jun 14 21:12:08 2013
@@ -47,9 +47,12 @@ import java.lang.reflect.Array;
/** The number of current values in the Page */
protected int nbElems;
- /** The Page offset on disk if the BTree is managed */
+ /** The first {@link PageIO} storing the serialized Page on disk */
private long offset;
+ /** The last {@link PageIO} storing the serialized Page on disk */
+ private long lastOffset;
+
/**
* Creates a default empty AbstractPage
@@ -290,7 +293,7 @@ import java.lang.reflect.Array;
/**
- * @return the offset
+ * {@inheritDoc}
*/
public long getOffset()
{
@@ -308,6 +311,24 @@ import java.lang.reflect.Array;
/**
+ * {@inheritDoc}
+ */
+ public long getLastOffset()
+ {
+ return lastOffset;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ /* No qualifier */void setLastOffset( long lastOffset )
+ {
+ this.lastOffset = lastOffset;
+ }
+
+
+ /**
* @see Object#toString()
*/
public String toString()
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java?rev=1493248&r1=1493247&r2=1493248&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java
Fri Jun 14 21:12:08 2013
@@ -1722,7 +1722,7 @@ public class BTree<K, V>
if ( value instanceof Page )
{
return new ReferenceHolder<Page<K, V>, K, V>( this, ( Page<K,
V> ) value,
- ( ( AbstractPage<K, V> ) value ).getOffset() );
+ ( ( Page ) value ).getOffset(), ( ( Page ) value
).getLastOffset() );
}
else if ( isAllowDuplicates() )
{
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java?rev=1493248&r1=1493247&r2=1493248&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
(original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
Fri Jun 14 21:12:08 2013
@@ -1019,9 +1019,11 @@ import org.apache.mavibot.btree.exceptio
page,
revision );
- // Store the offset on disk in the page in memory
+ // Store the offsets on disk in the page in memory
( ( AbstractPage<K, V> ) page ).setOffset( ( (
ReferenceHolder<Page<K, V>, K, V> ) holder )
.getOffset() );
+ ( ( AbstractPage<K, V> ) page ).setLastOffset( ( (
ReferenceHolder<Page<K, V>, K, V> ) holder )
+ .getLastOffset() );
return holder;
}
@@ -1220,13 +1222,13 @@ import org.apache.mavibot.btree.exceptio
public K getRightMostKey() throws EndOfFileExceededException, IOException
{
int index = ( nbElems + 1 ) - 1;
-
- if( children[index] != null )
+
+ if ( children[index] != null )
{
- return children[ index ].getValue( btree ).getRightMostKey();
+ return children[index].getValue( btree ).getRightMostKey();
}
-
- return children[ nbElems - 1 ].getValue( btree ).getRightMostKey();
+
+ return children[nbElems - 1].getValue( btree ).getRightMostKey();
}
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java?rev=1493248&r1=1493247&r2=1493248&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
(original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
Fri Jun 14 21:12:08 2013
@@ -29,7 +29,9 @@ import org.apache.mavibot.btree.exceptio
/**
* A MVCC Page interface. A Page can be either a Leaf (containing keys and
values) or a Node
- * (containing keys and references to child pages).
+ * (containing keys and references to child pages).<br/>
+ * A Page can be stored on disk. If so, we store the serialized value of this
Page into
+ * one or more {@link PageIO} (they will be linked)
*
* @param <K> The type for the Key
* @param <V> The type for the stored value
@@ -95,7 +97,7 @@ import org.apache.mavibot.btree.exceptio
*/
V get( K key ) throws KeyNotFoundException, IOException;
-
+
/**
* Gets the values associated with the given key, if any. If we don't have
* the key, this method will throw a KeyNotFoundException.<br/>
@@ -108,9 +110,9 @@ import org.apache.mavibot.btree.exceptio
* @throws IOException If we have an error while trying to access the page
* @throws IllegalArgumentException If duplicates are not enabled
*/
- BTree<V,V> getValues( K key ) throws KeyNotFoundException, IOException,
IllegalArgumentException;
+ BTree<V, V> getValues( K key ) throws KeyNotFoundException, IOException,
IllegalArgumentException;
+
-
/**
* Checks if the page contains the given key with the given value.
*
@@ -260,7 +262,13 @@ import org.apache.mavibot.btree.exceptio
/**
- * @return the offset
+ * @return the offset of the first {@link PageIO} which stores the Page on
disk.
*/
long getOffset();
+
+
+ /**
+ * @return the offset of the last {@link PageIO} which stores the Page on
disk.
+ */
+ long getLastOffset();
}
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/RecordManager.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/RecordManager.java?rev=1493248&r1=1493247&r2=1493248&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/RecordManager.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/RecordManager.java
Fri Jun 14 21:12:08 2013
@@ -630,8 +630,9 @@ public class RecordManager
{
// This is an Offset
long offset = OFFSET_SERIALIZER.deserialize( byteBuffer );
+ long lastOffset = OFFSET_SERIALIZER.deserialize( byteBuffer );
- ElementHolder valueHolder = new ReferenceHolder( btree, null,
offset );
+ ElementHolder valueHolder = new ReferenceHolder( btree, null,
offset, lastOffset );
( ( Node ) page ).setValue( i, valueHolder );
Object key = btree.getKeySerializer().deserialize( byteBuffer
);
@@ -640,8 +641,9 @@ public class RecordManager
// and read the last value, as it's a node
long offset = OFFSET_SERIALIZER.deserialize( byteBuffer );
+ long lastOffset = OFFSET_SERIALIZER.deserialize( byteBuffer );
- ElementHolder valueHolder = new ReferenceHolder( btree, null,
offset );
+ ElementHolder valueHolder = new ReferenceHolder( btree, null,
offset, lastOffset );
( ( Node ) page ).setValue( nodeNbElems, valueHolder );
}
@@ -928,6 +930,7 @@ public class RecordManager
// - the BTree name
// - the keySerializer FQCN
// - the valueSerializer FQCN
+ // - the flags that tell if the dups are allowed
// Starts at 0
long position = 0L;
@@ -1083,7 +1086,14 @@ public class RecordManager
if ( page instanceof Node )
{
Page child = ( ( Node ) page ).getReference( pos );
- buffer = LongSerializer.serialize( ( ( AbstractPage )
child ).getOffset() );
+
+ // The first offset
+ buffer = LongSerializer.serialize( child.getOffset() );
+ serializedData.add( buffer );
+ dataSize += buffer.length;
+
+ // The last offset
+ buffer = LongSerializer.serialize( child.getLastOffset() );
serializedData.add( buffer );
dataSize += buffer.length;
}
@@ -1115,7 +1125,14 @@ public class RecordManager
if ( page instanceof Node )
{
Page child = ( ( Node ) page ).getReference( nbElems );
- buffer = LongSerializer.serialize( ( ( AbstractPage ) child
).getOffset() );
+
+ // The first offset
+ buffer = LongSerializer.serialize( child.getOffset() );
+ serializedData.add( buffer );
+ dataSize += buffer.length;
+
+ // The last offset
+ buffer = LongSerializer.serialize( child.getOffset() );
serializedData.add( buffer );
dataSize += buffer.length;
}
@@ -1166,7 +1183,7 @@ public class RecordManager
HEADER_BUFFER.rewind();
LOG.debug( "Update RM header, FF : {}, LF : {}", firstFreePage,
lastFreePage );
- fileChannel.write( HEADER_BUFFER, 0L );
+ fileChannel.write( HEADER_BUFFER, 0 );
}
@@ -1612,7 +1629,9 @@ public class RecordManager
flushPages( pageIos );
// Build the resulting reference
- ElementHolder valueHolder = new ReferenceHolder( btree, newPage,
pageIos[0].getOffset() );
+ long offset = pageIos[0].getOffset();
+ long lastOffset = pageIos[pageIos.length - 1].getOffset();
+ ElementHolder valueHolder = new ReferenceHolder( btree, newPage,
offset, lastOffset );
return valueHolder;
}
@@ -2004,28 +2023,14 @@ public class RecordManager
for ( Page page : pages )
{
// Retrieve all the PageIO associated with this logical page
- long pageIoOffset = page.getOffset();
- long firstPageIoOffset = page.getOffset();
- long lastPageIoOffset = NO_PAGE;
-
- // Iterate on the pageIOs
- while ( pageIoOffset != NO_PAGE )
- {
- // Keep a track of the current page
- lastPageIoOffset = pageIoOffset;
-
- // Retrieve the first physical page from disk
- PageIO pageIo = fetchPage( pageIoOffset );
-
- // Get the next offset
- pageIoOffset = pageIo.getNextPage();
- }
+ long firstOffset = page.getOffset();
+ long lastOffset = page.getLastOffset();
// Update the pointers
if ( firstFreePage == NO_PAGE )
{
- firstFreePage = firstPageIoOffset;
- lastFreePage = lastPageIoOffset;
+ firstFreePage = firstOffset;
+ lastFreePage = lastOffset;
}
else
{
@@ -2033,7 +2038,7 @@ public class RecordManager
PageIO previousLastFreePage = fetchPage( lastFreePage );
// update its pointer to the next free pageIo
- previousLastFreePage.setNextPage( firstPageIoOffset );
+ previousLastFreePage.setNextPage( firstOffset );
LOG.debug( "Flushing the last free page" );
@@ -2041,12 +2046,12 @@ public class RecordManager
flushPages( previousLastFreePage );
// We can update the lastFreePage offset
- lastFreePage = lastPageIoOffset;
+ lastFreePage = lastOffset;
}
-
- // Last, not least, flush the header
- updateRecordManagerHeader();
}
+
+ // Last, not least, flush the header
+ updateRecordManagerHeader();
}
else
{
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ReferenceHolder.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ReferenceHolder.java?rev=1493248&r1=1493247&r2=1493248&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ReferenceHolder.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ReferenceHolder.java
Fri Jun 14 21:12:08 2013
@@ -42,9 +42,12 @@ public class ReferenceHolder<E, K, V> im
/** The BTree */
private BTree<K, V> btree;
- /** The offset for a value stored on disk */
+ /** The offset of the first {@link PageIO} storing the page on disk */
private long offset;
+ /** The offset of the last {@link PageIO} storing the page on disk */
+ private long lastOffset;
+
/** The reference to the element instance, or null if it's not present */
private SoftReference<E> reference;
@@ -55,10 +58,11 @@ public class ReferenceHolder<E, K, V> im
* @param offset The offset in disk for this value
* @param element The element to store into a SoftReference
*/
- public ReferenceHolder( BTree<K, V> btree, E element, long offset )
+ public ReferenceHolder( BTree<K, V> btree, E element, long offset, long
lastOffset )
{
this.btree = btree;
this.offset = offset;
+ this.lastOffset = lastOffset;
this.reference = new SoftReference<E>( element );
}
@@ -98,6 +102,9 @@ public class ReferenceHolder<E, K, V> im
}
+ /**
+ * @return The offset of the first {@link PageIO} storing the data on disk
+ */
/* No qualifier */long getOffset()
{
return offset;
@@ -105,6 +112,15 @@ public class ReferenceHolder<E, K, V> im
/**
+ * @return The offset of the last {@link PageIO} storing the data on disk
+ */
+ /* No qualifier */long getLastOffset()
+ {
+ return lastOffset;
+ }
+
+
+ /**
* @see Object#toString()
*/
public String toString()
Modified:
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/InMemoryBTreeTest.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/InMemoryBTreeTest.java?rev=1493248&r1=1493247&r2=1493248&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/InMemoryBTreeTest.java
(original)
+++
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/InMemoryBTreeTest.java
Fri Jun 14 21:12:08 2013
@@ -238,7 +238,7 @@ public class InMemoryBTreeTest
long l2 = System.currentTimeMillis();
System.out.println( "Delta : " + ( l2 - l1 ) + ", nbError = " + nbError
- + ", Nb insertion per second : " + ( nbTrees * nbElems ) / ( ( l2
- l1 ) / 1000 ) );
+ + ", Nb insertion per second : " + ( nbTrees * nbElems * 1000 ) /
( l2 - l1 ) );
}
@@ -360,7 +360,7 @@ public class InMemoryBTreeTest
long l2 = System.currentTimeMillis();
System.out.println( "Delta : " + ( l2 - l1 ) + ", nbError = " + nbError
- + ", Nb deletion per second : " + ( nbTrees * nbElems ) / ( ( l2 -
l1 ) / 1000 ) );
+ + ", Nb deletion per second : " + ( nbTrees * nbElems * 1000 ) / (
l2 - l1 ) );
}
@@ -1804,7 +1804,7 @@ public class InMemoryBTreeTest
long l2 = System.currentTimeMillis();
System.out.println( "Delta : " + ( l2 - l1 ) + ", nbError = " + nbError
- + ", Nb searches per second : " + ( ( nbElems ) / ( l2 - l1 ) ) *
1000 );
+ + ", Nb searches per second : " + ( ( nbElems * 1000 ) / ( l2 - l1
) ) );
}
@@ -1834,7 +1834,8 @@ public class InMemoryBTreeTest
// expected
}
}
-
+
+
/**
* Test a browse forward and backward
*/
@@ -1873,7 +1874,7 @@ public class InMemoryBTreeTest
assertFalse( cursor.hasNext() );
assertTrue( cursor.hasPrev() );
-
+
// Lets go backward. We should get the same value, as the next() call
have incremented the counter
assertEquals( 12, cursor.prev().getKey().intValue() );
@@ -1889,13 +1890,14 @@ public class InMemoryBTreeTest
// Get 8
assertEquals( 8, cursor.prev().getKey().intValue() );
- assertFalse(cursor.hasPrev());
- assertTrue(cursor.hasNext());
-
+ assertFalse( cursor.hasPrev() );
+ assertTrue( cursor.hasNext() );
+
cursor.close();
btree.close();
}
+
@Test
public void testNextAfterPrev() throws Exception
{
@@ -1908,19 +1910,19 @@ public class InMemoryBTreeTest
BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
int i = 7;
- for ( int k=0; k < i; k++ )
+ for ( int k = 0; k < i; k++ )
{
btree.insert( k, k );
}
-
+
// 3 is the last element of the first leaf
- Cursor<Integer, Integer> cursor = btree.browseFrom(4);
+ Cursor<Integer, Integer> cursor = btree.browseFrom( 4 );
assertTrue( cursor.hasNext() );
Tuple<Integer, Integer> tuple = cursor.next();
assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
-
+
assertTrue( cursor.hasPrev() );
tuple = cursor.prev();
assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
@@ -1931,6 +1933,6 @@ public class InMemoryBTreeTest
assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
cursor.close();
- }
-
+ }
+
}
Modified:
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java?rev=1493248&r1=1493247&r2=1493248&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java
(original)
+++
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java
Fri Jun 14 21:12:08 2013
@@ -237,11 +237,11 @@ public class LeafTest
right = insert( right, 13L, "v13" );
parent.children[0] = new ReferenceHolder<Page<Long, String>, Long,
String>( null, left,
- ( ( AbstractPage<Long, String> ) left ).getOffset() );
+ left.getOffset(), left.getLastOffset() );
parent.children[1] = new ReferenceHolder<Page<Long, String>, Long,
String>( null, target,
- ( ( AbstractPage<Long, String> ) target ).getOffset() );
+ target.getOffset(), target.getLastOffset() );
parent.children[2] = new ReferenceHolder<Page<Long, String>, Long,
String>( null, right,
- ( ( AbstractPage<Long, String> ) right ).getOffset() );
+ right.getOffset(), right.getLastOffset() );
// Update the parent
parent.keys[0] = 6L;
@@ -310,11 +310,11 @@ public class LeafTest
right = insert( right, 14L, "v14" );
parent.children[0] = new ReferenceHolder<Page<Long, String>, Long,
String>( null, left,
- ( ( AbstractPage<Long, String> ) left ).getOffset() );
+ left.getOffset(), left.getLastOffset() );
parent.children[1] = new ReferenceHolder<Page<Long, String>, Long,
String>( null, target,
- ( ( AbstractPage<Long, String> ) target ).getOffset() );
+ target.getOffset(), target.getLastOffset() );
parent.children[2] = new ReferenceHolder<Page<Long, String>, Long,
String>( null, right,
- ( ( AbstractPage<Long, String> ) right ).getOffset() );
+ right.getOffset(), right.getLastOffset() );
// Update the parent
parent.keys[0] = 6L;
@@ -383,11 +383,11 @@ public class LeafTest
right = insert( right, 12L, "v12" );
parent.children[0] = new ReferenceHolder<Page<Long, String>, Long,
String>( null, left,
- ( ( AbstractPage<Long, String> ) left ).getOffset() );
+ left.getOffset(), left.getLastOffset() );
parent.children[1] = new ReferenceHolder<Page<Long, String>, Long,
String>( null, target,
- ( ( AbstractPage<Long, String> ) target ).getOffset() );;
+ target.getOffset(), target.getLastOffset() );;
parent.children[2] = new ReferenceHolder<Page<Long, String>, Long,
String>( null, right,
- ( ( AbstractPage<Long, String> ) right ).getOffset() );
+ right.getOffset(), right.getLastOffset() );
// Update the parent
parent.keys[0] = 5L;
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
