InterBase: What Sets It Apart

Locking Schemes

The oldest and most common method of controlling concurrent access to data by several users is locking. When one user locks an object in a database he or she restricts the ability of other users to access that object. How much a lock affects concurrency depends on the granularity of the lock. For example, a lock placed on an entire table will restrict other users access to all of the rows in the table. Therefore, a table level lock has very low granularity. A lock placed on a single page in a table limits access to all of the rows on that page. A page level lock is more granular than a table level lock. By contrast, a lock placed on a single row is very granular and provides the minimum restriction to concurrent data access.

Database servers support either row or page level locking. The problem with page level locks is easy to see if you consider an example. Suppose the size of a page is 2k (2048 bytes) and the size of a row is 100 bytes. Then each page can hold 20 rows and each time a page is locked access is restricted to all 20 rows. With row level locking only a single row would be locked and other users would be free to access other records on the page so row level locking provides better concurrency.

If you come from a desktop database background you are probably most familiar with a scheme called pessimistic locking. Pessimistic locking is so named because it assumes that the probability is high that another user will try to modify the same object in the database that you are changing. In a pessimistic locking environment the object you wish to change is locked before you begin changing it and remains locked until you commit your change. The advantage of pessimistic locking is that you are guaranteed that you will be able to post the changed row.

Suppose you need to change a customer’s address. Using pessimistic locking you would first lock the customer information at either the page or row level. You can then read the customer’s record, change it and be guaranteed that you can write your changes to the database. Once you commit your changes your lock is released and others are free to change the customer’s record. Locks can persist for a long time when pessimistic locking is used. You could begin a change then go to lunch and not commit the change and release the lock until you return. Clearly you want to use locks with high granularity if you are going to use pessimistic locking in a multi-user environment. If you must lock an entire page of customer records while you are changing a single row no other user will be able to change any other customer record on that page. Row level locks are best when pessimistic locking is used because they impose the least restriction on access by other users. Page level locks are much less satisfactory because they restrict access to many rows as long as they persist.

The most common locking scheme found in database servers is optimistic locking. The locking mechanism is optimistic in that it assumes that it is very unlikely that another user will try to change the same row that you are changing. An optimistic lock is not placed until you try to commit your changes. To understand optimistic locking consider two users, John and Jane, trying to change a customer’s record. First John reads the record and begins to make changes. Next Jane reads the record and begins to make changes. This is possible because in the optimistic locking scheme no lock is placed when a user reads a record and begins changing it. Next John completes his changes and attempts to commit them. At this point the database locks the record, commits the change and releases the lock. When Jane tries to commit her change the software detects that the record has been changed since Jane read it and her change is rejected. Jane must now re-read the record and begin again.

Optimistic locking has a clear advantage in that locks are only held for a very brief period while the data is actually being updated. That means that with an optimistic locking scheme you can achieve adequate concurrency with less lock granularity. Therefore, databases that use optimistic locking may lock at the page level and not at the row level. On the other hand, optimistic locking does not fare well in an environment where there is a high probability that two users will try to update the same row at the same time.

From the database vendor’s point of view page level locking is advantageous in that fewer locks must be placed, particularly during batch operations that affect many rows. This means that the resource requirements of the lock manager module in the database management system are lower and this can help performance of the database server. However, users are invariably the slowest part of any database application so you will usually get better overall performance in an environment where one user cannot block another.

Understanding how your database manages locks can be critically important. Consider an orders table. New records are being added continuously as new orders are received. Because the order data does not include a field or fields which would form a natural primary key you decide to use an artificially generated order number as a surrogate key. Order numbers will be assigned sequentially as orders are received. Since your application will frequently need to select groups of orders you create a clustered index on the order number column. A clustered index provides superior performance when retrieving adjacent records because the records are physically stored in key order within the database pages.

Unfortunately this design is likely to produce poor performance if the database uses page level locking. Since sequential adjacent keys are being assigned and a clustered index is being used each new record that is added will probably be placed on the same page as the preceding record. Since the database locks at the page level two users cannot add new orders to the same page at the same time. Each new order must wait until the page lock placed by the preceding order is released. In this case you would get much better performance by assigning the keys randomly to reduce the chance that successive records will be added to the same page.

Transactions

Another requirement of database servers is the ability to group changes to the database into transactions. Update transactions consist of one or more changes to one or more tables in the database which must be treated as a single unit so that either all of the changes that comprise the transaction take place or none of the changes take place.

Transaction processing takes place in three steps. First you tell the database software that you wish to begin a transaction. This informs the database system that all changes until further notice are to be treated as a single unit. Next, the changes are actually made to the tables in the database. Finally, you notify the database system that you wish to either commit or rollback the transaction. If you commit the transaction then the changes become permanent. If you rollback the transaction all of the changes are undone.

Transaction processing is vital to ensure the logical integrity of the database. Consider the case where John transfers $100 from his savings account to his checking account. This transaction would proceed as follows.

1. Start a new transaction.
2. Update the balance in the savings account to show a withdrawal of $100.
3. Update the balance in the checking account to show an increase of $100.
4. Either commit or rollback the transaction.

Suppose the system crashes after step two but before step 3. Without transaction control John would have lost $100. With transaction control, when the system is restarted the database software will automatically rollback any transactions that had not been committed at the time of the crash. This guarantees that the database will be left in a consistent state.

You also need transaction control for read transactions that will read more than a single record to ensure that the read returns a consistent view of the data. This requirement is described in more detail in the next section.

Transaction Isolation

Transaction isolation governs how transactions that are executing simultaneously interact with each other. Many of today’s database servers were originally designed to process very short update transactions intermixed with single row reads. The perfect example is a bank automated teller (ATM). An ATM reads the balance in a single account or updates the balance in one or more accounts. In this environment, transactions are very short and reads involve a single row at a time so transaction isolation is not a serious concern. However, many of today’s database applications do not fit that model.

Short update transactions are still the norm but the advent of executive information systems has introduced long running read transactions that span whole tables and sometimes entire databases. To understand the problem with long read transactions consider the following scenario.

An executive requests the total value of the company’s inventory by warehouse. While the query is scanning the inventory table a user moves a pallet of platinum bars from warehouse A to warehouse B and commits the transaction. It is possible for the query to count the platinum in both warehouse A and warehouse B thus producing an erroneous inventory valuation report. The question then becomes, which updates should a read transaction see and when should it see them? This is what the transaction isolation level controls. There are four isolation levels defined in the SQL 92 standard as follows.

Read Uncommitted - this isolation level, sometimes called dirty read, allows any record in the database to be read whether it has been committed or not.

Read Committed - this level allows read transactions to see only those changes that have been committed.

Repeatable Read - ensures that if your transaction rereads records that it has read earlier it will find the same values in all of the fields of those records. This does not mean that you will get the same set of records on the second read. For example, if another transaction inserts a record that meets the criteria of the WHERE clause in your select you will see this new record the second time your transaction executes the SELECT.

Serializable - ensures that if you issue the same SELECT multiple times during the life of your transaction you will see exactly the same set of records with the same values in every field. It also ensures that there is some serial order of concurrent transactions that will produce the same result as that produced by concurrent execution. Interbase's snapshot transaction isolation level provides the same degree of isolation from changes made by other transactions as serializable.

In the example above what you need to ensure that your inventory valuation report is accurate is serializable isolation. The problem is the price that you must pay to get serializable isolation in a database that uses locking architecture. With the locking model the only way to ensure that data does not change during a long read transaction is to prevent any updates from taking place until the read transaction ends by locking each record as it is read. In many situations the effect on users of stopping all updates on a large number of rows for the duration of a long read transaction is unacceptable.

Versioning

There is another model for concurrency control called versioning which overcomes the problems that locking model databases have when the environment consists of a mixture of update and long read transactions. This model is called the versioning model and is the model used by InterBase. To understand the basics of the versioning model consider the preceding example. With a versioning database the read transaction to produce the inventory valuation report begins. When the update transaction to move the pallet of platinum from warehouse A to warehouse B is committed a new version of each updated record is created, however, the old version still exists in the database.

In a versioning database each transaction is assigned a sequential transaction number. In addition, the database manager maintains an inventory of all active transactions. The transaction inventory pages show whether the transaction is active, committed or rolled back.

When an update transaction commits, the database software checks to see if there are transactions with lower transaction numbers that are still active. If so then a new version of the record is created which contains the updated values. Each version also contains the transaction number of the transaction that created it. Note that InterBase does not create a complete copy of the row. Instead it creates a difference record that only contains the fields that were changed.

When a read transaction begins it gets the next transaction number and a copy of the transaction inventory pages that show the status of all transactions that have not yet committed. As a read transaction requests each row in a table the database software checks to see if the transaction number for the latest version of the row is greater than the transaction number of the transaction that is requesting the row and if the transaction was committed at the time the read transaction started. If the transaction number of the latest version of the row is greater than the number of the requesting transaction or if the transaction that created the latest version was active when the read transaction started InterBase looks back through the chain of prior versions until it encounters one whose transaction number is less than the transaction number of the transaction trying to read the row and whose transaction status was committed at the time the read transaction started. When the database manager finds the most recent version that meets these criteria it returns that version. The result is serializable transaction isolation without preventing updates during the life of the read transaction.

Consider the following example of a row for which four versions exist:

Tran=100 (status=committed)
Tran=80 (status=active when read started)
Tran=60 (status=rolled back)
Tran=40 (status=committed when read started)

Assume that a read transaction with transaction number 90 attempts to read this row. The read transaction will not see the version of the row created by transaction 100 because the update that created this version took place after transaction 90 began. Transaction 90 also will not be able to read the version created by transaction 80 although it has a lower transaction number because transaction 80 has not committed yet. Although the version for transaction 60 still exists on disk transaction 60 has rolled back and rolled back versions are always ignored. Therefore, the version that transaction 90 will read is the version created by transaction 40.

Note in this example that transaction 80 will not be allowed to commit. When transaction 80 attempts to commit the database manager will discover that transaction 100 has committed and transaction 80 will be rolled back.

How They Compare

To get a more complete understanding of how the locking and versioning models compare you need to look at the types of concurrency conflicts that can occur in a multi-user database and how each model behaves in each case. The following examples assume that the locking model uses a shared read lock and an exclusive write lock to implement optimistic locking. Multiple users can place read locks but no user can place a write lock if another user has either a read or write lock. If one user has a write lock another user can neither read or write the row. This is typical of databases that use locking architecture. In the following examples three scenarios are explored. The first is what happens with no concurrency control, the second is what happens using the locking model and the third is what happens with versioning.

Consider the case where a husband and wife go to two different ATM’s at the same time to withdraw money from their checking account. With no concurrency control the following sequence of events can occur:

John reads the balance of the account which is $1,000..
Jane reads the balance of the account which is still $1,000.
John posts a $700 withdrawal.
Jane posts a $500 withdrawal.

At this point the account balance is -$200 and the bank is not happy. This happened because with no concurrency control mechanism John’s update is lost as far as Jane is concerned. She never sees the change in account balance. Under the locking model:

1. John reads the balance of the account causing a read lock.
2. Jane reads the balance of the account causing a read lock.
3. John posts his withdrawal attempting a write lock which fails due to Jane’s read lock.
4. Jane posts her withdrawal attempting a write lock which fails due to John’s read lock.

A deadlock now exists. Hopefully the database software will detect the deadlock and rollback one of the transactions.

Under the versioning model:

1. John reads the balance of the account.
2. Jane reads the balance of the account
3. John posts his withdrawal which causes a new version with new balance to be written.
4. Jane posts her withdrawal but is rolled back when the newer version is detected.

A different problem occurs if a user rolls back a transaction.

1. John withdraws money from the account which updates the balance.
2. Jane reads the balance.
3. John rolls back his transaction before committing.
4. Jane has now seen the wrong balance.

In this case a dependency exists between the two transactions. Jane’s transaction produces the correct results only if John’s transaction commits. This illustrates the danger of reading uncommitted data and shows why most databases do not allow dirty read transaction isolation. Using locking the following occurs.

1. John reads the balance which places a read lock.
2. John commits his withdrawal which places a write lock during the update.
3. Jane reads the balance which attempts a read lock but must wait due to John’s write lock.
4. John cancels the transaction before committing. This rolls back and releases the write lock.
5. Jane can now read and get the correct balance.

Under versioning:

1. John withdraws money which updates the balance and creates new uncommitted version.
2. Jane reads the balance. This does not reflect John’s uncommitted withdrawal.
3. John rolls back so the version showing the withdrawal is marked rolled back.

This illustrates a performance advantage of versioning since Jane does not have to wait to read the balance.

The following is a different example but the same scenario as the example of the platinum moving form one warehouse to another earlier in this article.

1. John requests the total of all accounts.
2. Jane transfers money from savings to checking while John’s transaction is running.
3. John gets the wrong total.

Here the analysis of the data is inconsistent because the state of the data was not preserved throughout the life of the read transaction. Under locking:

1. John requests total of all accounts thereby placing a read lock.
2. Jane transfers money but cannot place a write lock to commit the transfer due to John’s read lock. Jane must wait until the read transaction finishes.
3. John gets the right total, releases the read lock and Jane’s transaction proceeds.

Under versioning:

1. John requests the total of all of his accounts.
2. Jane transfers money from savings to checking resulting in new versions which John’s transaction does not see.
3. John gets the right total and Jane’s update is not delayed.

Another variation of the serializable problem occurs if you need to reread the data in the course of the transaction. For example:

1. Query for all rows meeting certain criteria.
2. Another user inserts a new row that meets the criteria.
3. Repeat the query and you will get one additional row. The appearance of this phantom row is not consistent within the transaction.

With a database that uses the locking model the only way to prevent this inconsistency is to read lock the whole table for the duration of the transaction. Thus the sequence of events is:

Place a read lock on the table.

Query for all records meeting certain criteria.

Another user attempts to insert a record but is blocked by the table level read lock.

Repeat the query and you will get the same results because other users cannot commit changes.

Under versioning there is no problem because the newly inserted record has a higher transaction number than the read transaction and so it is ignored on the second and subsequent reads that are part of the same transaction.

So far it looks like the versioning model handles most concurrency conflicts better than the locking model. However, this is not always the case. Consider the following case where John and Jane are both told to make their salaries equal.

1. John reads John’s salary.
2. Jane reads Jane’s salary.
3. John sets Jane’s salary equal to John’s.
4. Jane sets John’s salary equal to Jane’s.

The result is that John’s and Jane’s salaries are swapped. Using locking you can prevent this by locking both records.

1. John reads his salary and places a read lock.
2. Jane reads her salary and places a read lock.
3. John sets Jane’s salary equal to his own but cannot commit due to Jane’s read lock.
4. Jane sets John’s salary equal to her own but cannot commit due to John’s read lock.

Once again you have a deadlock which the database system should resolve by rolling one transaction back. Another solution, using locking, is to write lock the entire table as in the following scenario.

1. John write locks the table.
2. John reads his salary.
3. Jane tries to read her salary but is blocked by John’s table level write lock.
4. John sets Jane’s salary equal to his own and releases the write lock.
5. Jane’s transaction is now free to proceed.

Under versioning:

1. John reads his own salary.
2. Jane reads her salary.
3. John sets Jane’s salary equal to his and commits.
4. Jane sets John’s salary equal to hers and commits.

Since versioning allows both transactions to process concurrently once again the salaries are swapped. The only way to solve this problem with the versioning model is as follows.

1. John reads John’s salary.
2. Jane reads Jane’s salary.
3. John sets Jane’s salary equal to John’s.
4. John sets John’s salary to itself creating a newer version.
5. Jane sets John’s salary equal to Jane’s but rolls back because a newer version exists.

Here the problem is solved by setting John’s salary equal to itself. This forces the creation of a new record version for John’s salary. Since versioning architecture will not allow a change to be committed when a version of the record to be updated exists which was created after the start of the current transaction Jane’s update rolls back.

Recovery

One very important issue in database applications is recovery time if the server crashes. No matter how robust your hardware and software and how reliable your power supply there is always a possibility that the server will fail. Both locking and versioning databases will recover automatically when the server is restarted but there is a significant difference in the time that recovery will take if many transactions are active at the time of the crash.

Locking model databases write each transaction to a log file. To recover after a crash the database manager must read the log file and rollback all of the transactions that were active at the time of the crash by copying information from the log to the database.

A versioning database does not have a log file. The record versions in the database provide all of the information needed to recover. No data needs to be copied from one place to another. Instead, when the database manager comes back on line it simply scans the transaction inventory pages and changes the status of all active transactions to rolled back. This will take at most a few seconds even with a large number of active transactions. Crash recovery is another area where the versioning model excels.

What happens if the one of the disk drives hosting the database has a mechanical failure? With locking model databases you can usually place the log file on a different device and log all transactions since the last database backup. If a physical drive failure occurs you can restore from the last backup and reprocess the log file to recover the database. With a versioning database the only protection against a drive failure is to mirror the database. You can use InterBase’s built in shadowing to accomplish this, use RAID drives or use mirroring at the operating system level.

Expanding the Database

While some databases require you to shutdown the database to increase the size of the log file and to unload and reload the data to increase the size of the database InterBase does not. InterBase databases expand automatically up to the maximum size allowed by the file system as more data is added. If the database is approaching the maximum size allowed by the operating system more space can be made available by adding a secondary file using the ALTER DATABASE command. While ALTER DATABASE requires exclusive use of the database it is very fast since it does not require the data to be dumped and reloaded.

Other Issues

At first it might appear that a versioning database has a significant disadvantage because the multiple record versions will cause the database size to increase rapidly compared to a locking database. While that is true do not forget that other databases grow also as their log files expand.

However, versioning databases will certainly grow rapidly if something is not done to control the proliferation of record versions. The database manager performs some of the housekeeping for you automatically. Each time a record is accessed the database manager checks to see if any of the prior versions of that record are no longer needed. A version is no longer needed if its transaction rolled back or if there is a later committed version of the record and there are no active transactions with a transaction number less than the transaction number of the newer committed version. Versions that are no longer needed are automatically deleted and the space they occupied in the database pages is reused.

Many rows in many databases are visited infrequently. To remove unneeded versions of these rows the database must be swept periodically. A sweep operation visits every row in every table in the database and deletes outdated versions. You can run the sweep while the database is in use but the sweep will impact performance while it is running.

InterBase, by default, will automatically start a sweep after 20,000 transactions. That is not the best way to manage sweeping because you have no control over when the sweep will start and the user that starts the transaction that triggers the sweep is locked until the sweep finishes. It is better to manually start a sweep periodically at a time when database usage is low. Transaction performance is also improved by a sweep performed when no one else is using the database or by a backup and restore. This is because InterBase will not remove record versions older than the Oldest Interesting Transaction (OIT). The OIT is the oldest transaction whose state is something other than committed. The state of all transactions since the OIT is maintained in the TIP and the record versions for these transactions are retained in the database. Performing a sweep when you have exclusive use of the database or performing a backup and restore will reset the OIT to the last committed transaction and remove all prior transactions from the TIP and remove their versions from the database. This not only frees the maximum amount of space in the database but also reduces the size of the TIP. Since the TIP must be copied for each transaction when it starts making the TIP smaller means that transactions will start faster.

InterBase has a very small footprint requiring less than 10 megabytes of disk space and is very easy to install and configure. There are only two parameters you need to set. The first is the page size of the database and the second is the cache size in pages. Once these parameters are set InterBase tunes itself to provide optimum performance. Easy installation and maintenance make InterBase a good choice for installations where there is no database administrator. Finally, InterBase runs on a wide variety of platforms which makes it easily scalable to handle changing needs.

InterBase also supports multiple character sets per table making it an ideal choice for international applications. InterBase pioneered efficient storage of BLOB data and supports multiple BLOB fields per database as well as updateable views.

Conclusion

Selecting the right database for your application requires a clear understanding of the types of transactions the system will have to process. Many applications today include a mixture of multi-row read transactions and updates. In this environment versioning has a clear advantage because it can process read and write transactions concurrently while still providing serializable isolation to ensure accuracy. Versioning also provides very rapid crash recovery since there is no log file to process. When a versioning database restarts it simply marks all open but uncommitted transactions as rolled back and is ready to go.

At this writing Inprise’s InterBase is both the newest of the major database servers and the only one to use the versioning model. In addition to the advantages of the versioning model InterBase has the smallest disk and memory footprint (it ships on two diskettes), is self tuning and runs on Netware, Windows NT and a wide variety of Unix platforms so it is highly scalable.