Re: [Asrg] About that e-postage draft [POSTAGE]

On Feb 21, 2009, at 4:07 PM, Bill Cole wrote:

> Steve Atkins wrote, On 2/20/09 7:26 PM:
> > On Feb 20, 2009, at 3:25 PM, Bill Cole wrote:
> > The reliability (SPoF), economics, business and usability issues  
> > are likely to be much more of a problem.
> Those are all problems. It seems to me that any attempt to seriously  
> address the SPoF problem makes the race resolution problem harder.
Almost by definition. If your definition of which of two redemption  
attempts is valid is the one that arrives at a particular place first,  
then that place is a single point of failure. If that's not your  
definition, things get a lot more complex.
> > At each redemption machine, look up the stamp  an "I've seen this"  
> > associative array. If you've seen it, reject the stamp, otherwise  
> > accept it. This is arbitrarily scalable, just by adding enough  
> > redemption machines that the memory access time to look up the  
> > entry in the associative array is enough to meet your throughput  
> > goal, and the size of the number of outstanding stamps fits in the  
> > storage space of the machine. Assuming there's a serial number in  
> > each stamp, your associative array could simply be 250 gigabits of  
> > RAM, so again it's not going to be many machines, maybe one, to do  
> > in software.
> I think it is a bit of a hand-wave to call this arbitrarily  
> scalable, but I'm happy to stipulate for the test of my hypothesis  
> that the entire server-side decision process for any one redemption  
> transaction can be reliably done correctly in uniform sub- 
> millisecond time if the stamp is either available for redemption or  
> already redeemed. The problem is that logically you need a third  
> intermediate state that will last for the RTT of the network  
> connection to the redeeming client, and that state will defer the  
> decision for other attempts to redeem the stamp.
>
> > To me it feels like the hard bit of this is handling a million  
> > packets in and out per second reliably, along with the overhead of  
> > providing robustness and redundancy, rather than the redemption  
> > itself.
> That was my point, because it seems to me that a redemption cannot  
> be done with just one packet in and one out, but really needs two in  
> and one out.
One in and one out will do it. The client MTA can include a nonce or  
serial number in the request. The redemption machine can keep track of  
the nonce value of the request that was accepted as valid, at a cost  
of a few times the number of machines needed. We're already keeping  
that state for a month anyway.
If any client doesn't receive a response (positive or negative) after  
a while, it can retry with the same nonce and it will still get a  
correct answer. (While the system may well need to deal with malicious  
clients, it only needs to give correct results to non-malicious  
clients). This eliminates any need to keep state for anything  
resembling packet RTT time.
The similarities of this to DNS might just betray my background rather  
than being anything particularly meaningful.

> A legitimate stamp needs to have 3 possible states in the server's  
> map: redeemed, unredeemed, and pending acknowledgment of redemption.  
> If the server only has two states for a stamp, then it would end up  
> with one of two flaws by design:
Or "unredeemed" and "redeemed for nonce value X".

> 1. If the stamp is marked as redeemed when a successful redemption  
> attempt completes on the server, it is possible that the success  
> will not be successfully communicated to the client. If the client  
> then retries the redemption, it will fail.
> 2. If the stamp is left as unredeemed while waiting for the client  
> ack of success, stamp "reuse" becomes a question of how many  
> redemption decisions can be made per client RTT.
> The server may have to defer many thousands of clients for scores of  
> milliseconds while waiting for one to send an ack. Handling a few  
> dozen such events per second seems to me to be a really hard problem  
> to address, but maybe I'm missing something. If the average  
> transaction lifetime is 100ms, then a million-TPS system needs to be  
> able to handle an average of 100k concurrent pending transactions  
> and spikes probably twice that. I think the ways to handle that all  
> include dividing the front end between multiple machines, but that  
> creates a tougher problem keeping the back end recordkeeping fast  
> and coherent from the viewpoints all of the front ends.
> I suspect that the "solution" that will be chosen if anyone tries to  
> create a real e-postage system instead of hand-waving about it will  
> be to open it to lost packet damage as the cost of scalability.  
> Network latency with clients becomes irrelevant if the server  
> assumes that its redemption messages are always delivered. That  
> allows for a lot of optimization. Once in a while a stamp that  
> should work will fail to do so, and if such a system ever gets into  
> the real world I'm sure its users will be shocked at how much higher  
> the real-world failures are than in their tests...
Don't forget that there is no state that needs to be kept or  
transferred other than that keyed on the stamp value itself. You can  
spread the load needed across as many systems as you need to keep up  
with demand. At an extreme, you can have the client MTAs use the  
cookie in the stamp to decide where to check the stamp, and spread  
load across multiple networks and locations - I check this stamp by  
sending a packet to whatever IP address <last 16 bits of  
cookie>.stampcheck.foo resolves to. (That's what I mean when I  
describe it as embarrassingly parallelizable.)
That might end up being expensive to operate, of course.

Cheers,
  Steve



_______________________________________________
Asrg mailing list
Asrg(_at_)irtf(_dot_)org
http://www.irtf.org/mailman/listinfo/asrg