title: Hash algorithms for load balancing
body: <p><strong>IMPORTANT</strong>: Before you suggest that we use a readily available load balancer, please understand that we're not trying to load balance normal internet traffic. We receive data from a number of sources, some of which aren't internet connected (ie they may use SMS, or similar). We process these and then forward the messages on to the next stage. It is this internal step that we need to load balance. <strong>It is not using HTTP requests</strong></p>
  
  <p>Now the scenario:</p>
  
  <p>I'm doing some testing on various hashing algorithms in PHP to use for load balancing. I need to guarantee that every <em>device</em> is load balanced to the same node. In our use case, every message has a <em>serial number</em> which is constant, so I'm planning on using this value. It is critical that all messages from a given device are load balanced to the same node. We are not interested in the node capacity at this point.</p>
  
  <p>So, I've read a few articles about using the modulus of a hash etc to determine which node to direct to. I've seen some stating that the decimal representation of a hash from MD5, SHA1, SHA256 and SHA512 will all exceed the <code>PHP_INT_MAX</code> therefore the modulus will always be zero, so we can't use that to load balance.</p>
  
  <p>I've also seen suggestions that we could simply bit shift away a chunk of the hash and use only the high bits to get the modulus and again, use that.</p>
  
  <p>This got me wondering... Since we only need to load balance between a relatively small number of nodes to begin (it won't exceed 16 for some time), are any algorithms adequate that we could just use the first byte and load balance based on that?</p>
  
  <p>So I wrote this really simple function:</p>
  
  <pre><code>function balanceToNode(string $serial, string $algo="md5", int $nodes=1)
  {
      $hash = hash($algo, $serial);
      return hexdec($hash[1]) % $nodes;
  }
  </code></pre>
  
  <p>I ran this with <code>md5</code>, <code>sha1</code>, <code>sha256</code> and <code>sha512</code> against a sample of 1000 real serial numbers from our database. I tested each with 4, 8 and 16 nodes and examined the standard deviation across each of the nodes.</p>
  
  <h1>Single Byte Test</h1>
  
  <p>What I found was that using <code>md5</code> resulted in predictable and well balanced data between the nodes, regardless of how many nodes we used. <code>sha1</code> balanced poorly if we had a small number of nodes, but balanced better with a larger number of nodes. <code>sha256</code> was even worse than <code>sha1</code> but still balanced better with more nodes, and <code>sha512</code> was almost unaffected by the number of nodes but still didn't balance as well as <code>md5</code>.</p>
  
  <p>Here is the actual data that we got from the tests. We took an estimated standard deviation from the sample to get to the numbers per node, and then the stdev of the population to get a figure for the algorithm consistency. I may be doing maths wrong! I'm looking for smaller numbers in all cases</p>
  
  <h2>MD5</h2>
  
  <ul>
  <li>4 nodes: 8.041558721</li>
  <li>8 nodes: 7.171371656</li>
  <li>16 nodes: 7.554248253</li>
  </ul>
  
  <p>Consistency: 0.356104153</p>
  
  <h2>SHA1</h2>
  
  <ul>
  <li>4 nodes: 17.53092506</li>
  <li>8 nodes: 13.24494513</li>
  <li>16 nodes: 7.966596931</li>
  </ul>
  
  <p>Consistency: 3.91162024</p>
  
  <h2>SHA256</h2>
  
  <ul>
  <li>4 nodes: 25.81988897</li>
  <li>8 nodes: 15.7116881</li>
  <li>16 nodes: 11.40741718</li>
  </ul>
  
  <p>Consistency: 6.040803998</p>
  
  <h2>SHA512</h2>
  
  <ul>
  <li>4 nodes: 11.5758369</li>
  <li>8 nodes: 10.87592361</li>
  <li>16 nodes: 9.535897091</li>
  </ul>
  
  <p>Consistency: 0.846358482</p>
  
  <h1>8 Byte Test</h1>
  
  <p>I ran the test again, this time using the first 8 bytes from any given hash. This made a massive difference, although <code>md5</code> still appears to perform the best. The big surprise for me here is that <code>sha512</code> performed significantly worse with 16 than with 8</p>
  
  <h2>MD5</h2>
  
  <ul>
  <li>4 nodes: 18</li>
  <li>8 nodes: 13.53302838</li>
  <li>16 nodes: 7.916228058</li>
  </ul>
  
  <p>Consistency: 4.12559407</p>
  
  <h2>SHA1</h2>
  
  <ul>
  <li>4 nodes: 27.41046029</li>
  <li>8 nodes: 17.63114128</li>
  <li>16 nodes: 8.181279444</li>
  </ul>
  
  <p>Consistency: 7.850664268</p>
  
  <h2>SHA256</h2>
  
  <ul>
  <li>4 nodes: 25.31139401</li>
  <li>8 nodes: 15.25029274</li>
  <li>16 nodes: 7.509993342</li>
  </ul>
  
  <p>Consistency: 7.287949408</p>
  
  <h3>SHA512</h3>
  
  <ul>
  <li>4 nodes: 17.60681686</li>
  <li>8 nodes: 6.886840453</li>
  <li>16 nodes: 11.44261042</li>
  </ul>
  
  <p>Consistency: 4.39280188</p>
  
  <h1>My Actual Question</h1>
  
  <p>Bearing in mind that we're using the hash algorithm PURELY to distribute messages across a cluster of nodes, and not to secure passwords. Also, based on the samples, the questions are:</p>
  
  <ol>
  <li>Am I safe to use the first byte only?</li>
  <li>Is it OK to use <code>md5</code></li>
  <li>Am I doing maths wrong?</li>
  </ol>