[concurrency-interest] Read-write-update lock

Niall Gallagher niall at npgall.com
Wed Aug 7 18:22:18 EDT 2013


Hi All,

Just a heads up that I have released the Read-Write-Update lock implementation[1] to Maven central.

Thanks to all for the feedback on this mailing list. I've been following this list for a number of years and therefore I would not have felt comfortable releasing this lock had it not had some discussion with experts here first. The library has full test coverage, and Maven coordinates can be found on the site.

Kind regards,
Niall

[1] http://code.google.com/p/concurrent-locks/

On 23 Jul 2013, at 22:16, Niall Gallagher <niall at npgall.com> wrote:

> Yes indeed, that is the same concept.
> 
> I mentioned in my earlier post that it's not a new concept, as the earliest reference to it that I could find, was on the Linux kernel mailing list circa 2000 (thirteen years ago). It might be older still. I guess RDBMSes have implemented it, at least via cursors in that case. Your link shows that JavaDB/Derby implements it in Java, just not via a programmatic API (and perhaps not reentrant). I don't know if it was added to the Linux kernel in the end.
> 
> I also found ReaderWriterLockSlim[1] on the .Net platform. It is the default readers-writer lock implementation on that platform.
> 
> [1] http://msdn.microsoft.com/en-us/library/system.threading.readerwriterlockslim.aspx
> 
> 
> On 23 Jul 2013, at 15:06, Zhong Yu <zhong.j.yu at gmail.com> wrote:
> 
>> same concept in RDBMS -
>> http://docs.oracle.com/javadb/10.6.2.1/devguide/cdevconcepts36402.html
>> 
>> On Tue, Jul 23, 2013 at 12:28 AM, Niall Gallagher <niall at npgall.com> wrote:
>>> Hi Zhong,
>>> 
>>> Not exactly, but that is very close indeed. The only difference is in POST it does not acquire the read lock, so it's simply like this:
>>> 
>>>  updateLock.lock();  // exclusive
>>> ...
>>>  if(...)  // occasionally
>>>      writeLock.lock();  // upgrade
>>>      ...
>>>      writeLock.unlock();
>>>  ...
>>>  updateLock.unlock();
>>> 
>>> 
>>> I initially did think that I'd have to roll my own ReentrantReadWriteLock for the reason you mentioned, but then I found a way around it. My reasoning is, it's not necessary to acquire an actual read lock from ReentrantReadWriteLock after the update lock has been acquired, because here we basically invent a new type of lock anyway (the update lock) so we just say in the documentation that the update lock gives the application "permission" to read but not write. So the number of threads with read "permission" at any one time can be <number of threads holding regular read locks from ReentrantReadWriteLock> + <0 or 1 threads holding the update lock>.
>>> 
>>> The write lock is only granted when two conditions hold: the requesting thread must hold the update lock (enforced in the logic in RWULock), and other threads holding regular read locks must release those read locks (enforced by ReentrantReadWriteLock itself which RWULock delegates to internally). So this way it re-uses the ReentrantReadWriteLock of the JDK, no need for a custom implementation.
>>> 
>>> Best regards,
>>> Niall Gallagher
>>> 
>>> On 23 Jul 2013, at 05:29, Zhong Yu <zhong.j.yu at gmail.com> wrote:
>>> 
>>>> Hi Niall, my understanding is that you are trying to implement
>>>> something like this
>>>> 
>>>> Lock readLock = ...;
>>>> Lock writeLock = ...;
>>>> Lock updateLock = ...;
>>>> 
>>>> GET:
>>>> 
>>>>  readLock.lock();
>>>>  ...
>>>>  readLock.unlock();
>>>> 
>>>> 
>>>> POST:
>>>> 
>>>>  updateLock.lock();  // exclusive
>>>>  readLock.lock();
>>>> ...
>>>>  if(...)  // occasionally
>>>>      writeLock.lock();  // upgrade
>>>>      ...
>>>>      writeLock.unlock();
>>>>  ...
>>>>  readLock.unlock();
>>>>  updateLock.unlock();
>>>> 
>>>> 
>>>> except that upgrade r->w isn't allowed by ReentrantReadWriteLock so
>>>> you need to roll your own. Is that correct?
>>>> 
>>>> Zhong Yu
>>>> 
>>>> 
>>>> 
>>>> 
>>>> On Mon, Jul 22, 2013 at 10:48 PM, Niall Gallagher <niall at npgall.com> wrote:
>>>>> Actually the read-write-update lock solves that deadlock problem.
>>>>> 
>>>>> The update lock is not the same as the read lock[1]. Only one thread can acquire the update lock at a time. Only the thread holding the update lock can acquire the write lock. Threads which might need to write, should not acquire read locks but should acquire the update lock instead, and the implementation will enforce that correct usage with exceptions. So there is not a situation where two threads could mutually hold a lock that the other is waiting for, which prevents deadlock.
>>>>> 
>>>>> [1] http://code.google.com/p/concurrent-locks/
>>>>> 
>>>>> 
>>>>> On 23 Jul 2013, at 02:57, Aaron Grunthal <aaron.grunthal at infinite-source.de> wrote:
>>>>> 
>>>>>> The problem with a read-update is that the lock can never guarantee that the update is going to succeed. A write lock is generally considered an exclusive lock, think of transaction semantics. If two threads hold a read lock and both of them try to upgrade to a write lock neither can upgrade since an exclusive write lock would violate the shared semantics of a read lock. So at least one of them would have to stay in read mode, finished their logic in read-only mode and then relinquish the read lock before the other thread can even acquire the write lock.
>>>>>> 
>>>>>> So read-update will always have to support fail-and-retry or the logic would have to ensure that only one reader thread would try to upgrade to write at any given time and get priority over threads that try to acquire a write lock directly.
>>>>>> 
>>>>>> Of course there are special scenarios where you actually have "read up to X in read mode, acquire write mode for X+1" where the write lock would not violate violate the semantics of the earlier read chunks, but those things are different from a simple read-write lock, they're sets of range-locks, such as used by database engines.
>>>>>> 
>>>>>> So as far as I can see the "non-replayable request" issue wouldn't be solved by a generic read-tryUpgrade lock.
>>>>>> 
>>>>>> 
>>>>>> On 23.07.2013 01:43, Niall Gallagher wrote:
>>>>>>> The motivation for this read-write-update lock was actually a
>>>>>>> distributed systems problem.
>>>>>>> 
>>>>>>> The crux of the problem was that it was not feasible to "re-play" requests.
>>>>>>> 
>>>>>>> Broadly, requests entering a front-end system could be classified as
>>>>>>> being "read-only" (HTTP GET) or "possibly requiring write" (HTTP POST).
>>>>>>> On receiving a request, the front-end system would read from a local
>>>>>>> data store and then forward the request to back-end systems. The
>>>>>>> front-end system would gather responses from the back-end systems and
>>>>>>> from those determine if its local data store needed to be updated.
>>>>>>> 
>>>>>>> In a system like that, it's not possible for the front-end system to
>>>>>>> "try" the request using a read lock, and then if it later detects that
>>>>>>> it needs to write, drop the read lock and re-play the request using a
>>>>>>> write lock. First, because dropping the read lock would allow another
>>>>>>> thread to steal the write lock, causing lost updates, and second because
>>>>>>> re-playing the request over multiple back-end systems would be
>>>>>>> expensive. The only solution would be to acquire the write lock on every
>>>>>>> HTTP POST.
>>>>>>> 
>>>>>>> So I started to view the read-write lock as somewhat limiting.
>>>>>>> 
>>>>>>> There is also the performance aspect. For simplicity say 50% of requests
>>>>>>> are HTTP GET and 50% are HTTP POST. Any HTTP POST would acquire the
>>>>>>> write lock which would (1) block all reading threads even if only a
>>>>>>> small fraction of POSTs would require writes, and (2) would block all
>>>>>>> reading threads for the entire latency of interactions with back-end
>>>>>>> servers.
>>>>>>> 
>>>>>>> A read-write-update lock on the other hand, (1) does not block reading
>>>>>>> threads unless a write actually is performed, and (2) only blocks
>>>>>>> reading threads from the point at which the lock is upgraded, which in
>>>>>>> the case above is after responses from back-end systems have been
>>>>>>> gathered and so is for only a fraction of the overall processing time.
>>>>>>> 
>>>>>>> I think the example scales-down to simpler situations too. The key
>>>>>>> advantage of a read-write-update lock is in read-before-write access
>>>>>>> patterns.
>>>>>>> 
>>>>>>> Read-before-write is common. Many applications do it in three steps: (1)
>>>>>>> read data, (2) do some computations on the data, (3) write out the
>>>>>>> resulting data. A conventional read-write lock does not support this use
>>>>>>> case well.
>>>>>>> 
>>>>>>> At the very least, a read-write-update lock would increase concurrency
>>>>>>> by not blocking reading threads until a writing thread reaches step 3;
>>>>>>> concurrent reads would be allowed during steps 1 & 2. A conventional
>>>>>>> read-write lock would block reads for all three steps.
>>>>>>> 
>>>>>>> I think also in some systems it's basically tricky to implement re-play
>>>>>>> functionality, so a read-write-update lock[1] seems like a nice
>>>>>>> proposal. YMMV!
>>>>>>> 
>>>>>>> Niall Gallagher
>>>>>>> www.npgall.com <http://www.npgall.com>
>>>>>>> 
>>>>>>> [1] Concurrent-Locks: Read-write-update / upgradable read-write locks
>>>>>>> for Java
>>>>>>> http://code.google.com/p/concurrent-locks/
>>>>>>> 
>>>>>>> 
>>>>>>> On 19 Jul 2013, at 18:27, Nathan Reynolds <nathan.reynolds at oracle.com
>>>>>>> <mailto:nathan.reynolds at oracle.com>> wrote:
>>>>>>> 
>>>>>>>> I ran into upgrading a lock problem a while back.  The solution I took
>>>>>>>> is first have the thread read acquire the lock.  Then if the thread
>>>>>>>> detects that it needs the write lock, it releases the read lock and
>>>>>>>> starts over by acquiring the write lock.  Of course, all of the data
>>>>>>>> the thread collected in the read lock is considered invalid.  This
>>>>>>>> greatly improved scalability and the "upgrade" didn't hurt
>>>>>>>> performance.  This is because  writes mostly happen at start up and
>>>>>>>> are rare otherwise.
>>>>>>>> 
>>>>>>>> The above logic works great and there hasn't been a need for a
>>>>>>>> read-write-update lock.  The problem in my situation is that I can't
>>>>>>>> predict at the time of acquiring the lock if I will need to do any
>>>>>>>> writes.  The thread has to check the protected state and then decide
>>>>>>>> if any writes are necessary.  (I would guess this scenario is true of
>>>>>>>> most caches.)  If all threads do update acquires, then I am back to
>>>>>>>> the same contention I had with all threads doing write acquires.
>>>>>>>> 
>>>>>>>> I haven't needed this kind of lock.  Every time I run into lock
>>>>>>>> contention, I always solve the problem without it.  If I had such a
>>>>>>>> lock in my toolbox, maybe I would select it.
>>>>>>>> 
>>>>>>>> Can you give a good example of where update acquires can actually
>>>>>>>> help?  A toy example is one method which always needs to do reads and
>>>>>>>> another method which has to do a lot of reads with a very small
>>>>>>>> portion to do writes.  The first method is called very frequently
>>>>>>>> relative to the second method.  Is there such a situation in software?
>>>>>>>> -Nathan
>>>>>>>> On 7/19/2013 4:21 AM, Niall Gallagher wrote:
>>>>>>>>> Hi,
>>>>>>>>> 
>>>>>>>>> I guess it must have been discussed when ReentrantReadWriteLock was being written, the limitation that the read lock cannot be upgraded to a write lock.
>>>>>>>>> 
>>>>>>>>> Two threads hold a read lock, both then try to acquire the write lock -> deadlock. So if a read-mostly thread might ever need write access, it must either hold a write lock for the whole time (blocking other concurrent readers for its whole duration), or it must drop the read lock before acquiring the write lock, with the risk that another thread might steal the write lock from it rendering any data it read as stale.
>>>>>>>>> 
>>>>>>>>> I've written an extension to the basic readers-writer lock concept: a read-write-update lock for Java: ReentrantReadWriteUpdateLock in Concurrent-Locks on Google Code[1].
>>>>>>>>> 
>>>>>>>>> I was wondering if people on this mailing list would like to code review it, or get involved in the project, before I make a 1.0 release to Maven Central?
>>>>>>>>> 
>>>>>>>>> The idea for a read-write-update lock is not new. I see a reference to it on the Linux kernel mailing list from circa 2000 here[2]. Maybe the concept goes by other names also?
>>>>>>>>> 
>>>>>>>>> Some differences between my implementation and the Linux kernel mailing list discussion:
>>>>>>>>> - My implementation is reentrant, which means you actually can acquire the Mutex again if you already hold a Write lock
>>>>>>>>> - I didn't see any reason for Nothing -> Update to acquire both the Mutex and Read locks, so my implementation only acquires Mutex (which is enough to prevent other threads acquiring the Write lock anyway). In fact if it did acquire both, deadlock would occur in reentrant scenario Nothing -> Update (lock Mutex, lock Read), Update -> Update (lock Mutex again, lock Read again) followed by Update -> Write (drop Read, but hold count remains at 1, lock write = deadlock).
>>>>>>>>> 
>>>>>>>>> There is also an implementation of CompositeLock in the project for group-locking and group-unlocking collections of locks with rollback support, which I plan to use for locking nodes in hierarchical structures such as trees (I'm the author of Concurrent-Trees[3]).
>>>>>>>>> 
>>>>>>>>> For ReentrantReadWriteUpdateLock I re-used the JDK ReentrantReadWriteLock as much as possible, so you'll see the code is quite simple. So another question is do you think this kind of R-W-U-Lock might ever make it into the JDK, or is it still too esoteric?
>>>>>>>>> 
>>>>>>>>> Best regards,
>>>>>>>>> 
>>>>>>>>> Niall Gallagher
>>>>>>>>> www.npgall.com
>>>>>>>>> 
>>>>>>>>> [1] Concurrent-Locks: Read-write-update / upgradable read-write locks for Java
>>>>>>>>>  http://code.google.com/p/concurrent-locks/
>>>>>>>>> 
>>>>>>>>> [2] Linux kernel mailing list: Read/Write locks that can be changed into each other
>>>>>>>>>  http://lkml.indiana.edu/hypermail/linux/kernel/0004.3/0117.html
>>>>>>>>> 
>>>>>>>>> [3] Concurrent-Trees: Concurrent Radix and Concurrent Suffix Trees for Java
>>>>>>>>>  http://code.google.com/p/concurrent-trees/
>>>>>>>>> 
>>>>>>>>> 
>>>>>>>>> _______________________________________________
>>>>>>>>> Concurrency-interest mailing list
>>>>>>>>> Concurrency-interest at cs.oswego.edu
>>>>>>>>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>>>>>>>> 
>>>>>>>> 
>>>>>>>> _______________________________________________
>>>>>>>> Concurrency-interest mailing list
>>>>>>>> Concurrency-interest at cs.oswego.edu
>>>>>>>> <mailto:Concurrency-interest at cs.oswego.edu>
>>>>>>>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>>>>>> 
>>>>>>> 
>>>>>>> 
>>>>>>> _______________________________________________
>>>>>>> Concurrency-interest mailing list
>>>>>>> Concurrency-interest at cs.oswego.edu
>>>>>>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>>>>>> 
>>>>>> 
>>>>>> _______________________________________________
>>>>>> Concurrency-interest mailing list
>>>>>> Concurrency-interest at cs.oswego.edu
>>>>>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>>>> 
>>>>> 
>>>>> _______________________________________________
>>>>> Concurrency-interest mailing list
>>>>> Concurrency-interest at cs.oswego.edu
>>>>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>> 
>>> 
>>> _______________________________________________
>>> Concurrency-interest mailing list
>>> Concurrency-interest at cs.oswego.edu
>>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
> 




More information about the Concurrency-interest mailing list