Once-only transactions

[Jeff Schnitzer]

I'd like to guarantee a transaction runs once, and once only. Let's
say I'm simulating a bank transfer of $5 from AccountA to AccountB.

The normal transaction is not idempotent:

Repeat until success {
* start txn
* debit $5 from AccountA
* credit $5 to AccountB
* commit txn
}

If this inadvertently runs multiple times, I will have very unhappy
customers. Maybe I should do this:

Create TxnID entity instance
Repeat until success {
* start txn
* load TxnID (if null, return success immediately)
* debit $5 from AccountA
* credit $5 to AccountB
* delete TxnID
* commit txn
}

With the pain of adding a third entity to my XG transaction (and a
cron that prunes really old, abandoned TxnIDs) it seems that I this
does the trick. Or am I missing something? Is this the best way to
accomplish once-only transactions? Is there an alternative approach?

Thanks in advance,
Jeff

[Robert Kluin]

Hey Jeff,
That is more-or-less the best I've come up with as well. My flow looks like:
1) produce a transaction marker entity with a deterministic key-name
from the involved "accounts",
2) Start transaction:
2.a) Load the involved entities (including the marker).
2.b) If I get a marker, abort.
2.c) Do the stuff that needs doing....
3) At some later (possibly much later) time, cleanup the markers.

In some cases, when I've got revision numbers on the entities, I
improve the process by cleaning the marker up after the transaction.
But if it is valid for an account to be updated multiple times,
provided some condition is met, I leave the marker. Note that nearly
all of my processing is task-based, so tasks could run multiple times,
or rerun with a delay, etc.... That is why I leave the markers for a
while.

Robert

> --
> You received this message because you are subscribed to the Google Groups "Google App Engine" group.
> To post to this group, send email to google-a...@googlegroups.com.
> To unsubscribe from this group, send email to google-appengi...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/google-appengine?hl=en.
>

[AndyD]

Would a task queue work here?  You could queue a task with a name that is unique to the operation (e.g. leveraging some payment ID, in the example case).  If a task with the same name is already in the queue, or was in the queue in the last 7 days, GAE won't queue it again.  This gives you the run-once, retry, and pruning of old tombstones (in this case, the task name) automatically.

Giving credit where due, this approach is taken from Dan Sanderson's "Programming Google App Engine" book (O'Reilly).

[Jeff Schnitzer]

I'm afraid that there is no guarantee that tasks execute once. The
named task prevents it from being inserted a second time, but an
enqueued task has "at least once" semantics.

Jeff

> --
> You received this message because you are subscribed to the Google Groups
> "Google App Engine" group.

> To view this discussion on the web visit
> https://groups.google.com/d/msg/google-appengine/-/VVq0iD0escIJ.

[AndyD]

Yes, I see what you're saying.  But in looking at both your and Robert's approaches, I still have questions.

Jeff, how does your approach avoid executing the operation twice?  Let's say there's a web page with a submit button that triggers the process, and the user clicks that button twice.  The algorithm you outlined...

Create TxnID entity instance
Repeat until success {
 * start txn
 * load TxnID (if null, return success immediately)
 * debit $5 from AccountA
 * credit $5 to AccountB
 * delete TxnID
 * commit txn
} 

 

...if run serially, would do the operation twice, wouldn't it?  The first execution would create the TxnID entity, then in the loop, it would load that entity successfully, perform the operation, then delete the TxnID entity.  Then, when the 2nd button click is handled, the operation would be be performed again.

Robert, I didn't quite follow your algorithm.  Does your marker indicate that the operation has not yet been performed?  If so, shouldn't 2b say "if the marker is not found, abort?  Also, is there an implied retry mechanism (e.g. a task) encompassing step 2?

It seems to me there are multiple challenges:

1) eliminate the potential of concurrency

2) retry on failure

3) only do the operation once

If we don't eliminate concurrency, then two parallel threads, in the same or different instances, could find the operation not yet completed and both perform it.   If we don't indicate (by the presence or absence of a marker) that the operation has been completed, then two serial executions would both perform it.  And if we don't have a retry mechanism, there is a risk that the operation won't be performed at all. 

It still seems to me that the task queue approach addresses 1 (by not dequeing a task to two handlers simultaneously and also not accepting a duplicate task into the queue) and 2 (by automatically retrying on failure), but as Jeff pointed out, not 3.  If you add an "operation not performed yet" marker entity to the picture that gets deleted in the same transaction as the run-once operation, does that cover all the bases? 

Just to make it interesting, what if the operation to be performed once was not a datastore operation?  What if it was a call to an external system (like a credit card processing service)?  You could successfully make the external call, but fail to write the "operation complete" entity.

-Andy

[Brandon Wirtz]

If it makes you feel better, Bank Of America doesn’t seem to have solved this, “auto-paid” my car payment 3 times this month because of an error and mailed off 3 checks to Capital One.

 

The solution to all of these problems could be what B Of A does, bounce one of the transaction, then send the user a bill for $35 * 10 for the $2.10 transactions from Google.

 

PS

If you solve this issue, please make the solution open source so B of A can use it.

 

PSS

It’d be awesome if we could get consolidated Monthly billing for GAE for less than $500  a month J

--

You received this message because you are subscribed to the Google Groups "Google App Engine" group.

To view this discussion on the web visit https://groups.google.com/d/msg/google-appengine/-/YU3N7fnt8rAJ.

[Jeff Schnitzer]

I think we might be talking about two different things. I'm not
worried about the user clicking the button twice; I prevent that with
javascript on the frontend. I just want an idempotent transaction
that safely transfers $5 from one account to another. Without
idempotence I can't hide contention (or any other datastore failure)
from the user.

Creating a txnId entity outside the transaction and deleting it in the
transaction gives me idempotence; no matter how many times the
transaction runs, only one of those transactions will complete and
delete the txnId entity and all the others will either rollback (eg
optimistic concurrency failure) or notice that the txnId has been
deleted and immediately return success.

The problem with calling to an external system (the cc processing
service example) is that there's no way to enlist it in the
transaction. You need to build up the framework of a 2pc transaction
to the cc service. All the cc processing services I know of sidestep
the issue by repeatedly posting some sort of IPN to you, which you are
expected to handle idempotently yourself. Actually, there's another
variation - some of them have separate auth/capture steps which are
kind of like a 2pc transaction.

Jeff

On Sat, Jan 21, 2012 at 6:04 PM, AndyD <goo...@adennie.e4ward.com> wrote:
> Yes, I see what you're saying.  But in looking at both your and Robert's
> approaches, I still have questions.
>
> Jeff, how does your approach avoid executing the operation twice?  Let's say
> there's a web page with a submit button that triggers the process, and the
> user clicks that button twice.  The algorithm you outlined...
>

> Create TxnID entity instance
> Repeat until success {
>  * start txn
>  * load TxnID (if null, return success immediately)
>  * debit $5 from AccountA
>  * credit $5 to AccountB
>  * delete TxnID
>  * commit txn
> }
>

> ...if run serially, would do the operation twice, wouldn't it?  The first
> execution would create the TxnID entity, then in the loop, it would load
> that entity successfully, perform the operation, then delete the TxnID
> entity.  Then, when the 2nd button click is handled, the operation would be
> be performed again.
>
> Robert, I didn't quite follow your algorithm.  Does your marker indicate
> that the operation has not yet been performed?  If so, shouldn't 2b say "if
> the marker is not found, abort?  Also, is there an implied retry mechanism
> (e.g. a task) encompassing step 2?
>
> It seems to me there are multiple challenges:
> 1) eliminate the potential of concurrency
> 2) retry on failure
> 3) only do the operation once
>
> If we don't eliminate concurrency, then two parallel threads, in the same or
> different instances, could find the operation not yet completed and both

> perform it.  If we indicate (by the presence or absence of a marker) that

> the operation has been completed, then two serial executions would both
> perform it.  And if we don't have a retry mechanism, there is a risk that
> the operation won't be performed at all.
>
> It still seems to me that the task queue approach addresses 1 (by not
> dequeing a task to two handlers simultaneously and also not accepting a
> duplicate task into the queue) and 2 (by automatically retrying on failure),

> but as Jeff pointed out, not 3.  If you add an "operation complete" marker
> entity to the picture that gets written in the same transaction as the
> run-once operation, does that cover all the bases?  The marker would still
> need to be cleaned up at some later point, of course.

>
> Just to make it interesting, what if the operation to be performed once was
> not a datastore operation?  What if it was a call to an external system
> (like a credit card processing service)?  You could successfully make the
> external call, but fail to write the "operation complete" entity.
>
> -Andy
>
>

> --
> You received this message because you are subscribed to the Google Groups
> "Google App Engine" group.
> To view this discussion on the web visit

> https://groups.google.com/d/msg/google-appengine/-/aKzPhfSgF0AJ.

[Brandon Wirtz]

Oh, and my 2 cents.

Transfers to process is a list
XFERID Jeff to Brandon $100
XFERID Brian to Brandon $100
XFERID Brandon to Safeway $7

Transactions to Process is a list.

TXID 51 Transfer $100 From Jeff
TXID 52 Transfer $100 From Brian
TXID 53 Transfer $7 From Brandon
TXID 54 Transfer $100 to Brandon
TXID 55 Transfer $100 to Brandon
TXID 56 Transfer $7 to Safeway

Brandon's account is a list
BWID 1 Account Opened with $150
BWID 2 Received $78 via TXID 38
BWID 3 Receive $100 via TXID 51
BWID 4 Receive $100 via TXID 52
BWID 5 Send $7 via TXID 53

Jeffs account is a list
JSID 1 Account opened with $5000
JSID 2 Send $100 via TXID 51

You don't move Dollars from X to Y. You always move to and from general
fund.
You add and remove dollars based on Transaction IDs which must be unique.
You rectify accounts in a batch which includes which transactions were
rectified. To determine the current balance.

I apologize for the brevity, I was typing this quickly between phone calls,
but hopefully this demonstrates the solution.
This solution creates more moving parts as a total, but fewer moving parts
per type, and the unique ids means that if you have two of the same ID you
ignore them when processing.

Also note that if I were implementing this Transfer requests would be
assigned an ID. The User would enter the information. They would be given a
confirmation. And then the transfer would be added to the queue. Unconfirmed
transfers would still consume a transfer ID.

-----Original Message-----
From: google-a...@googlegroups.com
[mailto:google-a...@googlegroups.com] On Behalf Of Jeff Schnitzer
Sent: Saturday, January 21, 2012 3:42 PM
To: google-a...@googlegroups.com
Subject: Re: [google-appengine] Re: Once-only transactions

[Pieter Coucke]

For once I may agree with Brandon ;-)

I used the approach described by Nick Johnson (http://blog.notdot.net/2009/9/Distributed-Transactions-on-App-Engine) even though there are now XG-transactions. To avoid duplicates (users can disable javascript) I add a hidden random orderId to the form and check in the datastore first if there exists a transfer object with that orderId. If it exists, I know the transaction has already been done. If not, proceed. The query for the check on orderId is transactional because it uses the same root entity as the transfer object (the user to which it belongs).

A benefit of this approach is also that you have less datastore contention on different entity groups because the "deposit" happens in a queue which can be retried so a payment will not fail because the beneficiary has a lot of updates at the moment.

--
Pieter Coucke

Onthoo BVBA - zamtam.com

[Jeff Schnitzer]

This is an interesting approach, but it's fairly invasive to the whole
application. My use case is not actually a bank account transfer but
a variety of other similar problems, many of which aren't driven by a
UI.

I ended up creating a little bit of glue so that I can run a once-only
transaction anywhere:

ofy.transactOnceOnly(keyOfSomeEntityGroup, new VoidWork() {
@Override
public void vrun(Objectify ofy) {
// execution transaction, it will only complete once
}
});

...where keyOfSomeEntityGroup defines an arbitrary parent for my
transaction marker entity, keeping the # of entity groups to a
minimum.

If someone else wants the code I can post it. It's Java/Objectify but
you could easily adapt it to Python since the Ofy and GAE/Python
transaction APIs are similar.

Jeff

[Robert Kluin]

On Sat, Jan 21, 2012 at 17:08, AndyD <goo...@adennie.e4ward.com> wrote:
> Yes, I see what you're saying.  But in looking at both your and Robert's
> approaches, I still have questions.
>
> Jeff, how does your approach avoid executing the operation twice?  Let's say
> there's a web page with a submit button that triggers the process, and the
> user clicks that button twice.  The algorithm you outlined...
>
> Create TxnID entity instance
> Repeat until success {
>  * start txn
>  * load TxnID (if null, return success immediately)
>  * debit $5 from AccountA
>  * credit $5 to AccountB
>  * delete TxnID
>  * commit txn
> }
>
> ...if run serially, would do the operation twice, wouldn't it?  The first
> execution would create the TxnID entity, then in the loop, it would load
> that entity successfully, perform the operation, then delete the TxnID
> entity.  Then, when the 2nd button click is handled, the operation would be
> be performed again.
>
> Robert, I didn't quite follow your algorithm.  Does your marker indicate
> that the operation has not yet been performed?  If so, shouldn't 2b say "if
> the marker is not found, abort?  Also, is there an implied retry mechanism
> (e.g. a task) encompassing step 2?

So my approach is effectively what Jeff had outlined, the difference
is that I use the existence of a marker to indicate that the
transaction has been completed. There may or may not be an implied
retry around step 2, but yes -- I generally run things like this in a
task.

>
> It seems to me there are multiple challenges:
> 1) eliminate the potential of concurrency
> 2) retry on failure
> 3) only do the operation once
>
> If we don't eliminate concurrency, then two parallel threads, in the same or
> different instances, could find the operation not yet completed and both
> perform it.   If we don't indicate (by the presence or absence of a marker)
> that the operation has been completed, then two serial executions would both
> perform it.  And if we don't have a retry mechanism, there is a risk that
> the operation won't be performed at all.
>
> It still seems to me that the task queue approach addresses 1 (by not
> dequeing a task to two handlers simultaneously and also not accepting a
> duplicate task into the queue) and 2 (by automatically retrying on failure),
> but as Jeff pointed out, not 3.  If you add an "operation not performed yet"
> marker entity to the picture that gets deleted in the same transaction as
> the run-once operation, does that cover all the bases?

There is a vey important note here. Tasks *do* occasionally run
multiple times. You should never assume that a task will be run
exactly once, rather the opposite; assume your task will be run twice,
either simultaneously or serially, which ever is worse for your app.

Robert

>
> Just to make it interesting, what if the operation to be performed once
> was not a datastore operation?  What if it was a call to an external system
> (like a credit card processing service)?  You could successfully make the
> external call, but fail to write the "operation complete" entity.
>
> -Andy
>

> --
> You received this message because you are subscribed to the Google Groups
> "Google App Engine" group.
> To view this discussion on the web visit

> https://groups.google.com/d/msg/google-appengine/-/YU3N7fnt8rAJ.