A few flavors of concurrent counter updates

I’ll discuss here a problem that I have seen at least twice in system design interviews, and at least once in a real-life production service, all related to concurrent updates of a single counter (with some slightly different flavors on which I will later elaborate). Let’s define these three problems and label them as such:

• Problem #1: we want to send a gift card by email to the first 10000 users who visit our website’s front page.
• Problem #2: we run a cashback service, where merchants define a maximum cashback budget, and users purchasing something from that merchant will get some money back, until the merchant’s budget is exhausted.
• Problem #3: we want to send a gift card to the user who will run the one hundred billion-th search query on google.com.

These are conceptually simple problems, but they will still allow us to cover quite a few interesting concepts that, based on my experience, are not all that widely known among software engineers.

I will mostly use pseudo-code for this article to focus on the important concepts and leave aside implementation details. In case you’d like to experiment with the methods mentioned in this blog post, you can refer to this demo project which implements the different approaches.

The naive approach

Let’s first look at problem #1, which is the simplest flavor. Let us assume our application uses a relational database supporting SQL¹, and that we keep track of the current “budgets” of remaining gift cards we can send in a table with the following schema:

1CREATE TABLE budgets (
2    id INT NOT NULL,
3    budget INT NOT NULL,
4    PRIMARY KEY (id)
5);

For those unfamiliar with concurrency issues, a first approach for problem #1 might be to check the current value of the budget, and then decrement it if it is still positive:

1SELECT budget FROM budgets WHERE id = 1;
2
3-- In case budget <=0, do nothing
4-- In case budget > 0, decrement it and send a gift card to user
5
6UPDATE budgets SET budget = budget - 1 WHERE id = 1;

This works just fine if users are accessing your website’s frontpage sequentially. But that’s probably not the case; and if you try implementing this approach with even a few concurrent users, you will likely end up with negative budget values. This is a fairly standard example of concurrency issue: when the current budget gets close to 0, several users may run the SELECT statement above, see a positive budget, and then decrement it, without being aware that other clients are doing the same thing concurrently.

If N users can browse your website simultaneously, you can hence at worst end up with a budget of 1-N.

Let’s make a brief pause here, and wonder how bad that would actually be? As we will discuss later, this problem has a simple solution that fixes this issue, so we shouldn’t settle for this half-working implementation. But one can imagine slight variations of this problem (e.g. relying on a database –in the broad sense– that does not support atomic read-write operations, such as memcached or Cassandra) where the solution we will cover later on does not apply. In that case, going with the above naive approach might be the only viable solution. But this may not be as bad as it looks in a real-life situation:

• even though it is typically hard to control, the number of concurrent users on your company’s website might not be that high
• you can mitigate the issue by using some buffer and setting in database a budget slightly lower than your actual budget
• you can also accept the risk of sending a few more gift cards than expected, or put in place an offline process to cancel the extra gift cards that might have been sent to your site’s visitors

Even though these options can sound lame from an engineering perspective, they can definitely be viable in an actual real-life situation. If, as an engineer, you need to implement a solution for problem #1 and your current system does not provide a way to implement the solution we’ll discuss below, you should definitely at least consider the naive solution and compare the drawback of potentially going over-budget with the cost of, e.g, bringing in a new database. I remember bringing that up during a system design interview, and I don’t think the interviewer was really happy about it, as I assume he wanted to focus on the technical challenge. So I wouldn’t recommend insisting on it during an interview; but in a real-life situation, please keep an open mind and consider all options.

Locking

The most common answer to this problem is to update the above statements to lock the budget row before updating it, using a SELECT ... FOR UPDATE statement, and including the UPDATE statement in the same transaction:

1BEGIN;
2SELECT budget FROM budgets WHERE id = 1 FOR UPDATE;
3
4-- In case budget <=0, do nothing
5-- In case budget > 0, decrement it and send a gift card to user
6
7UPDATE budgets SET budget = budget - 1 WHERE id = 1;
8COMMIT;

The SELECT ... FOR UPDATE statement above effectively makes the client lock the row, and release the lock after they are done updating the budget. This prevents the race condition explained in the naive approach, and ensures sequential data access, which is conceptually simpler to reason about: this is the reason why it is often considered whenever one has concerns about concurrent data access.

But it comes with a major drawback: this effectively makes all the clients wait in line for their turn to update the budget. When the number of concurrent users grows, this will significantly reduce the overall throughput and increase latency on client-side. As an example, using the demo project, and starting with a budget of 10000 and running 100 concurrent clients:

• the naive approach consumes the budget in roughly 2.4 seconds
• the locking approach takes 11.9 seconds

And sticking with this approach, there is little you can do to increase the throughput. As clients are waiting in line and processed sequentially, the throughput will always be the same regardless of the number of concurrent clients: the number of counter updates per second will be the inverse of the time taken by a client to lock, decrement and release the lock. We can use the demo project to illustrate that: contrary to the naive approach, increasing the number of concurrent users has close to no impact on the throughput.

In a real-life scenario, and assuming the client releases the lock as soon as possible (and sends the gift card after releasing the lock), I expect the time taken by a client to lock, update and release the lock will generally be dominated by the latency between the client and the database; and there is typically not much you can do to reduce that after going with low-hanging fruit optimizations (such as moving the clients close to the database).

“Lock-free” approach

For this particular problem though, we can do better. The main bottleneck of the locking approach is the round-trip time between the client and the database: the client must acquire the lock, read the budget, then decide and update — all while holding the lock. But as the logic implemented on client-side is fairly simple, we can actually combine these two concerns in a single atomic statement, and observe the number of updated rows to decide on whether or not we should send a gift card:

1UPDATE budgets SET budget = budget-1 WHERE id = 1 AND budget > 0;
2
3-- In case the number of updated rows is 0, do nothing: the budget has already been consumed
4-- In case the number of updated rows is 1, send a gift card to user

Using this surprisingly simple “lock-free” approach allows us, in a single atomic operation, to conditionally decrement the counter. It fixes the concurrency issue of the naive approach but still avoids the pitfall of the client-side locking mentioned above.

In that approach, the throughput should scale linearly with the number of concurrent clients until the database’s row-update throughput becomes the bottleneck. At that point, you can resort to vertical scaling of the database (CPU and disk IOPS) to keep increasing the throughput. We can see that linear scalability by running the demo project on relatively low numbers of users (until the point where the database becomes the bottleneck):

Wait, no transaction?!

The lock-free approach mentioned above is, as far as I can see, the best solution to tackle Problem #1. But readers who are used to dealing with money may frown upon the lack of a transaction.

So let’s now look at problem #2:

We run a cashback service, where merchants define a maximum cashback budget, and users purchasing something from that merchant will get some money back, until the merchant’s budget is exhausted.

The main difference with the first problem is that we now have to manipulate account balances, with the constraint that the overall balance of all accounts remains constant when money is transferred from the merchant’s account to the user’s account. Let’s assume here that the accounts are stored in a table with the following schema:

1CREATE TABLE accounts (
2    id INT NOT NULL,
3    balance INT NOT NULL,
4    PRIMARY KEY (id)
5);

This table looks similar to the budget one, but with some important differences:

• both merchants and end-users have accounts
• the overall balance stored in the table must remain constant when money is transferred from the merchant’s account to the user’s accounts

Problem #1’s solution relying on locking can be adapted in a straightforward way to solve problem #2: we just need to include both balance updates in the same transaction:

1BEGIN;
2SELECT balance FROM accounts WHERE id = 0 FOR UPDATE; -- assuming merchant's account id is 0
3
4-- In case balance <=0, do nothing
5-- In case balance > 0, we transfer money to the user
6
7UPDATE accounts SET balance = balance+1 WHERE id = ?; -- ? being the end-user's account id
8UPDATE accounts SET balance = balance-1 WHERE id = 0;
9COMMIT;

But this approach suffers from the same problem mentioned above: clients will have to wait in line to sequentially update the account’s balance.

On the other hand, the “lock-free” approach of problem #1 cannot be easily adapted to solve problem #2. If we try to simply increment the user account’s balance after conditionally decrementing the merchant’s one:

1UPDATE accounts SET balance = balance-1 WHERE id = 0 AND balance > 0;
2
3-- if no rows are updated, do nothing
4-- if one row is updated, increment the user account's balance
5-- (but ... what if the application crashes here?)
6UPDATE accounts SET balance = balance+1 WHERE id = ?;

Then we risk breaking the constant balance constraint if, for instance, our application crashes after decrementing the merchant account’s balance but before increasing the user’s.

Are we then stuck with the essentially sequential locking approach for problem #2? Not really! We need to understand that there are two separate constraints:

• we must ensure that the amount of money paid by the merchant does not exceed its budget
• and we must ensure the overall balance in the accounts remains constant

We can hence split the two concerns across two tables:

• in the budgets table (introduced for problem #1), we will keep track of the budget potentially used for the merchant, using the exact same approach as problem #1
• in the accounts table, we will keep track of the actual account balances, which will always be updated in pairs in transactions.

The code becomes:

1UPDATE budgets SET budget = budget-1 WHERE id = 1 AND budget > 0;
2
3-- if no rows are updated, do nothing
4-- if one row is updated, transfer money from merchant account to user account
5BEGIN;
6UPDATE accounts SET balance = balance+1 WHERE id = ?; -- ? being the end-user's account id
7UPDATE accounts SET balance = balance-1 WHERE id = 0; -- 0 being the merchant's account id
8COMMIT;

In case the application crashes after decrementing the budget and before committing the transaction, we may not end up using the full budget allocated by the merchant to its cashback campaign; but that’s very likely something that should be acceptable from a business perspective.

And as we can see using the select_for_update_cashback and lock_free_cashback_transaction variants in the demo project, this approach’s throughput will scale linearly with the number of concurrent users², contrary to the locking approach whose throughput will plateau:

Even without knowing in detail how InnoDB’s multi-version concurrency control works, we can conceptually understand that the second approach does not require locking: all transactions can decrement the merchant account’s balance without worrying about updates performed by concurrent transactions, which should make these transactions easier to handle concurrently.

Another advantage of this approach is that the current budget value does not have to live in the same database as the account balances. Depending on the service’s stack, it may be a better idea to move this counter to a different database (in the broad sense) that might be faster than the RDBMS used to store account balances.

When we cannot afford a central state

Finally, let’s now consider problem #3:

We want to send a gift card to the user who will run the one hundred billion-th search query on google.com.

This problem looks very similar to problem #1, with one major difference: in problem #1, we implicitly assumed our company’s website is of a slightly different scale than google.com. As with most companies’ websites, we assumed the website’s application server and its database run in a single region, and that we can use the application’s database as a single central state to keep track of the visitor count.

But even without knowing the internals of how Google search is deployed, we know that is not how google.com works. Google search typically generates a response within less than ~200 milliseconds³, which is faster than an ICMP ping between, let’s say, Paris and Auckland. As google.com operates globally, there is simply no way it could respond that quickly to users all around the world while reading and/or updating a central state, wherever it would be. Instead, we can assume that google.com is actually served by datacenters deployed all across the globe, each of them being able to serve search queries independently. These regional deployments still interact with one another in the background, but not while processing an end-user request.

So contrary to problem #1, there is, as far as I can tell, no exact solution to problem #3 that wouldn’t break the core functionality of google.com. So rather than trying to achieve exactness at the cost of responsiveness, we should try to find an approximate solution. The best approach that comes to my mind⁴ is to:

• keep a central counter in one location (let’s say in Paris)
• Every region sends a request to Paris to reserve a range of counter values, the range’s length being the number of queries this region expects to receive in the next second
• Every region keeps an internal counter in a local database, and increases it whenever it handles a search query, using the same lock-free approach as mentioned in problem #1
• When the region has exhausted the range it previously reserved, or is close to exhausting it, it sends a new query to Paris to reserve a new range. This is done in a background process to avoid impacting search response time.

Using this approach, one region will eventually fetch a range containing the one hundred billion-th value of the search counter, and the gift card will be sent to one user of that region. It may not be the actual one hundred billion-th visitor, but it should be close enough (within one second of the actual hundred-billion-th query), and one can adjust how precise this will be by adjusting how often regions pull a new range from the central location.