Reader/Writer Lock Pattern

A reader-writer lock is a lock which will allow multiple concurrent readers but only one writer. A reader-writer lock can be significantly more efficient than a standard mutex if reads on your shared memory far outnumber writes.

Reader-writer locks naturally fit together with caches, as caches are only effective if reads far outnumber writes.

Here is a general pattern for using a reader-writer lock with a cache:

  1. Acquire a reader lock.
  2. Check the cache for the value. If it exists, save the value and go to step 8.
  3. Upgrade the reader lock to a writer lock.
  4. Check the cache for the value. If it exists, save the value and go to step 7.
  5. Calculate the value (expensive, otherwise we wouldn’t cache it)
  6. Insert the value into the cache.
  7. Release the writer lock.
  8. Release the reader lock.
  9. Return the value.

The reason why we have to check the cache for the value again in step (4) is because of the following possibility (assume step 4 doesn’t exist):

Thread 1                         Thread 2
============================     ===============================
- Acquire reader lock            - Acquire reader lock
- Check cache for value          - Check cache for value
  with key A (not found)           with key A (not found)
- Upgrade to writer lock         - (block)
- Calculate value (expensive)
- Insert value into cache
- Release writer lock
- Release reader lock
                                 - Upgrade to writer lock
                                 - Calculate value (expensive)
                                   (We are paying this cost
                                   twice)
                                 - Insert value into cache
                                   (We are inserting two values
                                   with the same key, which may
                                   be fatal)

With step 4 it becomes:

Thread 1                         Thread 2
============================     ===============================
- Acquire reader lock            - Acquire reader lock
- Check cache for value          - Check cache for value
  with key A (not found)           with key A (not found)
- Upgrade to writer lock         - (block)
- Calculate value (expensive)
- Insert value into cache
- Release writer lock
- Release reader lock
                                 - Upgrade to writer lock
                                 - Check cache for value
                                   with key A (found)
                                 - Release writer lock
                                 - Release reader lock
- Return value                   - Return value

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s