I stumbled on this old book today called "Transaction Processing"[0] that never made it past a first edition in the early 90s. It is a leviathan treatise on the unification of conventional and distributed database systems, operating systems, computer networking and software engineering. How could a book like this end up in the digital dust bin?
I looked up the first author, Jim Gray. Apparently, the guy won the Turing Award in 1998 for "for seminal contributions to database and transaction processing research and technical leadership in system implementation."[1] I studied computer science at university and have never heard of such a thing. Frankly, I am shaken there are still astonishing ideas, like "transaction processing," that hover unnoticed over the ivory towers. What's the point of lofty ideas if everyone doesn't know about them?
Jim Gray seems to have disappeared mysteriously at sea around 10 years after receiving his Turing Award. Now he doesn't appear a widely recognizable name, even among HN. I searched for "Transaction Processing" in the HN archive, but didn't find anything on Jim Gray.
It makes me wonder who else didn't get all their roses when they were due? Who are the underrated Turing Award recipients?
Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems) ISBN-13: 978-1558605084
If the locking is not done properly it certainly is possible to get this type race condition, and the default locking mode (read committed) does allow it. In this mode, the reads only place a shared lock on the record, so they can both see 0, increment it and write 1 out to the database.
In order to avoid this race condition, you need to set an exclusive lock on the read operation. 'Serializable' and 'Repeatable Read' concurrency modes will do this, and for an operation on a single row they are pretty much equivalent.
To make it completely atomic you have to:
Set an appropriate transaction isolation level such as Serializable. Normally you can do this from a client library or explicilty in SQL.
Begin the transaction
Read the data
Update it
Commit the transaction.
You can also force an exclusive lock on the read with a HOLDLOCK (T-SQL) or equivalent hint, depending on your SQL dialect.
A single update query will do this atomically but you can't split the operation (perhaps to read the value and return it to the client) without ensuring that the reads take out an exclusive lock. You will need to get the value out atomically in order to implement a sequence, so the update by itself is probably not quite all you need. Even with the atomic update, you still have a race condition to read the value after the update. The read will still have to take place within a transaction (storing what it got in a variable) and issue an exclusive lock during the read.
Note that to do this without creating a hot spot your database needs to have proper support for autonomous (nested) transactions within a stored procedure. Note that sometimes 'nested' is used to refer to chaining transactions or save points, so the term can be a bit confusing. I've edited this to refer to autonomous transactions.
Without autonomous transactions your locks are inherited by the parent transaction, which can roll back the whole lot. This means they will be held until the parent transaction commits, which can turn your sequence into a hot spot that serialises all transactions using that sequence. Anything else trying to use the sequence will block until the whole parent transaction commits.
I looked up the first author, Jim Gray. Apparently, the guy won the Turing Award in 1998 for "for seminal contributions to database and transaction processing research and technical leadership in system implementation."[1] I studied computer science at university and have never heard of such a thing. Frankly, I am shaken there are still astonishing ideas, like "transaction processing," that hover unnoticed over the ivory towers. What's the point of lofty ideas if everyone doesn't know about them?
Jim Gray seems to have disappeared mysteriously at sea around 10 years after receiving his Turing Award. Now he doesn't appear a widely recognizable name, even among HN. I searched for "Transaction Processing" in the HN archive, but didn't find anything on Jim Gray.
It makes me wonder who else didn't get all their roses when they were due? Who are the underrated Turing Award recipients?
[0] https://www.amazon.com/Transaction-Processing-Concepts-Techniques-Management/dp/1558601902
[1] https://en.wikipedia.org/wiki/Jim_Gray_(computer_scientist)
https://www.amazon.com/dp/1558605088/?coliid=IYEILMZI5DVNM&c...
and
Transaction Processing: Concepts and Techniques (The Morgan Kaufmann Series in Data Management Systems) ISBN-13: 978-1558601901
https://www.amazon.com/dp/1558601902/?coliid=I2GWJZ9XJ5D4JI&...
Gray wrote a book titled "Transaction Processing: Concepts and Techniques" - http://www.amazon.com/Transaction-Processing-Concepts-Techniques-Management/dp/1558601902 - which covers a great deal of what you would need to build your own database.
One starting point for file systems would be http://www.amazon.com/The-Design-UNIX-Operating-System/dp/0132017997 - but I suspect you would have to chase down individual papers or Linux source code to keep up with the variety of different file systems created since then.
If the locking is not done properly it certainly is possible to get this type race condition, and the default locking mode (read committed) does allow it. In this mode, the reads only place a shared lock on the record, so they can both see 0, increment it and write 1 out to the database.
In order to avoid this race condition, you need to set an exclusive lock on the read operation. 'Serializable' and 'Repeatable Read' concurrency modes will do this, and for an operation on a single row they are pretty much equivalent.
To make it completely atomic you have to:
You can also force an exclusive lock on the read with a HOLDLOCK (T-SQL) or equivalent hint, depending on your SQL dialect.
A single update query will do this atomically but you can't split the operation (perhaps to read the value and return it to the client) without ensuring that the reads take out an exclusive lock. You will need to get the value out atomically in order to implement a sequence, so the update by itself is probably not quite all you need. Even with the atomic update, you still have a race condition to read the value after the update. The read will still have to take place within a transaction (storing what it got in a variable) and issue an exclusive lock during the read.
Note that to do this without creating a hot spot your database needs to have proper support for autonomous (nested) transactions within a stored procedure. Note that sometimes 'nested' is used to refer to chaining transactions or save points, so the term can be a bit confusing. I've edited this to refer to autonomous transactions.
Without autonomous transactions your locks are inherited by the parent transaction, which can roll back the whole lot. This means they will be held until the parent transaction commits, which can turn your sequence into a hot spot that serialises all transactions using that sequence. Anything else trying to use the sequence will block until the whole parent transaction commits.
IIRC Oracle supports autonomous transactions but DB/2 didn't until fairly recently and SQL Server doesn't. Off the top of my head I don't know whether InnoDB supports them, but Grey and Reuter go on at some length about how difficult they are to implement. In practice I'd guess it's quite likely that it might not. YMMV.
The thing with the Paxos algorithm is that it's fairly recent (published as a journal article in 1998 according to http://en.wikipedia.org/wiki/Paxos_(computer_science)) and classic books like Readings in Database Systems or Transaction Processing cover the other topics you care about, but actually pre-date Paxos!