gdk.mx

这个是内存数据库中的一个管理工具

@' The contents of this file are subject to the MonetDB Public License
@' Version 1.1 (the "License"); you may not use this file except in
@' compliance with the License. You may obtain a copy of the License at
@' http://monetdb.cwi.nl/Legal/MonetDBLicense-1.1.html
@'
@' Software distributed under the License is distributed on an "AS IS"
@' basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
@' License for the specific language governing rights and limitations
@' under the License.
@'
@' The Original Code is the MonetDB Database System.
@'
@' The Initial Developer of the Original Code is CWI.
@' Portions created by CWI are Copyright (C) 1997-2007 CWI.
@' All Rights Reserved.

@f gdk
@t The Goblin Database Kernel
@v Version 3.05
@a Martin L. Kersten & Peter Boncz

@* The Inner Core
The innermost library of the MonetDB database system is formed by
the library called GDK, an abbreviation of Goblin Database Kernel.
Its development was originally rooted in the design of a pure
active-object-oriented programming language, before development
was shifted towards a re-usable database kernel engine.

GDK is a C library that provides ACID properties on a DSM model
@tex
[@cite{Copeland85}]
@end tex
, using main-memory
database algorithms
@tex
[@cite{Garcia-Molina92}]
@end tex
 built on virtual-memory
OS primitives and multi-threaded parallelism.
Its implementation has undergone various changes over its decade
of development, many of which were driven by external needs to
obtain a robust and fast database system.

The coding scheme explored in GDK has also laid a foundation to
communicate over time experiences and to provide (hopefully)
helpful advice near to the place where the code-reader needs it.
Of course, over such a long time the documentation diverges from
reality. Especially in areas where the environment of this package
is being described.
Consider such deviations as historic landmarks, e.g. crystallization
of brave ideas and mistakes rectified at a later stage.

@+ Short Outline
The facilities provided in this implementation are:
@itemize
@item
GDK or Goblin Database Kernel routines for session management
@item
 BAT routines that define the primitive operations on the
database tables (BATs).
@item
 BBP routines to manage the BAT Buffer Pool (BBP).
@item
 ATOM routines to manipulate primitive types, define new types
using an ADT interface.
@item
 HEAP routines for manipulating heaps: linear spaces of memory
that are GDK's vehicle of mass storage (on which BATs are built).
@item
 DELTA routines to access inserted/deleted elements within a
transaction.
@item
 HASH routines for manipulating GDK's built-in linear-chained
hash tables, for accelerating lookup searches on BATs.
@item
 TM routines that provide basic transaction management primitives.
@item
 TRG routines that provided active database support. [DEPRECATED]
@item
 ALIGN routines that implement BAT alignment management.
@end itemize

The Binary Association Table (BAT) is the lowest level of storage
considered in the Goblin runtime system
@tex
[@cite{Goblin}]
@end tex
.  A BAT is a
self-descriptive main-memory structure that represents the @strong{binary
relationship} between two atomic types.
@
The association can be defined over:
@table @code
@item void:
 virtual-OIDs: a densely ascending column of OIDs (takes zero-storage).
@item bit:
 Booleans, implemented as one byte values.
@item chr:
A single character (8 bits @strong{integer}s).
DEPRECATED for storing text (Unicode not supported).
@item bte:
 Tiny (1-byte) integers (8-bit @strong{integer}s).
@item sht:
 Short integers (16-bit @strong{integer}s).
@item int:
 This is the C @strong{int} type (32-bit).
@item oid:
 Unique @strong{long int} values uses as object identifier. Highest bit cleared always.
	    Thus, oids-s are 31-bit numbers on 32-bit systems, and 63-bit numbers on 64-bit systems.
@item wrd:
 Machine-word sized integers
 (32-bit on 32-bit systems, 64-bit on 64-bit systems).
@item ptr:
Memory pointer values. DEPRECATED.  Can only be stored in transient BATs.
@item flt:
 The IEEE @strong{float} type.
@item dbl:
 The IEEE @strong{double} type.
@item lng:
 Longs: the C @strong{long long} type (64-bit integers).
@item str:
 UTF-8 strings (Unicode). A zero-terminated byte sequence.
@item bat:
 Bat descriptor. This allows for recursive adminstered tables, but
severely complicates transaction management. Therefore, they
CAN ONLY BE STORED IN TRANSIENT BATs.
[on the list to become depreciated,
@end table

This model can be used as a back-end model underlying other -higher
level- models, in order to achieve @strong{better performance} and
@strong{data independence} in one go. The relational model and
the object-oriented model can be mapped on BATs by vertically
splitting every table (or class) for each attribute. Each such a
column is then stored in a BAT with type @strong{bat[oid,attribute]}, where
the unique object identifiers link tuples in the different BATs.
Relationship attributes in the object-oriented model hence are
mapped to @strong{bat[oid,oid]} tables, being equivalent to the concept of
@emph{join indexes}
@tex
[@cite{Valduriez87}]
@end tex
.

The set of built-in types can be extended with user-defined types
through an ADT interface.  They are linked with the kernel to obtain
an enhanced library, or they are dynamically loaded upon request.

Types can be derived from other types. They represent something different
than that from which they are derived, but their internal storage management
is equal. This feature facilitates the work of extension programmers, by
enabling reuse of implementation code, but is also used to keep the GDK code
portable from 32-bits to 64-bits machines: the @strong{oid} and @strong{ptr} types
are derived from @strong{int} on 32-bits machines, but is derived from @strong{lng}
on 64 bits machines. This requires changes in only two lines of code each.

To accelerate lookup and search in BATs, GDK supports one built-in
search accelerator: hash tables. We choose an implementation efficient 
for main-memory: bucket chained hash 
@tex
[@cite{LehCar86,Analyti92}]
@end tex
. Alternatively, when the table is sorted, it will resort to merge-scan
operations or binary lookups.
@
BATs are built on the concept of heaps, which are large pieces of main
memory. They can also consist of virtual memory, in case the working
set exceeds main-memory. In this case, GDK supports operations that
cluster the heaps of a BAT, in order to improve performance of its
main-memory.


@- Rationale

The rationale for choosing a BAT as the building block for both
relational and object-oriented system is based on the following
observations:

@itemize
@item -
Given the fact that CPU speed and main-memory increase in
current workstation hardware for the last years has been exceeding
IO access speed increase, traditional disk-page oriented algorithms
do no longer take best advantage of hardware, in most database operations.

Instead of having a disk-block oriented kernel with a large memory
cache, we choose to build a main-memory kernel, that only under large data
volumes slowly degrades to IO-bound performance, comparable to
traditional systems
@tex
[@cite{boncz95,boncz96}]
@end tex
.

@item -
Traditional (disk-based) relational systems move too much data
around to save on (main-memory) join operations.

The fully decomposed store (DSM
@tex
[@cite{Copeland85})]
@end tex
assures that only those attributes of a relation that are needed,
will have to be accessed.

@item -
The data management issues for a binary association is much
easier to deal with than traditional @emph{struct}-based approaches
encountered in relational systems.

@item -
Object-oriented systems often maintain a double cache, one with the
disk-based representation and a C pointer-based main-memory structure.
This causes expensive conversions and replicated storage management.\\
GDK does not do such `pointer swizzling'. It used virtual-memory 
(@strong{mmap()}) and buffer management advice (@strong{madvise()}) OS primitives to
cache only once. Tables take the same form in memory as on disk,
making the use of this technique transparent
@tex
[@cite{oo7}]
@end tex
.
@end itemize

A RDBMS or OODBMS based on BATs strongly depends on our ability
to efficiently support tuples and to handle small joins, respectively.

The remainder of this document describes the Goblin Database kernel
implementation at greater detail. It is organized as follows:
@table @code
@item @strong{GDK Interface}:

It describes the global interface with which GDK sessions can be
started and ended, and environment variables used.

@item @strong{Binary Association Tables}:

As already mentioned, these are the primary data structure of GDK.
This chapter describes the kernel operations for creation, destruction
and basic manipulation of BATs and BUNs (i.e. tuples: Binary UNits).

@item @strong{BAT Buffer Pool:}

All BATs are registered in the BAT Buffer Pool. This directory is used
to guide swapping in and out of BATs. Here we find routines that guide
this swapping process.

@item @strong{GDK Extensibility:}

Atoms can be defined using a unified ADT interface.
There is also an interface to extend the GDK library with
dynamically linked object code.

@item @strong{GDK Utilities:}

Memory allocation and error handling primitives are provided. Layers
built on top of GDK should use them, for proper system monitoring.
Thread management is also included here.

@item @strong{Transaction Management:}

For the time being, we just provide BAT-grained concurrency and global
transactions. Work is needed here.

@item @strong{BAT Alignment:}
Due to the mapping of multi-ary datamodels onto the BAT model,
we expect many correspondences among BATs, e.g.  @emph{bat(oid,attr1),..
bat(oid,attrN)} vertical decompositions. Frequent activities will be
to jump from one attribute to the other (`bunhopping'). If the head
columns are equal lists in two BATs, merge or even array lookups
can be used instead of hash lookups. The alignment interface makes
these relations explicitly manageable.

In GDK, complex data models are mapped with DSM on binary tables.
Usually, one decomposes @emph{N}-ary relations into @emph{N} BATs with
an @strong{oid} in the head column, and the attribute in the tail column.
There may well be groups of tables that have the same sets of 
@strong{oid}s, equally ordered. The alignment interface is intended to make
this explicit.  Implementations can use this interface to detect this
situation, and use cheaper algorithms (like merge-join, or even array
lookup) instead.

@item @strong{BAT Iterators:}

Iterators are C macros that generally encapsulate a complex for-loop.
They would be the equivalent of cursors in the SQL model. The macro
interface (instead of a function call interface) is chosen to achieve
speed when iterating main-memory tables.

@item @strong{Common BAT Operations:}

These are much used operations on BATs, such as aggregate functions
and relational operators. They are implemented in terms of BAT- and
BUN-manipulation GDK primitives.
@end table
@

@+ Interface Files
In this section we summarize the user interface to the GDK library.
It consist of a header file (gdk.h) and an object library (gdklib.a),
which implements the required functionality. The header file must be
included in any program that uses the library. The library must be
linked with such a program.

@- Database Context

The MonetDB environment settings are collected in a configuration
file. Amongst others it contains the location of the database
directory.
First, the database
directory is closed for other servers running at the same time.
Second, performance enhancements may take effect, such as locking
the code into memory (if the OS permits) and preloading the
data dictionary.
An error at this stage normally lead to an abort.
@{
@h
#ifndef _GDK_H_
#define _GDK_H_

#include <monet_utils.h>

/* standard includes upon which all configure tests depend */
#include <stdio.h>
#ifdef HAVE_SYS_TYPES_H
# include <sys/types.h>
#endif
#ifdef HAVE_SYS_STAT_H
# include <sys/stat.h>
#endif
#ifdef STDC_HEADERS
# include <stdlib.h>
# include <stddef.h>
#else
# ifdef HAVE_STDLIB_H
#  include <stdlib.h>
# endif
#endif
#ifdef HAVE_STRING_H
# if !defined(STDC_HEADERS) && defined(HAVE_MEMORY_H)
#  include <memory.h>
# endif
# include <string.h>
#endif
#ifdef HAVE_STRINGS_H
# include <strings.h>
#endif
#ifdef HAVE_INTTYPES_H
# include <inttypes.h>
#else
# ifdef HAVE_STDINT_H
#  include <stdint.h>
# endif
#endif
#ifdef HAVE_UNISTD_H
# include <unistd.h>
#endif

#include <ctype.h>		/* isspace etc. */

#ifdef HAVE_SYS_FILE_H
# include <sys/file.h>
#endif
#ifdef HAVE_SYS_PARAM_H
# include <sys/param.h>		/* MAXPATHLEN */
#endif

#ifdef HAVE_DIRENT_H
# include <dirent.h>
# define NAMLEN(dirent) strlen((dirent)->d_name)
#else
# define dirent direct
# define NAMLEN(dirent) (dirent)->d_namlen
# ifdef HAVE_SYS_NDIR_H
#  include <sys/ndir.h>