MediaWiki  REL1_22
HashRing.php
Go to the documentation of this file.
00001 <?php
00029 class HashRing {
00031     protected $sourceMap = array();
00033     protected $ring = array();
00034 
00035     const RING_SIZE = 268435456; // 2^28
00036 
00040     public function __construct( array $map ) {
00041         $map = array_filter( $map, function( $w ) { return $w > 0; } );
00042         if ( !count( $map ) ) {
00043             throw new MWException( "Ring is empty or all weights are zero." );
00044         }
00045         $this->sourceMap = $map;
00046         // Sort the locations based on the hash of their names
00047         $hashes = array();
00048         foreach ( $map as $location => $weight ) {
00049             $hashes[$location] = sha1( $location );
00050         }
00051         uksort( $map, function ( $a, $b ) use ( $hashes ) {
00052             return strcmp( $hashes[$a], $hashes[$b] );
00053         } );
00054         // Fit the map to weight-proportionate one with a space of size RING_SIZE
00055         $sum = array_sum( $map );
00056         $standardMap = array();
00057         foreach ( $map as $location => $weight ) {
00058             $standardMap[$location] = (int)floor( $weight / $sum * self::RING_SIZE );
00059         }
00060         // Build a ring of RING_SIZE spots, with each location at a spot in location hash order
00061         $index = 0;
00062         foreach ( $standardMap as $location => $weight ) {
00063             // Location covers half-closed interval [$index,$index + $weight)
00064             $this->ring[$location] = array( $index, $index + $weight );
00065             $index += $weight;
00066         }
00067         // Make sure the last location covers what is left
00068         end( $this->ring );
00069         $this->ring[key( $this->ring )][1] = self::RING_SIZE;
00070     }
00071 
00078     public function getLocation( $item ) {
00079         $locations = $this->getLocations( $item, 1 );
00080         return $locations[0];
00081     }
00082 
00090     public function getLocations( $item, $limit ) {
00091         $locations = array();
00092         $primaryLocation = null;
00093         $spot = hexdec( substr( sha1( $item ), 0, 7 ) ); // first 28 bits
00094         foreach ( $this->ring as $location => $range ) {
00095             if ( count( $locations ) >= $limit ) {
00096                 break;
00097             }
00098             // The $primaryLocation is the location the item spot is in.
00099             // After that is reached, keep appending the next locations.
00100             if ( ( $range[0] <= $spot && $spot < $range[1] ) || $primaryLocation !== null ) {
00101                 if ( $primaryLocation === null ) {
00102                     $primaryLocation = $location;
00103                 }
00104                 $locations[] = $location;
00105             }
00106         }
00107         // If more locations are requested, wrap-around and keep adding them
00108         reset( $this->ring );
00109         while ( count( $locations ) < $limit ) {
00110             list( $location, ) = each( $this->ring );
00111             if ( $location === $primaryLocation ) {
00112                 break; // don't go in circles
00113             }
00114             $locations[] = $location;
00115         }
00116         return $locations;
00117     }
00118 
00124     public function getLocationWeights() {
00125         return $this->sourceMap;
00126     }
00127 
00134     public function newWithoutLocation( $location ) {
00135         $map = $this->sourceMap;
00136         unset( $map[$location] );
00137         if ( count( $map ) ) {
00138             return new self( $map );
00139         }
00140         return false;
00141     }
00142 }