Saturday, July 04, 2009
From Subversion to Mercurial
SimpleDBM source code repository has been migrated from Subversion to Mercurial. For a somewhat rude and OTT presentation on the benefits of distributed version control systems over traditional centralized systems see the Linus Torvald's presentation on GIT.
Sunday, April 12, 2009
What next?
The SimpleDBM core database engine has been out for a while, and although I am still working on improving the robustness of the code, writing more test cases, etc., it is also time to start thinking about what next.
Couple of areas interest me.
A simple SQL layer so that it becomes easier to write code against the database. Unlike other projects, I am not interested in a full-blown SQL implementation, just enough to cut down the procedural code one must write. My current thoughts are towards a very basic set of SQL statements to manipulate data from just one table. No joins, etc.
A network server/client so that instead of embedding SimpleDBM inside the application it can be accessed remotely. Embedded implementations are hard to make use of in a multi-user environment. I am looking at projects like Netty and MINA as the underlying TCP/IP framework so that I can concentrate on the functional aspects rather than writing all the network stuff.
Couple of areas interest me.
A simple SQL layer so that it becomes easier to write code against the database. Unlike other projects, I am not interested in a full-blown SQL implementation, just enough to cut down the procedural code one must write. My current thoughts are towards a very basic set of SQL statements to manipulate data from just one table. No joins, etc.
A network server/client so that instead of embedding SimpleDBM inside the application it can be accessed remotely. Embedded implementations are hard to make use of in a multi-user environment. I am looking at projects like Netty and MINA as the underlying TCP/IP framework so that I can concentrate on the functional aspects rather than writing all the network stuff.
Tuesday, March 31, 2009
Dwarfs standing on the shoulders of giants
As I mentioned in a previous post, when building SimpleDBM I have used design ideas that I have picked from various technical research papers as well as other OpenSource projects. I would like to list some of the influences here, and acknowledge my indebtedness.
Papers from IBM's System-R research project have influenced the role of the database engine in SimpleDBM. I have named the core engine as RSS in honor of the System-R Relational Storage System (RSS).
A general reference that has proved invaluable is the classic Transaction Processing: Concepts and Techniques, by Jim Gray and Andreas Reuter. The Lock Manager and the Buffer Manager modules are based upon descriptions in this book.
The Lock Manager also uses ideas from the OpenSource project Shore. The handling of lock conversions and the deadlock detector are based upon code from this project.
The Transaction Manager is based upon the algorithms published in the ARIES series of papers by C. Mohan of IBM. I am also indebted to Mohan for the implementation of lock isolation modes, and implementation of free space management in containers.
The BTree implementation is based upon the algorithms described by Ibrahim Jaluta et al in the paper Concurrency control and recovery for balanced B-link trees.
The idea of using the write ahead log records for normal execution of forward actions is taken from Apache Derby. This is a neat idea that ensures that both normal and recovery processes use the same code for performing updates to the database. Essentially all updates are executed through log records, even during normal execution.
Projects that I have learned from but that haven't directly influenced the implementation include:
Papers from IBM's System-R research project have influenced the role of the database engine in SimpleDBM. I have named the core engine as RSS in honor of the System-R Relational Storage System (RSS).
A general reference that has proved invaluable is the classic Transaction Processing: Concepts and Techniques, by Jim Gray and Andreas Reuter. The Lock Manager and the Buffer Manager modules are based upon descriptions in this book.
The Lock Manager also uses ideas from the OpenSource project Shore. The handling of lock conversions and the deadlock detector are based upon code from this project.
The Transaction Manager is based upon the algorithms published in the ARIES series of papers by C. Mohan of IBM. I am also indebted to Mohan for the implementation of lock isolation modes, and implementation of free space management in containers.
The BTree implementation is based upon the algorithms described by Ibrahim Jaluta et al in the paper Concurrency control and recovery for balanced B-link trees.
The idea of using the write ahead log records for normal execution of forward actions is taken from Apache Derby. This is a neat idea that ensures that both normal and recovery processes use the same code for performing updates to the database. Essentially all updates are executed through log records, even during normal execution.
Projects that I have learned from but that haven't directly influenced the implementation include:
Delayed release
The next BETA release of SimpleDBM has been delayed due to my desire to re-factor some of the code. The re-factoring has been focused on following:
- Removing all singletons - even Loggers. Unfortunately, Log4J and other logging packages all use singletons, so this is not completely possible unless I replace the entire logging package.
- Ensuring that the serialization mechanism uses constructor based object initialization rather than retrieving state after construction.
- Above enables the use of final fields in many objects, allowing them to be immutable.
Saturday, August 23, 2008
A History of SimpleDBM
The SimpleDBM project started as the DM1 project in August 2001. Initially, I started writing the database code in C. A year later, I ported the code to C++. Here is what I wrote at the time about my switch to C++:
I decided to port the product to C++ primarily for following reasons:Progress over the next few years was slow. This was partly because there were long periods when I wrote nothing, and partly because I had to do research for the project. I am self taught programmer with no formal degree in Computer Science. I have also never worked for a database vendor. Implementing a database has been an ambition for a long time. I had already implemented single user persistence storage system in C++, but this was nowhere near a real database system with transactions.
- I wanted to use the automatic construction and destruction facility in C++. I think this is one of the coolest features of C++. As an aside, I like Java's finally solution better than C++ destructors because with finally, I am able to control the destruction of objects better.
- I was apprehensive about using C++, because I find that C++ is a large and complicated language. In order to keep the DM1 Threads code simple, I made some decisions that are sure to be controversial:
- I do not use the C++ standard library, including the STL, at all. This is because I do not like the code bloat that results from its use. I also do not like the idea of using the heap for creating simple objects like strings. I think that C programs are generally more efficient than C++ programs, because they are much more circumspect about using the heap. One advantage of not using the C++ standard library is that it makes DM1 Threads more portable.
- I do not use templates other than in a very small way.
- I use sparingly or not at all, certain features of C++ language, such as multiple inheritance, operator overloading, new style typecast operators, etc. This is because I feel that none of these features are essential (Java does without them nicely).
- I think that Java is a better language than C++, but the lack of certain features (efficient array handling, pointers, etc.) makes it unsuitable for a project like DM1. In many ways, I use C++ as a better Java. C# would have been a good choice, but due to its lack of availability on UNIX platforms, I was unable to use it.
I was helped tremendously by reading code of other Open Source systems such as Shore and PostgreSQL. Another source of information was the research published by ACM and also by IBM researcher C. Mohan. I became a member of ACM in 2001 just so that I could access all the research.
There weren't and still aren't any books that go into the nitty-gritty of implementing relational databases. The only book that came remotely close to discussing some of the details of a database engine was the book Transaction Processing: Concepts and Techniques, by Jim Gray and Andreas Reuter. This was a life saver.
Then IBM announced in 2004 that they were open sourcing Cloudscape. I was very excited because here was a database that was written in Java, and that performed quite well. Another key event was the release of Java 1.5 (Java 5.0). Finally there was a version of Java that had the locking primitives that I needed for my database project. I procrastinated for a while because I did not fancy porting all the code I had written in C++ to Java.
Fortunately (for the project), the company I was working for at the time, got taken over. There was a period of inactivity as we awaited the fate of our IT department. Having not much to do at work meant that I had spare time and was able to use this time to port the code to Java. This was in late 2005, which was the most fruitful six months I spent on the project.
I completed most of the core modules of SimpleDBM in the six months between July and Dec 2005. Since then I have spent more time testing and refactoring, and added the TypeSystem and Database API modules. After I changed my job in 2006, progress has been sporadic. I had a period of year and half when I was so busy at work that I was taking work home every day. I was unable to spend time on SimpleDBM at all.
Early in 2008, I was approached by an ex-database enterpreneur who suggested that I should do some work on Apache Derby. I thought of ditching SimpleDBM to work on Derby. Unfortunately, this relationship did not work out. Now I think that if I am working on my own free time, then it is more fulfilling to work on SimpleDBM, as everything I create is my own. I have considerable freedom, and the ability to work on areas that interest me. I would very much like to work on Apache Derby but cannot afford to do so unless it is a paid job.
Wednesday, July 09, 2008
SimpleDBM release 1.0.8 BETA is out
At long last, I have put together the 1.0.8 BETA release. This contains the experimental TypeSystem and Database API module.
Thursday, July 03, 2008
Update on SimpleDBM's Data Dictionary
I have chosen to implement option 3 as described in a previous post. For each table, a special container is created, which is used to store not only the table structure but also structures of all associated indexes. Special containers are created for indexes as well but these contain pointers to the table structures. (The reason we need the index definition containers is that during recovery an index update may be performed prior to a table update.)
A memory cache is maintained of the entire data dictionary. When a new table is created, its structure is immediately saved into the memory cache. The structure is also persisted using a PostCommitAction - which is a type of redo only log that is executed once the transaction commits.
At system restart, the storage system is scanned for containers that have a specific naming convention and are in a well known location. This way, SimpleDBM is able to initialize the memory cache at startup. Note that this initialization occurs post recovery. The list of open containers is consulted to ensure that only those definitions are loaded that are relevant.
There is a problem that during recovery, any redo/undo operation on a table or index will require access to the table/index definition. Since the data dictionary memory cache is not available at this stage - it is populated after recovery, the solution is to retrieve the definitions on demand.
The table/index creation process uses a standalone transaction. During this time the container IDs are exclusively locked. This ensures that by the time any subsequent transaction performs a data manipulation operation against the table, the data dictionary memory cache has been updated to contain the table definition.
At present tables cannot be dropped, as this has not yet been implemented.
Along with the Data Dictionary implementation, there is also a high level Database API that is available. This hasn't been released yet as it is still being tested. I am hoping that a fully tested version will be available towards the later part of this year.
A memory cache is maintained of the entire data dictionary. When a new table is created, its structure is immediately saved into the memory cache. The structure is also persisted using a PostCommitAction - which is a type of redo only log that is executed once the transaction commits.
At system restart, the storage system is scanned for containers that have a specific naming convention and are in a well known location. This way, SimpleDBM is able to initialize the memory cache at startup. Note that this initialization occurs post recovery. The list of open containers is consulted to ensure that only those definitions are loaded that are relevant.
There is a problem that during recovery, any redo/undo operation on a table or index will require access to the table/index definition. Since the data dictionary memory cache is not available at this stage - it is populated after recovery, the solution is to retrieve the definitions on demand.
The table/index creation process uses a standalone transaction. During this time the container IDs are exclusively locked. This ensures that by the time any subsequent transaction performs a data manipulation operation against the table, the data dictionary memory cache has been updated to contain the table definition.
At present tables cannot be dropped, as this has not yet been implemented.
Along with the Data Dictionary implementation, there is also a high level Database API that is available. This hasn't been released yet as it is still being tested. I am hoping that a fully tested version will be available towards the later part of this year.
Wednesday, February 27, 2008
SimpleDBM update
SimpleDBM project work has been slow for the past couple of months. This is because I have decided to develop SimpleDBM as a plug-in storage engine for Apache Derby, as an alternative to the Derby Store implementation. If anyone is interested in tracking this work, please visit the Apache JIRA system and look for DERBY-3351.
There are a few problems to be overcome for this to happen. One of this is to make some changes to Derby so that the Store components can be easily replaced. The good news is that Derby is already very modular, and its original design was intended to allow using the Store implementation on its own. I am working on improving the modularity of Derby, and to reduce dependencies between the layers. This work is likely to take several months or even the whole of this year.
The other main hurdle is that there are some fundamental differences in the design approaches taken by SimpleDBM and Derby.
Principal amongst these is that SimpleDBM treats Row and Index data as transparent blobs. This is an attempt to allow higher level implementations to choose their own row/index formats. In Derby, the row structure and the type system is known to the Storage Engine. The former approach is more flexible, but adds performance overheads. At present, my thinking is that to interoperate with Derby, I may have to adopt the Derby type-system.
Another fundamental design choice is the way modules plug into each other. In SimpleDBM, a constructor based injection pattern is used. The modules themselves do not decide how to obtain references to other modules. Derby allows each module to obtain reference to other modules via an intermediary, the Monitor.
SimpleDBM does not use static data in any way. Even the core of the system that instantiates objects, uses a dynamic lookup mechanism (ObjectRegistry) to map type codes to class types. Derby on the other hand, uses a fair number of static constructs. The Monitor system and the Context Manager are two key examples.
There are other areas of incompatibility. In the end, I do not know if this experiment will succeed in the way I would like it to.
There are a few problems to be overcome for this to happen. One of this is to make some changes to Derby so that the Store components can be easily replaced. The good news is that Derby is already very modular, and its original design was intended to allow using the Store implementation on its own. I am working on improving the modularity of Derby, and to reduce dependencies between the layers. This work is likely to take several months or even the whole of this year.
The other main hurdle is that there are some fundamental differences in the design approaches taken by SimpleDBM and Derby.
Principal amongst these is that SimpleDBM treats Row and Index data as transparent blobs. This is an attempt to allow higher level implementations to choose their own row/index formats. In Derby, the row structure and the type system is known to the Storage Engine. The former approach is more flexible, but adds performance overheads. At present, my thinking is that to interoperate with Derby, I may have to adopt the Derby type-system.
Another fundamental design choice is the way modules plug into each other. In SimpleDBM, a constructor based injection pattern is used. The modules themselves do not decide how to obtain references to other modules. Derby allows each module to obtain reference to other modules via an intermediary, the Monitor.
SimpleDBM does not use static data in any way. Even the core of the system that instantiates objects, uses a dynamic lookup mechanism (ObjectRegistry) to map type codes to class types. Derby on the other hand, uses a fair number of static constructs. The Monitor system and the Context Manager are two key examples.
There are other areas of incompatibility. In the end, I do not know if this experiment will succeed in the way I would like it to.
Saturday, December 29, 2007
Implementing System Catalog or Data Dictionary
It is the classic chicken and egg problem.
I would like to implement the system catalog in database tables. However, the system catalog will contain information that is a pre-requisite for working with tables. I do not know how other database implementations handle this cyclic relationship. It is made more difficult for SimpleDBM because the core database engine has no knowledge of the data dictionary or the type-system. These are implemented by add-on modules.
I considered following options for implementing the system catalog:
1. Simplest option would be to pre-define the schema for a database using a configuration file, which can be loaded at database startup. This may be adequate for many use cases, but implies that the database schema is statically defined, and tables cannot be created or dropped dynamically.
2. Second option is to implement the catalog as dynamic tables. The catalog tables would be pre-created when the database is created, and their structure would be known to the database manager. When a regular table is created, a row would be added to the system catalog table, to record the structure of the new table. The table creation would be handled as a standalone transaction (covering both the container creation and updating of the system catalog table), to ensure that it is completed before any attempt is made to access the new table. Index creation would be handled similarly.
When a regular table is accessed, its type structure will have to be retrieved from the catalog tables. This means some recursive locking, which I am worried about because so far, SimpleDBM has not needed to carry out locking during system restarts. Perhaps, we could optimize away the need for locking because SimpleDBM locks containers anyway when they are accessed, which means that there is already a lock that protects the table definition. Unfortunately, at present the SimpleDBM API does not support a read uncommitted isolation mode - which would be necessary to avoid obtaining locks on catalog tables when they are being read.
To avoid accessing the catalog tables every time a container is accessed, the first time a table is accessed, its definition would be retrieved and cached in memory for subsequent use.
3. A third option is to maintain the table definitions in special containers, and manage updates to these containers without going through the buffer manager. Here is a tentative design:
The structure of a table or index will be stored in a special container. This may be a single shared container or one container for each table or index. The multiple container option has the advantage that a simple naming convention could be used to quickly locate the appropriate container.
The database module will perform special reads and writes to these containers, bypassing the Buffer Manager, and Lock Manager.
The problem is how to guarantee that the data in the special container is updated atomically as part of the transaction that created the table or index. One way of achieving this would be to generate PostCommitActions for updating the metadata when a table or index is created or dropped. The PostCommitAction would be executed even during restart recovery, and would therefore ensure that the table or index definition is atomically updated as part of the transaction that created the table.
When a table or index is accessed, its definition can be retrieved and cached. Subsequent access will refer to the cache.
I would like to implement the system catalog in database tables. However, the system catalog will contain information that is a pre-requisite for working with tables. I do not know how other database implementations handle this cyclic relationship. It is made more difficult for SimpleDBM because the core database engine has no knowledge of the data dictionary or the type-system. These are implemented by add-on modules.
I considered following options for implementing the system catalog:
1. Simplest option would be to pre-define the schema for a database using a configuration file, which can be loaded at database startup. This may be adequate for many use cases, but implies that the database schema is statically defined, and tables cannot be created or dropped dynamically.
2. Second option is to implement the catalog as dynamic tables. The catalog tables would be pre-created when the database is created, and their structure would be known to the database manager. When a regular table is created, a row would be added to the system catalog table, to record the structure of the new table. The table creation would be handled as a standalone transaction (covering both the container creation and updating of the system catalog table), to ensure that it is completed before any attempt is made to access the new table. Index creation would be handled similarly.
When a regular table is accessed, its type structure will have to be retrieved from the catalog tables. This means some recursive locking, which I am worried about because so far, SimpleDBM has not needed to carry out locking during system restarts. Perhaps, we could optimize away the need for locking because SimpleDBM locks containers anyway when they are accessed, which means that there is already a lock that protects the table definition. Unfortunately, at present the SimpleDBM API does not support a read uncommitted isolation mode - which would be necessary to avoid obtaining locks on catalog tables when they are being read.
To avoid accessing the catalog tables every time a container is accessed, the first time a table is accessed, its definition would be retrieved and cached in memory for subsequent use.
3. A third option is to maintain the table definitions in special containers, and manage updates to these containers without going through the buffer manager. Here is a tentative design:
The structure of a table or index will be stored in a special container. This may be a single shared container or one container for each table or index. The multiple container option has the advantage that a simple naming convention could be used to quickly locate the appropriate container.
The database module will perform special reads and writes to these containers, bypassing the Buffer Manager, and Lock Manager.
The problem is how to guarantee that the data in the special container is updated atomically as part of the transaction that created the table or index. One way of achieving this would be to generate PostCommitActions for updating the metadata when a table or index is created or dropped. The PostCommitAction would be executed even during restart recovery, and would therefore ensure that the table or index definition is atomically updated as part of the transaction that created the table.
When a table or index is accessed, its definition can be retrieved and cached. Subsequent access will refer to the cache.
Saturday, November 03, 2007
New release 1.0.6
A new SimpleDBM RSS release (1.0.6 BETA) is out. This release contains an important bug fix to the Buffer Manager. The release can be downloaded from www.simpledbm.org.
Along with this release, there is also updated documentation. The User Manual is for developers who wish to use the SimpleDBM RSS component within their own projects. The Developer's Guide is for hackers who want to understand how SimpleDBM works and help me enhance it.
I recently installed Solaris 10 Developer edition on my home server. I was pleasantly surprised by how fast Java is on this platform. I am using a Mac as well, but the Java support on Mac is disappointing. The JVM just hangs sometimes when I am running SimpleDBM tests. Not because of locking or any other issue - it literally hangs - and if I connect to it using JConsole, there is no response.
I am working on a new sample which will demonstrate a higher level API than currently available. I hope to get a working version out by the middle of the month.
Along with this release, there is also updated documentation. The User Manual is for developers who wish to use the SimpleDBM RSS component within their own projects. The Developer's Guide is for hackers who want to understand how SimpleDBM works and help me enhance it.
I recently installed Solaris 10 Developer edition on my home server. I was pleasantly surprised by how fast Java is on this platform. I am using a Mac as well, but the Java support on Mac is disappointing. The JVM just hangs sometimes when I am running SimpleDBM tests. Not because of locking or any other issue - it literally hangs - and if I connect to it using JConsole, there is no response.
I am working on a new sample which will demonstrate a higher level API than currently available. I hope to get a working version out by the middle of the month.
Friday, September 14, 2007
How portable is Java code?
In my last blog entry, I mentioned the differences in file locking behaviour I found between Sun's Windows JDK and Mac JDK. Well, I recently acquired a Dell server, and am running SLES 10.1 64-bit edition on it. The default Java 5 SDK that comes with SLES 10.1 is IBM's JDK 5 SR3. SimpleDBM fails to pass all its test cases under this JVM. All tests pass successfully when I run using Sun's Java 6 SE Update 2 64-bit JVM.
I haven't tried any other JDK's yet, but it would be interesting to see the results.
The point is that when I code in Java, I expect my code to run correctly on all JDKs. I do not want to have to worry about portability issues. But reality is that the JDK and its libraries are so large, that it must be very hard to make independently developed JVM's to be completely compatible.
Update: One of the test cases started failing because the HashMap.values().toArray() on IBM's JVM returns values in reverse order of the Sun JVM. This changed the results of the test to be different from what was expected, and therefore the test failed.
I haven't tried any other JDK's yet, but it would be interesting to see the results.
The point is that when I code in Java, I expect my code to run correctly on all JDKs. I do not want to have to worry about portability issues. But reality is that the JDK and its libraries are so large, that it must be very hard to make independently developed JVM's to be completely compatible.
Update: One of the test cases started failing because the HashMap.values().toArray() on IBM's JVM returns values in reverse order of the Sun JVM. This changed the results of the test to be different from what was expected, and therefore the test failed.
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:
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?
Sunday, June 24, 2007
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.
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.
Wednesday, November 29, 2006
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:
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.
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:
- 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.
- 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.
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.
Tuesday, November 28, 2006
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.
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.
Thursday, November 16, 2006
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.
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.
Saturday, November 04, 2006
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.
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.
Thursday, November 02, 2006
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:
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:
- It would be easier to generate JavaDoc for the API alone.
- The API could be packaged separately in its own jar file without too much effort.
Sunday, October 29, 2006
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.
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.
Sunday, June 11, 2006
SimpleDBM moving to ObjectWeb
SimpleDBM is moving to ObjectWeb. The reasons for this move are:
- 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.
- 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.
Subscribe to:
Posts (Atom)
