• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • paul wheaton
  • Jeanne Boyarsky
  • Ron McLeod
Sheriffs:
  • Paul Clapham
  • Liutauras Vilda
  • Devaka Cooray
Saloon Keepers:
  • Tim Holloway
  • Roland Mueller
Bartenders:

My locking approach...comments please

 
Ranch Hand
Posts: 53
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'm doing URLyBird 1.3.2, and have been thinking about locking for a while now. The best solution I can think of is to use multiversion concurrency control
http://en.wikipedia.org/wiki/Multiversion_concurrency_control
which makes reading and finding records easy.

Glossary:
Client: not a GUI client, but something that directly calls methods on a Data.java instance.
Timestamp: a unique serial number, larger number means newer (like an order number at a restaurant)


The interface methods I'm required to implement (DBMain.java) in the data access class (Data.java) don't have a cookie argument. Therefore I make an instance of Data for each client, and each Data object contains a timestamp which acts as the client ID (i.e. cookie). I can't think of any other way to identify a client.


Each Data.java also has a set of the timestamps of the records returned when the last search (or read) was done by this client, to avoid locking records that have been changed by some other client in the mean time.


Data.java has to implement this method:


To avoid blocking all the other clients, each instance of Data is run in a seperate thread.
If a client is waiting for a record to become available, they won't be able to do anything else.

The table is stored in memory as a ConcurrentHashMap of Record objects. Each Record has a list of RecordVersions. Each RecordVersion has a timestamp and a copy of the field values as they were at the time. RecordVersions are immutable.
I'll probably use a CopyOnWriteArrayList for Record.

The singleton lock manager contains:
-a synchronized treemap<int recordNo,int clientID> of the currently active locks, sorted by the time when they were acquired
-a synchronized treeset<Request> of the currently active requests, sorted by timestamp
-an unsorted synchronized set<int recordNo> of the record numbers of deleted records, so they can be reused for new records


Locking:
Check the record exists. Check that the Record's timestamp is not newer than our corresponding timestamp in our Data instance.
If it is, the Record has been changed by someone else in the mean time. Wait on the Record object. Do the check again when notified (BTW the Record will probably have been modified when we wake up, so waiting for the record to become unlocked seems kind of dumb to me. Oh well). Locks time out eventually (this should be enough to avoid deadlock).

Unlocking:
Check that Record is actually locked by us, unlock, notify any request that is waiting for this Record to become available.

Creating:
This is probably the most difficult operation.
First do a "find" to make sure the record does not exist...presumably the "primary key" is all the fields?
To avoid duplicates due to a race condition if 2 identical records are created at once, maintain a synchronized "create list" of the current pending Create requests.
We need to get a record number somehow, and should really re-use deleted record numbers, so attempt to get a number from the delete list.
Do we need to lock the record?? Hmmm....the record should definitely be unlocked (because it doesn't exist!) so if we just add it we should be ok, assuming we are careful about synchronizing the record number allocation properly.
Update corresponding timestamp in Data.

isLocked:
Just returns the Record's lock status as it currently is, makes no guarantees. A pretty useless method.
The alternative is to return the lock status as it *was* when the request was submitted, but that is even more useless.

Read:
If the current Record's timestamp is newer than ours, we need to go through the list of old versions. RecordVersions are immutable, so that makes reading easy :-)
Update corresponding timestamp in Data.

Find:
Iterate through the ConcurrentHashMap looking for matches, basically Read() in a loop.


* The following operations require a lock *

Updating/booking:
Check that the lock is ok and the record is valid, create a new RecordVersion object, populate the fields to the same as the most recent RecordVersion (except for the changed fields obviously), set timestamp to our timestamp, then add to the ConcurrentHashMap. Inform database file handler of the changed fields.
Do we need to check timestamps? I don't think so, because we have locked this record and each Data object can only be run by one thread.
Update corresponding timestamp in Data.

Deleting:
Very similar to updating. Add the record number to the delete list, mark RecordVersion as deleted.
We will have to trim off the old copies of RecordVersions as requests are fulfilled...should be easy to do with CopyOnWriteArrayList...after any write, the request checks to see if there are any obsolete RecordVersions, and if so removes them. *Any client holding a lock on the record should lose the lock*
Update corresponding timestamp in Data.

Well that's basically it...have I overlooked anything?
[ April 25, 2006: Message edited by: Roy Mallard ]
 
Ranch Hand
Posts: 1847
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I do something similar, except my Data class is little more than a wrapper around the actual database access code to which it forwards the requests.

My DB interface also does include calls containing cookies, relieving me of the problem of thinking of a solution to passing them.

This makes the update method (for example) rather simple and extremely generic:


 
author and jackaroo
Posts: 12200
280
Mac IntelliJ IDE Firefox Browser Oracle C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Roy Mallard:
The interface methods I'm required to implement (DBMain.java) in the data access class (Data.java) don't have a cookie argument. Therefore I make an instance of Data for each client, and each Data object contains a timestamp which acts as the client ID (i.e. cookie). I can't think of any other way to identify a client.

I'm not saying you're wrong, but just because you said you can't think of any other way to identify the client:
  • just a variation on the theme: each instance of the Data class is a unique object, so the instance of the Data class could be used to identify the client.
  • if you are desperately trying to save memory, then the hashcode of the instance of the Data class could be used to identify the client.
  • in the remote access code you could create your own private cookie for each connected client, then whenever the client calls a remote method, set the thread name to that cookie (that is a bad description - if you dont understand what I am suggesting, and are interested, then just say so and I will either try to work out a better way of saying it, or I will write some code to demonstrate this technique).
  • All the above options assume you are using RMI. For Sockets you are in control of the threads, so you can use the thread identifier.
  • Originally posted by Roy Mallard:Locks time out eventually (this should be enough to avoid deadlock).

    Well, that is one way of handling the problem (and it appears that candidates aren't being penalized for this), but I personally think it is wrong since there is nothing in the provided API that makes me think that I cant own a lock forever if I so desire.

    A more useful option (in my opinion) is to release locks if the client disconnects. And it is easy to find out that the client has disconnected by using the Unreferenced interface in RMI or by catching IOException if you are using Sockets.

    Originally posted by Roy Mallard:
    First do a "find" to make sure the record does not exist...presumably the "primary key" is all the fields?

    You could do that, or you could just ignore the DuplicateKeyException - your code has to declare that it can throw the exception, but that does not mean that it has to throw the exception.

    Originally posted by Roy Mallard:
    Well that's basically it...have I overlooked anything?

    I didnt see where you were writing the records back to disk.

    Regards, Andrew
     
    Jeroen T Wenting
    Ranch Hand
    Posts: 1847
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    indeed there's nothing requiring lock timeouts, but such systems are pretty common.
    Think of application servers timing out sessions when there's no communication in a set period, this is similar.

    Unreferenced would be an idea to detect clients getting disconnected, but not for clients causing deadlock like scenarios with each holding a lock on one record and waiting on another.
    Client A locks record 1 and wants 2 as well.
    Client B locks record 2 and wants 1 as well.
    While for the client required for the SCJD assignment (at least the way I've implemented it) this wouldn't happen as it won't ever hold a lock on more than one record at a time, another client to the same database could well do that.
    Unreferenced doesn't prevent such things. I did implement a method to check whether a record is locked which a client can call before attempting a lock, but there's nothing to force a client to actually call that before making the locking attempt.
     
    Roy Mallard
    Ranch Hand
    Posts: 53
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Thanks for your replies guys.
    Implementing Unreferenced sounds like a good idea. I am using RMI, although I don't know that much about it yet!


    if you are desperately trying to save memory, then the hashcode of the instance of the Data class could be used to identify the client.


    Sounds risky! Hashcodes aren't always unique...


    You could do that, or you could just ignore the DuplicateKeyException - your code has to declare that it can throw the exception, but that does not mean that it has to throw the exception.



    Technically yes, but to me the DuplicateKeyException seems to imply that there should not be two identical records.


    I didnt see where you were writing the records back to disk.



    I'll have a singleton database file manager to handle the file reads/writes.
    This will be notified when a record has been changed, and delegates the write to an URLyBirdFileParser object (which understands the urlybird .db file format, and implements FileParser interface). I don't see the .db file writing to be much of a problem.
     
    Jeroen T Wenting
    Ranch Hand
    Posts: 1847
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Technically yes, but to me the DuplicateKeyException seems to imply that there should not be two identical records



    I don't know about your assignment, but mine doesn't even define a key so a duplicate key can't be detected.
    And my supplied datafile contains 2 identical records, so just assuming that multiple records with identical data can't exist would mean the supplied sample data is corrupt.

    I've even gone so far as to in my choices.txt note that multiple identical records can exist, just to make sure.
     
    "I know this defies the law of gravity... but I never studied law." -B. Bunny Defiant tiny ad:
    Smokeless wood heat with a rocket mass heater
    https://woodheat.net
    reply
      Bookmark Topic Watch Topic
    • New Topic