B&S Locking Strategy

[Alex Sharkoff]

Hi all,

I'd appreciate your thoughts on the following locking strategy for B&S project.

Database Locking is broken into logical and physical parts.

Logical locking � is controlled via Data class's lock / unlock public methods and allows a client to explicitly lock specific record so that no other client can perform any operations on it. There is a contract for all client operations that modify a specific db record : first of all client asks db to lock the record, then client asks db to modify this record, then clients asks db to unlock the record. Having such contract allows to ensure that a thread that is unlocking a record is the same thread that's locked it. Therefore, any given record can be only modified by one thread at any given time.
Data class has a static member called lockedRecords that is used to store record ids that are currently being modified. Because the Data class instances can be associated with different database files lockedRecords stores the combination of a record id and the name of the record's database file rather than just record id.

<client operation that modifies a particular record>

LET db := create Data instance with dbFileName
 
-- contractual obligation #1 � lock the record
ASK db to lock record id
 
-- contractual obligation #2 � modify the record
ASK db to MODIFY this record 
 
-- contractual obligation #2 � unlock the record
ASK db to unlock record id

<db #lock method>

LET id := APPEND record id to dbFileName
 
GET lock on lockedRecords
WHILE lockedRecords CONTAINS id
RELEASE lock on lockedRecords
WAIT for notification that another thread modified lockedRecords
GET lock on lockedRecords
END WHILE loop

PLACE id INTO lockedRecords
LET other threads waiting on lockedRecords lock  to get ready
RELEASE lock on lockedRecords

<db #unlock method>

LET id :=  APPEND record id to dbFileName
 
GET lock on lockedRecords
REMOVE id from lockedRecords
LET other threads waiting on lockedRecords lock to get ready
RELEASE lock on lockedRecords 

Physical locking - ensures that only one thread reads or writes to a database file at any given time. As the Data class instances can be associated with different database files, it has a static member called dbFilesInUse. This member is used to store the names of the db files that are currently being read or written to by the different Data class instances.
The contract for all Data class methods that modify/read db file is that they need to first lock the file (ie place its name into dbFilesInUse storage place), then perform file modification/reading , then unlock the file (ie remove its name from dbFilesInUse storage place). Therefore, it ensures that the database file associated with a particular Data class instance can be only modified by one thread at any given time.

<db operation that modifies database file>

-- contract obligation #1 � lock the file
GET lock on dbFilesInUse
 
WHILE dbFilesInUse CONTAINS dbFileName
RELEASE lock on dbFilesInUse
WAIT for notification that another thread released a lock
GET lock on dbFilesInUse
END WHILE loop
 
PLACE dbFileName into dbFilesInUse
 
LET other threads waiting on dbFilesInUse lock to get ready
RELEASE lock on dbFilesInUse 
 
-- contract obligation #2 � modify the file
READ / WRITE to the database file
 

-- contract obligation #3 � unlock the file
GET lock on dbFilesInUse
 
REMOVE dbFileName from dbFilesInUse
 
LET other threads waiting on dbFilesInUse lock to get ready
RELEASE lock on dbFilesInUse

[Alex Sharkoff]

that is how this strategy would work in the following scenario.

Scenario description: two clients modify different records from the same database file at the same time.

Thread_1 creates Db_1 with db_file_1
 
Thread_2 creates Db_2 with db_file_1
 
 
Thread_1 asks Db_1 to lock record_1
 
Db_1 gets lock on lockedRecords # T1 IS BLOCKING
 
 
Thread_2 asks Db_2 to lock record_2
 
Db_2 waits for the lock on lockedRecords # T2 IS BLOCKED
 
 
Db_1 determines that lockedRecords does not contain record_1.db_file_1
 
Db_1 places record_1.db_file_1 into lockedRecords
 
Db_1 releases lock on lockedRecords #T1 stops blocking
 
 
Db_2 gets lock on lockedRecords # T2 IS BLOCKING
 
Db_2 determines that lockedRecords does not contain  record_2.db_file_1 
 
Db_2 places record_2.db_file_1 into lockedRecords
 
Db_2 releases lock on lockedRecords # T2 stops blocking
 
 
Thread_1 asks Db_1 to modify record_1
 
Thread_2 asks Db_2 to modify record_2 
 
 
Db_1 gets lock on dbFilesInUse # T1 is BLOCKING
 
Db_2 waits for the lock on dbFilesInUse # T2 is BLOCKED
 
 
Db_1 determines that dbFilesInUse does not contain db_file_1
 
Db_1 places db_file_1 into dbFilesInUse
 
Db_1 releases lock on dbFilesInUse # T1 stops blocking
 
 
Db_2 gets lock on dbFilesInUse # T2 is BLOCKING
 
Db_2 determines that dbFilesInUse contains db_file_1
 
Db_2 releases lock on dbFilesInUse # T2 stops blocking
 
Db_2 waits for the changes to dbFilesInUse # T2 WAITS
 
 
Db_1 modifies record_1 in db_file_1
 
 
Db_1 gets lock on dbFilesInUse # T1 is BLOCKING
 
Db_1 removes db_file_1 from dbFilesInUse
 
Db_1 asks all other threads waiting for the changes to dbFilesInUse to get ready 
# T2 WAKES up 
 
Db_1 releases lock on dbFilesInUse # T1 stops blocking
 
 
Db_2 gets lock on dbFilesInUse # T2 is BLOCKING
 
Db_2 determines that dbFilesInUse does not contain db_file_1
 
Db_2 places db_file_1 into dbFilesInUse
 
Db_2 releases lock on dbFilesInUse # T2 stops blocking
 
 
Db_2 modifies record_2 in db_file_1
 
 
Db_2 gets lock on dbFilesInUse # T2 is BLOCKING
 
Db_2 removes db_file_1 from dbFilesInUse
 
Db_2 asks all other threads waiting for the changes to dbFilesInUse to get ready 
# no other threads are waiting 
 
Db_2 releases lock on dbFilesInUse # T2 stops blocking
 
 
Thread_1 asks Db_1 to unlock record_1
 
Thread_2 asks Db_2 to unlock record_2
 
 
Db_1 gets lock on lockedRecords # T1 is BLOCKING
 
Db_2 waits for the lock on lockedRecords # T2 is BLOCKED
 
 
Db_1 removes record_1.db_file_1 from lockedRecords
 
Db_1 asks all other threads waiting for the changes to lockedRecords to get ready 
# no other threads are waiting
 
Db_1 releases lock on lockedRecords
 
 
 
Db_2 gets lock on lockedRecords # T2 is BLOCKING
 
Db_2 removes record_2.db_file_1 from lockedRecords 
 
Db_2 asks all other threads waiting for the changes to lockedRecords to wake up 
# no other threads are waiting
 
Db_2 releases lock on lockedRecords

[ August 16, 2005: Message edited by: Alex Sharkoff ]

[Andrew: Horizontal scrolling was hurting my eyes - wrapped a couple of lines to try and fit within a standard screen width]
[ August 16, 2005: Message edited by: Andrew Monkhouse ]

[Lara McCarver]

Is it really necessary for your server to support different database files at the same time? The assignment is pretty clear that there is a single database that you are supposed to use. I think you are supposed to let the user pick the database, but then all the Data files are supposed to use that database.

Also, think about how you are going to handle record creation (what if 2 clients try to simultaneously create a record) and deletion (What if... client A locks record 2, then deletes record 2, then client B creates a new record, which goes in at record 2... hopefully record 2 will not still be in the lock list).

[Alex Sharkoff]

Thanks a lot, Lara, for your reply.

Is it really necessary for your server to support different database files at the same time? The assignment is pretty clear that there is a single database that you are supposed to use....to let the user pick the database

I'd be much happier if there was no such requirement as it makes more sense to let the system administrator to configure database related attributes via a configuration file that is read by the database component at the initialisation time. In this case the user is completely unaware of the database component structure and therefore, we can swap between database file and DMBS (eg, MySQL) without affecting client code.
However, because the user can pick up the database file a scenario where two users choose different database files is very real (eg, one user works with dev database, another with production).

If our db component was to expect to work against the same db file then it could just simply remember the db file location passed as a parameter from the very first client and disregard all db file locations coming from all the subsequent client calls:

DB Server started
 
Client_1 calls a method on DB server passing in a db file location
 
DB Server REMEMBERS db file location
 
DB Server executes a methodrequested by Client_1
 
Client_2 calls a method on DB server passing in a db file location
 
DB Server IGNORES db file location passed in by Client_2
 
DB Server executes a methodrequested by Client_2 against a db file passed in by Client_1

For me it just does not sound right....

what if 2 clients try to simultaneously create a record

well, in this case our physical locking will come into play:

db_1 gets lock on the file_1 
    -> db_2 waits for the file_1 lock 
    -> db_1 creates a record in file_1 
    -> db_1 releases file_1 lock 
    -> db_2 picks up file_1 lock 
    -> db_2 creates a record in file_1

and deletion (What if... client A locks record 2, then deletes record 2, then client B creates a new record, which goes in at record 2... hopefully record 2 will not still be in the lock list)

Very good point.... We will only reuse deleted record's space if it's not locked (ie it is not in lockedRecords static member). Or may be even a simpier approach is to just write new records to the end of the file because the assignment requirements state that create() method // Creates a new record in the database (possibly reusing a// deleted entry) , although I am not in favour of this solution.

I do need to put more thinking into the deletion / creation process because deleted entries reuse brings new complexities into the pic.

Thanks a lot, Lara, for bringing it up...



[ August 16, 2005: Message edited by: Alex Sharkoff ]

[Andrew: still trying to stop horizontal scrolling]
[Andrew: hopefully I wasn't editing at the same time as you Alex ]
[ August 16, 2005: Message edited by: Andrew Monkhouse ]

[Andrew Monkhouse]

Hi Alex,

Just some general thoughts as I am reading through these. Bear in mind that I have a tendency to accept solutions unless I believe they are making a critical mistake. This can mean that I rarely say that something is beyond specifications (Lara is much better at that than I am).

Originally posted by Alex Sharkoff
first of all client asks db to lock the record, then client asks db to modify this record, then clients asks db to unlock the record. Having such contract allows to ensure that a thread that is unlocking a record is the same thread that's locked it.

I assume that either you are using a sockets based aproach or that all these operations are being called within one RMI method?

Originally posted by Alex Sharkoff

LET id := APPEND record id to dbFileName

Have you considered having one meta-collection containing dbFileName as the key and a collection as the value? This would mean that you are not continually adding a key that is a concatenation of dbFileName and record number. Your current way of doing this could require a very long key, since it would presumably need a fully qualified dbFileName in case you have files in different directories with the same name.

In your "<db #lock method>" you are explicitly releasing the lock on the lockedRecords - is this what you are really doing? Or are you just showing the implicit steps?

In your "<db #unlock method>" you do not show any form of verification that the client who locked the record is the same as the client who unlocked the record.

Originally posted by Lara McCarver
Also, think about how you are going to handle record creation ...

Originally posted by Alex Sharkoff
// Creates a new record in the database (possibly reusing a// deleted entry)

Some of the databases in the 80s (dBase, FoxPro) used to have the ability to reuse space as a separate function: The usual process would be to take the database down at night, back it up, then run the "compress" function to reuse any space caused by deleted records. Worked quite well as long as there was no 24*7 requirement. Unfortunately the Data class doesn't seem to have suitable methods for defragmenting the data file .

Many candidates get very high scores without worrying about reusing space. But if you do decide to do it, there are some easy solutions, however I will let you think about them before butting in with my thoughts .

Regards, Andrew

[Alex Sharkoff]

Thanks a lot, Andrew, for your thougts on this topic.

Bear in mind that I have a tendency to accept solutions unless I believe they are making a critical mistake. This can mean that I rarely say that something is beyond specifications (Lara is much better at that than I am).

Very cheeky

I assume that either you are using a sockets based aproach or that all these operations are being called within one RMI method?

Yes, they are being called within one RMI method (database client that runs in the same jvm as the database server)

Have you considered having one meta-collection containing dbFileName as the key and a collection as the value?

Very good point....

In your "<db #lock method>" you are explicitly releasing the lock on the lockedRecords - is this what you are really doing? Or are you just showing the implicit steps?

I am just showing the implicit steps. In fact, in Java land it would translate into lockedRecords.wait()

In your "<db #unlock method>" you do not show any form of verification that the client who locked the record is the same as the client who unlocked the record.

Should one take care of such verification? Because there is contract for all database client methods that modify / read a specific db record to always first lock / then modify the record / then unlock the record it ensures that the thread (ie client) that locked the record is the thread (ie same client) that is unlocking it. Am I missing something here ?

Many candidates get very high scores without worrying about reusing space. But if you do decide to do it, there are some easy solutions, however I will let you think about them before butting in with my thoughts

Well, I guess we could build in some kind of a defragmenter process into the db server. For instance, the db server starts and spawns another thread that will wake up every X minutes and compresses the files held by the db server (it would have to use physical locking in order to ensure that no more than one thread operates on a file at any given time)


Thanks a lot again for your time and help on this matter.

[Andrew Monkhouse]

Hi Alex,

Originally posted by Alex Sharkoff:
Very cheeky

Thank you, I try .

Originally posted by Andrew Monkhouse:
In your "<db #unlock method>" you do not show any form of verification that the client who locked the record is the same as the client who unlocked the record.

Originally posted by Alex Sharkoff:
Should one take care of such verification? Because there is contract for all database client methods that modify / read a specific db record to always first lock / then modify the record / then unlock the record it ensures that the thread (ie client) that locked the record is the thread (ie same client) that is unlocking it. Am I missing something here ?

Well it depends on how well you want to adhere to the interface provided. Check your instructions for lock - they may well have something similar to:

// Locks a record so that it can only be updated or deleted by this client.
// If the specified record is already locked, the current thread gives up
// the CPU and consumes no CPU cycles until the record is unlocked.

To me, this means that Data class itself has to be aware of which client is calling which methods.

Regards, Andrew
[ August 17, 2005: Message edited by: Andrew Monkhouse ]

[Lara McCarver]

My instructions... I don't have them with me now, but I think they said that the client needs to be able to specify the database if it is in stand-alone mode. And if it is connecting to the server, then the client is supposed to specify the server machine & port number instead. Meanwhile, the "GUI" to the server is supposed to specify which database the server is using.

In my opinion, it doesn't make sense for a client to specify a database directory on another machine... if it didn't happen to be the same machine, how would the client user know what the directory structure is on the server machine anyway?

[Alex Sharkoff]

Hi Lara and Andrew,

Thanks a lot for your answers.

Originally posted by Andrew Monkhouse
Well it depends on how well you want to adhere to the interface provided. Check your instructions for lock...

After reading the comments on the DBMain interface methods it does look like the Data methods need to be aware of who is calling them.
I am placing this point on my 'todo' list...

Originally posted by Lara McCarver
I think they said that the client needs to be able to specify the database if it is in stand-alone mode. And if it is connecting to the server, then the client is supposed to specify the server machine & port number instead. Meanwhile, the "GUI" to the server is supposed to specify which database the server is using.

I agree with you, Lara. That's why I've just re-read instructions and it looks like I was too quick to commit to "multiple db files" solution. The instructions only indicate that the program must allow the user to specify the location of the database. I guess it can be implemented in the following manner:

Server mode (client and server run in diff JVMs)- server GUI lets the user choose the file -> store file location in db server -> start db server

Standalone mode (client and server run in the same JVM) - bring up dialog box to let the user choose the file -> store file location in db server -> bring up client GUI

The above solution ensures that db server works with just one file (rather than with multiple files as I initially specified).

Originally posted by Alex Sharkoff
Physical locking - ensures that only one thread reads or writes to a database file at any given time

We could possibly leverage on the strategy used by the Concurrent Versions System by creating .rlock and .wlock files.



[ August 18, 2005: Message edited by: Alex Sharkoff ]

[Andrew Monkhouse]

Hi Alex,

We could possibly leverage on the strategy used by the Concurrent Versions System by creating .rlock and .wlock files.

I need to think about this later, but just a quick thought - are you perhaps reimplementing JDK 5's ReadWriteLock functionality?

Regards, Andrew

[Alex Sharkoff]

Andrew, as far as I can see ReadWriteLock will not prevent different database servers (ie the ones running in different JVMs) from accessing the db file at the same time. I was just thinking that the following algorithm could potentially solve this problem:

user1 starts program in standalone mode and chooses db_file_1
user2 starts program in standalone mode and chooses db_file_1

user1 asks db layer to update record1
user2 asks db layer to read record2

in order to update record1 db layer does the following:
checks that the db file's directory does not contain [I]<dbFileName>.rlock[/I] and [I]<dbFileName>.wlock[/I] files
creates [I]<clientName>.<dbFileName>.[B]w[/B]lock[/I] file in the db file's directory
updates <dbFileName> file with the modified record1
deletes [I]<clientName>.<dbFileName>.wlock[/I] file from the db file's directory

at the same time in order to read record2 db layer does the following:
sees that there is a [I]<dbFileName>.wlock[/I] file and waits for this file to disappear
as soon as there are no [I]<dbFileName>.wlock[/I] files it creates [I]<clientName>.<dbFileName>.[B]r[/B]lock[/I] 
reads record2 from <dbFileName>
deletes [I]<clientName>.<dbFileName>.rlock[/I] file from the db file's directory

However, as you've already mentioned in one of your previous posts B&S assignment explicitly indicates that "You may assume that at any moment, at most one program is accessing the database file; therefore your locking system only needs to be concerned with multiple concurrent clients of your server". Therefore, we can just use physical locking, ie synchronisation on the file object in our db layer to deal with the concurrency issues.



Kind regards,



[ August 23, 2005: Message edited by: Alex Sharkoff ]

[ August 24, 2005: Message edited by: Alex Sharkoff ]
[ August 24, 2005: Message edited by: Alex Sharkoff ]