Concurrency for compound edits

Question

I have these classes that I use to create objects that I want to store at runtime

Class Person
    String name
    Pet[] pets

Class Pet
    String name
    Person[] owners
    boolean neutered

At first I used these HashMaps to store them

HashMap people
HashMap pets

But I wanted to make the implementation concurrent so I changed these maps like so

ConcurrentHashMap people
ConcurrentHashMap pets

I used the "compareAndSet in a while loop" pattern to make atomic updates.

But I still had a problem because each person in my People map has associated pets in the Pets map. To keep updates atomic I added ReentrantReadWriteLocks So that I could update People objects simultaneously with associated Pet objects.

ConcurrentHashMap people
ConcurrentHashMap peopleLocks
ConcurrentHashMap pets
ConcurrentHashMap petLocks

Now when I perform an edit on multiple records, I first grab all the write locks, then I make my edits, and finally release the write locks. This ensures no reading while I make the update.

changePetNames(Person person, Pets[] pets, String[] names) {
    // get Person lock
    // get Pet locks
    // make updates
    // release locks
}

neuter(Pets[] pets) {
    // get Pet locks
    // make updates
    // release locks

I then had all my edit methods synchronize on one object, so that competing edits wouldn't deadlock

private final Object leash = new Object();
changePetNames(Person person, Pets[] pets, String[] names) {
    synchronized(leash) {
     // get Person lock
     // get Pet locks
     // make updates
     // release locks
    }
}

neuter(Pets[] pets) {
    synchronized(leash) {
        // get Pet locks
        // make updates
        // release locks
    }
}

So now I have runtime storage that allows concurrent reads and synchronized writes. My question is whether there's a way to make the writes concurrent as well while protecting the relationship between people and pets.

Answer 1

Instead of synchronizing on the leash object, you can synchronize on the People person object. This allows concurrent changes to different persons and their pets while blocking simultatneous changes to one person and her pets.

PS, from the looks of it your locking system seems to be a bit overly complex. On the assumption that People - Pets is a 1 to many relationship, one person can have many pets but any pet only has one owner, only synchonizing on the person object might be all that you need.

PS2, naming is important and your class names are plural, I think using Person and Pet instead of People and Pets would describe the concepts better making your code easier to understand.

Edit Methods like neuter that only take pets without needing to change data in the owner would, to make them concurrent, synchronize on the pet but that means that:

• when you edit a person and her pets, you need to synchronize on both the person and the pet to guard against pet only changes
• sometimes a pet can be locked while a person with that pet also needs to be locked

The above can lead to deadlock situations when one thread has a pet lock and tries to get a person lock while another thread has the person lock and tries to get the pet lock. My solution would be to synchronize on the owner, even if only the pet needs to be changed, this means that changePetNames and neuter would look like:

changePetNames(Person person, Pets[] pets, String[] names) {
    synchronized(person) {
        // make updates
    }
}

neuter(Pets[] pets) {
    for (Pets pet: pets) {
        // make sure pets owner exists
        synchronized(pet.getOwner()) {
            // make updates
        }
    }
}

This way no deadlocks can occur if you never nest synchronized actions on different persons.

Edit2 When owners to pets is a many to many relationship, you would need to synchronize on a represenatation of a unique combination of persons and pets, which would reproduce the write locks you aquire for updates already. My conclusion here would be that the extra synchronization lease is unneeded if you can make sure deadlock does not occur.

Deadlock occurs if two threads want to aquire a lock that the other has aquired before, so if you can make sure locks are always aquired in the same sequence, this problem cannot ocur.

If you would add a unique creation ID to both Person and Pet and aquire locks per update set in increasing order always, a deadlock situation cannot occur:

changePetNames(Person person, Pets[] pets, String[] names) {
    // sort Person ID's
    // get Person lock in ID sequence
    // sort Pet ID's
    // get Pet locks in ID sequence
    // make updates
    // release locks
}

should do the trick.

Answer 2

I then had all my edit methods synchronize on one object, so that competing edits wouldn't lock each other out.

Now all edits "lock each other out". In what way is this an improvement?

I don't see why you can't simply omit that sychronization. The aquisition of the ReadWrite lock on Person already prevents conflicting concurrent updates (unless a pet changes an owner, which can be dealt with by additional sychronization on the original owner).

Edit: Ah, "lock each other out" means "deadlock" ...

Wikipedia's article on the Dining Philosophers problem discusses several typical techniques for avoiding deadlock. Probably the easiest solution in your case is the "Resource hierarchy solution" with a total order on the objects to synchronize to. For instance, if you lock objects in order of ascending (unique) id, then perform the operation, and then release all locks, a deadlock can not occur. (Because the thread holding the "highest" lock is not impeded by any other thread.)