4

Let's say we have an app where the users gain points and can exchange them for rewards. The exchange request, in pseudo-code, could look like this:

function exchangePointsForReward(userId, rewardId){
    user = getUser(userId)
    reward = getReward(rewardId)
    if (user.points >= reward.requiredPoints){
        giveRewardToUser(userId, rewardId)
        reduceUserPoints(userId, reward.requiredPoints)
    }
}

But if we have a malicious user what stops them from crafting a request in their favorite programming language and sending it 20 times at the same time? Before the first request reaches reduceUserPoints() ten other might've already got as far as addNewReward(). Sure, the user's points at the end of the day might go deep into negative, but what stops the user from quickly grabbing the rewards and using them up? How can I ensure that only one operation can be executed for a user at the same time?

One solution I can think of is the operation tries to acquire a lock at the beginning of the operation and only a single lockable operation can run for a user at any moment:

function aquireLock(userId){
    lockId = getRandomLockId()
    database.query("UPDATE user SET lock={lockId} WHERE user={userId} AND lock IS NULL");
    return database.query("SELECT lock WHERE user = {userId}").first === lockId;
}

function exchangePointsForReward(userId, rewardId){
    if (!aquireLock(userId)){
        throw new Error("Failed to acquire lock");
    }
    user = getUser(userId)
    reward = getReward(rewardId)
    if (user.points >= reward.requiredPoints){
        giveRewardToUser(userId, rewardId)
        reduceUserPoints(userId, reward.requiredPoints)
    }
    releaseLock(userId);
}

But is there any better strategy here? The question is database-agnostic.

2

I think your locking strategy will work, although I'd suggest looking at a distributed lock manager (e.g., Apache's Helix project) instead of going to the database just to get a lock. This would ensure that users didn't get locked out if your service gets restarted mid-request.

Another possibility would be to bucket the user IDs to queue them to specific request handlers; this would serialize the parallel requests, but is probably more complicated and could lead to processing bottlenecks (at least until you got your configuration tuned).

| improve this answer | |
  • Hm, locking out could probably be solved by adding a lockTime column/field to the database and allow aquiring the lock if it's been more than, say, 15 seconds. – Maurycy Jan 4 '16 at 14:30
  • Sure, or you could use optimistic locking and add a lastUpdated field to the record and reject any updates that have an earlier update timestamp. The request handler could be configured to either return a failure status for rejected updates or retry them. – TMN Jan 4 '16 at 14:35
1

You can make reduceUserPoints check if the result would become negative and fail if so.

function exchangePointsForReward(userId, rewardId){
    user = getUser(userId)
    reward = getReward(rewardId)
    try{
        reduceUserPoints(userId, reward.requiredPoints) //throws if result would become negative
        giveRewardToUser(userId, rewardId)
    }catch(){
        //show error message to user
    }
}

Key here is that the check gets rolled into the reduceUserPoints.

Another option is to use transactions that will give you the proper isolation and locking automatically.

| improve this answer | |
  • I suppose I could make the query be like UPDATE user SET points-=15 WHERE points > 15 but this only solves the specific case - what if the requirement to get the reward was "pay 15 points and give up 2 tokens from your inventory" or something even more complex? – Maurycy Jan 4 '16 at 14:27
  • And would transactions really help here? If the user makes 5 requests and all 5 start before the first transaction ends I still won't be able to detect the problem, unless I am missing something. – Maurycy Jan 4 '16 at 14:29
0

You could use an optimistic approach. Most databases use some sort of row versioning mechanism. For example, in SQL Server...

https://msdn.microsoft.com/en-us/library/ms182776.aspx

So, every request gets the row version sent back to them if they wish to update the data. The update then uses that row version as part of the update. If the row version don't match, you know that someone else has updated the record previously and you can reject it (not perform the update). Just note, that the row version doesn't make a good key candidate so some other data point should be used for the search and them compare the row version after the data is returned. So, if there are multiple reads, only 1 subsequent update wins.

This can all be done is a simple stored procedure that queries and updates and you can use database transactions to manage the 'lock' since the row version is updated atomically.

Pessimistic locking will also work, but your taking out a lock for every transaction, which is probably overkill for the the normal use case.

| improve this answer | |
0

I'd require that to run the next operation the user must pass a token returned by a previous operation.

Imagine that you have a table of issued tokens (opaque random numbers). Once a user successfully runs a request, a new token is inserted into the table, and returned to the user.

You can serialize access to marking a token 'redeemed', so that it is guaranteed that a token can only be redeemed if it is still new; then the points are gained by the user. An attempt to redeem an already redeemed token, or an unknown token, results in an error, and the points are not counted.

Even if a user runs several requests in parallel, each request can only carry the same unredeemed token, and only one of the requests will succeed, since redeeming is serialized.

Periodically old redeemed tokens and excessively old unredeemed tokens are removed from the table.

If a user passes an incorrect token, points are not gained, but a new valid token is returned to the user in the reply. This way new clients, or clients that lost sync, can reconnect to the sequence.

The problem, of course, is in the serialized update. But if you only lock a record corresponding to a token, and not the whole table, many requests can be served in parallel.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.