MediaWiki  master
HashRingTest.php
Go to the documentation of this file.
1 <?php
2 
8 
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  $locations = [];
41  for ( $i = 0; $i < 25; $i++ ) {
42  $locations[ "hello$i"] = $ring->getLocation( "hello$i" );
43  }
44  $expectedLocations = [
45  "hello0" => "s4",
46  "hello1" => "s6",
47  "hello2" => "s3",
48  "hello3" => "s6",
49  "hello4" => "s6",
50  "hello5" => "s4",
51  "hello6" => "s3",
52  "hello7" => "s4",
53  "hello8" => "s3",
54  "hello9" => "s3",
55  "hello10" => "s3",
56  "hello11" => "s5",
57  "hello12" => "s4",
58  "hello13" => "s5",
59  "hello14" => "s2",
60  "hello15" => "s5",
61  "hello16" => "s6",
62  "hello17" => "s5",
63  "hello18" => "s1",
64  "hello19" => "s1",
65  "hello20" => "s6",
66  "hello21" => "s5",
67  "hello22" => "s3",
68  "hello23" => "s4",
69  "hello24" => "s1"
70  ];
71  $this->assertEquals( $expectedLocations, $locations, 'Items placed at proper locations' );
72 
73  $locations = [];
74  for ( $i = 0; $i < 5; $i++ ) {
75  $locations[ "hello$i"] = $ring->getLocations( "hello$i", 2 );
76  }
77 
78  $expectedLocations = [
79  "hello0" => [ "s4", "s5" ],
80  "hello1" => [ "s6", "s5" ],
81  "hello2" => [ "s3", "s1" ],
82  "hello3" => [ "s6", "s5" ],
83  "hello4" => [ "s6", "s3" ],
84  ];
85  $this->assertEquals( $expectedLocations, $locations, 'Items placed at proper locations' );
86  }
87 
91  public function testHashRingRatios( $locations, $expectedHits ) {
92  $ring = new HashRing( $locations, 'whirlpool' );
93 
94  $locationStats = array_fill_keys( array_keys( $locations ), 0 );
95  for ( $i = 0; $i < 10000; ++$i ) {
96  ++$locationStats[$ring->getLocation( "key-$i" )];
97  }
98  $this->assertEquals( $expectedHits, $locationStats );
99  }
100 
101  public static function providor_getHashLocationWeights() {
102  return [
103  [
104  [ 'big' => 10, 'medium' => 5, 'small' => 1 ],
105  [ 'big' => 6037, 'medium' => 3314, 'small' => 649 ]
106  ]
107  ];
108  }
109 
113  public function testHashRingRatios2( $locations, $expected ) {
114  $ring = new HashRing( $locations, 'sha1' );
115  $locationStats = array_fill_keys( array_keys( $locations ), 0 );
116  for ( $i = 0; $i < 1000; ++$i ) {
117  foreach ( $ring->getLocations( "key-$i", 3 ) as $location ) {
118  ++$locationStats[$location];
119  }
120  }
121  $this->assertEquals( $expected, $locationStats );
122  }
123 
124  public static function providor_getHashLocationWeights2() {
125  return [
126  [
127  [ 'big1' => 10, 'big2' => 10, 'big3' => 10, 'small1' => 1, 'small2' => 1 ],
128  [ 'big1' => 929, 'big2' => 899, 'big3' => 887, 'small1' => 143, 'small2' => 142 ]
129  ]
130  ];
131  }
132 
133  public function testHashRingEjection() {
134  $map = [ 's1' => 5, 's2' => 5, 's3' => 10, 's4' => 10, 's5' => 5, 's6' => 5 ];
135  $ring = new HashRing( $map, 'md5' );
136 
137  $ring->ejectFromLiveRing( 's3', 30 );
138  $ring->ejectFromLiveRing( 's6', 15 );
139 
140  $this->assertEquals(
141  [ 's1' => 5, 's2' => 5, 's4' => 10, 's5' => 5 ],
142  $ring->getLiveLocationWeights(),
143  'Live location weights'
144  );
145 
146  for ( $i = 0; $i < 100; ++$i ) {
147  $key = "key-$i";
148 
149  $this->assertNotEquals( 's3', $ring->getLiveLocation( $key ), 'ejected' );
150  $this->assertNotEquals( 's6', $ring->getLiveLocation( $key ), 'ejected' );
151 
152  if ( !in_array( $ring->getLocation( $key ), [ 's3', 's6' ], true ) ) {
153  $this->assertEquals(
154  $ring->getLocation( $key ),
155  $ring->getLiveLocation( $key ),
156  "Live ring otherwise matches (#$i)"
157  );
158  $this->assertEquals(
159  $ring->getLocations( $key, 1 ),
160  $ring->getLiveLocations( $key, 1 ),
161  "Live ring otherwise matches (#$i)"
162  );
163  }
164  }
165  }
166 
167  public function testHashRingCollision() {
168  $ring1 = new HashRing( [ 0 => 1, 6497 => 1 ] );
169  $ring2 = new HashRing( [ 6497 => 1, 0 => 1 ] );
170 
171  for ( $i = 0; $i < 100; ++$i ) {
172  $this->assertEquals( $ring1->getLocation( $i ), $ring2->getLocation( $i ) );
173  }
174  }
175 
176  public function testHashRingKetamaMode() {
177  // Same as https://github.com/RJ/ketama/blob/master/ketama.servers
178  $map = [
179  '10.0.1.1:11211' => 600,
180  '10.0.1.2:11211' => 300,
181  '10.0.1.3:11211' => 200,
182  '10.0.1.4:11211' => 350,
183  '10.0.1.5:11211' => 1000,
184  '10.0.1.6:11211' => 800,
185  '10.0.1.7:11211' => 950,
186  '10.0.1.8:11211' => 100
187  ];
188  $ring = new HashRing( $map, 'md5' );
189  $wrapper = \Wikimedia\TestingAccessWrapper::newFromObject( $ring );
190 
191  $ketama_test = function ( $count ) use ( $wrapper ) {
192  $baseRing = $wrapper->baseRing;
193 
194  $lines = [];
195  for ( $key = 0; $key < $count; ++$key ) {
196  $location = $wrapper->getLocation( $key );
197 
198  $itemPos = $wrapper->getItemPosition( $key );
199  $nodeIndex = $wrapper->findNodeIndexForPosition( $itemPos, $baseRing );
200  $nodePos = $baseRing[$nodeIndex][HashRing::KEY_POS];
201 
202  $lines[] = sprintf( "%u %u %s\n", $itemPos, $nodePos, $location );
203  }
204 
205  return "\n" . implode( '', $lines );
206  };
207 
208  // Known correct values generated from C code:
209  // https://github.com/RJ/ketama/blob/master/libketama/ketama_test.c
210  $expected = <<<EOT
211 
212 2216742351 2217271743 10.0.1.1:11211
213 943901380 949045552 10.0.1.5:11211
214 2373066440 2374693370 10.0.1.6:11211
215 2127088620 2130338203 10.0.1.6:11211
216 2046197672 2051996197 10.0.1.7:11211
217 2134629092 2135172435 10.0.1.1:11211
218 470382870 472541453 10.0.1.7:11211
219 1608782991 1609789509 10.0.1.3:11211
220 2516119753 2520092206 10.0.1.2:11211
221 3465331781 3466294492 10.0.1.4:11211
222 1749342675 1753760600 10.0.1.5:11211
223 1136464485 1137779711 10.0.1.1:11211
224 3620997826 3621580689 10.0.1.7:11211
225 283385029 285581365 10.0.1.6:11211
226 2300818346 2302165654 10.0.1.5:11211
227 2132603803 2134614475 10.0.1.8:11211
228 2962705863 2969767984 10.0.1.2:11211
229 786427760 786565633 10.0.1.5:11211
230 4095887727 4096760944 10.0.1.6:11211
231 2906459679 2906987515 10.0.1.6:11211
232 137884056 138922607 10.0.1.4:11211
233 81549628 82491298 10.0.1.6:11211
234 3530020790 3530525869 10.0.1.6:11211
235 4231817527 4234960467 10.0.1.7:11211
236 2011099423 2014738083 10.0.1.7:11211
237 107620750 120968799 10.0.1.6:11211
238 3979113294 3981926993 10.0.1.4:11211
239 273671938 276355738 10.0.1.4:11211
240 4032816947 4033300359 10.0.1.5:11211
241 464234862 466093615 10.0.1.1:11211
242 3007059764 3007671127 10.0.1.5:11211
243 542337729 542491760 10.0.1.7:11211
244 4040385635 4044064727 10.0.1.5:11211
245 3319802648 3320661601 10.0.1.7:11211
246 1032153571 1035085391 10.0.1.1:11211
247 3543939100 3545608820 10.0.1.5:11211
248 3876899353 3885324049 10.0.1.2:11211
249 3771318181 3773259708 10.0.1.8:11211
250 3457906597 3459285639 10.0.1.5:11211
251 3028975062 3031083168 10.0.1.7:11211
252 244467158 250943416 10.0.1.5:11211
253 1604785716 1609789509 10.0.1.3:11211
254 3905343649 3905751132 10.0.1.1:11211
255 1713497623 1725056963 10.0.1.5:11211
256 1668356087 1668827816 10.0.1.5:11211
257 3427369836 3438933308 10.0.1.1:11211
258 2515850457 2520092206 10.0.1.2:11211
259 3886138983 3887390208 10.0.1.1:11211
260 4019334756 4023153300 10.0.1.8:11211
261 1170561012 1170785765 10.0.1.7:11211
262 1841809344 1848425105 10.0.1.6:11211
263 973223976 973369204 10.0.1.1:11211
264 358093210 359562433 10.0.1.6:11211
265 378350808 380841931 10.0.1.5:11211
266 4008477862 4012085095 10.0.1.7:11211
267 1027226549 1028630030 10.0.1.6:11211
268 2386583967 2387706118 10.0.1.1:11211
269 522892146 524831677 10.0.1.7:11211
270 3779194982 3788912803 10.0.1.5:11211
271 3764731657 3771312500 10.0.1.7:11211
272 184756999 187529415 10.0.1.6:11211
273 838351231 845886003 10.0.1.3:11211
274 2827220548 2828019973 10.0.1.6:11211
275 3604721411 3607668249 10.0.1.6:11211
276 472866282 475506254 10.0.1.5:11211
277 2752268796 2754833471 10.0.1.5:11211
278 1791464754 1795042583 10.0.1.7:11211
279 3029359475 3031083168 10.0.1.7:11211
280 3633378211 3639985542 10.0.1.6:11211
281 3148267284 3149217023 10.0.1.6:11211
282 163887996 166705043 10.0.1.7:11211
283 3642803426 3649125922 10.0.1.7:11211
284 3901799218 3902199881 10.0.1.7:11211
285 418045394 425867331 10.0.1.6:11211
286 346775981 348578169 10.0.1.6:11211
287 368352208 372224616 10.0.1.7:11211
288 2643711995 2644259911 10.0.1.5:11211
289 2032983336 2033860601 10.0.1.6:11211
290 3567842357 3572867530 10.0.1.2:11211
291 1024982737 1028630030 10.0.1.6:11211
292 933966832 938106828 10.0.1.7:11211
293 2102520899 2103402846 10.0.1.7:11211
294 3537205399 3538094881 10.0.1.7:11211
295 2311233534 2314593262 10.0.1.1:11211
296 2500514664 2503565236 10.0.1.7:11211
297 1091958846 1093484995 10.0.1.6:11211
298 3984972691 3987453644 10.0.1.1:11211
299 2669994439 2670911201 10.0.1.4:11211
300 2846111786 2846115813 10.0.1.5:11211
301 1805010806 1808593732 10.0.1.8:11211
302 1587024774 1587746378 10.0.1.5:11211
303 3214549588 3215619351 10.0.1.2:11211
304 1965214866 1970922428 10.0.1.7:11211
305 1038671000 1040777775 10.0.1.7:11211
306 820820468 823114475 10.0.1.6:11211
307 2722835329 2723166435 10.0.1.5:11211
308 1602053414 1604196066 10.0.1.5:11211
309 1330835426 1335097278 10.0.1.5:11211
310 556547565 557075710 10.0.1.4:11211
311 2977587884 2978402952 10.0.1.1:11211
312 
313 EOT;
314 
315  $this->assertEquals( $expected, $ketama_test( 100 ), 'Ketama mode (diff check)' );
316 
317  // Hash of known correct values from C code
318  $this->assertEquals(
319  'c69ac9eb7a8a630c0cded201cefeaace',
320  md5( $ketama_test( 1e5 ) ),
321  'Ketama mode (large, MD5 check)'
322  );
323 
324  // Slower, full upstream MD5 check, manually verified 3/21/2018
325  // $this->assertEquals( '5672b131391f5aa2b280936aec1eea74', md5( $ketama_test( 1e6 ) ) );
326  }
327 }
serialize()
Apache License January AND DISTRIBUTION Definitions License shall mean the terms and conditions for use
const KEY_POS
Definition: HashRing.php:59
static providor_getHashLocationWeights2()
static providor_getHashLocationWeights()
null means default in associative array with keys and values unescaped Should be merged with default with a value of false meaning to suppress the attribute in associative array with keys and values unescaped noclasses just before the function returns a value If you return true
Definition: hooks.txt:1982
Convenience class for weighted consistent hash rings.
Definition: HashRing.php:39
unserialize( $serialized)
This document is intended to provide useful advice for parties seeking to redistribute MediaWiki to end users It s targeted particularly at maintainers for Linux since it s been observed that distribution packages of MediaWiki often break We ve consistently had to recommend that users seeking support use official tarballs instead of their distribution s and this often solves whatever problem the user is having It would be nice if this could such as
Definition: distributors.txt:9
injection txt This is an overview of how MediaWiki makes use of dependency injection The design described here grew from the discussion of RFC T384 The term dependency this means that anything an object needs to operate should be injected from the the object itself should only know narrow no concrete implementation of the logic it relies on The requirement to inject everything typically results in an architecture that based on two main types of and essentially stateless service objects that use other service objects to operate on the value objects As of the beginning MediaWiki is only starting to use the DI approach Much of the code still relies on global state or direct resulting in a highly cyclical dependency which acts as the top level factory for services in MediaWiki which can be used to gain access to default instances of various services MediaWikiServices however also allows new services to be defined and default services to be redefined Services are defined or redefined by providing a callback the instantiator that will return a new instance of the service When it will create an instance of MediaWikiServices and populate it with the services defined in the files listed by thereby bootstrapping the DI framework Per $wgServiceWiringFiles lists includes ServiceWiring php
Definition: injection.txt:35
$lines
Definition: router.php:61
testHashRingRatios( $locations, $expectedHits)
providor_getHashLocationWeights
HashRing HashRing.
Definition: HashRingTest.php:7
foreach( $res as $row) $serialized
testHashRingRatios2( $locations, $expected)
providor_getHashLocationWeights2