perst.html

Perst开源实时数据库

In this case Perst will derive generated wrapper class from
<code>Perst.Persistent</code> class (or from <code>Perst.PersistentResource</code> class 
if specified interface extends <code>Perst.IResource</code> interface).
Wrapper class will implement specified interface and contains correspondent fields:

<pre>
class NodeWrapper:Persistent, Node {
    public int Weight {
        get {
            return weight;
        }
        set {
            weight = value;
            Modify();
        }
    }
    public Node Parent {
        get {
            return (Node)Storage.getByOid(parent);
        }
        set {
            parent = value.MakePersistent(Storage);
            Modify();
        }
    }
}
</pre>

         
In the second case you are using abstract class instead of interface:

<pre>
interface Node:Persistent {
    public abstract int Weight {
        get;
        set;
    }
    public abstract Node Parent { 
        get;
        set;
    }
}
</pre>

This class has to be derived from Persistent or PersistentResource class.
There is only one difference in generated wrapper class - it extends specified 
abstract class:

<pre>
class NodeWrapper:Node {
    ...
}
</pre><p>

As far as there are not direct references between objects when this API is used, 
garbage collector will remove from memory all persistent objects which are not referenced
from some program variables. That is why it is highly recommended to use LRU object cache
to increase performance (it is used by default).<p>

<code>PropGuess</code> example illustrates using of this Perst transparent API.<p>


<H2> <A NAME = "implementation">PERST implementation issues</A></H2>

Below is more detailed description of PERST implementation.
This section can be skipped if you are not interested in the details of implementation:<P>


<H3> <A NAME = "memory">Memory allocation</A></H3>

Memory allocation is performed in PERST by bitmap. Memory is allocated in
chunks called allocation quantum. In current version of PERST size of
allocation quantum is 64 byte. It means that size of all allocated objects is
aligned on 64 byte boundary. Each 64 byte of database memory is represented by
one bit in the bitmap. To locate hole of requested size in bitmap, PERST
sequentially searches bitmap pages for correspondent number of successive
cleared bits. PERST use three arrays indexed by bitmap byte, which
makes possible fast calculation of hole offset and size within the byte.<P>

PERST performs cyclic scanning of bitmap pages. It keeps identifier
of current bitmap page and current position within the page. Each time
when allocation request arrives, scanning of the bitmap starts from the
current position.
When last allocated bitmap page is scanned, scanning continues from the
beginning (from the first bitmap page) and until current position.
When no free space is found after full cycle through all bitmap pages,
new bulk of memory is allocated. Size of extension is maximum of
size of allocated object and extension quantum. Extension quantum is parameter
of database, specified in constructor. Bitmap is extended to be able to map
additional space. If virtual space is exhausted and no more
bitmap pages can be allocated, then <code>OutOfMemory</code> error
is reported.<P>

Allocation memory using bitmap provides high locality of references
(objects are mostly allocated sequentially) and also minimizes
number of modified pages. Minimization of number of modified pages is
significant when commit operation is performed and all dirty pages should
be flushed on the disk. When all cloned objects are placed sequentially,
number of modified pages is minimal and so transaction commit time is also
reduced. Using extension quantum also helps to
preserve sequential allocation. Once bitmap is extended, objects will
be allocated sequentially until extension quantum will be completely used.
Only after reaching the end of the bitmap, scanning restarts from the beginning
searching for holes in previously allocated memory.<P>


To reduce number of bitmap pages scans, PERST associates descriptor with
each page, which is used to remember maximal size of the hole on the page.
Calculation of maximal hole size is performed in the following way:
if object of size <I>M</I> can not be allocated from this bitmap pages,
then maximal hole size is less than <I>M</I>, so <I>M</I>
is stored in the page descriptor if previous value of descriptor is large
than <I>M</I>. For next allocation of object of size greater or
equal than <I>M</I>, we will skip this bitmap page. Page descriptor
is reset when some object is deallocated within this bitmap page.<P>

Some database objects
(like hash table pages) should be aligned on page boundary
to provide more efficient access. PERST memory  allocator checks requested
size and if it is aligned on page boundary, then address of
allocated memory segment is also aligned on page boundary. Search of free hole
will be done faster in this case, because PERST increases step of current
position increment according to the value of alignment.<P>

To be able to deallocate memory used by object, PERST needs to keep
somewhere
information about object size. PERST memory allocator deals with two types
of objects - normal table records and page objects.
All table records are prepended by record header, which contains
record size and pointer of L2-list linking all records in the table.
So size of the table record object can be extracted from record header.
Page objects always occupies the whole database page are are allocated at
the positions aligned on page boundary. Page objects has no headers.
PERST distinguish page objects
with normal object by using special marker in object index.<P>


<H3> <A NAME = "logless">Shadow transaction mechanism</A></H3>

Each record (object) in PERST has unique identifier (OID).
Object identifiers
are used to implement references between objects. To locate object by
reference, its OID is used as index in array of object offsets within the file.
This array is called <I>object index</I> and element of this array -
<I>object handle</I>. These are two copies of object
indices in PERST, one of which is current and other - shadow.
Header of database contains pointers to both object indices and indicator
which index is current at this moment.<P>

When object is modified first time, it is cloned
(copy of the object is created) and object handle in current index is
changed to point to newly created object copy. And shadow index still
contains handle which points to the original version of the object.
All changes are done with the object copy, leaving original object unchanged.
PERST marks in special bitmap page of the object index, which contains
modified object handle.<P>

When transaction is committed, PERST first checks if size of object index
was increased during current transaction. If so, it also reallocates shadow
copy of object index. Then PERST frees memory for all "old objects",
i.e. objects which was cloned within transaction. Memory can not be
deallocated before commit, because we wants to preserve consistent
state of the database by keeping cloned object unchanged.
If we deallocate memory immediately after cloning, new object can be
allocated at the place of cloned object and we loose
consistency. As far as memory deallocation is done in PERST by bitmap
using the same transaction mechanism as for normal database objects,
deallocation of object space will require clearing some bits in bitmap page,
which also should be cloned before modification. Cloning bitmap page will
require new space for allocation the page copy, and we can reuse space of
deallocated objects. And it is not acceptable due to the reason explained
above - we will loose database consistency. That is why deallocation
of object is done in two steps. When object is cloned, all bitmap pages
used for marking objects space, are also cloned (if not
not cloned before). So when transaction is committed, we only clear bits in
bitmap pages and no more requests for allocation memory can be generated at
this moment.<P>

After deallocation of old copies, PERST flushes all modified pages on disk
to synchronize content of the memory and disk file. After that PERST
changes current object index indicator in database
header to switch roles of the object indices. Now object index, which was
current becomes shadow, and shadow index becomes current. Then PERST again
flushes modified page (i.e. page with database header) on disk, transferring
database to new consistent state.
After that PERST copies all modified handles from new object index
to object index which was previously shadow and now becomes current.
At this moment contents of both indices is synchronized and PERST is ready
to start new transaction.<P>

Bitmap of modified object index pages is used to minimize time of committing
transaction. Not the whole object index, but only its modified pages should be
copied. After committing of transaction bitmap is cleared.<P>

When transaction is explicitly aborted by <code>Storage.rollback</code>
method, shadow object index is copied back to the current index, eliminating
all changes done by aborted transaction. After the end of copying,
both indices are identical again and database state corresponds to the moment
before the start of current transaction.<P>

Allocation of object handles is done by free handles list. Header of the list
is also shadowed and two instances of list headers are stored in database
header. Switch between them is done in the same way as switch of
object indices. When there are no more free elements in the list, PERST
allocates handles from the unused part of new index. When there is no
more space in the index, it is reallocated. Object index is the only
entity in database whose is not cloned on modification. Instead of this
two copies of object index are always used.<P>

There are some predefined OID values in PERST. OID <I>0</I> is reserved
as invalid object identifier. OID starting from <I>1</I> are reserved for bitmap pages.
Number of bitmap pages depends on database maximum virtual space.
For one terabyte virtual space, 8 Kb page size and 64 byte allocation quantum,
32K bitmap pages are required. So 32K handles are reserved in object index for
bitmap. Bitmap pages are allocated on demand, when database size is extended.
So OID of first users object will be 0x8002.<P>

Recovery procedure is trivial in PERST. There are two instances of
object index, one of which is current and another corresponds to
consistent database state. When database is opened, PERST checks database
header to detect if database was normally closed. If not
(<code>dirty</code> flag is set in database header), then PERST performs
database recovery. Recovery is very similar to rollback of transaction.
Indicator of current index in database object header is used to
determine index corresponding to consistent database state and object handles
from this index are copied to another object index, eliminating
all changes done by uncommitted transaction. As far as the only action
performed by recovery procedure is copying of objects index (really only
handles having different values in current and shadow indices are copied to
reduce number of modified pages) and size of object index is small,
recovery can be done very fast.
Fast recovery procedure reduces "out-of-service" time of application.<P>


<H2> <A NAME = "where">Where to use</A></H2>

PERST is simple and fast embedded database engine. 
If your applications need embedded database engine and do not need to execute complex SQL queries, 
and the only thing you need is to be able to store/fetch/locate object in the database using navigation 
through references or indexed search by key, then PERST is what you need. It will provide much better performance
than relational database and other (more sophisticated) object oriented database.<P>

The table below summarize <B>pro</B> features of PERST:<P>

<OL>
<LI>Tight and transparent integration with programming language
<LI>No gap in database and application data model
<LI>Easy to use
<LI>Minimal requirements (PERST package itself has size only 51Kb and it can be configured to use minimal memory and disk
space during it