On the Influence of PRNGs on Data Distribution

The amount of digital information produced grows rapidly and constantly. Storage systems use clustered architectures designed to store and process this information efficiently. Their use introduces new challenges in storage systems development, like load-balancing and data distribution. A variety of randomized solutions handling data placement issues have been proposed and utilized. However, to the best of our knowledge, there has not yet been a structured analysis of the influence of pseudo random number generators (PRNGs) on the data distribution. In the first part of this paper we consider Consistent Hashing [1] as a combination of two consecutive phases: distribution of bins and distribution of balls. We analyze PRNGs in terms of their efficiency in either phase independently, but also in terms of the overall behavior. The result of this analysis helps to choose a PRNG according to the quality of the load distribution and the performance. In the second part we explore PRNGs for different data placement schemes. We investigate the influence of the distribution strategies on the generators and try to identify the correlations between PRNG internal algorithm types and their properties.