I am close to finishing my database classes (without networking). But today my multithreading tests revealed a possible leak in my implementation of reusing deleted records.
I have a list of deleted records that is loaded at database startup and only changed by the 'addRecord' and 'deleteRecord' methods.
Here's a pseudocode listing of my implementation. In reality, all unlocking is done in a 'finally' clause, which is omitted here for brevity.
This implementation of the 'addRecord' method (note the scope of the 'writeLock') allows other threads to come in between removing a record from the 'deletedRecords' Map and storing that new record (including it's 'deleted' flag) in the file. So for the other threads, the record is no longer deleted (see the 'isDeleted' method) and could be read, updated or deleted. But on the other hand, the 'addRecord' method still has to write the data to the file and according to the file, the record is still deleted (every record in my datafiel has a flag indicating it's deleted status).
For a read operation this problem can be easily tackled: I have a private 'loadRecord' operation that performs the read from the file and returns 'null' for a deleted record. So I can throw a 'RecordNotFoundException' from within the 'readRecord' method whenever 'loadRecord' returns a 'null'.
But for an update operation this might mean that an update of the (no longer) deleted record might occur before the added record has been written to disk. So adding the record might overwrite the update, which started later in time. The same holds for a delete operation by another thread.
Now I think this kind of situation where an ex-deleted record is updated by another thread, before the undeleting thread was able to store it's new record should be very rare.
I was wondering what you other scjd candidates might think about this. Could I allow this kind of 'dirty write' or is this a definite 'no-go'?
I don't really see another (simple) solution to minimise the scope of the writeLock while still reusing deleted records.
This problem is actually quite similar to one of my previous posts, where I wanted to remove the unlocked records from my LockManager: Working with a shared Map of resources is simple as long as you do not delete any elements from the Map. As soon as deleting is required, the scope of the writeLock has to be seriously expanded, and that's excactly what I would like to avoid.
Access to my randomAccesFile is within a synchronized block on the RAF
The only other data that can change in my fileManager is
So methods that change this data use a writeLock, methods that only read this data use a readLock. This allows more concurrency between threads.
But to make using a readWriteLock worth the overhead, the writing block should be as small as possible. That's why I want to avoid doing I/O from within a code block that is sycnhronized with a write lock.
Hope that clears things a bit up.
Thanks for your interst. Feel free to make any suggestions.