tests/phpunit/includes/libs/HashRingTest.php

   1 <?php
   2
   3 /**
   4  * @group HashRing
   5  * @covers HashRing
   6  */
   7 class HashRingTest extends PHPUnit\Framework\TestCase {
   8
   9         use MediaWikiCoversValidator;
  10
  11         public function testHashRingSerialize() {
  12                 $map = [ 's1' => 3, 's2' => 10, 's3' => 2, 's4' => 10, 's5' => 2, 's6' => 3 ];
  13                 $ring = new HashRing( $map, 'md5' );
  14
  15                 $serialized = serialize( $ring );
  16                 $ringRemade = unserialize( $serialized );
  17
  18                 for ( $i = 0; $i < 100; $i++ ) {
  19                         $this->assertEquals(
  20                                 $ring->getLocation( "hello$i" ),
  21                                 $ringRemade->getLocation( "hello$i" ),
  22                                 'Items placed at proper locations'
  23                         );
  24                 }
  25         }
  26
  27         public function testHashRingMapping() {
  28                 // SHA-1 based and weighted
  29                 $ring = new HashRing(
  30                         [ 's1' => 1, 's2' => 1, 's3' => 2, 's4' => 2, 's5' => 2, 's6' => 3, 's7' => 0 ],
  31                         'sha1'
  32                 );
  33
  34                 $this->assertEquals(
  35                         [ 's1' => 1, 's2' => 1, 's3' => 2, 's4' => 2, 's5' => 2, 's6' => 3 ],
  36                         $ring->getLocationWeights(),
  37                         'Normalized location weights'
  38                 );
  39
  40                 $this->assertEquals( null, $ring->getLastNodeScanSize() );
  41
  42                 $locations = [];
  43                 for ( $i = 0; $i < 25; $i++ ) {
  44                         $locations[ "hello$i"] = $ring->getLocation( "hello$i" );
  45                 }
  46                 $expectedLocations = [
  47                         "hello0" => "s4",
  48                         "hello1" => "s6",
  49                         "hello2" => "s3",
  50                         "hello3" => "s6",
  51                         "hello4" => "s6",
  52                         "hello5" => "s4",
  53                         "hello6" => "s3",
  54                         "hello7" => "s4",
  55                         "hello8" => "s3",
  56                         "hello9" => "s3",
  57                         "hello10" => "s3",
  58                         "hello11" => "s5",
  59                         "hello12" => "s4",
  60                         "hello13" => "s5",
  61                         "hello14" => "s2",
  62                         "hello15" => "s5",
  63                         "hello16" => "s6",
  64                         "hello17" => "s5",
  65                         "hello18" => "s1",
  66                         "hello19" => "s1",
  67                         "hello20" => "s6",
  68                         "hello21" => "s5",
  69                         "hello22" => "s3",
  70                         "hello23" => "s4",
  71                         "hello24" => "s1"
  72                 ];
  73                 $this->assertEquals( $expectedLocations, $locations, 'Items placed at proper locations' );
  74
  75                 $locations = [];
  76                 for ( $i = 0; $i < 5; $i++ ) {
  77                         $locations[ "hello$i"] = $ring->getLocations( "hello$i", 2 );
  78                 }
  79
  80                 $expectedLocations = [
  81                         "hello0" => [ "s4", "s5" ],
  82                         "hello1" => [ "s6", "s5" ],
  83                         "hello2" => [ "s3", "s1" ],
  84                         "hello3" => [ "s6", "s5" ],
  85                         "hello4" => [ "s6", "s3" ],
  86                 ];
  87                 $this->assertEquals( $expectedLocations, $locations, 'Items placed at proper locations' );
  88         }
  89
  90         /**
  91          * @dataProvider providor_getHashLocationWeights
  92          */
  93         public function testHashRingRatios( $locations, $expectedHits ) {
  94                 $ring = new HashRing( $locations, 'whirlpool' );
  95
  96                 $locationStats = array_fill_keys( array_keys( $locations ), 0 );
  97                 for ( $i = 0; $i < 10000; ++$i ) {
  98                         ++$locationStats[$ring->getLocation( "key-$i" )];
  99                 }
 100                 $this->assertEquals( $expectedHits, $locationStats );
 101         }
 102
 103         public static function providor_getHashLocationWeights() {
 104                 return [
 105                         [
 106                                 [ 'big' => 10, 'medium' => 5, 'small' => 1 ],
 107                                 [ 'big' => 6037, 'medium' => 3314, 'small' => 649 ]
 108                         ]
 109                 ];
 110         }
 111
 112         /**
 113          * @dataProvider providor_getHashLocationWeights2
 114          */
 115         public function testHashRingRatios2( $locations, $expected ) {
 116                 $ring = new HashRing( $locations, 'sha1' );
 117                 $locationStats = array_fill_keys( array_keys( $locations ), 0 );
 118                 for ( $i = 0; $i < 1000; ++$i ) {
 119                         foreach ( $ring->getLocations( "key-$i", 3 ) as $location ) {
 120                                 ++$locationStats[$location];
 121                         }
 122                 }
 123                 $this->assertEquals( $expected, $locationStats );
 124         }
 125
 126         public static function providor_getHashLocationWeights2() {
 127                 return [
 128                         [
 129                                 [ 'big1' => 10, 'big2' => 10, 'big3' => 10, 'small1' => 1, 'small2' => 1 ],
 130                                 [ 'big1' => 929, 'big2' => 899, 'big3' => 887, 'small1' => 143, 'small2' => 142 ]
 131                         ]
 132                 ];
 133         }
 134
 135         public function testBigHashRingRatios() {
 136                 $locations = [];
 137                 for ( $i = 0; $i < 128; ++$i ) {
 138                         $locations["server$i"] = 100;
 139                 }
 140
 141                 $ring = new HashRing( $locations, 'md5' );
 142
 143                 $scans = [];
 144                 for ( $i = 0; $i < 1000; ++$i ) {
 145                         $ring->getLocation( "item$i" );
 146                         $scans[] = $ring->getLastNodeScanSize();
 147                 }
 148
 149                 $this->assertEquals( 1, min( $scans ) );
 150                 $this->assertEquals( 24, max( $scans ) );
 151                 // Note: log2( 140 * 128) = 14.129 (e.g. divide & conquer)
 152                 $this->assertEquals( 4.4, round( array_sum( $scans ) / count( $scans ), 1 ) );
 153         }
 154
 155         public function testHashRingEjection() {
 156                 $map = [ 's1' => 5, 's2' => 5, 's3' => 10, 's4' => 10, 's5' => 5, 's6' => 5 ];
 157                 $ring = new HashRing( $map, 'md5' );
 158
 159                 $ring->ejectFromLiveRing( 's3', 30 );
 160                 $ring->ejectFromLiveRing( 's6', 15 );
 161
 162                 $this->assertEquals(
 163                         [ 's1' => 5, 's2' => 5, 's4' => 10, 's5' => 5 ],
 164                         $ring->getLiveLocationWeights(),
 165                         'Live location weights'
 166                 );
 167
 168                 for ( $i = 0; $i < 100; ++$i ) {
 169                         $key = "key-$i";
 170
 171                         $this->assertNotEquals( 's3', $ring->getLiveLocation( $key ), 'ejected' );
 172                         $this->assertNotEquals( 's6', $ring->getLiveLocation( $key ), 'ejected' );
 173
 174                         if ( !in_array( $ring->getLocation( $key ), [ 's3', 's6' ], true ) ) {
 175                                 $this->assertEquals(
 176                                         $ring->getLocation( $key ),
 177                                         $ring->getLiveLocation( $key ),
 178                                         "Live ring otherwise matches (#$i)"
 179                                 );
 180                                 $this->assertEquals(
 181                                         $ring->getLocations( $key, 1 ),
 182                                         $ring->getLiveLocations( $key, 1 ),
 183                                         "Live ring otherwise matches (#$i)"
 184                                 );
 185                         }
 186                 }
 187         }
 188
 189         public function testHashRingCollision() {
 190                 $ring1 = new HashRing( [ 0 => 1, 6497 => 1 ] );
 191                 $ring2 = new HashRing( [ 6497 => 1, 0 => 1 ] );
 192
 193                 for ( $i = 0; $i < 100; ++$i ) {
 194                         $this->assertEquals( $ring1->getLocation( $i ), $ring2->getLocation( $i ) );
 195                 }
 196         }
 197
 198         public function testHashRingKetamaMode() {
 199                 // Same as https://github.com/RJ/ketama/blob/master/ketama.servers
 200                 $map = [
 201                         '10.0.1.1:11211' => 600,
 202                         '10.0.1.2:11211' => 300,
 203                         '10.0.1.3:11211' => 200,
 204                         '10.0.1.4:11211' => 350,
 205                         '10.0.1.5:11211' => 1000,
 206                         '10.0.1.6:11211' => 800,
 207                         '10.0.1.7:11211' => 950,
 208                         '10.0.1.8:11211' => 100
 209                 ];
 210                 $ring = new HashRing( $map, 'md5' );
 211                 $wrapper = \Wikimedia\TestingAccessWrapper::newFromObject( $ring );
 212
 213                 $ketama_test = function ( $count ) use ( $wrapper ) {
 214                         $baseRing = $wrapper->baseRing;
 215
 216                         $lines = [];
 217                         for ( $key = 0; $key < $count; ++$key ) {
 218                                 $location = $wrapper->getLocation( $key );
 219
 220                                 $itemPos = $wrapper->getItemPosition( $key );
 221                                 $guess = $wrapper->guessNodeIndexForPosition( $itemPos, $baseRing );
 222                                 $nodeIndex = $wrapper->findNodeIndexForPosition( $itemPos, $guess, $baseRing );
 223                                 $nodePos = $baseRing[$nodeIndex][HashRing::KEY_POS];
 224
 225                                 $lines[] = sprintf( "%u %u %s\n", $itemPos, $nodePos, $location );
 226                         }
 227
 228                         return "\n" . implode( '', $lines );
 229                 };
 230
 231                 // Known correct values generated from C code:
 232                 // https://github.com/RJ/ketama/blob/master/libketama/ketama_test.c
 233                 $expected = <<<EOT
 234
 235 2216742351 2217271743 10.0.1.1:11211
 236 943901380 949045552 10.0.1.5:11211
 237 2373066440 2374693370 10.0.1.6:11211
 238 2127088620 2130338203 10.0.1.6:11211
 239 2046197672 2051996197 10.0.1.7:11211
 240 2134629092 2135172435 10.0.1.1:11211
 241 470382870 472541453 10.0.1.7:11211
 242 1608782991 1609789509 10.0.1.3:11211
 243 2516119753 2520092206 10.0.1.2:11211
 244 3465331781 3466294492 10.0.1.4:11211
 245 1749342675 1753760600 10.0.1.5:11211
 246 1136464485 1137779711 10.0.1.1:11211
 247 3620997826 3621580689 10.0.1.7:11211
 248 283385029 285581365 10.0.1.6:11211
 249 2300818346 2302165654 10.0.1.5:11211
 250 2132603803 2134614475 10.0.1.8:11211
 251 2962705863 2969767984 10.0.1.2:11211
 252 786427760 786565633 10.0.1.5:11211
 253 4095887727 4096760944 10.0.1.6:11211
 254 2906459679 2906987515 10.0.1.6:11211
 255 137884056 138922607 10.0.1.4:11211
 256 81549628 82491298 10.0.1.6:11211
 257 3530020790 3530525869 10.0.1.6:11211
 258 4231817527 4234960467 10.0.1.7:11211
 259 2011099423 2014738083 10.0.1.7:11211
 260 107620750 120968799 10.0.1.6:11211
 261 3979113294 3981926993 10.0.1.4:11211
 262 273671938 276355738 10.0.1.4:11211
 263 4032816947 4033300359 10.0.1.5:11211
 264 464234862 466093615 10.0.1.1:11211
 265 3007059764 3007671127 10.0.1.5:11211
 266 542337729 542491760 10.0.1.7:11211
 267 4040385635 4044064727 10.0.1.5:11211
 268 3319802648 3320661601 10.0.1.7:11211
 269 1032153571 1035085391 10.0.1.1:11211
 270 3543939100 3545608820 10.0.1.5:11211
 271 3876899353 3885324049 10.0.1.2:11211
 272 3771318181 3773259708 10.0.1.8:11211
 273 3457906597 3459285639 10.0.1.5:11211
 274 3028975062 3031083168 10.0.1.7:11211
 275 244467158 250943416 10.0.1.5:11211
 276 1604785716 1609789509 10.0.1.3:11211
 277 3905343649 3905751132 10.0.1.1:11211
 278 1713497623 1725056963 10.0.1.5:11211
 279 1668356087 1668827816 10.0.1.5:11211
 280 3427369836 3438933308 10.0.1.1:11211
 281 2515850457 2520092206 10.0.1.2:11211
 282 3886138983 3887390208 10.0.1.1:11211
 283 4019334756 4023153300 10.0.1.8:11211
 284 1170561012 1170785765 10.0.1.7:11211
 285 1841809344 1848425105 10.0.1.6:11211
 286 973223976 973369204 10.0.1.1:11211
 287 358093210 359562433 10.0.1.6:11211
 288 378350808 380841931 10.0.1.5:11211
 289 4008477862 4012085095 10.0.1.7:11211
 290 1027226549 1028630030 10.0.1.6:11211
 291 2386583967 2387706118 10.0.1.1:11211
 292 522892146 524831677 10.0.1.7:11211
 293 3779194982 3788912803 10.0.1.5:11211
 294 3764731657 3771312500 10.0.1.7:11211
 295 184756999 187529415 10.0.1.6:11211
 296 838351231 845886003 10.0.1.3:11211
 297 2827220548 2828019973 10.0.1.6:11211
 298 3604721411 3607668249 10.0.1.6:11211
 299 472866282 475506254 10.0.1.5:11211
 300 2752268796 2754833471 10.0.1.5:11211
 301 1791464754 1795042583 10.0.1.7:11211
 302 3029359475 3031083168 10.0.1.7:11211
 303 3633378211 3639985542 10.0.1.6:11211
 304 3148267284 3149217023 10.0.1.6:11211
 305 163887996 166705043 10.0.1.7:11211
 306 3642803426 3649125922 10.0.1.7:11211
 307 3901799218 3902199881 10.0.1.7:11211
 308 418045394 425867331 10.0.1.6:11211
 309 346775981 348578169 10.0.1.6:11211
 310 368352208 372224616 10.0.1.7:11211
 311 2643711995 2644259911 10.0.1.5:11211
 312 2032983336 2033860601 10.0.1.6:11211
 313 3567842357 3572867530 10.0.1.2:11211
 314 1024982737 1028630030 10.0.1.6:11211
 315 933966832 938106828 10.0.1.7:11211
 316 2102520899 2103402846 10.0.1.7:11211
 317 3537205399 3538094881 10.0.1.7:11211
 318 2311233534 2314593262 10.0.1.1:11211
 319 2500514664 2503565236 10.0.1.7:11211
 320 1091958846 1093484995 10.0.1.6:11211
 321 3984972691 3987453644 10.0.1.1:11211
 322 2669994439 2670911201 10.0.1.4:11211
 323 2846111786 2846115813 10.0.1.5:11211
 324 1805010806 1808593732 10.0.1.8:11211
 325 1587024774 1587746378 10.0.1.5:11211
 326 3214549588 3215619351 10.0.1.2:11211
 327 1965214866 1970922428 10.0.1.7:11211
 328 1038671000 1040777775 10.0.1.7:11211
 329 820820468 823114475 10.0.1.6:11211
 330 2722835329 2723166435 10.0.1.5:11211
 331 1602053414 1604196066 10.0.1.5:11211
 332 1330835426 1335097278 10.0.1.5:11211
 333 556547565 557075710 10.0.1.4:11211
 334 2977587884 2978402952 10.0.1.1:11211
 335
 336 EOT;
 337
 338                 $this->assertEquals( $expected, $ketama_test( 100 ), 'Ketama mode (diff check)' );
 339
 340                 // Hash of known correct values from C code
 341                 $this->assertEquals(
 342                         'c69ac9eb7a8a630c0cded201cefeaace',
 343                         md5( $ketama_test( 1e5 ) ),
 344                         'Ketama mode (large, MD5 check)'
 345                 );
 346
 347                 // Slower, full upstream MD5 check, manually verified 3/21/2018
 348                 // $this->assertEquals( '5672b131391f5aa2b280936aec1eea74', md5( $ketama_test( 1e6 ) ) );
 349         }
 350 }