fastdb.htm

实现内存数据库的源代码

current. If there is no next record, then the previous record
(if it exists)  becomes the current. The method <code>removeAll()</code>
removes all records in the table.
Whereas the method <code>removeAllSelected</code> only removes 
all records selected by the cursor.<P>

When records are updated, the size of the database may increase.
Thus an extension of the database section in the virtual memory 
is needed. As a result of such remapping, base addresses of the section can be
changed and all pointers to database fields kept by applications will become 
invalid. FastDB automatically updates current records in all opened 
cursors when a database section is remapped. So, when a database is updated, 
the programmer should access record fields only through the cursor 
<code>-&gt;</code> method. She/he should  not use pointer variables.<P>

Memory used for the current selection can be released by the
<code>reset()</code> method.
This method is automatically called by the <code>select(), 
dbDatabase::commit(), dbDatabase::rollback()</code> methods
and the cursor destructor, so in most cases there is no need to
call the <code>reset()</code> method explicitly.<P>

Cursors can also be used to access records by reference. The method
<code>at(dbReference&lt;T&gt; const& ref)</code> sets the cursor to the record
pointed to by the reference. In this case, the selection consists exactly of
one record and the <code>next(), prev()</code> methods will always return 
<code>NULL</code>. Since cursors and references in FastDB are strictly 
typed, all necessary checking can be done statically by the compiler and 
no dynamic type checking is needed. The only kind of checking,
which is done at runtime, is checking for null references.
The object identifier of the current record in the cursor can be obtained by
the <code>currentId()</code> method.<P> 

It is possible to restrict the number of records returned by a select statement.
The cursor class has the two methods
<code>setSelectionLimit(size_t lim)</code> and
<code>unsetSelectionLimit()</code>,
which can be used to set/unset the limit
of numbers of records returned by the query. In some situations,
a  programmer may want to receive
only one record or only few first records;  so the query execution
time and size of consumed memory can be reduced by limiting the size of 
selection. But if you specify an order for selected records, 
the query with the restriction to 
<I>k</I> records will not return the first <I>k</I> records
with the smallest value of the key. Instead of this, arbitrary <I>k</I>
records will be taken and then sorted.<P>

So all operations with database data can be performed by means of
cursors. The only exception is the insert operation, for which 
FastDB provides an overloaded insert function:

<PRE>
        template&lt;class T&gt;
        dbReference&lt;T&gt; insert(T const& record);
</PRE>

This function will insert a record at the end of the table and return
a reference of the created object.
The order of insertion is strictly specified in FastDB
and applications can use this assumption about the record order in the
table. For applications widely using references for navigation between
objects, it is necessary to have some <I>root</I> object, from which a
traversal by references can be made. A good candidate for such root object
is the first record in the table (it is also the oldest record in the 
table). This record can be accessed by execution of the <code>select()</code>
method without parameter. The current record in the cursor will
be the first record in the table.<P>


The C++ API of FastDB defines a special <code>null</code> variable
of reference type.
It is possible to compare the <code>null</code> variable with references 
or assign it to the reference:<P>

<PRE>
        void update(dbReference&lt;Contract&gt; c) {
            if (c != null) { 
	        dbCursor&lt;Contract&gt; contract(dbCursorForUpdate);
		contract.at(c);
		contract-&gt;supplier = null;
            }
        }
</PRE>


Query parameters usually are bound to C++ variables. In most cases in is convenient and 
flexible mechanism. But in multithreaded application, there is no warranty that the same 
query will not be executed at the same moment of time by another thread with different values
of parameters. One solution is to use synchronization primitives (critical sections or mutexes)
to prevent concurrent execution of the query. But this will lead to performance degradation.
FastDB is able to perform read requests in parallel, increasing total system throughput.
The other solution is to use delayed parameter binding. This approach is illustrated by the 
following example:<P>  

<PRE>
dbQuery q;

struct QueryParams { 
    int         salary;
    int         age;
    int         rank;
};

void open()
{
    QueryParams* params = (QueryParams*)NULL;
    q = "salary > ", params->salary, "and age < ", params->age, "and rank =", params->rank;
}

void find(int salary, int age, int rank) 
{ 
    QueryParams params;
    params.salary = salary;
    params.age = age;
    params.rank = rank;
    dbCursor&lt;Person&gt; cusor;
    if (cursor.select(q, &params) &gt; 0) { 
        do { 
	    cout &lt;&lt; cursor->name &lt;&lt; NL;
        } while (cursor.next());
    }
}
</PRE>

So in this example function <code>open</code> binds query parameters just to offsets of 
fields in structure. Later in <code>find</code> functions, actual pointer to the structure
with parameters is passed to the <code>select</code> structure. Function <code>find</code>
can be concurrently executed by several threads and only one compiled version of the query
is used by all these threads. This mechanism is available since version 2.25.<P>


<H3><A NAME = "database">Database</A></H3>
The class <code>dbDatabase</code> controls the application interactions
with the database. It performs synchronization of concurrent accesses to the
database, transaction management, memory allocation, error handling,...<P>

The constructor of <code>dbDatabase</code> objects allows programmers to specify
some database parameters:

<PRE>
    dbDatabase(dbAccessType type = dbAllAccess,
	       size_t dbInitSize = dbDefaultInitDatabaseSize,
	       size_t dbExtensionQuantum = dbDefaultExtensionQuantum,
	       size_t dbInitIndexSize = dbDefaultInitIndexSize,
	       int nThreads = 1);
</PRE>

A database can be opened in readonly mode (<code>dbDatabase::dbReadOnly</code>
access type) or in normal mode, allowing modification of the database 
(<code>dbDatabase::dbAllAccess</code>). When the database is opened in readonly 
mode, no new class definitions can be added to the database and definitions
of existing classes and indices can not be altered.<P>

The parameter
<code>dbInitSize</code> specifies the initial size of the database file.
The database file increases on demand; setting the initial size can only 
reduce the number of reallocations (which can take a lot of time).
In the current implementation of the FastDB database
the size is at least doubled at each extension.
The default value of this parameter is 4 megabytes.<P>

The parameter <code>dbExtensionQuantum</code>
specifies the quantum of extension of the
memory allocation bitmap. 
Briefly speaking, the value of this parameter specifies how much memory
will be allocated sequentially without attempt to reuse space of
deallocated objects. The default value of this parameter is 4 Mb.
See section <A HREF="#memory">Memory allocation</A> for more details.<P> 

The parameter <code>dbInitIndexSize</code> specifies the initial index size. 
All objects in FastDB are accessed through an object index.
There are two copies of this object index:
current and committed. Object indices are reallocated on 
demand; setting an initial index size can only reduce (or increase)
the number of reallocations. The default value of this parameter is 64K object 
identifiers.<P>

And the last parameter <code>nThreads</code> controls the level of query
parallelization. If it is greater than 1, then FastDB can start the parallel
execution of some queries (including sorting the result). 
The specified number of parallel threads will
be spawned by the FastDB engine in this case. Usually it does not make
sense to specify the value of this parameter to be greater than the
number of online CPUs in the system. It is also possible to pass zero
as the value of this parameter. In this case, FastDB will automatically detect
the number of online CPUs in the system. The number of threads also can be set 
by the <code>dbDatabase::setConcurrency</code> method at any moment of time.<P>

The class <code>dbDatabase</code> contains a static field 
<code>dbParallelScanThreshold</code>, which specifies a threshold for the
number of records in the table after which query parallelization
is used. The default value of this parameter is 1000.<P>

The database can be opened by the
<code>open(char const* databaseName, char const* fileName = NULL, unsigned waitLockTimeout = INFINITE)</code> method.
If the file name parameter is omitted, it is constructed from
the database name by appending the ".fdb" suffix. The database name should
be an arbitrary identifier consisting of any symbols except '\'.
The last parameter <code>waitLockTimeout</code> can be set to prevent locking of all
active processes working with the database when some of them is crashed.
If the crashed process had locked the database, then no other process can continue 
execution. To prevent it, you can specify maximal delay for waiting for the lock, 
after expiration of which system will try to perform recovery and continue execution
of active processes.
The method&nbsp;<code>open</code> returns <code>true</code> if the database was
successfully opened; or <code>false</code> if the open operation failed. 
In the last case, the database <code>handleError</code> method is called with a
<code>DatabaseOpenError</code> error code. A database session can be terminated
by the <code>close</code> method, which implicitly commits current transactions.<P>

In a multithreaded application each thread, which wants to access the database,
should first be attached to it. The method <code>dbDatabase::attach()</code>
allocates thread specific data and attaches the thread to the database.
This method is automatically called by the <code>open()</code> method, so
there is no reason to call the <code>attach()</code> method for the thread,
which opens the database. When the thread finishes work with the database, it should
call the <code>dbDatabase::detach()</code> method. The method 
<code>close</code> automatically invokes the <code>detach()</code> method. 
The method <code>detach()</code> implicitly commits current transactions.
An attempt to access a database by a detached thread causes an assertion failure.<P>

FastDB is able to perform compilation and execution of queries in parallel, 
providing significant increase of performance in multiprocessor systems.
But concurrent updates of the database are not possible (this is the price
for the efficient log-less transaction mechanism and zero time recovery).
When an application wants to modify the database (open a cursor for update or
insert a new record in the table), it first locks the database in exclusive mode, 
prohibiting accesses to the database by other applications, even for
read-only queries. So to avoid blocking of database applications for a long 
time, the modification transaction should be as short as possible. 
No blocking operations (like waiting for input from the user) should be
done within this transaction.<P>

Using only shared and exclusive locks on the database
level, allows FastDB to almost eliminate overhead of locking and 
to optimize the speed of execution of non-conflicting operations. But if many 
applications simultaneously update different parts of the database, then the
approach used in FastDB will be very inefficient. That is why FastDB is most
suitable for a single-application database access model or for
multiple applications with a read-dominated access pattern model.<P>
 
Both cursor and query objects should be used only by one thread in a
multithreaded application. If there are more than one threads in your
application, use local variables for cursors and queries objects 
in each thread. The <code>dbDatabase</code> object is shared between all
threads and uses thread specific data to perform query
compilation and execution in parallel with minimal synchronization overhead.
There are few global things, which require synchronization: symbol table,
pool of tree node,... But scanning, parsing and execution of the query can
be done without any synchronization, providing high level of concurrency
at multiprocessor systems.<P>

A database transaction is started by the first select or an insert operation.
If a cursor for update is used, then the database is locked in exclusive
mode, prohibiting access to the database by other applications and threads.
If a read-only cursor is used, then the database is locked in shared mode, preventing 
other applications and threads from modifying the database,
but allowing the execution of concurrent read requests.
A transaction should be explicitly terminated
either by the <code>dbDatabase::commit()</code> method, which fixes all 
changes done by the transaction in the database; or by the
<code>dbDatabase::rollback()</code> method to undo all modifications 
done by transactions. The method <code>dbDatabase::close()</code> automatically 
commits current transactions.<P>

If you start a transaction by performing selection using a read-only cursor and
then use a cursor for update to perform some modifications of the database, 
the database will be first locked in shared mode; then the lock will be upgraded
to exclusive mode. This can cause a deadlock problem if the database is simultaneously 
accessed by several applications. Imagine that application A starts
a read transaction and application B also starts a read transaction. Both
of them hold shared locks on the database. If both of them want to
upgrade their locks to exclusive mode, they will forever block each other
(exclusive lock can not be granted until a shared lock of another process exists).
To avoid such situations try to use a cursor for update at the beginning of the
transaction; or expli