[ http://issues.apache.org/jira/browse/NUTCH-122?page=all ]
Sami Siren resolved NUTCH-122:
------------------------------
Resolution: Invalid
this is more related to hadoop
> block numbers need a better random number generator
> ---------------------------------------------------
>
> Key: NUTCH-122
> URL: http://issues.apache.org/jira/browse/NUTCH-122
> Project: Nutch
> Type: Bug
> Components: fetcher, indexer, searcher
> Versions: 0.8-dev
> Reporter: Paul Baclace
> Attachments: MersenneTwister.java, MersenneTwister.java
>
> In order to support billions of block numbers, a better PRNG than
> java.util.Random is needed. To reach billions with low probability of
> collision, 64 bit random numbers are needed (the Birthday Problem is the
> model for the number of bits needed; the result is that twice as many bits
> are needed as the number of bits to count the expected number of items.) The
> built-in java.util.Random keeps only 48 bits of state which is only
> sufficient for 2^24 items. Using repeated calls to or more than one instance
> of Random does not increase its total entropy.
> Analysis
> util.Random is a linear congruential generator (LCG) identical to drand48.
> util.Random keeps 48 bits of state and gangs together 2 consecutive
> values to return 64 bit values.
> LCGs suffer from periodicity in the low order bits which would make
> modular binning less than random.
> "low order bits" could mean least significant byte.
> LCGs have periods in the range 106 to 109 when using 32 bit words, a
> range of poor to fair.
> seed = ( 0x5DEECE66DL * seed + 0xBL ) & ((1L << 48) - 1);
> the origin of 0x5DEECE66D, a non-prime, is shrouded in the mists of
> time.
> Results of the Birthday Spacings Test look good.
> References
> http://www.math.utah.edu/~beebe/java/random/README
> http://www.pierssen.com/arcview/upload/esoterica/randomizer.html
> Recommended alternative: MersenneTwister
> Matsumoto and Nishimura (1998).
> Longest period of any known generator 2^19937 or about 10^6001.
> A period that exceeds the number of unique values seems ideal;
> obviously a shorter period than the number of unique values (like
> util.Random) is a problem).
> Faster than java.util.Random (Random was recent tweaked, however).
> Excellent result for Diehard Birthday Spacings Test.
> Can be seeded with up to 624 32 bit integers.
> Doug Cutting wrote on nutch-dev:
> > It just occurred to me that perhaps we could simply use sequential block
> > numbering.
> > All block ids are generated centrally on the namenode.
> Response from Paul Baclace:
> I'm not sure what the advantage of sequential block numbers would be
> since long period PRNG block numbering does not even need to store
> it's state, just pick a new starting place.
> Sequential block numbering does have the downside that picking a datanode
> based on (BlockNum % DataNodeCount) would devolve into round robin. Any
> attempt to pass the sequence through a hash ends up becoming a random number
> generator.
> Sequential numbering provides contiguous numbers, but after G.C. that would
> be lost, so no advantage there.
> When human beings eyeball block numbers, many with small differences are more
> likely to be misread than many that are totally different.
> If block numbering is sequential, then there is a temptation to use 32 bits
> instead of 64, but 32 bits leads to wrap-around and uh oh.
> FSNamesystem uses Random to help pick a target datanode, but it could just
> use the randomness of block numbers.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
