What a difference two years makes

Preamble

When I started this project some 4 years ago I really didn’t think I would still be writing it but here I am… To be fair much has happened in the past two years that has kept me away from this creation – I’ve changed country, lifestyle and even computer systems!

Not only that but the .NET framework has evolved from .NET 1.1 when I started this beast into .NET 3.5 SP1. I imagine that the code will be ported to .NET 4.0 when that sees the light of day in due course too…

Following the last post, the low-level entities were looked at in great detail – so much so that it took some three months to fix the problems this “look” caused. However it was all worthwhile – the low-level memory management, sparse file and overlapped I/O logic has been successfully used in a separate project (a multi-request HTTP file downloader) to great effect. The resultant system was very fast, resilient and efficient!

The asynchronous code was successfully ported from the .NET APM (that’s Asynchronous Processing Model to you) to the Microsoft CCR which resulted in code that was much easier to test, maintain and extend. Licensing issues mean that I may yet change the underlying concurrency framework used but for the moment CCR is king!

So where are we now?

State = current

Well the index implementation was always half-complete – as in index entries can be added but not removed and if that wasn’t enough – some of the index models have not been implemented (such as clustered indexing)

So the first stage is creating a suitable test rig for playing with paged index trees and writing the necessary code to support adding/removing entries and hopefully balancing the trees too!

With working indices we then get finalised table handling and then I will at long last be able to look at the next phase – hosting a table-driven neural network (actually a page-based neural network would be rather nice and might come first)

C# Port to 3.5

The project has long since been migrated to .NET 3.5 and now it is running on 3.5SP1 but the language features are only being taken advantage of with new code – I need to revisit all code classes to ensure the best use of the language features are being made use of – in particular – more use of LINQ – instead of explicit loop constructs. This work does have a purpose – Parallel LINQ is already here and could form an alternative to using the CCR in certain cases plus there is much talk of merging the codebase of CCR with that of Parallel LINQ – so having CCR code and LINQ code in place makes the next transition much easier to make – when I am called upon to do so, and they say future proofing is impossible…

Code expose

Yes I may begin to expose some of the miles and miles of source code I have painstakingly put together for this project – however I will not be releasing the software into Code Project / CodePlex or any other open-source repository – it’s taken too much of my time to give freely!

Anyway – that’s enough for now – this post was really about catch-up! Now it’s time for sleep!

The Final Shove... I mean - push!

Okay the integration of the new memory manager and low-level streaming improvements is now almost finished - as you can imagine - if you change a set of low-level objects to a new set that function completely differently it may take a while to wade through all the error messages...

If I can find the time then I'll be able to commence testing early next week - if I don't find the time then I may well end up repeating myself next week/next month etc...

Low-Level Engineering

Technorati tags: Sparse Files, Scatter Gather, Virtual Memory, I/O, allocation, buffers

Well I've been so busy with so many other projects that I've not had the time to devote to the Audio Database of late!

All has not been lost and sometimes a break from a project means you can look at it with fresh eyes when you return - assuming of course that you do infact return at all...

My fresh eyes have been taking a critical look at the low-level file and buffer handling and I have implemented three rather important features which have interestingly enough led to a fourth rather radical change in the architecture. These three features are listed as follows (in no particular order);

• Sparse Files
• Overlapped I/O
• Scatter/Gather I/O
• Memory Allocation

Sparse Files are a feature of NTFS 5.1 which allow big files that contain mostly zeros to occupy only the space needed for the non-zero portions - clearly a feature every database file should be making use of!

Overlapped I/O is a system of reading and writing files that allows for asynchronous data-transfer. Without Overlapped I/O the implementation of the buffer cache manager would be much more difficult! This is because the cache manager takes care of reading and writing data and does so using a rather elegant algorithm.

Scatter/Gather file I/O is a method of reading and writing files that allows seperate non-contiguous buffers to be read and written to using overlapped I/O - this technology is important as both the Read Ahead manager and the cache manager use this technique to speed up data-transfer to and from the underlying file. This I/O technology places a number of demands on the caller however these requirements are easily dealt with and in almost all cases exactly what is required for a DBMS file system.

Memory Allocation had to change in order to properly support scatter/gather I/O and lead to an improvement in the way buffers are allocated and managed. To support the scatter/gather logic buffers must be sized according to the system page size which for most Win32 systems is 4096 bytes and the buffers must also be aligned on a page boundary. To satisfy the first requirement is simple - the second requirement however is surprisingly tricky. The other tricky aspect is dealing with .NET as the buffers need to be pinned and passed to the scatter/gather IO wrapped in yet another structure! As it turns out the solution involves turning the memory allocation scheme on it's head!

The Memory Manager

The Windows Virtual Memory APIs have been around for ages but one of the things they give you is page-aligned memory. One of the other things they give you is the ability to reserve blocks of memory. To implement the scatter/gather support both features are used - now a managed virtual memory manager takes care of buffer allocation by using the virtual memory functions to reserve the space needed for the buffer pool. The manager also tracks allocated buffers by maintaining a linked list of allocated buffers. Memory is only allocated when the buffer instance is requested and the requested buffer is taken from the reserved address space - hence the system can reserve say 32Mb of memory for data pages (that's 8192 pages of 8192 bytes incidentally) but the actual memory consumed is determined by the actual buffers currently in use. Nice!

The Advanced File Stream

Bringing the sparse files, overlapped I/O, scatter/gather I/O and virtual memory buffers together under one so-called roof is done with a new managed class derived directly from System.Stream. Unfortunately I had to derived directly from System.Stream rather than the more obvious System.FileStream because the later does not allow the creation of unbuffered streams or write-cache disabled streams (both requirements for using scatter/gather I/O) thankfully much of the code can be lifted directly from System.FileStream (I love Reflector) with the only changes being a changed set of constructors since we can only use scatter/gather on overlapped files and several of the other options are also fixed which simplifies things somewhat.

To support scatter/gather four new methods are added to the stream code;

• BeginReadScatter / EndReadScatter
• BeginWriteGather / EndWriteGather

No synchronous methods are provided - although these would simply call their asynchronous counterparts in any case.

The begin methods take the usual asynchronous method parameters of a callback object and a state object in addition to an array of virtual buffer objects that indicate the memory blocks to be persisted.

Buffer Changes

To integrate these changes into the existing database framework I have needed to make some rather drastic changes to the Buffer class used by the page classes for their internal persistence. Up until now the Buffer classes have been in control of their own loading and saving however this cannot continue - the loading and saving (possibly of multiple buffers) must now be controlled by an external object - this may well wind up being a scatter/gather helper object rather than the read/write request handler directly - the idea being that buffers and page-ids can be added to this mystical helper and when contiguous runs are detected then these can be cached for a single overlapped operation.

While I am breaking the internal buffer implementation it's probably the right time to look at splitting the implementation of transacted and non-transacted buffers into seperate classes - it's confusing enough as it is!

Conclusion

These changes will take a while to implement however the effort will be well worth it - the overall performance increment both from a memory usage viewpoint and outright I/O performance viewpoint will be staggering. The use of sparse file technology will optimise the disk space usage too!

CCR + DSSP = Distributed Scalable Buffer Devices

Technorati tags: Robotics Studio, Concurrency and Coordination Runtime, Decentralised Software Services Protocol
After much fiddling around and moving of code I've finally got to a point where I can test the implementation of a feature I call distributed buffer device service. Now before I go on to describe what this you might want to read about the CCR and DSSP sub-systems upon which all the service implementations are based...
Okay so where was I? Ah yes, the past two months I investigated whether it was possible (and desirable) to write parts of the database engine as DSSP services.
I had already integrated and converted the code-base to utilise the CCR framework rather than using the difficult to code/debug Asynchronous Programming Model - shame really since I'd become rather good at writing those wrappers!
So this investigative process was really a continuation of existing work. The initial implementation of a Physical Buffer Service was simple enough and even compiled and built without too much hassle however the Container Buffer Service (which is regarded as the minimum service needed to perform useful testing) ran into difficult and damn obscure issues - all related to the generation of the proxy project code.
I have finally (after much hair pulling - very painful considering I've no hair on my head) got this Container Buffer Service to compile and the proxy service to build! Wow!
So what's the point of all this abstraction? Well DSSP allows services to communicate with each other using HTTP and hence each service need not exist on a single machine - now since our services are now DSSP services then we automatically get distributed physical device services - now we didn't have THAT before so this must be considered "progress"...
Now the test harness for these services is actually an NT service - I call this service the "Block File-System Service" and this could well form the underpinnings to the Audio Database service.
The implications of all this is the fact that the database file-group devices will maintain a one-to-many relationship with FileSystem service instances running on potentially multiple machines - sounds super uber scalable to me...
Once I have Container Buffer Services working - it will be time to look at the caching version. Note the caching implementation will provide caching at both ends of the network connection to increase networking performance.

Concurrent Pains in my Brain

Long time no post means the new messiah that is the encapsulated within the Microsoft Robotics Toolkit is proving a right devil to implement!

Right now it has caused the creation of four more projects to the overall solution and no end of changes to the code framework!

The most important change is the adoption of DSS (aka Distributed Soap Services) and all devices are being rewritten to take advantage of this concept. The basic idea is to encapsulate all messages between systems in SOAP messages. These messages can then use a unified transport mechanism to reach their destination and with DSS this can be another machine with no further coding!

The first service to arrive from this happy relationship was the PhysicalBufferDevice service. This service is responsible for low-level reading and writing to and from an associated file using asynchronous I/O together with coordination of resizing operations.

The next one up is the ContainerBufferDevice service that deals with clusters of PhysicalBufferDevices.

Following that is the CachingBufferDevice service that not only deals with clusters of PhysicalBufferDevices like ContainerBufferDevice but also uses optimised buffer caching to increase node performance.

Since DSS is being used a new hosting environment was devised to ensure we can control how our DB services are started and obviously control who has access to the service instances.

Still with me? Good! Well all this is wrapped up in the Audio File-System NT service. The purpose of this is to allow the upstream database core to distribute not only files but caching too to multiple machines - this will be extremely scalable and promises to have scope beyond the Audio DB project.

Now you can see why I've been too busy to post... Anyways the NT service is complete and is undergoing final testing. Once this has been completed I will be able to do some proper stress testing and assuming all goes as well as I expect (haha) I'll be able to continue with the next layer up and something tells me that there is another layer in front of what was the next layer - I will be needing a file-system unification layer for all those distributed file-system services...

Concurrency Messiah

Well it's a funny old game this programming lark and every so often you come across something so ground-breaking that it quite simply takes your breath away - today's breath-taking event concerns a new piece of pre-release software from those good old folk at Microsoft; this .NET toolkit known as the Robotics Studio and despite having robots in mind it comes with a fantastic toolkit for helping with multi-threaded applications and this database is very threaded indeed...

From initial experiments I will be able to fully recode the BufferDevices and all the Locking Primatives to make use of this new technology and seriously reduce the complexity of the underlying software - yes folks it's another piece of reengineering ahead and I think the 27 errors I have at the moment will slowly but surely expand before I get the codebase back under control - shame really as the table row persistence was almost finished too!!

However this is a worthwhile excersize as a fully thread-safe maintainable piece of code is not an easy thing to achieve but right now it is looking entirely possible! I am not looking forward to entering the world of locks - they were a nightmare the first, second and third time around!

Transaction Log Testing

It always pays to test your codebase regularly and I have finally got to the point where I can test the transaction logging code and you'd be surprised with the amount of code I have had to write in order to get this far!

However it has also been such a surprise to find that most of the transaction log writing code worked without modification! The only part requiring work was the class responsible for providing a virtual file-system over a stream - this object is crucial for dividing the backing storage used for transaction logs into smaller chunks. It had a problem where it was reporting the stream position incorrectly which led to all plenty of unrelated problems...

So the writing of transaction log records is working but the recovery process still remains untested but in order to conclude that portion of the application I will need to get to a point where the cache writer is correctly saving logged pages and that means I will be retesting the buffer class state-machine which until recently had a few too many states!

Fields, Properties and Serialisation

In a bid to ease the task of writing row and index information to a given page I set out on a major mission (major due to the number of classes that would need modification) to revised the use of explicit member fields and change these into objects that can not only serialise themselves to and from a suitable backing store but also support the concept of being locked.

Locked fields support both read and write of their associated values whereas unlocked fields perform a dummy read of existing data instead of the corresponding write. This makes it easier to update a buffer when extent information of a distribution page changes without causing all distribution page extent changes to require an exclusive object lock - this alone will speed concurrent updates but will need further coordination plus additional LogEntry derived classes to deal with the information actually written in the event of a rollback operation.

As one can imagine with over 100 classes and almost one thousand fields and properties to update this was an erronous task to undertake...

The net result was a true simplification in the implementation of Page object persistence and as an added bonus the persistence of both table and index key information has become so simple I ended up removing classes - that is always a great feeling!

So after a good 50 hours of near continuous programming I have finally got the codebase back to a situation where it builds! It took another 12 hours to fix the variety of bugs and race-condition related problems before the creation of a database is actually working without problem!

No time to rest and relax - I also modified the LogEntry classes to incorporate the same mechanism for reading and writing themselves.

Async Continues

Page splitting implementation has at long last been converted to a fully asynchronous operation and relatively painlessly too - I must be becoming something of an expert in writing implementations of IAsyncResult as it seems to be getting easier and easier although I must admit to wondering sometimes with all these async wrappers all over the place where the real thread is hiding doing the actual work - scary but ever so true...

It's easier doing this stuff than doing the "real" work I'm dreading - finishing off the index manager and table manager... What's worse is that I'm almost certain I'll need a final wrapper that sits on top of the Table Index Manager and the Table Page Manager and coordinates the actions of both.

It never ceases to amaze me to the sheer number of layers and wrappers this project seems to be creating - I once joked it was like peeling an onion but in actual fact it is more like building an onion!

Magic Tables, Constraints and Columns

It's been frantic - as the low-level engine edges ever closer to completion my attention has been squarely focused on that mainstay of RDBMS systems known affectionately as tables!

As it happens the table implementation has not proved too difficult to implement thus far and currently support is in-place for the following;

• Overflow table definition pages


• Column constraints


• Data page-splitting

The row block writer and row block reader objects have an initial implementation and the internal row organisation is finished!

The work required to finish the row block persistence can only continue when the Table Index Page/Table Index Manager logic has been completed. This will take a bit longer now that an implementation of clustered indices is required plus the Index Delete/Index Page Combine operations have yet to be written - yet more work!

Magic Tables, Constraints and Columns

It's been frantic - as the low-level engine edges ever closer to completion my attention has been squarely focused on that mainstay of RDBMS systems known affectionately as tables!

As it happens the table implementation has not proved too difficult to implement thus far and currently support is in-place for the following;

• Overflow table definition pages


• Column constraints


• Data page-splitting

The row block writer and row block reader objects are complete and the internal row organisation is finished!

This work needs to be synchronised with ongoing work on the Table Index Manager to ensure we can add/update/delete rows along with appropriate index trees - yippee!

An old column object has been extended to provide serialisation support to both RowReader and RowWriter classes - as one might have expected - to centralise persistence logic and column capabilities. Hence when I get around to supporting User Defined Types or whatever the rest of the code should simply carry on working - famous last words I know...

Lock Testing

Been busy testing the generic locking class and implementing the specialised derivatives to establish the lock-hierarchy and so far it all works - nice!
Added bonus has been getting the Visual Studio Team System testing framework going again as that is allowing stress testing and such madness to be initiated.

Incidentally it also occurred to me that the locking primatives used to get page level locks could be written to support asynchronous operation (they are fully synchronous at the moment) which might just eke a bit more performance out of them - not sure if I want to go through the pain
Need to reimplement testers for the buffer devices as actually testing the transactioning of a page may well take some time - I dunno I shall see.

The lock manager and the associated lock-owner-block/transaction owner blocks have been rejigged - they are easier to implement now that I'm thinking in terms of how they will be used rather than as the next layer out from the page/buffer implementation! That also made the page logic easier to implement so maybe there is something to learn here...

As ever there is no rest for the wicked and I've turned my attention to tables. The row reader needs careful consideration as this code will need to read both from the table pages themselves and from a result-set defined on search results. I need to think about that some more...

ACID Fundamentals - Locks

I'm wading around in the guts of transaction locking code and it is nothing short of a nightmare! I have a number of generic classes which do all the hard work these are then specialised by final classes for each lock type which deal with the specifics. These "specifics" amount to handling state transitions and determining compatable lock types from different transactions and even the state class is defined within the generic implementation - very clean and somewhat tidy.

Right now I cannot decide whether the escalation behaviour needs a way of being plugged into this generic implementation and I still don't know where to put contextual information such as "whether to hold a read lock until the end of a transaction" as it can't stay in the DatabasePage object...

While I investigate escalation options, I have split the Page lock into seperate sub-types;

• Database Locks


• Root Page Locks


• Object Locks


• Distribution Page Locks


• Extent Locks


• Schema Locks


• Page Locks

Each of these locks has slightly differing state logic and this is the cleanest way of dealing with that.

Added a collection object to the transaction context which allows transaction context to track the objects which have outstanding locks during the lifespan of a transaction. This is very important when using ReadCommitted (with hold lock) isolation and above as these locks will be released after the commit/rollback has happened - hence the best place for that is the transaction context - not the lock manager!

Weekend should involve more major work on this project - it's Friday already and I should be sleeping!

Async Wrappers

The implementation is once again making more and more sense - proof of my own self-delusional state or perhaps proof that the project and the design are going in the right direction! Now fleshing out the data device initialisation/mounting code and that is proving not too strenuous. Need to get the root page and distribution page init code sorted - then I'll be able to see the log-writer do its work - I can't wait!

I was under the mistaken impression that these updates to promote asynchronous behaviour and removing swaths of class hierarchy were going to make the app a dash simpler but as I found out the stack trace during writes is actually longer than before - lots and lots of async wrapper objects the root of the issue - I may need to assign these wrappers from a pool of the things to keep the C# memory manager happy but then again this is what .NET is all about so I'll just flag it for now!

Taken a brief look at the index manager implementation - which still looks rather slick with it's generics all over the place and crossed another TODO off the list... I created an initial implementation of B-Trees operating over pages ages ago but the code was totally synchronous. I realised it needed some careful rework in order to get it to work efficiently with the BeginLoadPage/EndLoadPage APIs that have cropped up following the async conversions and today I can happily say I have solved it with some of the scariest code I've ever written!! Not scary for it's complexity - it is some of the most elegant encapsulated OO code you'll ever meet - no, what scared me was the fact that when I started I didn't actually think the task at hand was entirely possible - writing the B-Tree handler in the first place was nothing short of pain and misery...

Worse yet I still need to provide the B-tree implementation for the table index manager - similar but with the added complication of defining a class hierarchy for dealing with the different data-types I plan to support and the obvious headaches involved in doing string comparisons... I have never understood the various collations - ever...

Anyways I'm happy - my writing of asynchronous code has come of age - almost to the point where I am considering writing an article on just that! Watch this space for a URL...

Need to revisit the locking implementation as it currently needs too much information some of which is not present until the page is loaded - a situation I am keen to avoid...

Database Devices Cracked

Wahey! Good news!

Page level functionality is now tested and working. This includes the behaviour of the CheckPointer and the Log Writer although in the case of the latter the recovery process remains untested and uncharted waters!

Extensive debugging was been achieved since the installer classes were rewritten to emcompass the new class framework (the test harness utilising the installers was already in existence) and now the Buffer state-machine has been tested along side the asynchronous behaviour exposed by just about every buffer/page class available!

It's not been plain sailing though - the implementation of the Free Buffer Service had to ensure Data Page device buffers were marked transactional and log buffers were not... The Buffer state machine pattern also unearthed a number of peculiarities which caused the moving of some of the state switching logic and I also found out that the NestedContainer object does not forward calls to GetService to the owner component - so I had to write one that did in order to get my own proprietry routing chain to work!

Now that the Log Writer appears to be working - at least in an initial capacity (I've just had to changed the default log-page block size - it was far too large) my attention will now turn to initialisation of the primary data device and the setup of file-group primary devices which share more than a few attributes.

After that the real hard work begins!

Buffer Internals

Finally the asynchronous support has been completed. :-D and as a result the BufferDevice hierarchy is far simpler and the PageDevice hierarchy is also far flatter.

So now I have two class hierarchies - one deals with buffers and can be considered the low-level API and the other deals with pages and can be considered the next level up the chain. The buffer handlers were surprisingly easy to write - more a question of moving code from various other classes which was made a nice change.

The page classes were also surprisingly straightforward especially given the fact that I chopped lots and lots of classes out!!

The real pain came when I decided to unravel the state machine for buffer objects - this turned into a week-long adventure but the result is an incredibly flexible finite-state-machine which ensures consistent buffer state transitions and proper state handling without littering the Buffer class with lots of boolean flags! This task was necessary in order to make the object fully asynchronous...

The buffer can now support the following async operations;

• Read From Device Stream


• Write To Device Stream


• Write To Log Device

With this support in buffers and their corresponding devices complete, attention now turns to pages and their devices. There are a couple of loose ends which still need to be tied up with regard to hand off and lock acquisition - I also need to ensure the transaction handler will correctly unlock pages during the commit phase...

Finally the outer DatabaseDevice device can be completed with regard to recovery and the final mounting procedure before I once again fix the installer classes (and use them to test the initial portion of the codebase).

Asynchronous Persistence

Major change is underway in order to clean the implementation of asynchronous persistence used through out the database classes.

Seemed to me that there was far too many methods and more than a little confusion in the implementation so I've simplified the arrangement of devices with respect to loading, saving and initialising DeviceBuffer objects.

These simplified BufferDevice objects will handle the low-level buffer load/save/init operations and be wrapped by a single class used to handle page-level processing.

This arrangement will be easier to test and have better performance due to a significant reduction in the number of method calls...

It means revising an awful lot of code which is more than a small pain but one well worth taking on!

Transaction Logging

Installation testing is going very well and more of the various subsystems are undergoing functional testing now. The maze of tasks involved with installing hierarchical devices have largely been solved so now attention has turned towards the creating .NET transactions for wrapping the overal install and getting the custom transaction implementation to enlist itself into this framework feature.

Well the enlistment part was fairly straightforward with the designed classes needing only minor modifications in order to start working however the changes needed to handle saving transacted pages involved a little more head scratching and code tweaking! The freshly written code was saving pages and their associated buffers directly to the underlying device - this is clearly illegal if you want a recoverable system!

Ultimately the code was modified for transacted buffers such that calls to SavePage will update the database transaction holder with information pertaining to the buffer and the current timestamp. During the Commit-Preparation phase these buffers can be committed (scratchpad data moved to write-pending area) and the transaction log records can be generated from the two images (or single image in the case of newly initialised buffers). Finally in Commit phase the Commit log record is written to validate the log records.

That's the idea at least - so far the distribution pages are following this regime fine but root pages seem to have a mind of their own - it's that or I'm not actually saving them...

All this work meant I needed to provide an implementation of the CheckPoint handler at long last and thankfully this has proved relatively easy - the only real problem seems to be with the cache management threads which don't seem to be unlocking the cache in all scenarios - still at least I know where the problem is - multithreaded mayhem can be a pain to debug but .NET gives us flexible tracing!

Development should move into overdrive following the arrival of a new desk and chair for comfortable programming however the country-wide mayhem that is Songkran now lies directly in my path so it's all on hold for the next 5 days or so - fun fun fun (with a water gun!)

Installers Reach Runnable Stage

Been working like a demon despite being on holiday from my holiday in Hanoi!!!

The installation components are now being rigourously tested by a new test-harness and as a result the call sequence and the mount operations performed by devices have been debugged and tweaked so that now the installation completes without problem.

It is still not a complete success - I need to check the log-writer is logging the writes to the root pages and I need to check the data device root pages are correct. After all that is done I will be able to test the non-create mount operation and move delicately onto testing the recovery logic which could be quite painful!

Found that VS2005 disconnected check-outs from Source Control work like a dream and my edits are checked in successfully and with a minimum of fuss (well once it worked out the network drive was back online that is...)

Installers Reach Runnable Stage

Been working like a demon despite being on holiday from my holiday in Hanoi!!!

The installation components are now being rigourously tested by a new test-harness and as a result the call sequence and the mount operations performed by devices have been debugged and tweaked so that now the installation completes without problem.

It is still not a complete success - I need to check the log-writer is logging the writes to the root pages and I need to check the data device root pages are correct. After all that is done I will be able to test the non-create mount operation and move delicately onto testing the recovery logic which could be quite painful!

Found that VS2005 disconnected check-outs from Source Control work like a dream and my edits are checked in successfully and with a minimum of fuss (well once it worked out the network drive was back online that is...)