Consistent hashing

ConsistentHash.php

<?php

/**
 * @see https://github.com/pda/flexihash
 * @see http://www.martinbroadhurst.com/Consistent-Hash-Ring.html
 */
class ConsistentHash
{
  /** @var int Number of positions to hash each target. This has the effect of distributing the servers more evenly over the ring. Note that this has nothing to do with server replication */
  private $replicas;

  /** @var array List of targets */
  private $targets = array();

  /** @var array Map of positions (hashes) to targets */
  private $positions = array();

  /** @var bool Whether the map of positions to targets is already sorted */
  private $sortedPositions = false;

  /**
   * @param string[] $targets
   * @param int $replicas
   */
  public function __construct($targets, $replicas = 64)
  {
    $this->replicas = $replicas;

    foreach ($targets as $target)
    {
      $this->addTarget($target);
    }
  }

  /**
   * @param string $target
   * @param float $weight
   * @return $this
   * @throws \Exception
   */
  public function addTarget($target, $weight = 1.0)
  {
    if (array_key_exists($target, $this->targets))
    {
      throw new \Exception('Target ' . $target . ' already exists');
    }
    $this->targets[] = $target;

    // hash the target into multiple positions
    $count = min($this->replicas, round($this->replicas * $weight));
    for ($i = 0; $i < $count; $i++)
    {
      $position = $this->hash($target . $i);
      $this->positions[$position] = $target;
    }

    $this->sortedPositions = false;

    return $this;
  }

  /**
   * Looks up the target for the given resource
   *
   * @param string $resource
   * @return string
   * @throws \Exception
   */
  public function lookup($resource)
  {
    if (empty($this->targets) || empty($this->positions))
    {
      throw new \Exception('No targets exist');
    }

    if (count($this->targets) == 1)
    {
      return $this->targets[0];
    }

    $this->sortPositions();

    // hash resource to a position
    $resourcePosition = $this->hash($resource);

    $results = array();
    $collect = false;

    // search values above the resourcePosition
    foreach ($this->positions as $key => $value)
    {
      // start collecting targets after passing resource position
      if (!$collect && $key > $resourcePosition)
      {
        return $value;
      }
    }

    // search values below the resourcePosition
    foreach ($this->positions as $key => $value)
    {
      return $value;

    }
  }

  /**
   * Sorts the positions map
   */
  private function sortPositions()
  {
    // sort by key (position) if not already
    if (!$this->sortedPositions)
    {
      ksort($this->positions, SORT_REGULAR);
      $this->sortedPositions = true;
    }
  }

  /**
   * Calculate the hash of a string
   *
   * @param string $string
   * @return string
   */
  protected function hash($string)
  {
    return substr(md5($string), 0, 8);
  }

}