title: NoSQL - modelling RDBMS transactional reads
body: <p>NoSQL databases do not, <em>in general</em>, provide RDBMS-style transactions that are guaranteed to fully succeed or fail. (I'm aware some do, but I'm interested in exploring the case where they don't.) NoSQL providers, however, are quick to point out that behaviour requiring transactions in traditional RDBMS databases can be done in atomic NoSQL operations (i.e. single-document writes). For example, here's the <a href="http://guide.couchdb.org/draft/recipes.html" rel="nofollow">CouchDB approach to doing bank transactions</a> - rather than decreasing one balance and increasing another (two writes in a transaction in an RDBMS), you write a new document that describes the transfer.</p>
  
  <p>However, doing such a transfer in an RDBMS transaction would probably involve <strong>three</strong> operations:</p>
  
  <ol>
  <li><strong>Verify that the current balance of the sender is sufficient to transfer the funds</strong>, and if so:</li>
  <li>Decrease balance of sender</li>
  <li>Increase balance of recipient</li>
  </ol>
  
  <p>When dealing with two payments both attempting to take funds from an account that can only afford one or the other, how can we manage this in a NoSQL environment and ensure that we don't end up overdrawn? NoSQL databases generally have a mechanism to detect and prevent write collisions when two operations try to update the same document. However, since the approach of writing a document to describe the transfer means writing a <strong>new</strong> document, this won't detect two payments happening at the same time.</p>
  
  <p>There's an obvious cop-out here, which is to use code locks to prevent the two payments starting at the same time at the application level, but what I'm interested in is <strong>is there a "reasonable" lock-free method of checking a value and then altering it that prevents concurrent operations putting the value in an invalid state?</strong></p>
  
  <p>I have come up with a couple of methods that achieve this aim, but both are unpleasant for one reason or another - I'm interested as to whether there's a neater solution that I've missed. I'll describe them in terms of balance transfers, for the sake of a useful metaphor. Assume Alice is trying to pay both Bob and Charlie at the same time, but can only afford to pay one of them.</p>
  
  <ol>
  <li>Do operations naively with a single document write each, and then reverse if we end up overdrawn</li>
  </ol>
  
  <p>Simply put both payments through. After each payment, check that Alice isn't overdrawn. The problem here is that it's possible for both payments to spot the overdraft and back out. If they both give up at this point, neither will succeed when one could have. If they both check the balance again after backing out, they may both see that there's enough money to try again, and they could do so. The loop continues. This could be resolved (eventually) with random back-off delays, but this puts a burden on the application to manage retries in a relatively complex way, and can also leave a long trail of failed payments.<br>
     It's also possible that, if someone transfers funds <em>into</em> Alice's account while this is going on, then both payments will actually succeed. Alice will have been very briefly overdrawn, but is now in the black. This may or may not be acceptable.</p>
  
  <ol start="2">
  <li>Rather than writing a new document for each payment, append to a single document</li>
  </ol>
  
  <p>This way we can use write-collision detection to force one payment to try again. However, the document we're appending to is going to get really big really fast, and we've also thrown away our ability to index on the payments.</p>
  
  <p>All told it seems to me that, vendor claims aside, for applications such as this an RDBMS is probably still the best tool for the job.</p>