Avoiding Double Booking / Double Spending

user_1782560 0
Viewed 454

I'm running a high throughput application in which many auction-like processes happen every second and budgets are spent based on auction-winning bids.

However, there's a slight latency between the moment a bid is placed and the time when the auction is decided, so what started happening is this:

  • two similar auctions are won by the same highest bidder in the same second, but the total bids for the 2 auctions exceed the budget of the user, so by the time the second auction tries to get the bid, the first one already got it and the user now ends up with a negative balance.

I do understand this is a complicated problem, but I would like to know your opinions.

Some details about my application might offer insights into what the right tradeoffs might be:

  • the bids are, generally, much smaller than the user budget, so not allowing the users to spend the last few cents of their $5 budget might not be a big issue, but there's no limit to the bids, so this might not, in fact, help decreasing risk (might work for the low-bid transactions, but as soon as the user places, say, a $3 bid, the budget can still go from $5 to -$7 in a second, by winning just 4 auctions with this higher than normal bid).

  • not allowing bids higher than a certain budget ratio can also be an acceptable solution, but this might affect the user experience quite a lot and the bid/budget ratio will be rather arbitrary. The lower the ratio, the safer the budget and the worse user experience, but there's still no guarantee the budget won't be exceeded.

  • booking the bid for a certain time can also be an option, but with 100k users bidding multiple times per second, the solution for booking all the bids and releasing the funds can become quite complex

  • simply not paying for the second transaction can also be a (rather crappy and unfair) solution, but it might limit the incentive to abuse this bug.

I realize these details are all direct attempts to solve the problem, but none of them is good enough and I'm curious what your opinion is and if there are any better solution to the Double Spending problem. Unlike the solution found for the Bitcoin protocol, in my case the exchange of "goods" is done in real time and I cannot revert it once there are no more funds available (the goods, in my case, are website visits, so they're instantaneous, can't be stored until the transaction is settled and can't be delayed).

bitcoin redis transactions mysql php
2 Answers

This might work: change the rule for winning an auction.

Now, I guess, a user wins an auction if she's the highest bidder at the conclusion of the auction. You can change the rule so the user must BOTH be the high bidder AND have sufficient budget to cover the bid. If both criteria aren't met, the next highest bidder with enough budget wins.

This is easy to explain to users. "to win, you need enough in your budget. If you're losing auctions you can increase your budget."

Implementation wise, you can use a database transaction to handle the "win" operation. Inside a single database transaction, debit the winning buyer's budget and credit the seller's account.

You can use SQL sequences like this:

START TRANSACTION;
SELECT budget 
  FROM user 
 WHERE id = nnnn 
   AND budget >= bid
   FOR UPDATE;
/* if you got a result do this */
UPDATE user SET budget=budget-bid 
 WHERE id= nnnn;
UPDATE seller SET balance=balance+bid 
 WHERE ID = sssss;
UPDATE auction
   SET winner=nnnn, winning_bid=bid,
       closetime=NOW()
 WHERE auction = aaaa;
COMMIT;
/* if you got no result from the SELECT do this */
ROLLBACK;
user_2056080

You can use distributed locks to solve the double-spending /double booking issue. You need to acquire at least three locks that would update

  • User's budget i.e. bidder's account balance
  • Seller's account balance
  • Auction

You can also create a bid ledger to verify the user's spending, seller account balance, and user's wallet balance. You can run a cron job hourly or every 10 minutes to verify any error and notify support/dev to check for potential errors.

Your logic could be like this

Procedure BidProcessor
   input: user, bid, seller
   // this should get locks for auction, user wallet balance and seller balance
   success = acquireLocks( bid.auction_id, user.id, seller.id )
   if success then
      hasSufficientFund = user.hasSufficientFund( bid.amount )
      if hasSufficientFund then
          ExecuteBid( user, bid, seller )
          releaseLocks( bid.auction_id, user.id, seller.id )
      else 
          releaseLocks( bid.auction_id, user.id, seller.id )
      endif
   else
      releaseLocks( bid.auction_id, user.id, seller.id )  
   endif

Each executor can use their identity id as a lock value to avoid releasing someone else lock.

Procedure ExecuteBid
    input: user, bid, seller
    Description: Run a SQL transaction to update all related entities 
      START TRANSACTION;
        UPDATE user SET budget=budget-bidAmount WHERE id= user.id;
        UPDATE seller SET balance=balance+bidAmount WHERE ID = seller.id;
        UPDATE auction SET winner=bid.id, closed_at=NOW() WHERE id = bid.auction_id;
        UPDATE bid SET processed_at = NOW(), status='WON' WHERE id = bid.id;
      COMMIT;
      if commit fails then do a rollback  
        ROLLBACK;
user_42551070
Related