Random number generators for NDFS block numbers

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Random number generators for NDFS block numbers

Paul E. Baclace
Doug Cutting expressed a concern to me about using util.Random to generate
random 64 bit block numbers for NDFS.  The following is my analysis.

Random number generators for NDFS block numbers
   Requirements
     capable of billions of block numbers
     64 bit block numbers
     deterministic for reproducible testing
     ideally, want a generator that makes no repeats and is serializable.
   Concern
     Currently using built-in util.Random, is it good enough?
   Background
     Theory of hashing
       In a hashing system, the collision rate is calculated just like the birthday problem/paradox.
         rule of thumb is to have twice as many bits as number of bits needed for the total number of items.
           example: 4 bits needed to count 16 items, needs 8 bit hashes.
       In a non-hashing system, block numbers are not related to block contents, but the birthday problem still applies.
     Theory of  random numbers
       The amount of entropy that a PRNG instance has cannot be increased by concatenation.
         A full 64 bits are needed to to store 4 billion items.
       Diehard test suite is a good randomness benchmark.
   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 10^6 to 10^9 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
   Alternative
     MersenneTwister replacement for Random is best choice, has a mind-bogglingly long period.
       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
         (intuitively ideal; obviously a shorter period than the number of unique values is a problem).
       Faster than standard Random.
       Excellent result for Diehard Birthday Spacings Test.
       Java Implementations.
         All the implementation are derived from the free to use C source.
         BSD type license
           Sean Luke implementation
         GNU Library General Public License
           Brian O. Bush implementation
         public domain
          Michael L. Brundage implementation
Reply | Threaded
Open this post in threaded view
|

Re: Random number generators for NDFS block numbers

Dawid Weiss

I'm not into random generators, but this is a useful overview. I know
mersenne and a few others are also implemented in Colt bundled library
(although it might be one of the implementations you mention):

http://hoschek.home.cern.ch/hoschek/colt/V1.0.3/doc/index.html

D.

Paul Baclace wrote:

> Doug Cutting expressed a concern to me about using util.Random to generate
> random 64 bit block numbers for NDFS.  The following is my analysis.
>
> Random number generators for NDFS block numbers
>   Requirements
>     capable of billions of block numbers
>     64 bit block numbers
>     deterministic for reproducible testing
>     ideally, want a generator that makes no repeats and is serializable.
>   Concern
>     Currently using built-in util.Random, is it good enough?
>   Background
>     Theory of hashing
>       In a hashing system, the collision rate is calculated just like
> the birthday problem/paradox.
>         rule of thumb is to have twice as many bits as number of bits
> needed for the total number of items.
>           example: 4 bits needed to count 16 items, needs 8 bit hashes.
>       In a non-hashing system, block numbers are not related to block
> contents, but the birthday problem still applies.
>     Theory of  random numbers
>       The amount of entropy that a PRNG instance has cannot be increased
> by concatenation.
>         A full 64 bits are needed to to store 4 billion items.
>       Diehard test suite is a good randomness benchmark.
>   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 10^6 to 10^9 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
>   Alternative
>     MersenneTwister replacement for Random is best choice, has a
> mind-bogglingly long period.
>       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
>         (intuitively ideal; obviously a shorter period than the number
> of unique values is a problem).
>       Faster than standard Random.
>       Excellent result for Diehard Birthday Spacings Test.
>       Java Implementations.
>         All the implementation are derived from the free to use C source.
>         BSD type license
>           Sean Luke implementation
>         GNU Library General Public License
>           Brian O. Bush implementation
>         public domain
>       Michael L. Brundage implementation
Reply | Threaded
Open this post in threaded view
|

Re: Random number generators for NDFS block numbers

Paul E. Baclace
In reply to this post by Paul E. Baclace
Thanks to archive.org, I found this additional reference:

   http://www.math.sci.hiroshima-u.ac.jp/~m-mat/eindex.html

which is the English home page of Matsumoto san, co-originator of Mersenne Twister.
There is a faq and the original C source.

Paul


Paul Baclace wrote:
> [...]
>   Alternative
>     MersenneTwister replacement for Random is best choice, has a
> mind-bogglingly long period.
>       Matsumoto and Nishimura (1998)
 > [...]
Reply | Threaded
Open this post in threaded view
|

Re: Random number generators for NDFS block numbers

Doug Cutting-2
In reply to this post by Paul E. Baclace
Paul Baclace wrote:
> Doug Cutting expressed a concern to me about using util.Random to generate
> random 64 bit block numbers for NDFS.  The following is my analysis.

Nice stuff, Paul.  Thanks.

It just occurred to me that perhaps we could simply use sequential block
numbering.  All block ids are generated centrally on the namenode.  If
it can simply maintain a persistent counter then sequential allocation
could be used.  Since each block addition is logged, this is easy to
persist.  When re-playing the log on namenode startup we simply keep
track of the highest known block id.

Blocks are not logged until the file is closed, so there could be a
problem on restart if datanodes report blocks for files that were never
closed.  These would collide with yet-unallocated block numbers,
potentially corrupting the filesystem.  I'm not sure what the best way
to handle that would be... Ideas?

Doug
Reply | Threaded
Open this post in threaded view
|

Re: Random number generators for NDFS block numbers

Paul E. Baclace
Doug Cutting wrote:
> It just occurred to me that perhaps we could simply use sequential block
> numbering.  All block ids are generated centrally on the namenode.  

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.

> Blocks are not logged until the file is closed, so there could be a
> problem on restart if datanodes report blocks for files that were never
> closed.  These would collide with yet-unallocated block numbers,
> potentially corrupting the filesystem.

I suppose a large margin of block ids could be skipped if there
was doubt about the previous shutdown, but the random block numbers
have many advantages.

Paul