[Zope3-dev] randid()

[Jim Fulton]

Jeremy Hylton wrote:
> 
> >>>>> "SA" == Steve Alexander <steve@cat-box.net> writes:
> 
>   SA> Jeremy Hylton wrote:
>   >> Tim and I were talking about the randid() function yesterday
>   >> afternoon.  It seems to have two serious problems if it's used
>   >> for generated unique ids:
>   >>
>   >> - It's subject to the birthday paradox.  We should expect to see
>   >>   a
>   >> duplicate after 2**16 calls.
> 
>   SA> Occasional duplicates shouldn't be a problem. That's the price
>   SA> we pay for not needing to persistently store the next id in
>   SA> sequence.  The duplicates should be infrequent, so this
>   SA> shouldn't be a worry.
> 
> What are the use cases for randid()?  It's called from something that
> creates an ruid, where u probably implies unique.  It's not clear from
> the iplementation what party is reposnsible for guaranteeing that the
> number is unique?

randid is reposponsible to returning a "probably" unique value.
The method called on the BTree is responsble for making sure that
they key is unique.


>   >> - It's not in the least bit thread safe.  Two threads executing
>   >>   in
>   >> parallel could get the same sequence of random ids.
> 
>   SA> That shouldn't be much of a problem, as you'd get a conflict
>   SA> error and a re-try.
> 
> Where would the ConflictError occur?

If two threads picked the same id, there would be a conflict
when they both tried to add objects with the same id.
 
>   SA> Perhaps there could be one random number generator with a
>   SA> high-entropy seed per ZODB Connection?
> 
> Or per thread?  I'm not sure if the thread -> Connection mapping will
> be managed the same way in ZODB4.

This isn't necessary. The current algorthm should be fine.
 
>   >> Is there any reason we can't replace its use in ObjectHub with a
>   >> simple persistence counter?
> 
>   SA> I don't know. Obviously, there's less overhead if we can get
>   SA> random ids to work.l This has implications for its use in
>   SA> ZCatalog (+ ZEO too) in Zope 2. Any important change should be
>   SA> considered for backporting to zope 2.
> 
> If any onld random number would do, we can implement an even simpler
> randid()?  Would we care if it returned numbers in a range of 2**30
> instead of 2**32?

The bigger the space the better. The current generator is not that 
complicated and it works.

Jim


--
Jim Fulton           mailto:jim@zope.com       Python Powered!        
CTO                  (888) 344-4332            http://www.python.org  
Zope Corporation     http://www.zope.com       http://www.zope.org