HashRing.php

Go to the documentation of this file.

<?php
class HashRing {
    protected $sourceMap = array();
    protected $ring = array();

    protected $liveRing;
    protected $ejectionExpiries = array();
    protected $ejectionNextExpiry = INF;

    const RING_SIZE = 268435456; // 2^28

    public function __construct( array $map ) {
        $map = array_filter( $map, function ( $w ) {
            return $w > 0;
        } );
        if ( !count( $map ) ) {
            throw new UnexpectedValueException( "Ring is empty or all weights are zero." );
        }
        $this->sourceMap = $map;
        // Sort the locations based on the hash of their names
        $hashes = array();
        foreach ( $map as $location => $weight ) {
            $hashes[$location] = sha1( $location );
        }
        uksort( $map, function ( $a, $b ) use ( $hashes ) {
            return strcmp( $hashes[$a], $hashes[$b] );
        } );
        // Fit the map to weight-proportionate one with a space of size RING_SIZE
        $sum = array_sum( $map );
        $standardMap = array();
        foreach ( $map as $location => $weight ) {
            $standardMap[$location] = (int)floor( $weight / $sum * self::RING_SIZE );
        }
        // Build a ring of RING_SIZE spots, with each location at a spot in location hash order
        $index = 0;
        foreach ( $standardMap as $location => $weight ) {
            // Location covers half-closed interval [$index,$index + $weight)
            $this->ring[$location] = array( $index, $index + $weight );
            $index += $weight;
        }
        // Make sure the last location covers what is left
        end( $this->ring );
        $this->ring[key( $this->ring )][1] = self::RING_SIZE;
    }

    public function getLocation( $item ) {
        $locations = $this->getLocations( $item, 1 );

        return $locations[0];
    }

    public function getLocations( $item, $limit ) {
        $locations = array();
        $primaryLocation = null;
        $spot = hexdec( substr( sha1( $item ), 0, 7 ) ); // first 28 bits
        foreach ( $this->ring as $location => $range ) {
            if ( count( $locations ) >= $limit ) {
                break;
            }
            // The $primaryLocation is the location the item spot is in.
            // After that is reached, keep appending the next locations.
            if ( ( $range[0] <= $spot && $spot < $range[1] ) || $primaryLocation !== null ) {
                if ( $primaryLocation === null ) {
                    $primaryLocation = $location;
                }
                $locations[] = $location;
            }
        }
        // If more locations are requested, wrap-around and keep adding them
        reset( $this->ring );
        while ( count( $locations ) < $limit ) {
            list( $location, ) = each( $this->ring );
            if ( $location === $primaryLocation ) {
                break; // don't go in circles
            }
            $locations[] = $location;
        }

        return $locations;
    }

    public function getLocationWeights() {
        return $this->sourceMap;
    }

    public function newWithoutLocation( $location ) {
        $map = $this->sourceMap;
        unset( $map[$location] );

        return count( $map ) ? new self( $map ) : false;
    }

    public function ejectFromLiveRing( $location, $ttl ) {
        if ( !isset( $this->sourceMap[$location] ) ) {
            throw new UnexpectedValueException( "No location '$location' in the ring." );
        }
        $expiry = time() + $ttl;
        $this->liveRing = null; // stale
        $this->ejectionExpiries[$location] = $expiry;
        $this->ejectionNextExpiry = min( $expiry, $this->ejectionNextExpiry );

        return ( count( $this->ejectionExpiries ) < count( $this->sourceMap ) );
    }

    public function getLiveRing() {
        $now = time();
        if ( $this->liveRing === null || $this->ejectionNextExpiry <= $now ) {
            $this->ejectionExpiries = array_filter(
                $this->ejectionExpiries,
                function( $expiry ) use ( $now ) {
                    return ( $expiry > $now );
                }
            );
            if ( count( $this->ejectionExpiries ) ) {
                $map = array_diff_key( $this->sourceMap, $this->ejectionExpiries );
                $this->liveRing = count( $map ) ? new self( $map ) : false;

                $this->ejectionNextExpiry = min( $this->ejectionExpiries );
            } else { // common case; avoid recalculating ring
                $this->liveRing = clone $this;
                $this->liveRing->ejectionExpiries = array();
                $this->liveRing->ejectionNextExpiry = INF;
                $this->liveRing->liveRing = null;

                $this->ejectionNextExpiry = INF;
            }
        }
        if ( !$this->liveRing ) {
            throw new UnexpectedValueException( "The live ring is currently empty." );
        }

        return $this->liveRing;
    }

    public function getLiveLocation( $item ) {
        return $this->getLiveRing()->getLocation( $item );
    }

    public function getLiveLocations( $item ) {
        return $this->getLiveRing()->getLocations( $item );
    }

    public function getLiveLocationWeights() {
        return $this->getLiveRing()->getLocationWeights();
    }
}