BTreeTxnTest.cpp

Go to the documentation of this file.
00001 /*
00002 // $Id: //open/dev/fennel/test/BTreeTxnTest.cpp#15 $
00003 // Fennel is a library of data storage and processing components.
00004 // Copyright (C) 2005-2009 The Eigenbase Project
00005 // Copyright (C) 2005-2009 SQLstream, Inc.
00006 // Copyright (C) 2005-2009 LucidEra, Inc.
00007 // Portions Copyright (C) 1999-2009 John V. Sichi
00008 //
00009 // This program is free software; you can redistribute it and/or modify it
00010 // under the terms of the GNU General Public License as published by the Free
00011 // Software Foundation; either version 2 of the License, or (at your option)
00012 // any later version approved by The Eigenbase Project.
00013 //
00014 // This program is distributed in the hope that it will be useful,
00015 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00016 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00017 // GNU General Public License for more details.
00018 //
00019 // You should have received a copy of the GNU General Public License
00020 // along with this program; if not, write to the Free Software
00021 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00022 */
00023 
00024 #include "fennel/common/CommonPreamble.h"
00025 #include "fennel/test/SegStorageTestBase.h"
00026 #include "fennel/test/ThreadedTestBase.h"
00027 #include "fennel/btree/BTreeWriter.h"
00028 #include "fennel/btree/BTreeBuilder.h"
00029 #include "fennel/btree/BTreeVerifier.h"
00030 #include "fennel/btree/BTreeRecoveryFactory.h"
00031 #include "fennel/txn/LogicalTxnLog.h"
00032 #include "fennel/txn/LogicalTxn.h"
00033 #include "fennel/tuple/StandardTypeDescriptor.h"
00034 #include "fennel/db/Database.h"
00035 #include "fennel/db/CheckpointThread.h"
00036 #include "fennel/cache/Cache.h"
00037 #include "fennel/cache/CacheParams.h"
00038 #include "fennel/synch/SXMutex.h"
00039 
00040 #include <boost/test/test_tools.hpp>
00041 #include <boost/scoped_ptr.hpp>
00042 
00043 #include <functional>
00044 
00045 using namespace fennel;
00046 
00047 // TODO:  factor out BTreeTestBase
00048 
00049 class BTreeTxnTest
00050     : virtual public ThreadedTestBase
00051 {
00052     struct TestThreadData
00053     {
00054         std::subtractive_rng randomNumberGenerator;
00055         SharedBTreeReader pReader;
00056         SharedBTreeWriter pWriter;
00057         TupleData keyData;
00058     };
00059 
00063     enum OpType {
00064         OP_INSERT,
00065         OP_DELETE,
00066         OP_SCAN,
00067         OP_CHECKPOINT,
00068         OP_MAX
00069     };
00070 
00071     // NOTE:  this matches the Fennel Tuple format, so it can be used
00072     // directly for input into BTreeWriter
00073     struct Record
00074     {
00075         int32_t key;
00076         int32_t value;
00077     };
00078     SharedCache pCache;
00079     SharedDatabase pDatabase;
00080 
00081     BTreeDescriptor treeDescriptor;
00082 
00083     boost::thread_specific_ptr<TestThreadData> pTestThreadData;
00084     PageId rootPageId;
00085 
00086     bool testRollback;
00087     uint iKeyMax;
00088     uint nInsertsPerTxn;
00089     uint nDeletesPerTxn;
00090     uint nKeysPerScan;
00091 
00092     uint nSecondsBetweenCheckpoints;
00093 
00094     void testTxns();
00095 
00096     void insertTxn();
00097     void deleteTxn();
00098     void scanTxn();
00099     void testCheckpoint();
00100 
00101     void endTxn(SharedLogicalTxn pTxn);
00102 
00103     uint generateRandomNumber(uint iMax);
00104 
00105     void createTree();
00106     RecordNum verifyTree();
00107     BTreeReader &getReader();
00108     BTreeWriter &getWriter();
00109     TupleData &getKeyData();
00110     void bindKey(int32_t &key);
00111 
00112 public:
00113     explicit BTreeTxnTest();
00114 
00115     virtual void testCaseSetUp();
00116     virtual void testCaseTearDown();
00117 
00118     virtual void threadInit();
00119     virtual void threadTerminate();
00120     virtual bool testThreadedOp(int iOp);
00121 };
00122 
00123 BTreeTxnTest::BTreeTxnTest()
00124 {
00125     nInsertsPerTxn = configMap.getIntParam("insertsPerTxn",5);
00126     nDeletesPerTxn = configMap.getIntParam("deletesPerTxn",5);
00127     nKeysPerScan = configMap.getIntParam("keysPerScan",5);
00128     iKeyMax = configMap.getIntParam("maxKey",1000000);
00129     nSecondsBetweenCheckpoints = configMap.getIntParam("checkpointInterval",20);
00130     testRollback = configMap.getIntParam(
00131         "testRollback",1);
00132 
00133     threadCounts.resize(OP_MAX,-1);
00134 
00135     threadCounts[OP_INSERT] = configMap.getIntParam(
00136         "insertThreads",-1);
00137     threadCounts[OP_DELETE] = configMap.getIntParam(
00138         "deleteThreads",-1);
00139     threadCounts[OP_SCAN] = configMap.getIntParam(
00140         "scanThreads",-1);
00141 
00142     if (nSecondsBetweenCheckpoints < nSeconds) {
00143         threadCounts[OP_CHECKPOINT] = 1;
00144     } else {
00145         threadCounts[OP_CHECKPOINT] = 0;
00146     }
00147 
00148     FENNEL_UNIT_TEST_CASE(BTreeTxnTest,testTxns);
00149 }
00150 
00151 void BTreeTxnTest::testCaseSetUp()
00152 {
00153     // TODO:  cleanup
00154 
00155     configMap.setStringParam(
00156         Database::paramDatabaseDir,".");
00157     configMap.setStringParam(
00158         "databaseInitSize","1000");
00159     configMap.setStringParam(
00160         "tempInitSize","1000");
00161     configMap.setStringParam(
00162         "databaseShadowLogInitSize","2000");
00163     if (!configMap.isParamSet("databaseTxnLogInitSize")) {
00164         configMap.setStringParam(
00165             "databaseTxnLogInitSize","2000");
00166     }
00167 
00168     CacheParams cacheParams;
00169     cacheParams.readConfig(configMap);
00170     pCache = Cache::newCache(cacheParams);
00171     pDatabase = Database::newDatabase(
00172         pCache,
00173         configMap,
00174         DeviceMode::createNew,
00175         shared_from_this());
00176 
00177     statsTimer.addSource(pDatabase);
00178     statsTimer.start();
00179 
00180     rootPageId = NULL_PAGE_ID;
00181     createTree();
00182     pDatabase->checkpointImpl();
00183 }
00184 
00185 void BTreeTxnTest::testCaseTearDown()
00186 {
00187     statsTimer.stop();
00188 
00189     pDatabase.reset();
00190     pCache.reset();
00191 }
00192 
00193 void BTreeTxnTest::createTree()
00194 {
00195     TupleDescriptor &tupleDesc = treeDescriptor.tupleDescriptor;
00196     StandardTypeDescriptorFactory stdTypeFactory;
00197     TupleAttributeDescriptor attrDesc(
00198         stdTypeFactory.newDataType(STANDARD_TYPE_INT_32));
00199     tupleDesc.push_back(attrDesc);
00200     tupleDesc.push_back(attrDesc);
00201     TupleProjection &keyProj = treeDescriptor.keyProjection;
00202     keyProj.push_back(0);
00203 
00204     treeDescriptor.segmentAccessor.pSegment = pDatabase->getDataSegment();
00205     treeDescriptor.segmentAccessor.pCacheAccessor = pCache;
00206     treeDescriptor.rootPageId = rootPageId;
00207 
00208     BTreeBuilder builder(treeDescriptor,pDatabase->getDataSegment());
00209     builder.createEmptyRoot();
00210     treeDescriptor.rootPageId = builder.getRootPageId();
00211 }
00212 
00213 void BTreeTxnTest::threadInit()
00214 {
00215     ThreadedTestBase::threadInit();
00216     pTestThreadData.reset(new TestThreadData());
00217     pTestThreadData->pReader.reset(new BTreeReader(treeDescriptor));
00218     pTestThreadData->keyData.compute(getReader().getKeyDescriptor());
00219 
00220     SegmentAccessor scratchAccessor =
00221         pDatabase->getSegmentFactory()->newScratchSegment(
00222             pCache,
00223             1);
00224 
00225     pTestThreadData->pWriter.reset(
00226         new BTreeWriter(treeDescriptor,scratchAccessor));
00227 }
00228 
00229 void BTreeTxnTest::threadTerminate()
00230 {
00231     pTestThreadData.reset();
00232     ThreadedTestBase::threadTerminate();
00233 }
00234 
00235 uint BTreeTxnTest::generateRandomNumber(uint iMax)
00236 {
00237     return pTestThreadData->randomNumberGenerator(iMax);
00238 }
00239 
00240 BTreeReader &BTreeTxnTest::getReader()
00241 {
00242     return *(pTestThreadData->pReader);
00243 }
00244 
00245 TupleData &BTreeTxnTest::getKeyData()
00246 {
00247     return pTestThreadData->keyData;
00248 }
00249 
00250 BTreeWriter &BTreeTxnTest::getWriter()
00251 {
00252     return *(pTestThreadData->pWriter);
00253 }
00254 
00255 // NOTE: eventually this will fail due to non-serializability (if an
00256 // insert/delete sequence affecting the same key is reordered during recovery).
00257 // Need to add locking support.
00258 
00259 void BTreeTxnTest::testTxns()
00260 {
00261     runThreadedTestCase();
00262     RecordNum nEntries = verifyTree();
00263     pDatabase->checkpointImpl(CHECKPOINT_DISCARD);
00264 
00265     statsTimer.stop();
00266     pDatabase.reset();
00267     pDatabase = Database::newDatabase(
00268         pCache,
00269         configMap,
00270         DeviceMode::load,
00271         shared_from_this());
00272     BOOST_CHECK(pDatabase->isRecoveryRequired());
00273 
00274     StandardTypeDescriptorFactory typeFactory;
00275     SegmentAccessor scratchAccessor =
00276         pDatabase->getSegmentFactory()->newScratchSegment(
00277             pCache,
00278             1);
00279     SegmentAccessor segmentAccessor(pDatabase->getDataSegment(),pCache);
00280     BTreeRecoveryFactory btreeRecoveryFactory(
00281         segmentAccessor,
00282         scratchAccessor,
00283         typeFactory);
00284     segmentAccessor.reset();
00285     scratchAccessor.reset();
00286     pDatabase->recover(btreeRecoveryFactory);
00287 
00288     // Don't restart the stats timer until after recovery has completed.
00289     statsTimer.addSource(pDatabase);
00290     statsTimer.start();
00291 
00292     treeDescriptor.segmentAccessor.pSegment = pDatabase->getDataSegment();
00293     RecordNum nEntriesRecovered = verifyTree();
00294 
00295     // FIXME jvs 8-Mar-2004:  Turn this back on once NOTE above is taken
00296     // care of.  Tautological checks are just to shut warnings up.
00297 
00298     // BOOST_CHECK_EQUAL(nEntries,nEntriesRecovered);
00299     BOOST_CHECK_EQUAL(nEntries,nEntries);
00300     BOOST_CHECK_EQUAL(nEntriesRecovered,nEntriesRecovered);
00301 }
00302 
00303 void BTreeTxnTest::insertTxn()
00304 {
00305     SharedLogicalTxn pTxn = pDatabase->getTxnLog()->newLogicalTxn(pCache);
00306     pTxn->addParticipant(pTestThreadData->pWriter);
00307     BTreeWriter &writer = getWriter();
00308     for (uint i = 0; i < nInsertsPerTxn; ++i) {
00309         Record record;
00310         record.key = generateRandomNumber(iKeyMax);
00311         record.value = generateRandomNumber(iKeyMax);
00312         // TODO:  test with and without duplicates
00313         writer.insertTupleFromBuffer(
00314             reinterpret_cast<PConstBuffer>(&record),DUP_DISCARD);
00315     }
00316     endTxn(pTxn);
00317 }
00318 
00319 void BTreeTxnTest::deleteTxn()
00320 {
00321     SharedLogicalTxn pTxn = pDatabase->getTxnLog()->newLogicalTxn(pCache);
00322     pTxn->addParticipant(pTestThreadData->pWriter);
00323     BTreeWriter &writer = getWriter();
00324     for (uint i = 0; i < nDeletesPerTxn; ++i) {
00325         int32_t key = generateRandomNumber(iKeyMax);
00326         bindKey(key);
00327         if (writer.searchForKey(getKeyData(),DUP_SEEK_ANY)) {
00328             writer.deleteCurrent();
00329         }
00330         writer.endSearch();
00331     }
00332     endTxn(pTxn);
00333 }
00334 
00335 void BTreeTxnTest::scanTxn()
00336 {
00337     BTreeReader &reader = getReader();
00338     int32_t key = generateRandomNumber(iKeyMax);
00339     bindKey(key);
00340     if (reader.searchForKey(getKeyData(),DUP_SEEK_ANY)) {
00341         for (uint i = 0; i < nKeysPerScan; ++i) {
00342             if (!reader.searchNext()) {
00343                 break;
00344             }
00345         }
00346     }
00347     reader.endSearch();
00348 }
00349 
00350 void BTreeTxnTest::endTxn(SharedLogicalTxn pTxn)
00351 {
00352     if (testRollback) {
00353         if (generateRandomNumber(2)) {
00354             pTxn->commit();
00355         } else {
00356             pTxn->rollback();
00357         }
00358     } else {
00359         pTxn->commit();
00360     }
00361 }
00362 
00363 bool BTreeTxnTest::testThreadedOp(int iOp)
00364 {
00365     SXMutexSharedGuard checkpointSharedGuard(
00366         pDatabase->getCheckpointThread()->getActionMutex(),false);
00367     assert(iOp < OP_MAX);
00368     OpType op = static_cast<OpType>(iOp);
00369     switch (op) {
00370     case OP_INSERT:
00371         checkpointSharedGuard.lock();
00372         insertTxn();
00373         break;
00374     case OP_DELETE:
00375         checkpointSharedGuard.lock();
00376         deleteTxn();
00377         break;
00378     case OP_SCAN:
00379         scanTxn();
00380         break;
00381     case OP_CHECKPOINT:
00382         testCheckpoint();
00383         break;
00384     default:
00385         permAssert(false);
00386     }
00387     return true;
00388 }
00389 
00390 void BTreeTxnTest::bindKey(int32_t &key)
00391 {
00392     getKeyData()[0].pData = reinterpret_cast<PConstBuffer>(&key);
00393 }
00394 
00395 void BTreeTxnTest::testCheckpoint()
00396 {
00397     snooze(nSecondsBetweenCheckpoints);
00398     CheckpointType checkpointType;
00399     if (configMap.getIntParam("fuzzyCheckpoint",1)) {
00400         checkpointType = CHECKPOINT_FLUSH_FUZZY;
00401     } else {
00402         checkpointType = CHECKPOINT_FLUSH_ALL;
00403     }
00404     pDatabase->requestCheckpoint(checkpointType,false);
00405 }
00406 
00407 RecordNum BTreeTxnTest::verifyTree()
00408 {
00409     BTreeVerifier verifier(treeDescriptor);
00410     verifier.verify(false);
00411 
00412     BTreeStatistics const &stats = verifier.getStatistics();
00413     BOOST_MESSAGE("height = " << stats.nLevels);
00414     BOOST_MESSAGE("record count = " << stats.nTuples);
00415     BOOST_MESSAGE("leaf nodes = " << stats.nLeafNodes);
00416     BOOST_MESSAGE("nonleaf nodes = " << stats.nNonLeafNodes);
00417     return stats.nTuples;
00418 }
00419 
00420 FENNEL_UNIT_TEST_SUITE(BTreeTxnTest);
00421 
00422 // End BTreeTxnTest.cpp

Generated on Mon Jun 22 04:00:20 2009 for Fennel by  doxygen 1.5.1