I knew of this issue for some time (default DB isolation is less than SERIALIZABLE on most DB).
But assuming you do not want to change the default isolation for your transaction or for the whole DB.
How do you write unit-test that check your code will work correctly because it's using "select balance from accounts FOR UPDATE"?
The issue is that the race condition exists in the database, not in any application code. So you can either simulate the race, or you need to integration test, and that's outside the scope of TLA+ and model checking.
I haven't heard of Coyote (it's still amazing how many tools are out there). It's good that it operates on the actual code level, but I'm still not sure that would reproduce concurrency non-determinism at the database level.
The problem is that you don’t really know if your mock accurately implements the behavior of the database. The only way you could verify the mock behaves correctly would be to run the mock and a real database instance through a set of tests to verify they both implement different isolation levels identically.
At that point—why bother with the mock at all? Cutting out the intermediary and running integration tests of your application against a real database will be faster.
You can’t use SQLite here either because all SQLite isolation levels are serializable anyway, which is _very_ different from how PostgreSQL works. Testing against SQLite could end up giving you a false sense of security that your code is safe against race conditions, whereas in reality it’s vulnerable when connected to a PostgreSQL server because of the difference in default isolation levels
At this level of testing detail the only real option is to test against a real database that matches what you’re running in production. Otherwise you’re just testing a mock.
Except in the case of shared cache database connections with PRAGMA read_uncommitted turned on, all transactions in SQLite show "serializable" isolation
It's not perfect, but I have had success running postgres in Docker and running integration tests against that. Usually you can trigger the problem by running a handful of queries in parallel.
Why optimistic locking is never considered in those articles ? Adding a version column and checking the affected numbers of row scales a lot better that a select for update...
Optimistic locking is a great solution to avoid holding a lock for an indeterminate period of time as you wait for a user or external system to provide updates.
I don’t know about databases but I’ve done similar with testing interactive web apps and it works quite well. When your architecture supports it, at least.
Essentially a hidden field on the page that tracks interactions and outstanding Ajax calls. When you assert that a field on the page hasn’t changed, you need to know that it’s not still in the process of painting. And just waiting “long enough” makes for very slow testing overall.
You're right. Locking the rows or using serializable isolation would be required to achieve an atomic operation if and only if both accounts are in the pristine state before it.
>Hopefully it’s clear why this is an issue. If you have an important column value, say a user’s account balance, you might query multiple different values in the same transaction
and that is a feature, not a bug. During your transaction user withdrew money from his account. If you wanna see the same value, i.e. block that user from withdrawals while you process his current balance, you take a lock on that row. Similar in many ways to the concurrent programming with threads.
Bearing in mind that “handling” the locks may mean a deadlock is detected and the transaction is aborted by the DB, which the application has to handle by retrying in a correct manner. (Which is another point often missed in naive application code.)
Not exactly - the database doesn't know whether you want to block that account update or not. So, speaking very roughly, it allows you to choose general level of such a blocking behavior. It manages those locks, very coarse, at serializable and some of those locks at repeatable read. At read committed it manages basically only small set of locks just to avoid dirty reads (plus of course all the WAL/rollback/etc. which is the main features and the point of the database with the isolation levels being just the icing on that cake). Isolation levels is a tool, and you choose what is needed and suitable.
The serializable actually is a pain in the neck for any meaningfully serious large enterprise application. The decreased concurrency kills overall performance, and I haven't seen any such application running in serializable (and for example at my current job our customers are running our application on servers with low tens of TB RAM (largest so far was 40TB RAM) per single machine with high hundreds of cores with thousands of users - in serializable that would slow to a crawl as it wouldn't allow to achieve the concurrency the database on those machines is otherwise capable of). While not precise illustration it still communicates my point - the serializable against read committed is like the global Python lock against the fine grained locks in normal languages.
If you're storing a balance, rather than a ledger of the transactions which caused that balance to be the case, you're probably already off to a bad start when it comes to design.
Just imagine if you called your bank and asked them why my balance was $500, and they said "I don't know, hit F5 and see if it changes"...
When it comes to this topic, almost all examples don't match how things work in the real world where they are eventually consistent.
For example, my bank lets me go negative and then if I don't settle by the end of the day, overdraft protection will kick in for a little more than that negative amount.
Indeed - seeing account balance used as an example of database transactions is a red flag to me, and would absolutely cause me to dig deeper into whether the author/speaker understands how banking actually works.
I don’t claim to be a banking expert, but I did work at a payment processor that handled real money, and we used “select for update” extensively.
We also (obviously) used a ledger, but “just let everyone overdraft whenever” wasn’t something that the executives of the company thought was a good idea. So we did try and prevent insufficient funds errors as much as possible.
I personally witnessed several scenarios where the company lost a notable amount of money, (not only rated to concurrency bugs of course) and it’s a pretty bad feeling.
Anyway, I’m legitimately curious to know from people who worked at larger banks perhaps. How is weak transaction isolation not a problem for banks?
Can you elaborate? Does your bank allow you to overdraft on $50k for example? I think it’s more complicated than “eventual consistency solves all problems.”
I assume there's some point where they will start declining transactions and it could be some fixed number or some complex calculation based on all the data the bank has about my finances.
My point is that these examples are bad ones because they don't match the real world, which is messy and complex and inconsistent.
I hear what you're saying, the real world is often complex. However, I don't agree that means banking examples aren't useful, because they do lay out the problem that all banks have to consider, one way or another.
There are many ways of solving the consistency problem, but understanding what consistency and serializability is means that you'll be better educated in coming up with solutions.
Also, I believe that all else being equal, you would want serializability. It simplifies everything. There's a new [financial database under development named TigerBeetle](https://docs.tigerbeetle.com/design/consistency). They chose to implement strict serializability by default because:
> Strict consistency guarantees (at the database level) simplify 1) application logic and 2) error handling farther up the stack.
So the banks of today may have to deal with inconsistency, but that doesn't mean the banks of tomorrow want to.
I briefly dabbled in financial ledgers in a previous job. We made plans to do what you seem to be describing, which is to store the transactions themselves and calculate a balance as needed, but we frankly lacked expertise. I always wondered what would happen if we scaled to millions of transactions in that system.
Is there a standard strategy for optimizing balance queries against a series of transactions? I assumed that we would eventually have to cache some kind of snapshot for each account to avoid the overhead of totaling every transaction on every balance check.
There are quite a few standards - "closing the books" on some period (monthly, daily, hourly, depending on volume/regulatory requirements) is usually the way.
There's also a good, sadly now out of print, book named "Analysis Patterns" by Martin Fowler which has a large section about account representation strategies from an object modelling perspective which also translates reasonably well to functional programming.
It's annoying it's out of print, since it contains timeless information rather than the fad-du-jour!
> Is there a standard strategy for optimizing balance queries against a series of transactions?
Nope!
But it's not terribly hard to design something.
I demote the DB down to a caching layer, and promote the ledger as the source of truth. All writes are appended to the ledger. Something listens to the ledger and updates the DB. Reads are against the DB.
Generally, for a lot of application usage patterns, read committed is the default for a reason.
From the Postgres docs:
> The partial transaction isolation provided by Read Committed level is adequate for many applications, and this level is fast and simple to use. However, for applications that do complex queries and updates, it may be necessary to guarantee a more rigorously consistent view of the database than the Read Committed level provides.
Also, consider storing the transactions that change the balances (credits, debits, etc) in a ledger and calculate the balance. You can avoid the complex update logic and keep your accountants and auditors happy.
Stricter isolation levels are useful but have a lot of trade-offs to be aware of.
Sometimes restructuring your data is a lot more effective than trying to reason about locks and concurrency. The more locks you have to more points of contention, dead locks, etc you have to be concerned about. Humans and general rules/folklore are alright at avoiding some mistakes but these systems get complicated quickly and can hide a surprising number of errors.
As for testing these things, I've gotten a lot of good mileage out of model checking. TLA+ and Alloy are better at finding concurrency errors than I am at avoiding them.
Can you recommended a good article that goes over the ledger pattern (the easy part) and the performant calculation of balances as the ledger grows? I'm going to start working on a warehouse management system in the coming months and that would come in handy.
I don't have a link but when I've implemented systems with a "ledger" of changes I would have a field that indicated whether the ledger item had been "posted" to the the affected account(s) and therefore the balance was just the account balance +/- any unposted ledger items.
I've had ledgers that were posted once a day, or more often, up to nearly real-time.
But once a ledger item is posted, it should never be changed. If an error is discovered, make a new ledger entry to correct it.
The pattern in general is called "event sourcing", but unfortunately it's popular enough to make a lot of bad articles appear, and I can't recommend a good one.
The ledger pattern is called double-entry accounting.
Make sure your product managers understood that you’re being tasked with creating an accounting system. They probably haven’t really thought it through very well.
How can you store ledger operations without locking on the balance? The race condition still exists - you can't accept a withdrawal if the user doesn't have enough funds.
You can use some sort of concurrency index on the ledger.
For example you read the ledger entries for Account Id X
Those ledger entries are numbered sequentially up to the current index Y
You calculate the current balance, approve the withdrawal, and try to insert the next ledger entry as Y + 1
If another operation has already inserted a Y + 1 your insert fails and you throw an error or try again, starting with the new ledger state and balance.
Basically optimistic concurrency but knowing that you are always appending to the ledger and that the index is always incrementing.
> Also, consider storing the transactions that change the balances (credits, debits, etc) in a ledger and calculate the balance. You can avoid the complex update logic and keep your accountants and auditors happy.
This was written (to me) as if using a ledger alone would get rid of the race conditions caused by the read committed isolation level.
But what you described is manually implementing locking, which requires additional schema and application logic.
Optimistic concurrency and a ledger lets you do those checks without locking any rows and you don’t have multiple processes fighting to update a single row.
Instead of leaving an AccountBalance row locked for the entirety of the Withdrawal process, you have a condition on the insert and a retry mechanism if that insert fails.
You still have to implement concurrency logic, it’s just less likely to have the database isolation be your bottleneck.
I made a little project called Concurrency Runner a while ago to attempt to test these kinds of scenarios: https://github.com/weinberg/concurrencyRunner. It does so by running multiple copies of your process in debug mode with breakpoints set to allow specific interleaved execution paths to be explored. This allows you to trigger concurrency scenarios which are difficult to analyze because they otherwise would rely on random timing. That repo has examples which demonstrate "read skew", "write skew" and "read modify write" concurrency scenarios. I was hoping I could make it into something you could run in CI to actively test for these things. Ultimately it was more of a research project than anything else but maybe someone will find it useful or interesting.
That’s really cool. It reminds me of Meta’s hermit, which intercepts system calls and records them so that they can be replayed back deterministically.
Non-determinism is the name of all testing. Anything that we can do to improve it is extremely important.
This and other concurrency problems often fall into the “you just have to know how to not get it wrong” camp. If you know to write an automated test for it, you probably know enough to reason about it and get it right. For very important things, sure, maybe write a test, but these tests are very expensive to write and maintain. It’s often cheaper to recognize (and train other team members to recognize) these scenarios and use a higher isolation level. Postgres makes this easy because serializable doesn’t come with a huge perf penalty (mostly memory, I believe).
I’m strongly in the TDD camp too, btw. So I don’t say this flippantly. I appreciate this article bringing further awareness to this.
Also, I cannot recommend partitioning (and event sourcing) enough to eliminate and simplify these problems.
55 comments
[ 2.7 ms ] story [ 104 ms ] threadBut assuming you do not want to change the default isolation for your transaction or for the whole DB. How do you write unit-test that check your code will work correctly because it's using "select balance from accounts FOR UPDATE"?
It seem to me the only way to really validate this is using tool like TLA+. Or something like https://github.com/microsoft/coyote
If your app contain 10 distinct transactions.
you have to test what happen if 2 instances of tx #1 run concurrently.
But also if tx #1 and tx #2 run concurrently.
And also what if tx #1 and tx #3 run concurrently ....
I haven't heard of Coyote (it's still amazing how many tools are out there). It's good that it operates on the actual code level, but I'm still not sure that would reproduce concurrency non-determinism at the database level.
The problem is your mock need to implement the same isolation level as your real DB and support transaction ...
You could use SQLITE in memory DB to run your test but that would make your test a lot slower I assume.
At that point—why bother with the mock at all? Cutting out the intermediary and running integration tests of your application against a real database will be faster.
You can’t use SQLite here either because all SQLite isolation levels are serializable anyway, which is _very_ different from how PostgreSQL works. Testing against SQLite could end up giving you a false sense of security that your code is safe against race conditions, whereas in reality it’s vulnerable when connected to a PostgreSQL server because of the difference in default isolation levels
At this level of testing detail the only real option is to test against a real database that matches what you’re running in production. Otherwise you’re just testing a mock.
Except in the case of shared cache database connections with PRAGMA read_uncommitted turned on, all transactions in SQLite show "serializable" isolation
But there are definitely many valid solutions, including just setting the specific transaction to serializable and handling transaction retries.
Essentially a hidden field on the page that tracks interactions and outstanding Ajax calls. When you assert that a field on the page hasn’t changed, you need to know that it’s not still in the process of painting. And just waiting “long enough” makes for very slow testing overall.
if your goal is to transfer 10 dollars for account A to account B but only if account A balance is larger than 10 dollars.
You have to update account A to be 10 dollars less
and
you have to update account B to be 10 dollars more.
you can read both account a keep track of current version number for each.
then do
"UPDATE Accounts SET Balance = CASE AccountID WHEN 1 THEN Balance - 10 WHEN 2 THEN Balance + 10 END WHERE (AccountID, version) IN ((1,v1), (2,v2))"
But if using Read Uncommited isolation level I am not sure this UPDATE would actually lock both row until commit.
IF @@ROWCOUNT = 2 BEGIN COMMIT TRANSACTION; END ELSE BEGIN ROLLBACK TRANSACTION; END
to make sure both rows have been updated. so its a lot simpler to explicitly take a lock on the rows.
and that is a feature, not a bug. During your transaction user withdrew money from his account. If you wanna see the same value, i.e. block that user from withdrawals while you process his current balance, you take a lock on that row. Similar in many ways to the concurrent programming with threads.
The serializable actually is a pain in the neck for any meaningfully serious large enterprise application. The decreased concurrency kills overall performance, and I haven't seen any such application running in serializable (and for example at my current job our customers are running our application on servers with low tens of TB RAM (largest so far was 40TB RAM) per single machine with high hundreds of cores with thousands of users - in serializable that would slow to a crawl as it wouldn't allow to achieve the concurrency the database on those machines is otherwise capable of). While not precise illustration it still communicates my point - the serializable against read committed is like the global Python lock against the fine grained locks in normal languages.
Just imagine if you called your bank and asked them why my balance was $500, and they said "I don't know, hit F5 and see if it changes"...
For example, my bank lets me go negative and then if I don't settle by the end of the day, overdraft protection will kick in for a little more than that negative amount.
I don’t claim to be a banking expert, but I did work at a payment processor that handled real money, and we used “select for update” extensively.
We also (obviously) used a ledger, but “just let everyone overdraft whenever” wasn’t something that the executives of the company thought was a good idea. So we did try and prevent insufficient funds errors as much as possible.
I personally witnessed several scenarios where the company lost a notable amount of money, (not only rated to concurrency bugs of course) and it’s a pretty bad feeling.
Anyway, I’m legitimately curious to know from people who worked at larger banks perhaps. How is weak transaction isolation not a problem for banks?
My point is that these examples are bad ones because they don't match the real world, which is messy and complex and inconsistent.
There are many ways of solving the consistency problem, but understanding what consistency and serializability is means that you'll be better educated in coming up with solutions.
Also, I believe that all else being equal, you would want serializability. It simplifies everything. There's a new [financial database under development named TigerBeetle](https://docs.tigerbeetle.com/design/consistency). They chose to implement strict serializability by default because:
> Strict consistency guarantees (at the database level) simplify 1) application logic and 2) error handling farther up the stack.
So the banks of today may have to deal with inconsistency, but that doesn't mean the banks of tomorrow want to.
Is there a standard strategy for optimizing balance queries against a series of transactions? I assumed that we would eventually have to cache some kind of snapshot for each account to avoid the overhead of totaling every transaction on every balance check.
There's also a good, sadly now out of print, book named "Analysis Patterns" by Martin Fowler which has a large section about account representation strategies from an object modelling perspective which also translates reasonably well to functional programming.
It's annoying it's out of print, since it contains timeless information rather than the fad-du-jour!
Nope!
But it's not terribly hard to design something.
I demote the DB down to a caching layer, and promote the ledger as the source of truth. All writes are appended to the ledger. Something listens to the ledger and updates the DB. Reads are against the DB.
From the Postgres docs:
> The partial transaction isolation provided by Read Committed level is adequate for many applications, and this level is fast and simple to use. However, for applications that do complex queries and updates, it may be necessary to guarantee a more rigorously consistent view of the database than the Read Committed level provides.
Also, consider storing the transactions that change the balances (credits, debits, etc) in a ledger and calculate the balance. You can avoid the complex update logic and keep your accountants and auditors happy.
Stricter isolation levels are useful but have a lot of trade-offs to be aware of.
Sometimes restructuring your data is a lot more effective than trying to reason about locks and concurrency. The more locks you have to more points of contention, dead locks, etc you have to be concerned about. Humans and general rules/folklore are alright at avoiding some mistakes but these systems get complicated quickly and can hide a surprising number of errors.
As for testing these things, I've gotten a lot of good mileage out of model checking. TLA+ and Alloy are better at finding concurrency errors than I am at avoiding them.
I've had ledgers that were posted once a day, or more often, up to nearly real-time.
But once a ledger item is posted, it should never be changed. If an error is discovered, make a new ledger entry to correct it.
Make sure your product managers understood that you’re being tasked with creating an accounting system. They probably haven’t really thought it through very well.
For example you read the ledger entries for Account Id X
Those ledger entries are numbered sequentially up to the current index Y
You calculate the current balance, approve the withdrawal, and try to insert the next ledger entry as Y + 1
If another operation has already inserted a Y + 1 your insert fails and you throw an error or try again, starting with the new ledger state and balance.
Basically optimistic concurrency but knowing that you are always appending to the ledger and that the index is always incrementing.
This was written (to me) as if using a ledger alone would get rid of the race conditions caused by the read committed isolation level.
But what you described is manually implementing locking, which requires additional schema and application logic.
Instead of leaving an AccountBalance row locked for the entirety of the Withdrawal process, you have a condition on the insert and a retry mechanism if that insert fails.
You still have to implement concurrency logic, it’s just less likely to have the database isolation be your bottleneck.
You can.
ATMs around the country aren't doing account-level locking. If you overdraw, you overdraw.
If you store the ledger operations (reliably! no half-writing them and then throwing an exception!), then your system knows what happened.
Having a ledger which you're confident about is more important than trying to use exceptions to prevent 'bad' ledger messages being written.
I don’t think you want to let a $500k withdrawal go through optimistically.
Non-determinism is the name of all testing. Anything that we can do to improve it is extremely important.
I’m strongly in the TDD camp too, btw. So I don’t say this flippantly. I appreciate this article bringing further awareness to this.
Also, I cannot recommend partitioning (and event sourcing) enough to eliminate and simplify these problems.
Article on partitioning: https://github.com/aaronjensen/software-development/blob/mas...