Possible race condition with bid placement

[adelevie]

It looks like we might have a race condition on our hands.

Problem

In order to successfully place a Bid, we check that it is valid. Validity means, among other things, that the bid amount is less than the current winning bid. In pseudocode:

def current_bid_amount
  @auction.bids.last.amount
end

# BREAKPOINT

if @bid.amount >= current_bid amount
   raise UnauthorizedError, 'Bid amount must be less than the current bid.'
end

@bid.save

Suppose that after execution passes # BREAKPOINT, a user in another session successfully places a bid such that the value already returned in this session by #current_bid_amount is stale. This feels like a race condition to me.

Proposed Solution(s)

Optimistic Locking + a new field on Auction + Transactions

Read the docs on optimistic locking in ActiveRecord:

Optimistic locking allows multiple users to access the same record for edits, and assumes a minimum of conflicts with the data. It does this by checking whether another process has made changes to a record since it was opened, an ActiveRecord::StaleObjectError exception is thrown if that has occurred and the update is ignored.

Currently Auction.has_many :bids, but with locking, we should add a field (or fields) to Auction that represent the current winning bid. These fields could be a current_winning_user_id, an current_winning_bid_amount, and a current_winning_bid_updated_at timestamp. In pseudocode again:

# Assumes optimistic locking is enabled for Auction

def current_bid_amount
  @auction.current_winning_bid_amount
end

if @bid.amount >= current_bid amount
   raise UnauthorizedError, 'Bid amount must be less than the current bid.'
end

@auction.current_winning_bid_amount = @bid.amount
@auction.current_winning_user_id = @bid.bidder_id
@auction.current_winning_bid_updated_at = DateTime.now

if @auction.save
  @bid.save
end

Notice that we have two instances whose creation depends on the other. If @auction cannot save successfully, then we cannot create @bid. If @bid cannot be successfully created, the @auction update should be rolled back. To ensure consistency, we could use ActiveRecord::Base::transaction:

# Assumes optimistic locking is enabled for Auction

def current_bid_amount
  @auction.current_winning_bid_amount
end

if @bid.amount >= current_bid amount
   raise UnauthorizedError, 'Bid amount must be less than the current bid.'
end

ActiveRecord::Base.transaction do
  @auction.current_winning_bid_amount = @bid.amount
  @auction.current_winning_user_id = @bid.bidder_id
  @auction.current_winning_bid_updated_at = DateTime.now

  @auction.save
  @bid.save
end

With this transaction, if @auction.save raises an ActiveRecord::StaleObjectError (due to optimistic locking--e.g. @auction.current_winning_* was updated in another session), the entire transaction will fail/be rolled back.

@harrisj alluded to some problems with such a lock, mainly that if a process got slow, it would temporarily halt bidding for everyone. Let's discuss!

cc @baccigalupi

and the rest of our Rails pals @afeld, @jessieay, @ccostino, @yozlet, and @monfresh (who am I missing?).

[harrisj]

So, reading up on optimistic locking, I noticed this salient point in the documentation

This locking mechanism will function inside a single Ruby process. To make it work across all web requests, the recommended approach is to add lock_version as a hidden field to your form.

This potentially gives someone the ability to tamper with the auction by setting lock version to +100 more although I suppose they would still hit the UnauthorizedError if they tried to push the price back up.

My other question I have right now is how to test this in our integration tests. It seems like we would want some sort of multithreaded approach where the first thread blocks at the breakpoint, the second thread is run and then the first thread is allowed to resume and then should hopefully trigger an exception. To do this, we would probably have to add a special no-op method at the breakpoint that could be mocked on one instance, but I am still looking into that. This example of multithreaded requests looks like how we could do it though.

[adelevie]

Re using lock_version, shouldn't the authenticity token/csrf protection ensure that the hidden field is not tampered with?

Re testing, the multi-threaded approach seems correct. Not sure how to do it though ...

[jamesarosen]

shouldn't the authenticity token/csrf protection ensure that the hidden field is not tampered with?

No. The Authenticity Token's job is to ensure that only forms generated on your domain are accepted. That is, no other domain can generate a form and trick the user into submitting it to your domain.

If you want to guarantee that a value you sent to the user is returned unedited, you must sign it. You could do something like

<input type='hidden' name='auction[lock_version]' value='<%= @auction.lock_version %>' />
<input type='hidden' name='auction[lock_version_hash]' value='<%= @auction.lock_version_hash %>' />

where

def lock_version_hash
  some_crypto_hash_of self.lock_version
end

In this case, the thing that guarantees that the user sent back the same value is the security of whatever key (and algorithm, but let's assume you use whatever NIST currently recommends) you use to sign.

[stvnrlly]

If I understand this correctly, optimistic locking would mean that a bid would be rejected even if it is the lowest? That might be confusing to a bidder, and cause them to submit an even-lower bid unnecessarily.

[allalala]

!!! @stvnrlly in the house!

[adelevie]

oh hey @stvnrlly.

a bid would be rejected even if it is the lowest?

I don't think so. It would mean that a call to #save an object would fail if the object had been updated elsewhere. So to a user, it might appear to be the lowest bid, but in reality it is not. The error prompt would tell them that.

[adelevie]

That's very helpful, @jamesarosen. I wonder if there are any Rails libraries for ensuring hidden values cannot be tampered.

[ajb]

Hey @adelevie,

Saw the tweet and wanted to chime in quickly. I had some recent experience with this -- take a look at derrickreimer/sequenced#16 for a good example of a possible solution as well as some good ideas for setting up a test case.

Given the potential interaction that @stvnrlly mentions, it might be a better idea to use pessimistic locking here. From what I understand, I would also be averse to adding columns to the Auction table, since that seems like you're basically asking for data to get out-of-sync. While you could always acquire a row lock on the auction record, this might be overkill... especially since I'm assuming that the majority of your requests involve a read to the auctions table.

I'm having success using https://github.com/mceachen/with_advisory_lock for something like this, although you could also use Redis to acquire a mutex.

[ajb]

Actually, shit, I should correct myself here:

While you could always acquire a row lock on the auction record, this might be overkill... especially since I'm assuming that the majority of your requests involve a read to the auctions table.

Since:

Row-level locks do not affect data querying; they block only writers and lockers to the same row.

(http://www.postgresql.org/docs/9.4/static/explicit-locking.html)

So yeah, acquiring a row-level lock on the related auctions record might be an alright solution, but I still prefer the explicitness of an advisory lock.

[monfresh]

I haven't read everything in detail, but it seems to me that this can be solved by a database constraint, no? Rather than specifying the validation at the app level only, set it at the DB level, then let the app handle the error appropriately. If the validation is set at the DB level, the DB will never allow a bid that is greater than the current winning bid.

[karansag]

Hey @adelevie, just saw the tweet, too. I haven't looked at everything in detail either, but I agree with @monfresh that it seems like a data issue. You could set a database constraint, issue a transactional statement with an "IF" clause, or, my first thought, increase the transaction isolation level. Serializable or repeatable read might be what you want: http://www.postgresql.org/docs/current/static/transaction-iso.html .

UPDATE, DELETE, SELECT FOR UPDATE, and SELECT FOR SHARE commands behave the same as SELECT in terms of searching for target rows: they will only find target rows that were committed as of the transaction start time. However, such a target row might have already been updated (or deleted or locked) by another concurrent transaction by the time it is found. In this case, the repeatable read transaction will wait for the first updating transaction to commit or roll back (if it is still in progress). If the first updater rolls back, then its effects are negated and the repeatable read transaction can proceed with updating the originally found row. But if the first updater commits (and actually updated or deleted the row, not just locked it) then the repeatable read transaction will be rolled back with the message

[adelevie]

I am elated with the public response. It seems that a db constraint would
be the most reliable solution. I'll look into it.

It also seems that the techniques outlined here (
http://blog.bruzilla.com/2012/04/10/using-multiple-capybara-sessions-in-rspec-request.html)
will allow us to (re)produce the error and build a fix against it.

On Tuesday, December 15, 2015, Karan Sagar notifications@github.com wrote:

Hey @adelevie https://github.com/adelevie, just saw the tweet, too. I
haven't looked at everything in detail either, but I agree with @monfresh
https://github.com/monfresh that it seems like a data issue. You could
set a database constraint, issue a transactional statement with an "IF"
clause, or, my first thought, increase the transaction isolation level.
Serializable or repeatable read might be what you want:
http://www.postgresql.org/docs/current/static/transaction-iso.html .

UPDATE, DELETE, SELECT FOR UPDATE, and SELECT FOR SHARE commands behave
the same as SELECT in terms of searching for target rows: they will only
find target rows that were committed as of the transaction start time.
However, such a target row might have already been updated (or deleted or
locked) by another concurrent transaction by the time it is found. In this
case, the repeatable read transaction will wait for the first updating
transaction to commit or roll back (if it is still in progress). If the
first updater rolls back, then its effects are negated and the repeatable
read transaction can proceed with updating the originally found row. But if
the first updater commits (and actually updated or deleted the row, not
just locked it) then the repeatable read transaction will be rolled back
with the message

—
Reply to this email directly or view it on GitHub
#123 (comment).

[monfresh]

Looking at the current DB schema, I don't see any unique indexes. The rule of thumb is that anything that needs to be unique should be enforced at the DB level. So, if you want to make sure that no 2 users have the same email address or duns_number, then you need to add a uniqueness index. Rails provides a DSL for doing that in migrations, such as:

class AddMissingIndexes < ActiveRecord::Migration
  def change
    add_index :users, :email, unique: true
    add_index :users, :duns_number, unique: true
  end
end

[jessieay]

I agree w @monfresh re: DB constraint would solve this problem.

Wrapping updates in AR transactions is a great idea when you want to make sure that no records are saved if all are not valid. Just found this helpful post on the topic: http://vaidehijoshi.github.io/blog/2015/08/18/safer-sql-using-activerecord-transactions/ -- it seems like in this case, though, AR transactions won't be needed.

It also seems like the problem you are describing is an edge case that might not occur very frequently -- have you seen instances where two people were creating bids at the exact same millisecond? My impression was that this app, because it caters to a small user set, would have few concurrent users, making bid creation at the same time highly unlikely.

You know this app much better than I do, so I defer to you on whether this is something to be concerned about.

[harrisj]

I just want to note for the sake of pedantic completeness that @stvnrlly is indeed correct. If user A came in with a lower bid, but user B saved first, user A's bid would be rejected under optimistic locking.

It does indeed sound like DB constraints are a preferred solution if we are good with requiring that Postgresql is used through. I just would want to make sure that you have enough information when the constraint is violated so you can indicate to the user the difference between someone has entered a lower bid than you vs. a database error has occurred

[adelevie]

Requiring Postgresql is fine in my book.

On Tuesday, December 15, 2015, Jacob Harris notifications@github.com
wrote:

I just want to note for the sake of pedantic completeness that @stvnrlly
https://github.com/stvnrlly is indeed correct. If user A came in with a
lower bid, but user B saved first, user A's bid would be rejected under
optimistic locking.

It does indeed sound like DB constraints are a preferred solution if we
are good with requiring that Postgresql is used through. I just would want
to make sure that you have enough information when the constraint is
violated so you can indicate to the user the difference between someone
has entered a lower bid than you vs. a database error has occurred

—
Reply to this email directly or view it on GitHub
#123 (comment).

[harrisj]

Are we okay with closing this? I think we just don't worry about it too much, especially since it's not an issue with sealed-bid auctions...

[mtorres253]

Should we close this @adelevie @harrisj @jessieay

[jessieay]

yes, from my perspective we can close because we not longer have the separate page for confirming a bid.