Open Stack

On Thu, 2013-04-25 at 17:01 -0400, Simo Sorce wrote:
> On Thu, 2013-04-25 at 15:27 -0400, Eric Windisch wrote: 
> > Message are not guaranteed to be in order. First, this is not expected
> > of the RPC abstraction, and secondly, it isn't true of the
> > implementations we have. I can't speak for Rabbit/Qpid, but I know
> > that ZeroMQ will certainly deliver messages out of order as they're
> > sent over separate TCP connections. I suspect the same is probably
> > true of Rabbit/Qpid, at least if you happen to have multiple processes
> > per host (i.e. two processes of 'nova-scheduler'). 
> 
> Ok, then I will think again about it.

I thought more about it :-)

> > > If that is possible I guess using a nonce will be necessary, but I dread
> > > having to keep a dictionary of received packets, search through it every
> > > single time you receive a message, scrub it regularly to prune old
> > > entries and so on.
> > 
> > Dictionary key lookups are fast. Memory is a bigger concern. You only need to keep signatures, not message contents. There are data structures and patterns that are appropriate for this task that won't require active scrubbing.
> > > Keep in mind this database would have to be on shared if you really run
> > > multiple processes with the same name on the same host as they all have
> > > to share the replay database, so you need to use shared memory or IPC
> > > and some sort and locking ... which tends to slow done processing and it
> > > is usually a blocking operation.
> > 
> > 
> > At least that will be per-host and not per-service. 
> 
> The thing is, in order to use a nonce you need to do interprocess
> locking and keep a table of all the numbers previously used (or use a
> counter). Unless by nonce, you really mean a 'random' number.
> 
> 1. A nonce cannot ever repeat. To guarantee this you have to have a
> single source for this number (back to monotonic timestamp and
> serialization, just different output).
> 
> 2. A random number can repeat but it is very unlikely that will happen
> if you have a good random generator that has uniform distribution. 
> 
> I think you mean 2, because the chance we get out of the hat 2 identical
> numbers chosen at random within the same hundredth of a second on the
> same machine if the numbers are big enough, say 2^64, are very, very
> low, so we might decide to ignore that it may happen.
> 
> However, how bad is it is it *does* happen ?
> 
> 
> If we really need a *nonce* then we should use a counter that is updated
> atomically cross-process.

Ok we can actually use a per process counter so that we do not have to
synchronize between processes or threads, we just need a big enough
number, say a 64bit unsigned integer and then slice the number space
equally between each process or thread.

All we need to do is register a slice each time a new process/thread
starts so that the synchronization happens only once at process startup.

By dividing a 64 bit integer in slices of 32 bits we can have 4 billion
processes running at the same time and each of them can send 400 billion
messages per second without generating a conflict (if the timestamp has
hundredth of second resolution like time.time() has.

I guess this is sufficient, if we can have machines so fast to sign 4
billion messages per 1/100s .. well I'll be really glad to have this
problem :-)

So I'll re-add the nonce and specify it is a 64bit number, the mechanics
of how multiple processes handle it and the fact it actually should be a
counter at implementation are implementation details.
I will simply specify the nonce must be unique within the same timestamp
interval.

Simo.


-- 
Simo Sorce * Red Hat, Inc * New York