Java on Mac

Recently bought an iMac - with 24inch screen, and this is now my development platform for simpledbm. I am using JDK 5 and Eclipse 3.3.

So far one test case has failed. Upon investigation, found that the behaviour of FileChannel locking is different on the Mac. It seems that Mac JVM allows multiple threads within the same JVM to acquire exclusive locks on a file concurrently - whereas on Windows, we get an OverlappingFileLockException exception. It also seems that within the same thread, it is okay to acquire a lock more than once on the same file on Mac but not on Windows.

I was relying on the locking behaviour I saw on Windows, to allow simpledbm to detect multiple instances of simpledbm running concurrently against the same database.

Interestingly, the specification of locking behaviour seems contradictory:

File locks are held on behalf of the entire Java virtual machine. They are not suitable for controlling access to a file by multiple threads within the same virtual machine.

But on the other hand:

The locks held on a particular file by a single Java virtual machine do not overlap. The overlaps method may be used to test whether a candidate lock range overlaps an existing lock.

Which is right?

SimpleDBM Beta release is out

At long last, an early Beta release of SimpleDBM is out. Downloads are available from SimpleDBM project website. A User Manual is also available.

Due to work pressures, progress has been very slow during the last one year. I am now hoping to build a few sample applications. Testing is still a priority as there are still not enough test cases in some areas, such as the Tuple Manager module, and in particular, coverage of crash/recovery scenarios.

Why another database manager?

A friend asked me recently why I spent my time implementing a DBMS, when there are already a number of open source databases. It is a good question because clearly I am not breaking any new ground here. In fact, I find myself incapable of inventing great new technology. Most of what I am implementing is well known stuff. I am a software engineer, rather than a scientist, going by the definitions of engineers and scientists by C.A.R.Hoare. It seems that this project is pure self indulgence, when I could be spending my time more fruitfully, either contributing to projects like Apache Derby, or working on something more relevant.

I guess that if I am honest with myself, I have to admit that there is an element of self indulgence here. But there is also some utility. The knowledge I gain in the process is a benefit to me in my work life. But apart from that, I think that my DBMS implementation is better documented and easier to understand than other opensource implementations. This is for a couple of reasons:

1. I use well established algorithms, which are well documented in computer science literature. I am also putting more effort into documentation than is typical of many opensource projects.
   
2. The system is decomposed into well defined modules which are loosely coupled. I find most other implementations are far more integrated, and therefore difficult to understand. I have traded off performance and efficiency in favour of ease of understanding.

There are still no books that describe how to build a real DBMS, and also show you with real code how DBMS features such as transactions, locking, recovery, btrees, etc. work. The only book that comes close is Transaction Processing: Concepts and Techniques, but the sample code contained in this book is not complete. In some ways, my project provides a sample implementation of many of the techniques described in this book.

Finally, there is the question of pride. When I started this project many years ago in C++, I never thought I could do it. I had no training in this field, and no access to people who do this type of stuff at work. Having come this far, it seems a shame to give up.

Premature Optimisation

Here is an example of C.A.R.Hoare's statement that premature optimization is the root of all evils.

In implementing the Lock Manager in SimpleDBM, I was concerned about the impact thread synchronisation would have on the scalability of the Lock Manager. The Lock Manager uses a hash table to speed up lookups of the locks. Many implementations of Lock Managers synchronize the entire hash table while manipulating locks. There is an issue within the Apache Derby project discussing the scalability problems posed by such global synchronisation. The SimpleDBM implementation does not use a global lock. Instead it uses a custom hash table, where every hash bucket contains a ReentrantLock. The hash bucket lock is acquired before any traversal or modification is performed on the bucket's chain. I went even further and put a ReentrantLock into each Lock Header object. A Lock Header is required for each active lock in the system. The Lock Header maintains a queue of lock requests (clients) for the lock. Lock Headers are the objects that get put on the hash chains.

The idea was that the hash bucket lock could be released early by obtaining a lock on the Lock Header, once the Lock Header had been found. This would increase concurrency by reducing the duration for which the hash bucket needs to be kept locked.

In my attempt to further reduce locking, I tried to find ways of reducing the time for which the hash bucket lock was held. One such optimisation involved setting a field in the Lock Header to null rather than manipulating the hash bucket chain when releasing a lock. This code worked fine until the day I tried testing in a multi processor environment (CoreDuo), when I found that one of my test cases started failing. This test case was designed to stress concurrent operations on the same hash bucket. The problem was that in attempting to optimise I had broken the code. The optimisation was flawed because in one section of the code I was modifying the field in the Lock Header while holding the Lock Header lock, while in another section, a search was being performed on the hash bucket while holding the hash bucket lock, and this search was inspecting the field that was being updated.

A lesson from this is that multi-threaded code must be tested on a multi-processor machine.

Anyway, when I hit the bug described above, I decided that it was time to revisit the thread synchronisation code in the Lock Manager. I realised that I was attacking the wrong problem in my tuning efforts, because there were bigger scalability issues that needed fixing compared to the problem I was trying to fix.

The first problem was of memory usage. I was using too many ReentrantLocks; one per hash bucket, plus one for each lock header. In a system with 10,000 concurrent active locks, the total number of ReentrantLocks would be 10,000 plus the number of buckets in the hash chain. If I wanted to make the Lock Manager scalable, I needed to reduce the amount of memory used per lock.

The second problem was that the hash table was not dynamic. Its size was fixed at the time of creating the Lock Manager. This was likely to cause severe performance and scalability problems due to hash collisions. It would be virtually impossible to set the correct hash table size statically, and a poor hash table would cause more hash collisions leading to long hash chains, which would mean greater contention between threads trying to access the same hash bucket.

I decided that locking at the level of Lock Headers was not giving me sufficient bang for money, whereas, if I made the hash table dynamic, and used Java's inbuilt monitors instead of ReentrantLocks to synchronise the buckets, the system's overall efficiency and scalability would be greater than what my current code was achieving. The increase in the number of hash buckets would reduce the number of hash collisions and thereby lock contention amongst threads. The reduction in the number of ReentrantLocks would reduce memory usage and therefore make the Lock Manager more scalable. The refactored code would also be simpler and easier to maintain.

Lock Manager updates

SimpleDBM's Lock Manager is based upon the algorithms described in Transaction Processing: Concepts and Techniques. Until now, the Lock Manager did not have support for deadlock detection. A simple timeout mechanism was used to abort transactions that were in a deadlock. Yesterday I decided to start implementing a deadlock detector. As I was researching this, I discovered a problem in the way rollback to a savepoint is implemented by the Transaction Manager. When rolling back to savepoint, any locks acquired after the savepoint are released. However, any locks released after the savepoint are not re-acquired. There are times when locks can be released early, for example, when using cursor stability mode, the lock on current row is released when the cursor moves to the next row. When rolling back to a savepoint, we need to restore cursors to their status as at the time of savepoint, and ensure that the cursors reacquire locks on the current row. Since SimpleDBM does not have cursors yet, this is not a problem right now. The difficulty is how to implement this type of interaction between cursors and the Transaction Manager. It seems to me that the Transaction Manager needs to know which cursors are being used by a transaction, and for each cursor, save current row in the savepoint. When the transaction rolls back to a savepoint, the saved information can be used to reposition the cursors to the correct rows and reacquire locks. Since I want to avoid this type of close dependency between the transaction manager and other modules, it will most likely be necessary to implement the Observer pattern.

Speaking of the Observer pattern, I had to recently add a LockListener interface to the Lock Manager module. This was required to allow me to write better test cases. Designing test cases where multiple threads interact in a certain way is complicated. Earlier I used a simple strategy - threads went to sleep for certain intervals, and the pauses between the thread executions were timed just so that the correct thread interaction could be achieved. Unfortunately, this meant that the test cases often had a number of sleeps in them, which slowed everything down. Also, I dislike the approach because it is a hack. In some of the new and revised test cases, I now use the LockListener facility to identify wait points within the locking subsystem. Thus an event is generated when the lock requester is about to start waiting for a lock. This event is trapped by the test cases to synchronize between multiple concurrent threads of activity.

The deadlock detection algorithm I am using is based upon the simple deadlock detector described in the Transaction Processing book alluded to before. However, the code presented in the book requires tight coupling between the Lock Manager and the Transaction Manager, whereas in my implementation, the Lock Manager has no knowledge of the Transaction Manager. Loose coupling makes code more flexible, but there is a cost. Tight coupling can reduce memory consumption quite a bit and improve efficiency, as there is less need for redundant information. For example, in the book, each Transaction contains a pointer to the lock request that is being waited for, and the Lock Manager freely accesses this information. In SimpleDBM, the Lock Manager maintains a separate HashMap where lock waits are recorded, so that the Lock Manager can navigate the lock waits graph without any knowledge of the clients invoking the Lock Manager.

New source repository for SimpleDBM

SimpleDBM has a new source code repository. I moved the source code from ObjectWeb's repository to Google Code because I found the ObjectWeb repository somewhat slow and unresponsive. The SimpleDBM web pages are still hosted at ObjectWeb.

In the past few months, SimpleDBM's source code repository has move from java.net to ObjectWeb to Google Code, which I hope will be its final resting place. Compared with ObjectWeb and java.net, Google Code has the usual Google stamp of clean uncluttered interface, and relatively faster response. Another thing I like is that as soon as the code is checked in, it appears on the web site.

Package structure

There has been a revision in the package structure within SimpleDBM.

In the earlier structure, the API and the implementation of a module were designed to be together. Hence, if there was a module named test, the packages would have been org.simpledbm.rss.test for the API, and org.simpledbm.rss.test.impl for the implementation.

The current structure is more favoured towards separating the whole of the API from the implementation. In the new structure, all APIs are under org.simpledbm.rss.api.<module>, and all implementations are under org.simpledbm.rss.impl.<module>. I decided to separate the API from the implementation in this way for two reasons:

1. It would be easier to generate JavaDoc for the API alone.
2. The API could be packaged separately in its own jar file without too much effort.

Unit testing and MVCC in Berkeley DB

After a break of several months, I am about to start working on SimpleDBM again. I am determined not to add any new functionality until existing functionality is thoroughly tested and fully documented.

Currently I am working on improving the unit test cases for the BTree module. This is easily the most complex module in SimpleDBM, and producing comprehensive unit test cases is a significant task in its own right. Anyhow, the effort will be worthwhile as a database system is only useful if it is completely reliable.

It was exciting to learn that Oracle has added support for Multi Version Concurrency in Berkeley DB. I haven't looked at the implementation in great detail but a cursory look seems to indicate that the changes are mainly in the Buffer Pool. To support MVCC, the Buffer Pool has been enhanced to hold multiple versions of pages. Readers can obtain a snapshot of the database using older versions of pages, and thus avoid obtaining locks on rows being read. Unlike Oracle's own version which reconstructs older versions of pages using the undo log, the Berkeley DB implementation appears to be a simple memory based versioning solution. The downside will be that this will not scale to large workloads as it will require huge amounts of memory if the number of pages being versioned increases significantly.

SimpleDBM moving to ObjectWeb

SimpleDBM is moving to ObjectWeb. The reasons for this move are:

1. ObjectWeb specializes in building middleware solutions. I hope to build a community of users and developers who are like-minded and interested in middleware technologies.
2. Java.net is run by and has too much focus on Sun Microsystems. In some ways it is a propaganda tool for Sun. I wanted a more open environment for SimpleDBM, where every project has the same status.

A related news is that I am migrating the version control from CVS to Subversion.

Creating Oracle DataSource in Glassfish

To setup an Oracle Datasource in Glassfish, follow these steps:

1. Copy the Oracle JDBC drivers to /glassfish/domains/domain1/lib/ext directory. You may need to change the directory /glassfish/domains/domain1 to match your installation of Glassfish and the domain name.

2. Start Glassfish.

3. Login to the admin interface and create a JDBC Connection Pool.
Delete all properties, and add following properties:
user - set this to Oracle userid
password - set this to Oracle password
URL - set this to the URL, example jdbc:oracle:thin:@localhost:1521:xe.
xa-driver-does-not-support-non-tx-operations - set this to true.
Test the connection pool using ping.

4. Create a JDBC DataSource using the Connection Pool.

Testing

Due to changes in my work life, I have not been able to devote much time to SimpleDBM in recent weeks. Things are getting back to normal slowly and I am beginning to work on some of the outstanding tasks. The main focus is to provide a usable RSS component, which is feature complete, but needs more test cases, and more testing.

Although test coverage is a useful measure of the effectiveness of test cases, it does not help you much with issues related to multi-threading. Sometimes, obscure bugs are discovered by chance - for example, I discovered a bug in my BTree test harness when I disabled some diagnostic logging. The small time difference caused by this change led to a different interaction between threads, and exposed the bug.

I want to devote more time to testing the RSS components because they provide core services that are fundamental to the rest of the system. Higher level components need to be able to rely completely on the correct functioning of RSS.

Oracle JDeveloper as JSF Editor

After trying out various IDEs for editing Java Server Faces (JSF) files, I have finally settled on Oracle's JDeveloper as the best tool for the purpose. I had assumed that JDeveloper would insist on using ADF, but found to my pleasant surprise that it also allows you to design standard JSF pages in a visual manner. Unlike Sun Java Studio Creator which creates its own backing bean class, JDeveloper gives you full control, and lets you decide whether you want all/some/none of your UI components to be in your backing bean.

The Java IDE marketplace is such that no single tool meets all your needs. I find Eclipse is good for general purpose Java programming but not much use for J2EE stuff. Netbeans doesn't work for me - I have tried to use it several times but each time I have given up in frustration because I either cannot resolve some wierd error, or cannot get the IDE to do something simple. To give you an example, I try to edit a JSF file in Netbeans, and it will show code completion for jsp tags, but not for JSF. I don't have the time to work out why.

Servlets and dependency injection

There is a very useful thread at the Glassfish discussion forum on the why it is not a good idea to use dependency injection to obtain references to EJBs or EntityManagers in Servlets.

Remote or Local interface?

EJB 3.0 takes away much of the pain associated with maintaining the Local and Remote interfaces for Session Beans. However, there are still some issues that you need to be aware of.

By design, the EJB specification disallows the same Business interface to be marked as @Local as well as @Remote (this restriction has been added in a revision to the PFD). The reason for this is that remote interfaces have different semantics to local interfaces, and it is usually inappropriate for the same method to be exposed as a remote interface as well as local interface. The problems are two-fold:

1. Remote interfaces must typically be designed to be coarse-grained.
2. Remote interfaces do not support the pass-by-reference semantics of parameter passing as in local interfaces.

Having separate Remote and Local interfaces forces designers to think about how the interfaces will be used and ensure that the design is optimised for the use case. It also reduces the chances of errors caused by incorrect semantics, such as clients relying upon ability to pass parameters by reference.

A drawback to this approach is that it does not allow transparent redeployment of an EJB from a co-located environment to a distributed environment or vice-versa. While such re-deployment has its dangers, there are times when it can prove useful to have such a facility.

Ideally, you should define your Session beans to have either remote or local interface. This will keep the design simple and allow you to implement Business Logic as POJOs.

If you do want to endow the same Session Bean with both remote and local interfaces, then, I suggest that you use the following example as a model:

public interface CustomerService {
    
   void createCustomer(District d, Customer c);
   void removeCustomer(Long id);
   List findByDistrict(District d);
    
   @Remote 
   public interface IRemote extends CustomerService {
   }

   @Local 
   public interface ILocal extends CustomerService {
   }
}

Note that the local and remote interfaces extend a common business interface. Also note that the local and remote interfaces are nested within the business interface. I like this model because it reduces the clutter, keeps related interfaces together, and eases understanding.

When using dependency injection, you can specify explicitly whether you want the remote or local interface. For example:

@EJB(beanInterface=services.DistrictService.IRemote.class)
public final void setDistrictService(DistrictService districtService) {
   this.districtService = districtService;
}

I also suggest that when specifying dependency injection, always annotate your setters rather than instance variables. This will allow you to use your beans outside the J2EE container, for example in a Spring Framework environment.

EJB 3.0 Packaging - Entities

I am looking at the various EJB 3.0 packaging options and trying to determine best practice. My first recommendation is that you should create separate projects for your entities and package your entities in independent jar files. This is important for a number of reasons.

Firstly, you will want to share your entities in multiple projects, so having them maintained independently makes it easier to share them across projects.

Secondly, the teams that define the entities are probably going to work closely with the folks that are responsible for defining the database Entity Model. It will be easier if these teams can work independently from other teams.

Last but not least, it is not possible to define Entities in a portable manner. The main portability issues are with the way Surrogate Keys are generated using Sequence Generators. Having separate projects for your entities will allow you to create drop-in replacements for different database vendors. So you can have one set of entities for Oracle, another for Apache Derby, and so on. For an example of this, please have a look at the EJB3Demo project.

When you create your application archives, place the Entity jar files in the lib sub-directory within the archive. This will ensure that the entity definitions are available to all your EJBs and Web applications within the application. This article by Sahoo explains the benefits of putting your entity jar files in the lib directory.

More EJB 3.0

For the past few days I have been working on a number of things. I shall blog about them in more detail when I have some time, but in the meantime, here is a summary:

1. Packaging issues. EJB 3.0 brings hassle-free packaging, however, it is still not easy to understand what the rules are. A discussion on packaging issues can be found here and here.

2. Semantics of merge() and persist() and how they are implemented in Glassfish is being discussed here.

3. Does EJB live up to its promise to bring POJO style programming to J2EE? I previously blogged about the fact that EJB 3.0 Entities are not really POJOs because they contain hidden semantics. See here for a discussion of dependency injection of EJBs and whether it is possible to implement Business Logic as POJOs.

Tuple Manager implementation is feature complete

Recently completed the implementation of Tuple Scans. Unlike Index Scans which use next key locking to avoid phantom reads, the Tuple Scan implementation does not protect the gap between one tuple and the next. This means that Tuple Scans cannot provide strictly Serializable behaviour. I wonder if this will be an issue later on.

Sharing attributes across Entities

One way to share common attributes across entities is to use inheritance, and put the common attributes in a super class. Another way is to abstract the common attributes into a separate Embeddable class and then embed it within the regular Entity classes. The latter approach has been used for some of the entities in the EJB3Demo project.

The entities Customer, District and Warehouse all contain some very similar columns for storing address information. I created a new class called Address to hold this common data. The Address class is marked as @Embeddable and contains the getters/setters for the attributes. Here is an extract:

@Embeddable public class Address implements Serializable {
    String street1;
    String city;
    @Column(length=20)
    public String getCity() {
        return city;
    }
    @Column(length=20)
    public String getStreet1() {
        return street1;
    }
}

Note that the getters have been annotated using @Column - this is useful for capturing the bits that are shared across the entities.

When you embed the Address object within an Entity, you can fine-tune the column mapping. Example:

@Entity
public class Customer {
    Address address;
    @Embedded
    @AttributeOverrides({
        @AttributeOverride(name="street1", column=@Column(name="C_STREET_1")),
        @AttributeOverride(name="city", column=@Column(name="C_CITY")),
    })
    public Address getAddress() {
        return address;
    }
}

The getter for the Address object is decorated with the @Embedded annotation. The address object can be shared amongst multiple entities, and each entity can define its own column names, etc.

When you access embedded objects in EJBQL, you use the property name in the Query statement. For example, to access the city field in Customer, you would write:

SELECT c.address.city FROM Customer c

This syntax is also used when you have relationship mappings. For example, a District belongs to a Warehouse, and hence the District object contains an instance of the Warehouse object. To access the fields within Warehouse, you would write:

SELECT d.warehouse.name FROM District d

Although one could use inheritance to model above, I prefer to use the Embeddable class option as it more accurately reflects what is happening here. A Customer is not an instance of Address - a Customer has an Address. In this situation, Has-A relationship is more natural than Is-A relationship.

EJB3Demo project

I have started a new project at www.java.net. The goal of this project is to try out various features of Java EE 50, such as EJB 3.0, JAX-WS, JAXB, etc., and identify design/code patterns that result in:

1. Improved portability and reusability of code, in particular, allow Business Logic and Data Access logic to be deployed inside and outside J2EE containers.
2. Better separation of concerns while exploiting new persistence features of EJB 3.0.

I hope to blog about some of this stuff soon - stay tuned. In the meantime, I would welcome anyone who would like to contribute to the project.

The source code for the project is available for download from https://ejb3demo.dev.java.net/servlets/ProjectDocumentList.

Reusability of Code

I have given up trying to get the TPCC schema work as defined, i.e., using composite keys. Glassfish at present does not support Id Generators with composite keys, which poses a problem, as it means writing extra code for generating keys. As a workaround to this issue, I have modified the schema to use surrogate primary keys.

EJB persistence design favours Entity Relationships based upon surrogate primary keys.

One of the great benefits of EJB 3.0 is that it gets rid of all the boiler plate EJB code, allowing you to code Entity and Session beans as if they were POJOs. This raises the expectation that in this new world, it should be possible to write reusable code that is environment agnostic. By this I mean that I should be able to reuse my J2EE Business Logic classes and the Persistent classes in a J2SE or Servlet Container (Tomcat) environment without having to change any code.

There is an immediate stumbling block to achieving this, however. The unfortunate decision to introduce a new abstraction for Transaction Management for J2SE environment means that tranaction management code is not portable. The first rule for writing reusable code therefore is to avoid transaction management code in your classes. I will report on other pitfalls as I progress with my attempts to create reusable code.