my dog learned polymorphism
The moose likes Developer Certification (SCJD/OCMJD) and the fly likes B&S: Reusing deleted records Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Certification » Developer Certification (SCJD/OCMJD)
Bookmark "B&S: Reusing deleted records" Watch "B&S: Reusing deleted records" New topic

B&S: Reusing deleted records

Luc Feys

Joined: Nov 21, 2005
Posts: 20
Hello again,

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.

I hope this explanation was a bit clear.

Thanks in advance for any suggestions.

Luc Feys
Ed Tse
Ranch Hand

Joined: Sep 18, 2003
Posts: 183
May I ask which methods are already synchronized?
What method are the SCJD required interface (I am not writing B&S)?
What is the purpose of 2 locks Read lock and write lock

SCJP, Pre-SCJD (URLyBird 1.3.1), Teradata Cert'd Prof
Luc Feys

Joined: Nov 21, 2005
Posts: 20

I'll add a little more information on my locking:

Access to my randomAccesFile is within a synchronized block on the RAF

The only other data that can change in my fileManager is
  • recordCount
  • deletedItems

  • 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.

    I agree. Here's the link:
    subject: B&S: Reusing deleted records
    It's not a secret anymore!