Mr. Klein introduces us to a database called Beagle SQL that he developed as a learning experience.
by Rob Klein
I'd like to introduce you to a client-server database package that I've been developing on Linux since May 1996. I picked Linux because it is one of the most robust development environments available for the development of advanced client-server applications. Beagle SQL began life as a learning project. I've always had a fascination with figuring out how things work under the hood. After years of working with many major (and minor) database packages, I decided to build my own. Since then I've received a lot of comments from people who are looking for more choices in database packages, particularly ones that support Linux. I have benefited greatly from the hard work so many people have contributed to the development of Linux and other freely available tools. Beagle SQL (BSQL) is my way of giving something back.
Database management systems come in many different forms. Here I'll discuss the client/server architecture of BSQL. The three base components of this architecture are the client process, the Connection Manager and the Database Manager.
The client process is the user application that sends requests to the Database Manager. The client is simply a program written using the available API (Application Programming Interface) provided by the DBMS to access the data in the database. BSQL comes with both C and Perl APIs.
The Connection Manager handles all incoming connections to the Database Manager. When the client program issues a connect request, the Connection Manager spawns a copy of the Database Manager to handle all subsequent requests from the client. Once the client and the Database Manager are talking, the Connection Manager is free to handle connection requests from other clients.
In this scenario, each client process is serviced by its own server process on the remote machine. One advantage of this type of architecture is that the server process only needs to worry about its own client, making the communication between the client and server processes easy to handle. Unfortunately, this architecture is memory-intensive as a server process is spawned for each client.
Another disadvantage is that the locking algorithms become more complicated as each server process needs to be aware of the other server processes updating the database. Database management systems typically incorporate one of two locking methods, coarse locking and fine locking.
Coarse locking, also known as table-level locking, is the easiest of the two to implement. It requires that each client process writing to a table requests a lock be placed on the entire table and its associated indices. Once the database manager grants this lock, the client process has permission to write to the table. Any other clients needing to write to the same table must wait until the first client is done. Typically, the duration of the lock is handled using a transaction. In its simplest form, a transaction would be a single UPDATE or DELETE statement. Some database managers give the client the ability to expand the size of a transaction using a keyword to block several statements together. This can be very critical in systems where data is replicated throughout several tables in a database. The main problem with this type of locking is the bottleneck that can be created when several clients are trying to update the same table at the same time.
Fine locking, also known as row-level locking, is much more complicated to implement. When a client writes to a table, it requests a lock only for the row in the table it is currently updating. This allows several clients to update the same table at the same time as long as they are not trying to lock the same row. The complexity comes in when a client is trying to update a table that has indices associated with it. BSQL uses an indexing method known as B-trees. Whenever a client updates, deletes or inserts rows into a table, the B-tree indices for the table may need to be re-balanced. Concurrent balancing of B-trees is way beyond the scope of this article, but there have been many books and papers dedicated to the topic.
Currently, BSQL uses the client->connection->database architecture without locking. I plan to implement coarse locking first, eventually evolving into fine locking as time allows.
The client process is usually a user-written program that accesses the database using the provided API, in this case, BSQL's C API. For those who prefer Perl, a demo client with full Perl source is provided with the BSQL distribution downloadable from http://www.beaglesql.org/. The first thing the client program needs to do is request a connection to the server process using the API function BSQLConnect(). The connect function returns the file handle needed by all subsequent communications with the server. Next, the database you want to manipulate is set using the BSQLSetCurrentDB() function call, passing the file handle returned by BSQLConnect() and the name of the database to which you wish to connect. The following code example illustrates how a client process connects to a server process running on the same machine:
s = BSQLConnect (host);
if (!BSQLSetCurrentDB (s, "test")) {
fprintf (stdout,
"\nCan't send current database");
exit (s);
}
Once you are connected to the database, you can begin sending SQL queries using the BSQLQueryDB() function, passing the file handle assigned to the connection and a string containing your SQL query. A pointer to a result structure is returned that contains the status of your request. Status information includes whether or not the query succeeded and, in the case of an SQL SELECT, how many records or tuples returned to the client process. The code fragment in Listing 1 shows the results of a SELECT statement sent to the Database Manager.
In the above example, the BSQLnfields() function returns the number of fields per record returned by the SELECT statement. The BSQLFieldName() function returns a string containing the field name of the nth field returned. The function BSQLntuples() returns the number of records that match the SELECT's WHERE clause. The omission of the WHERE clause in the above example tells the server process to return all records from the table phone book. The call to the BSQLFieldValue() function returns a string containing the data from the nth field of the ith record. Because the result structure returned by the BSQLQueryDB() function is dynamically allocated, it must be freed after you are finished with it. The BSQLFreeResult() function does just that. The last BSQL API function called in any client program should be the BSQLDisconnect() function. When called, it passes an exit message to the server process so it can terminate the connection and exit cleanly. Without it, you will litter your system with stray server processes that eat up system resources.
This is probably the most straightforward piece of the client-server puzzle. The Connection Manager is simply a loop waiting for incoming messages from client processes. First a socket is opened for the ``beagled'' service (defined in your /etc/services file), so that the Connection Manager can listen for incoming connections. Then an endless loop is entered. Once the Connection Manager receives a signal from a client processes, a call to accept() returns the socket number that the client and server processes will communicate through. At this point, the Connection Manager fork()s the Database Manager, passing the socket number returned by accept(). After the Database Manager is successfully started, the Connection Manager starts listening for the next incoming connection.
The Database Manager does all the work. The basic components of the Database Manager are the expression parser, the query optimizer (currently, no query optimization is done in BSQL), the index manager, the locking manager and the low-level I/O manager. The SELECT statement is the most complex operation performed by the Database Manager. As BSQL supports explicit joins, a single SELECT statement can search through several tables to return the requested information. The expression parser must be intelligent enough to tell which fields in the SELECT list belong to which tables. If you are joining two tables with duplicate field names, the SELECT statement must explicitly state which field belongs to which tables. Wild cards are allowed. When the expression parser sees wild cards in the field list, it inserts the appropriate field names into the list.
There are three examples in the sidebar to give you an idea of how the expression parser does its work. The statement in Example 3 fails because field1 is ambiguous. The expression parser can't tell if it belongs to table A or table B as both have a field called field1.
When joining tables, the SELECT statement's WHERE clause can contain several different parts that need to be treated separately. When joining two tables these parts can include the conditionals for the first table, the conditionals for the second table and the join condition. The Database Manager searches each of the two tables using the appropriate conditionals from the WHERE clause. Next, it joins the two tables into a temporary table using the fields in the SELECT field list as well as the fields used in the join condition. Last, the records in the temporary table are matched with the join condition and the appropriate records are made available for retrieval by the client process.
This operation can get quite complicated and time consuming when dealing with large and multiple tables. This is where the query optimizer comes in. Its purpose is to determine the most efficient order to search and join the tables. BSQL currently doesn't do query optimization and joins the tables from left to right as they appear in the SELECT statement. This leaves it up to the person writing the SQL statement to put some thought into the order the tables appear in the join.
When performing searches, the Database Manager uses a set of low-level I/O routines to retrieve records from the database. Most commercial database vendors use proprietary file systems to house their databases. In the case of BSQL, the Linux file system sufficed. A future enhancement will be a flexible file format that can allow for such things as BLOBs, images, text documents and anything else. (A BLOB is a large binary datatype used to store images, sound bites, programs, etc. in a database table.)
The method used to store these variable-length records will significantly impact the performance of the Database Manager. When a record is written to the database, it is broken down into fixed-size segments. The database administrator can set the size of these segments for each database. If a record containing 850 bytes is written to a table that uses 256 byte segments, it is broken down into four segments that are chained together. If at a later time the record size is changed to 1200 bytes, an additional segment is added to the chain. If the record is reduced to 700 bytes, the unneeded segments are marked for reuse. One drawback here is that over time the database can become fragmented. Routine maintenance using a de-fragmenting utility should be performed on databases that see a lot of UPDATEs and DELETEs. This utility will be provided with the first official release of BSQL v1.0.
Hopefully, I've given you some insight into how client server databases work and the many late nights that go into their development. For more information on Beagle SQL, point your web browser to http://www.beaglesql.org/. Here you can follow its development history from day one to present as well as download the code to try it out for yourself. Also, be sure to look into the other freely available database resources on the Web.
Rob Klein has been a Developer/Administrator for 11 years. Although software development can be fun, his main interests are football, baseball and spending quiet evenings with this wife Cathy (absolutely not in that order). He welcomes your comments sent to rvklein@ober.com.