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