How our users exploited concurrency and how we fixed it

http://eviltrout.com/2013/01/10/exploiting-concurrency.html

by EvilTrout • 14 years ago

60 39 14 years ago

mcherm• 14 years ago

I like collecting tales like this one. They are useful for scaring new programmers who think they understand how to safely do multi-thread programming.

wulczer• 14 years ago

I believe this won't work on PostgreSQL, which will always say one row has been updated, even if the new value is the same as the old value.

There are numerous ways around that, from less fancy to really fancy.

  1. use SELECT FOR UPDATE, which will lock the row (I'd say that's the normal way)

  session1> BEGIN;
  session1> SELECT * FROM goals WHERE player_id = ? FOR UPDATE
  session2> BEGIN;
  session2> SELECT * FROM goals WHERE player_id = ? FOR UPDATE
  # session2 is now hanging
  session1> UPDATE goals SET completed = true WHERE goal_id = ?
  session1> UPDATE players SET points = points + 1 WHERE player_id = ?
  session1> COMMIT;
  # session2 now proceeds, sees that the goal has been completed, forfeits awarding the reward

  2. use suppress_reduntant_updates_trigger (fun)

  session> CREATE TRIGGER suppress_goal_t BEFORE UPDATE ON goals FOR EACH ROW EXECUTE PROCEDURE suppress_redundant_updates_trigger();
  session> UPDATE goals SET completed = true WHERE goal_id = ?
  UPDATE 1
  session> UPDATE goals SET completed = true WHERE goal_id = ?
  UPDATE 0
  # now you can use the approach mentioned in the article

  3. use true serialisability
  session1> BEGIN;
  session1> SET transaction_isolation TO serializable;
  session1> SELECT * FROM goals WHERE player_id = ?
  session2> BEGIN;
  session2> SET transaction_isolation TO serializable;
  session2> SELECT * FROM goals WHERE player_id = ?
  session1> UPDATE goals SET completed = true WHERE goal_id = ?
  session1> UPDATE players SET points = points + 1 WHERE player_id = ?
  session1> COMMIT;
  session2> UPDATE goals SET completed = true WHERE goal_id = ?
  ERROR:  could not serialize access due to concurrent update
  # session2 now has to rollback the transaction

There's a few more, but I ran out of steam typing ;) Yay, Postgres!

EvilTrout7• 14 years ago

facepalm

I forgot a very important part of the query:

row_count = Goal.update_all "completed = true", ["player_id = ? AND completed = false", player.id]

If you update where completed = false, the rowcount will only be 1 when the update works.

(I've updated the blog post.)

amikazmi• 14 years ago

No need for a workaround, you have Optimistic Locking (via lock_version field)

It raises an exception in case you try to update stale data.

http://api.rubyonrails.org/classes/ActiveRecord/Locking/Opti...

EvilTrout7• 14 years ago

Right, but that involves changing your database and adding hidden form fields to your app in order for it to work on a multi process environment (like every production server should be.)

My solution is basically the same amount of lines, requires no such changes.

gnaritas• 14 years ago

Yes, but optimistic locking with a version is the general and known solution to this problem in all cases and is built into the framework already. Your solution works in just one case, not the general case.

amichal• 14 years ago

Or no table changes with http://api.rubyonrails.org/classes/ActiveRecord/Locking/Pess...

but in this specific case `affected_rows` works better as long as you know its reliable.

aufreak3• 14 years ago

Umm ... and the 'Player.transaction' doesnt seem to be one then if it allows two transactions to overlap?

EvilTrout7• 14 years ago

There's a difference between a transaction that locks for writes and one that locks for reads. By default the reading is not locked in this (common) case.

Strilanc• 14 years ago

That's a terrible default! Ignoring read-write races is a surefire way to... well, create bugs like the one in the post.

Lozzer• 14 years ago

For a lot of RDBMS, transaction semantics can be later with different transaction isolation levels. There levels like repeatable read which work in this way, but the default level is usually weaker.

emeraldd2• 14 years ago

If I remember correctly, one of the ways around this is to do a no-op update before querying. So you'd update a field in the goal table to it's original value, which would cause the database to lock the table for the duration of the transaction.

Also, if I remember correctly, this is one of the things that can be solved with an MVCC aware engine.

http://en.wikipedia.org/wiki/Multiversion_concurrency_contro...

With MVCC a transaction should be aborted if another thread modifies the underlying data.

jamieb• 14 years ago

Best to discover the joys of concurrency while writing a game than a bank. =) Welcome! Our playground is a lot of fun!

EGreg• 14 years ago

Basically, the correct way is to use transactions. Use a transactional database because it supports MVCC.

EvilTrout7• 14 years ago

In the example code I gave, by default in Rails with Postgres (which supports MVCC) you'll still get the error. So it's not as simple as using a transactional database: you either use a trick like this one, an row-based version column, or you need to change your isolation levels which has other performance issues.

delano• 14 years ago

You could wrap the transaction in a lock based on the player ID which you could do with Redis or Memcached with near-zero impact on performance.

A good reference: http://www.nateware.com/an-atomic-rant.html

rlpb• 14 years ago

Even better, rearrange your database to store immutable facts instead of mutable state.

In this example, you might have a goal_completion table to which you append a row when the player completes a goal, instead of changing an existing row. The table could have suitable unique constraints to make sure that each player can only complete a goal once.

This way, it is much harder for your data to accidentally be modified in a way that it becomes wrong.

This also gives you a way to store facts about the completion for free, such as a timestamp for each goal completion. And having data like timestamps is really useful for auditing, debugging and testing.

AdamTReineke• 14 years ago

I've heard you sometimes shouldn't actually delete data from a database and should use an "IsDeleted" flag instead, particularly with customer orders and such.

What are the proper circumstances to use immutable facts? Anytime you need an undo or audit features?

CaveTech• 14 years ago

The isDeleted flag is good because it gives the appearance that the data is gone, without removing the context of the data itself.

Immutable facts are great if you want to:

1) Avoid a large amount of updates/race conditions on your tables. Immutable facts, being immutable, can be done using purely inserts.

2) Want to keep a trail or context to the data you're storing. This has a benefit of keeping a log that you can later use to trace issues, behaviours or generate statistics. If you're keeping a state in a database column, without external logs you aren't able to check when or why that state changes. Immutable facts keep track of this for you, but require quite a bit more overhead.

voidlogic4• 14 years ago

"I was worried that I’d have to resort to semaphores or some kind of other exotic programming construct."

I'm not saying a semaphore would have been appropriate here but- For real? A semaphore is exotic? It is an one of the oldest original synchronization methods. Semaphore were developed by Dijkstra in 1965. The author's C-S program failed him.

EvilTrout7• 14 years ago

Everyone's got to start somewhere!

In the sentence before I explicitly said I was a newbie to this stuff at the time. Obviously it's not exotic to a more experienced developer :)

voidlogic4• 14 years ago

My point was that a semaphore is freshmen or sophomore level undergrad stuff, something I would expect every professional developer to understand. Here someone who considers themselves a developer, which I assume means a professional software developer, considers it an exotic construct. Things like this shakes my faith in the computer science educational system.

kaffeinecoma• 14 years ago

Use Optimistic Locking:

http://railscasts.com/episodes/59-optimistic-locking-revised...

vemv2• 14 years ago

Really not that much of a subtle bug I'm afraid, the pattern of "mutating the condition itself on success" is error-prone in single-threaded code too.

A good example being asynchronous javascript, where you'd do this to prevent issues like the exposed in the article:

    var some_mutable_condition = false;
    var requested = false;

    if (!some_mutable_condition && !requested){
        requested = true; // ensure one request is performed at most
        $.ajax(/*async code that'll set some_mutable_condition to true*/);
    }

mguterl• 14 years ago

Underscore.js has a function called once for this exact purpose.

vemv2• 14 years ago

Good to know, thank you.

jessaustin• 14 years ago

Another solution would be to have e.g. a "Completions" table indexed on user and on date. Then the RDBMS wouldn't allow duplicate goal completions for the same user and day. If you wanted to allow up to X completions/day, just add a new column to track that, and limit that column to the range [0, X). I often find that updating rows in response to transactions is a code smell. Each transaction should write one or more rows to one or more tables. Of course, if you have denormalized summary tables, they might have to update, but you only do that when you know you have to.

How our users exploited concurrency and how we fixed it

Related Stories