title: MongoDB: Implement a read / write lock (mutex)
body: <p>I need to implement some locking mechanism with MongoDB, in order to prevent inconsistent data, but allow dirty reads.</p>
  
  <h2>The conditions:</h2>
  
  <ul>
  <li><p>Acquiring a <code>WRITE</code> lock is only possible, if there's no <code>READ</code> lock <strong>and</strong> no <code>WRITE</code> lock.</p></li>
  <li><p>Acquiring a <code>READ</code> lock is only possible, if there's no <code>WRITE</code> lock.</p></li>
  <li><p>There can be many parallel <code>READ</code> locks on a single document.</p></li>
  <li><p>There must be some kind of timeout mechanism: If (for whatever reason) some process does not release its lock, the application must be able to recover.</p></li>
  </ul>
  
  <p>Dirty reads are possible by simply ignoring all locks within the query.</p>
  
  <p>(Starvation of <code>WRITE</code> processes is not part of this topic)</p>
  
  <h2>Why <code>READ</code> and <code>WRITE</code> locks / why not only using a <code>WRITE</code> lock:</h2>
  
  <p>Let's assume, we have 2 collections: <code>contacts</code> and <code>categories</code>. It's a n-m relationship, where each contact has an array of category IDs.</p>
  
  <p><strong><code>READ</code> lock:</strong> When adding a category to a contact, we must make sure that this category isn't getting deleted at the moment (which requires a <code>WRITE</code> lock, see below). And because there can be many <code>READ</code> locks on the same document, it's possible for multiple processes to add this single category to multiple contacts.</p>
  
  <p><strong><code>WRITE</code> lock:</strong> When deleting a category, we must first remove the category ID from all contacts. While this operation is running, we must make sure, that it's not possible to add this category to any contact (this operation needs a <code>READ</code> lock). Afterwards we can safely remove the category document.</p>
  
  <p>This way, there will be always a consistent state.</p>
  
  <h2>The timeout:</h2>
  
  <p>That's the hardest part. I already tried to implement it twice, but always found some issues, that seemed to be too hard to solve.</p>
  
  <p><strong>The basic idea:</strong> Every acquired lock comes with a timestamp until when this lock is valid. If this timestamp is in the past, we can ignore that lock. When a process finished its task, it should remove its lock.</p>
  
  <p>The big challenge was, to have multiple <code>READ</code> locks, where each <code>READ</code> lock has its own timeout, but multiple <code>READ</code> locks can have the same timeout value. And when releasing a <code>READ</code> lock it must only release itself, all other <code>READ</code> locks must be preserved.</p>
  
  <h2>My last implementation:</h2>
  
  <pre><code>{
    _id: 1234,
    lock: {
      read: [
        ISODate("2015-06-26T12:00:00Z")
      ],
      write: null
    }
  }
  </code></pre>
  
  <p>Either <code>lock.read</code> can contain elements <strong>or</strong> <code>lock.write</code> can be set. It must be never possible to have both set!</p>
  
  <h2>The queries:</h2>
  
  <p>The queries for this are okay, some could be a bit easier (especially "release read lock"). But the main reason for showing them to you is that I'm still not sure if I haven't missed something.</p>
  
  <p><strong>Preface:</strong></p>
  
  <ul>
  <li><code>ISODate("now")</code> is the current time. It's used to ignore all locks that are expired. And it's also used to remove all expired read locks.</li>
  <li><code>ISODate("lock expiration")</code> is used to indicate when this lock will expire and can be ignored / removed. (e.g. <code>now + 5 seconds</code>)
  
  <ol>
  <li>This is used when acquiring a new lock.</li>
  <li>And it's also used when releasing a read lock.</li>
  </ol></li>
  </ul>
  
  <p><strong>Acquire <code>READ</code> lock:</strong></p>
  
  <p>If there's no valid write lock, then insert a read lock.</p>
  
  <pre><code>update(
    {
      _id: 1234,
      $or: [
        { 'lock.write': null },
        { 'lock.write': { $lt: ISODate("now") } }
      ]
    },
    {
      $set: { 'lock.write': null },
      $push: { 'lock.read': ISODate("lock expiration") }
    }
  )
  </code></pre>
  
  <p><strong>Acquire <code>WRITE</code> lock:</strong></p>
  
  <p>If there's no valid read lock <strong>and</strong> no valid write lock, then set the write lock.</p>
  
  <pre><code>update(
    {
      _id: 1234,
      $and: [
        $or: [
          { 'lock.read':{ $size: 0 } },
          { 'lock.read':{ $not: { $gte: ISODate("now") } } }
        ],
        $or: [
          { 'lock.write': null },
          { 'lock.write': { $lt: ISODate("now") } }
        ]
      ]
    },
    {
      $set: {
        'lock.read': [],
        'lock.write': ISODate("lock expiration")
      }
    }
  )
  </code></pre>
  
  <p><strong>Release <code>READ</code> lock:</strong></p>
  
  <p>Remove the acquired read lock by using its expiration timestamp.</p>
  
  <pre><code>update(
    {
      _id: 1234,
      'lock.read': ISODate("lock expiration")
    },
    {
      $unset: { 'lock.read.$': null }
    }
  )
  
  update(
    {
      _id: 1234,
    },
    {
      $pull: { 'lock.read': { $lt: ISODate("now") } }
    }
  )
  
  update(
    {
      _id: 1234
    },
    {
      $pull: { 'lock.read': null }
    }
  )
  </code></pre>
  
  <p>(It's possible that <code>lock.read</code> array contains multiple identical timestamps, if multiple processes acquired a <code>READ</code> lock. Though we need to only remove <strong>one</strong> timestamp, and this won't work with <code>$pull</code>, but works using the positional operator <code>$</code>.
  Also I remove all expired locks with an additional update. I tried some things, but wasn't able to reduce it to 2 or even 1 update.)</p>
  
  <p><strong>Release <code>WRITE</code> lock:</strong></p>
  
  <p>Remove the write log. Here should be nothing to check.</p>
  
  <pre><code>update(
    {
      _id: 1234
    },
    {
      $set: { 'lock.write': null }
    }
  )
  </code></pre>
  
  <h1>EDIT 1: Simplified Acquire <code>READ</code> and <code>WRITE</code> queries</h1>
  
  <p><code>{ $not: { $gte: ISODate("now") } }</code> will match only, if the field does <strong>not</strong> contain anything <code>$gte: ISODate("now")</code>. Though it will match <code>null</code> and non-existing fields as well as an empty array.</p>
  
  <p><strong>Acquire <code>READ</code> lock:</strong></p>
  
  <pre><code>update(
    {
      _id: 1234,
      'lock.write': { $not: { $gte: ISODate("now") } }
    },
    {
      $set: { 'lock.write': null },
      $push: { 'lock.read': ISODate("lock expiration") }
    }
  )
  </code></pre>
  
  <p><strong>Acquire <code>WRITE</code> lock:</strong></p>
  
  <pre><code>update(
    {
      _id: 1234,
      'lock.write': { $not: { $gte: ISODate("now") } },
      'lock.read': { $not: { $gte: ISODate("now") } }
    },
    {
      $set: {
        'lock.read': [],
        'lock.write': ISODate("lock expiration")
      }
    }
  )
  </code></pre>
  
  <p>But still no idea regarding the "Release <code>READ</code> lock" query... </p>
  
  <p>I thought about some kind of tuple having the timeout timestamp and the count of locks. But then the problem comes with the Acquire <code>READ</code> lock query.</p>
  
  <hr>
  
  <h1>EDIT 2: Different data structure for easier release <code>READ</code> lock</h1>
  
  <pre><code>{
    _id: 1234,
    lock: {
      read: [
        { timeout: ISODate("2015-06-26T12:00:00Z"), process: ObjectId("...") }
      ],
      write: null
    }
  }
  </code></pre>
  
  <p>This works, because an <code>ObjectId</code> consists of timestamp, machine id, process id and a counter. This way it's not possible to create multiple equal <code>ObjectIds</code>. Long story short:</p>
  
  <p>When acquiring a <code>READ</code> lock, we insert a document that consists of the timeout timestamp and a unique <code>ObjectId</code>. And when releasing it, we use this combination to remove it from the array. So the only interesting queries are:</p>
  
  <p><strong>Aquire <code>WRITE</code> lock:</strong></p>
  
  <pre><code>update(
    {
      _id: 1234,
      'lock.write': { $not: { $gte: 4 } },
      'lock.read.timeout': { $not: { $gte: 4 } }
    },
    {
      $set: {
        'lock.read': [],
        'lock.write': ISODate("lock expiration")
      }
    }
  )
  </code></pre>
  
  <p><strong>Release <code>READ</code> lock:</strong></p>
  
  <pre><code>update(
    {
      _id: 1234,
    },
    {
      $pull: {
        'lock.read': {
          $or: [
            { 'timeout': ISODate("lock expiration"), process: ObjectId("...") },
            { 'timeout': { $lt: ISODate("now") } }
          ]
        }
      }
    }
  )
  </code></pre>
  
  <p>As you can see, we now only need a single query to remove our lock on clean up all timed out locks.</p>
  
  <p>The unique process identifier is quite important, because without it, the <code>$pull</code> operation could remove the lock of another process if it acquired a lock with the very same timeout value.</p>
  
  <p>Next step would be, to get rid of the <code>process</code> field and only use an <code>ObjectId</code> which should be able to hold the <code>timeout</code> part within. ( e.g. <a href="https://stackoverflow.com/questions/13593896/mongodb-perform-a-date-range-query-from-the-objectid-in-the-mongo-shell">Mongodb: Perform a Date range query from the ObjectId in the mongo shell</a> )</p>
  
  <hr>
  
  <h1>Questions:</h1>
  
  <ul>
  <li><p>Is this a valid and bulletproof implementation using MongoDB?</p></li>
  <li><p>If "yes": Can I somehow improve it? (at least the "Release <code>READ</code> lock" part)</p></li>
  <li><p>If "no": What's wrong with it? What have I missed?</p></li>
  </ul>
  
  <p><strong>Thanks in advance for your help!</strong></p>