Merge branch '16325-test-container-collection-properties'
[arvados.git] / services / keep-balance / balance_test.go
1 // Copyright (C) The Arvados Authors. All rights reserved.
2 //
3 // SPDX-License-Identifier: AGPL-3.0
4
5 package keepbalance
6
7 import (
8         "crypto/md5"
9         "fmt"
10         "sort"
11         "strconv"
12         "testing"
13         "time"
14
15         "git.arvados.org/arvados.git/sdk/go/arvados"
16         "git.arvados.org/arvados.git/sdk/go/ctxlog"
17         check "gopkg.in/check.v1"
18 )
19
20 // Test with Gocheck
21 func Test(t *testing.T) {
22         check.TestingT(t)
23 }
24
25 var _ = check.Suite(&balancerSuite{})
26
27 type balancerSuite struct {
28         Balancer
29         srvs            []*KeepService
30         blks            map[string]tester
31         knownRendezvous [][]int
32         signatureTTL    int64
33 }
34
35 const (
36         // index into knownRendezvous
37         known0 = 0
38 )
39
40 type slots []int
41
42 type tester struct {
43         known       int
44         desired     map[string]int
45         current     slots
46         timestamps  []int64
47         shouldPull  slots
48         shouldTrash slots
49
50         shouldPullMounts  []string
51         shouldTrashMounts []string
52
53         expectBlockState *balancedBlockState
54         expectClassState map[string]balancedBlockState
55 }
56
57 func (bal *balancerSuite) SetUpSuite(c *check.C) {
58         bal.knownRendezvous = nil
59         for _, str := range []string{
60                 "3eab2d5fc9681074",
61                 "097dba52e648f1c3",
62                 "c5b4e023f8a7d691",
63                 "9d81c02e76a3bf54",
64         } {
65                 var slots []int
66                 for _, c := range []byte(str) {
67                         pos, _ := strconv.ParseUint(string(c), 16, 4)
68                         slots = append(slots, int(pos))
69                 }
70                 bal.knownRendezvous = append(bal.knownRendezvous, slots)
71         }
72
73         bal.signatureTTL = 3600
74         bal.Logger = ctxlog.TestLogger(c)
75 }
76
77 func (bal *balancerSuite) SetUpTest(c *check.C) {
78         bal.srvs = make([]*KeepService, 16)
79         bal.KeepServices = make(map[string]*KeepService)
80         for i := range bal.srvs {
81                 srv := &KeepService{
82                         KeepService: arvados.KeepService{
83                                 UUID: fmt.Sprintf("zzzzz-bi6l4-%015x", i),
84                         },
85                 }
86                 srv.mounts = []*KeepMount{{
87                         KeepMount: arvados.KeepMount{
88                                 UUID:           fmt.Sprintf("zzzzz-mount-%015x", i),
89                                 StorageClasses: map[string]bool{"default": true},
90                         },
91                         KeepService: srv,
92                 }}
93                 bal.srvs[i] = srv
94                 bal.KeepServices[srv.UUID] = srv
95         }
96
97         bal.MinMtime = time.Now().UnixNano() - bal.signatureTTL*1e9
98         bal.cleanupMounts()
99 }
100
101 func (bal *balancerSuite) TestPerfect(c *check.C) {
102         bal.try(c, tester{
103                 desired:     map[string]int{"default": 2},
104                 current:     slots{0, 1},
105                 shouldPull:  nil,
106                 shouldTrash: nil,
107                 expectBlockState: &balancedBlockState{
108                         needed: 2,
109                 }})
110 }
111
112 func (bal *balancerSuite) TestDecreaseRepl(c *check.C) {
113         bal.try(c, tester{
114                 desired:     map[string]int{"default": 2},
115                 current:     slots{0, 2, 1},
116                 shouldTrash: slots{2},
117                 expectBlockState: &balancedBlockState{
118                         needed:   2,
119                         unneeded: 1,
120                 }})
121 }
122
123 func (bal *balancerSuite) TestDecreaseReplToZero(c *check.C) {
124         bal.try(c, tester{
125                 desired:     map[string]int{"default": 0},
126                 current:     slots{0, 1, 3},
127                 shouldTrash: slots{0, 1, 3},
128                 expectBlockState: &balancedBlockState{
129                         unneeded: 3,
130                 }})
131 }
132
133 func (bal *balancerSuite) TestIncreaseRepl(c *check.C) {
134         bal.try(c, tester{
135                 desired:    map[string]int{"default": 4},
136                 current:    slots{0, 1},
137                 shouldPull: slots{2, 3},
138                 expectBlockState: &balancedBlockState{
139                         needed:  2,
140                         pulling: 2,
141                 }})
142 }
143
144 func (bal *balancerSuite) TestSkipReadonly(c *check.C) {
145         bal.srvList(0, slots{3})[0].ReadOnly = true
146         bal.try(c, tester{
147                 desired:    map[string]int{"default": 4},
148                 current:    slots{0, 1},
149                 shouldPull: slots{2, 4},
150                 expectBlockState: &balancedBlockState{
151                         needed:  2,
152                         pulling: 2,
153                 }})
154 }
155
156 func (bal *balancerSuite) TestMultipleViewsReadOnly(c *check.C) {
157         bal.testMultipleViews(c, true)
158 }
159
160 func (bal *balancerSuite) TestMultipleViews(c *check.C) {
161         bal.testMultipleViews(c, false)
162 }
163
164 func (bal *balancerSuite) testMultipleViews(c *check.C, readonly bool) {
165         for i, srv := range bal.srvs {
166                 // Add a mount to each service
167                 srv.mounts[0].KeepMount.DeviceID = fmt.Sprintf("writable-by-srv-%x", i)
168                 srv.mounts = append(srv.mounts, &KeepMount{
169                         KeepMount: arvados.KeepMount{
170                                 DeviceID:       bal.srvs[(i+1)%len(bal.srvs)].mounts[0].KeepMount.DeviceID,
171                                 UUID:           bal.srvs[(i+1)%len(bal.srvs)].mounts[0].KeepMount.UUID,
172                                 ReadOnly:       readonly,
173                                 Replication:    1,
174                                 StorageClasses: map[string]bool{"default": true},
175                         },
176                         KeepService: srv,
177                 })
178         }
179         for i := 1; i < len(bal.srvs); i++ {
180                 c.Logf("i=%d", i)
181                 if i == 4 {
182                         // Timestamps are all different, but one of
183                         // the mounts on srv[4] has the same device ID
184                         // where the non-deletable replica is stored
185                         // on srv[3], so only one replica is safe to
186                         // trash.
187                         bal.try(c, tester{
188                                 desired:     map[string]int{"default": 1},
189                                 current:     slots{0, i, i},
190                                 shouldTrash: slots{i}})
191                 } else if readonly {
192                         // Timestamps are all different, and the third
193                         // replica can't be trashed because it's on a
194                         // read-only mount, so the first two replicas
195                         // should be trashed.
196                         bal.try(c, tester{
197                                 desired:     map[string]int{"default": 1},
198                                 current:     slots{0, i, i},
199                                 shouldTrash: slots{0, i}})
200                 } else {
201                         // Timestamps are all different, so both
202                         // replicas on the non-optimal server should
203                         // be trashed.
204                         bal.try(c, tester{
205                                 desired:     map[string]int{"default": 1},
206                                 current:     slots{0, i, i},
207                                 shouldTrash: slots{i, i}})
208                 }
209                 // If the three replicas have identical timestamps,
210                 // none of them can be trashed safely.
211                 bal.try(c, tester{
212                         desired:    map[string]int{"default": 1},
213                         current:    slots{0, i, i},
214                         timestamps: []int64{12345678, 12345678, 12345678}})
215                 // If the first and third replicas have identical
216                 // timestamps, only the second replica should be
217                 // trashed.
218                 bal.try(c, tester{
219                         desired:     map[string]int{"default": 1},
220                         current:     slots{0, i, i},
221                         timestamps:  []int64{12345678, 12345679, 12345678},
222                         shouldTrash: slots{i}})
223         }
224 }
225
226 func (bal *balancerSuite) TestFixUnbalanced(c *check.C) {
227         bal.try(c, tester{
228                 desired:    map[string]int{"default": 2},
229                 current:    slots{2, 0},
230                 shouldPull: slots{1}})
231         bal.try(c, tester{
232                 desired:    map[string]int{"default": 2},
233                 current:    slots{2, 7},
234                 shouldPull: slots{0, 1}})
235         // if only one of the pulls succeeds, we'll see this next:
236         bal.try(c, tester{
237                 desired:     map[string]int{"default": 2},
238                 current:     slots{2, 1, 7},
239                 shouldPull:  slots{0},
240                 shouldTrash: slots{7}})
241         // if both pulls succeed, we'll see this next:
242         bal.try(c, tester{
243                 desired:     map[string]int{"default": 2},
244                 current:     slots{2, 0, 1, 7},
245                 shouldTrash: slots{2, 7}})
246
247         // unbalanced + excessive replication => pull + trash
248         bal.try(c, tester{
249                 desired:     map[string]int{"default": 2},
250                 current:     slots{2, 5, 7},
251                 shouldPull:  slots{0, 1},
252                 shouldTrash: slots{7}})
253 }
254
255 func (bal *balancerSuite) TestMultipleReplicasPerService(c *check.C) {
256         for s, srv := range bal.srvs {
257                 for i := 0; i < 3; i++ {
258                         m := *(srv.mounts[0])
259                         m.UUID = fmt.Sprintf("zzzzz-mount-%015x", (s<<10)+i)
260                         srv.mounts = append(srv.mounts, &m)
261                 }
262         }
263         bal.try(c, tester{
264                 desired:    map[string]int{"default": 2},
265                 current:    slots{0, 0},
266                 shouldPull: slots{1}})
267         bal.try(c, tester{
268                 desired:    map[string]int{"default": 2},
269                 current:    slots{2, 2},
270                 shouldPull: slots{0, 1}})
271         bal.try(c, tester{
272                 desired:     map[string]int{"default": 2},
273                 current:     slots{0, 0, 1},
274                 shouldTrash: slots{0}})
275         bal.try(c, tester{
276                 desired:     map[string]int{"default": 2},
277                 current:     slots{1, 1, 0},
278                 shouldTrash: slots{1}})
279         bal.try(c, tester{
280                 desired:     map[string]int{"default": 2},
281                 current:     slots{1, 0, 1, 0, 2},
282                 shouldTrash: slots{0, 1, 2}})
283         bal.try(c, tester{
284                 desired:     map[string]int{"default": 2},
285                 current:     slots{1, 1, 1, 0, 2},
286                 shouldTrash: slots{1, 1, 2}})
287         bal.try(c, tester{
288                 desired:     map[string]int{"default": 2},
289                 current:     slots{1, 1, 2},
290                 shouldPull:  slots{0},
291                 shouldTrash: slots{1}})
292         bal.try(c, tester{
293                 desired:     map[string]int{"default": 2},
294                 current:     slots{1, 1, 0},
295                 timestamps:  []int64{12345678, 12345678, 12345679},
296                 shouldTrash: nil})
297         bal.try(c, tester{
298                 desired:    map[string]int{"default": 2},
299                 current:    slots{1, 1},
300                 shouldPull: slots{0}})
301 }
302
303 func (bal *balancerSuite) TestIncreaseReplTimestampCollision(c *check.C) {
304         // For purposes of increasing replication, we assume identical
305         // replicas are distinct.
306         bal.try(c, tester{
307                 desired:    map[string]int{"default": 4},
308                 current:    slots{0, 1},
309                 timestamps: []int64{12345678, 12345678},
310                 shouldPull: slots{2, 3}})
311 }
312
313 func (bal *balancerSuite) TestDecreaseReplTimestampCollision(c *check.C) {
314         // For purposes of decreasing replication, we assume identical
315         // replicas are NOT distinct.
316         bal.try(c, tester{
317                 desired:    map[string]int{"default": 2},
318                 current:    slots{0, 1, 2},
319                 timestamps: []int64{12345678, 12345678, 12345678}})
320         bal.try(c, tester{
321                 desired:    map[string]int{"default": 2},
322                 current:    slots{0, 1, 2},
323                 timestamps: []int64{12345678, 10000000, 10000000}})
324 }
325
326 func (bal *balancerSuite) TestDecreaseReplBlockTooNew(c *check.C) {
327         oldTime := bal.MinMtime - 3600
328         newTime := bal.MinMtime + 3600
329         // The excess replica is too new to delete.
330         bal.try(c, tester{
331                 desired:    map[string]int{"default": 2},
332                 current:    slots{0, 1, 2},
333                 timestamps: []int64{oldTime, newTime, newTime + 1},
334                 expectBlockState: &balancedBlockState{
335                         needed:   2,
336                         unneeded: 1,
337                 }})
338         // The best replicas are too new to delete, but the excess
339         // replica is old enough.
340         bal.try(c, tester{
341                 desired:     map[string]int{"default": 2},
342                 current:     slots{0, 1, 2},
343                 timestamps:  []int64{newTime, newTime + 1, oldTime},
344                 shouldTrash: slots{2}})
345 }
346
347 func (bal *balancerSuite) TestCleanupMounts(c *check.C) {
348         bal.srvs[3].mounts[0].KeepMount.ReadOnly = true
349         bal.srvs[3].mounts[0].KeepMount.DeviceID = "abcdef"
350         bal.srvs[14].mounts[0].KeepMount.UUID = bal.srvs[3].mounts[0].KeepMount.UUID
351         bal.srvs[14].mounts[0].KeepMount.DeviceID = "abcdef"
352         c.Check(len(bal.srvs[3].mounts), check.Equals, 1)
353         bal.cleanupMounts()
354         c.Check(len(bal.srvs[3].mounts), check.Equals, 0)
355         bal.try(c, tester{
356                 known:      0,
357                 desired:    map[string]int{"default": 2},
358                 current:    slots{1},
359                 shouldPull: slots{2}})
360 }
361
362 func (bal *balancerSuite) TestVolumeReplication(c *check.C) {
363         bal.srvs[0].mounts[0].KeepMount.Replication = 2  // srv 0
364         bal.srvs[14].mounts[0].KeepMount.Replication = 2 // srv e
365         bal.cleanupMounts()
366         // block 0 rendezvous is 3,e,a -- so slot 1 has repl=2
367         bal.try(c, tester{
368                 known:      0,
369                 desired:    map[string]int{"default": 2},
370                 current:    slots{1},
371                 shouldPull: slots{0},
372                 expectBlockState: &balancedBlockState{
373                         needed:  1,
374                         pulling: 1,
375                 }})
376         bal.try(c, tester{
377                 known:      0,
378                 desired:    map[string]int{"default": 2},
379                 current:    slots{0, 1},
380                 shouldPull: nil,
381                 expectBlockState: &balancedBlockState{
382                         needed: 2,
383                 }})
384         bal.try(c, tester{
385                 known:       0,
386                 desired:     map[string]int{"default": 2},
387                 current:     slots{0, 1, 2},
388                 shouldTrash: slots{2},
389                 expectBlockState: &balancedBlockState{
390                         needed:   2,
391                         unneeded: 1,
392                 }})
393         bal.try(c, tester{
394                 known:       0,
395                 desired:     map[string]int{"default": 3},
396                 current:     slots{0, 2, 3, 4},
397                 shouldPull:  slots{1},
398                 shouldTrash: slots{4},
399                 expectBlockState: &balancedBlockState{
400                         needed:   3,
401                         unneeded: 1,
402                         pulling:  1,
403                 }})
404         bal.try(c, tester{
405                 known:       0,
406                 desired:     map[string]int{"default": 3},
407                 current:     slots{0, 1, 2, 3, 4},
408                 shouldTrash: slots{2, 3, 4},
409                 expectBlockState: &balancedBlockState{
410                         needed:   2,
411                         unneeded: 3,
412                 }})
413         bal.try(c, tester{
414                 known:       0,
415                 desired:     map[string]int{"default": 4},
416                 current:     slots{0, 1, 2, 3, 4},
417                 shouldTrash: slots{3, 4},
418                 expectBlockState: &balancedBlockState{
419                         needed:   3,
420                         unneeded: 2,
421                 }})
422         // block 1 rendezvous is 0,9,7 -- so slot 0 has repl=2
423         bal.try(c, tester{
424                 known:   1,
425                 desired: map[string]int{"default": 2},
426                 current: slots{0},
427                 expectBlockState: &balancedBlockState{
428                         needed: 1,
429                 }})
430         bal.try(c, tester{
431                 known:      1,
432                 desired:    map[string]int{"default": 3},
433                 current:    slots{0},
434                 shouldPull: slots{1},
435                 expectBlockState: &balancedBlockState{
436                         needed:  1,
437                         pulling: 1,
438                 }})
439         bal.try(c, tester{
440                 known:      1,
441                 desired:    map[string]int{"default": 4},
442                 current:    slots{0},
443                 shouldPull: slots{1, 2},
444                 expectBlockState: &balancedBlockState{
445                         needed:  1,
446                         pulling: 2,
447                 }})
448         bal.try(c, tester{
449                 known:      1,
450                 desired:    map[string]int{"default": 4},
451                 current:    slots{2},
452                 shouldPull: slots{0, 1},
453                 expectBlockState: &balancedBlockState{
454                         needed:  1,
455                         pulling: 2,
456                 }})
457         bal.try(c, tester{
458                 known:      1,
459                 desired:    map[string]int{"default": 4},
460                 current:    slots{7},
461                 shouldPull: slots{0, 1, 2},
462                 expectBlockState: &balancedBlockState{
463                         needed:  1,
464                         pulling: 3,
465                 }})
466         bal.try(c, tester{
467                 known:       1,
468                 desired:     map[string]int{"default": 2},
469                 current:     slots{1, 2, 3, 4},
470                 shouldPull:  slots{0},
471                 shouldTrash: slots{3, 4},
472                 expectBlockState: &balancedBlockState{
473                         needed:   2,
474                         unneeded: 2,
475                         pulling:  1,
476                 }})
477         bal.try(c, tester{
478                 known:       1,
479                 desired:     map[string]int{"default": 2},
480                 current:     slots{0, 1, 2},
481                 shouldTrash: slots{1, 2},
482                 expectBlockState: &balancedBlockState{
483                         needed:   1,
484                         unneeded: 2,
485                 }})
486 }
487
488 func (bal *balancerSuite) TestDeviceRWMountedByMultipleServers(c *check.C) {
489         dupUUID := bal.srvs[0].mounts[0].KeepMount.UUID
490         bal.srvs[9].mounts[0].KeepMount.UUID = dupUUID
491         bal.srvs[14].mounts[0].KeepMount.UUID = dupUUID
492         // block 0 belongs on servers 3 and e, which have different
493         // UUIDs.
494         bal.try(c, tester{
495                 known:      0,
496                 desired:    map[string]int{"default": 2},
497                 current:    slots{1},
498                 shouldPull: slots{0}})
499         // block 1 belongs on servers 0 and 9, which both report
500         // having a replica, but the replicas are on the same volume
501         // -- so we should pull to the third position (7).
502         bal.try(c, tester{
503                 known:      1,
504                 desired:    map[string]int{"default": 2},
505                 current:    slots{0, 1},
506                 shouldPull: slots{2}})
507         // block 1 can be pulled to the doubly-mounted volume, but the
508         // pull should only be done on the first of the two servers.
509         bal.try(c, tester{
510                 known:      1,
511                 desired:    map[string]int{"default": 2},
512                 current:    slots{2},
513                 shouldPull: slots{0}})
514         // block 0 has one replica on a single volume mounted on two
515         // servers (e,9 at positions 1,9). Trashing the replica on 9
516         // would lose the block.
517         bal.try(c, tester{
518                 known:      0,
519                 desired:    map[string]int{"default": 2},
520                 current:    slots{1, 9},
521                 shouldPull: slots{0},
522                 expectBlockState: &balancedBlockState{
523                         needed:  1,
524                         pulling: 1,
525                 }})
526         // block 0 is overreplicated, but the second and third
527         // replicas are the same replica according to volume UUID
528         // (despite different Mtimes). Don't trash the third replica.
529         bal.try(c, tester{
530                 known:   0,
531                 desired: map[string]int{"default": 2},
532                 current: slots{0, 1, 9},
533                 expectBlockState: &balancedBlockState{
534                         needed: 2,
535                 }})
536         // block 0 is overreplicated; the third and fifth replicas are
537         // extra, but the fourth is another view of the second and
538         // shouldn't be trashed.
539         bal.try(c, tester{
540                 known:       0,
541                 desired:     map[string]int{"default": 2},
542                 current:     slots{0, 1, 5, 9, 12},
543                 shouldTrash: slots{5, 12},
544                 expectBlockState: &balancedBlockState{
545                         needed:   2,
546                         unneeded: 2,
547                 }})
548 }
549
550 func (bal *balancerSuite) TestChangeStorageClasses(c *check.C) {
551         // For known blocks 0/1/2/3, server 9 is slot 9/1/14/0 in
552         // probe order. For these tests we give it two mounts, one
553         // with classes=[special], one with
554         // classes=[special,special2].
555         bal.srvs[9].mounts = []*KeepMount{{
556                 KeepMount: arvados.KeepMount{
557                         Replication:    1,
558                         StorageClasses: map[string]bool{"special": true},
559                         UUID:           "zzzzz-mount-special00000009",
560                         DeviceID:       "9-special",
561                 },
562                 KeepService: bal.srvs[9],
563         }, {
564                 KeepMount: arvados.KeepMount{
565                         Replication:    1,
566                         StorageClasses: map[string]bool{"special": true, "special2": true},
567                         UUID:           "zzzzz-mount-special20000009",
568                         DeviceID:       "9-special-and-special2",
569                 },
570                 KeepService: bal.srvs[9],
571         }}
572         // For known blocks 0/1/2/3, server 13 (d) is slot 5/3/11/1 in
573         // probe order. We give it two mounts, one with
574         // classes=[special3], one with classes=[default].
575         bal.srvs[13].mounts = []*KeepMount{{
576                 KeepMount: arvados.KeepMount{
577                         Replication:    1,
578                         StorageClasses: map[string]bool{"special2": true},
579                         UUID:           "zzzzz-mount-special2000000d",
580                         DeviceID:       "13-special2",
581                 },
582                 KeepService: bal.srvs[13],
583         }, {
584                 KeepMount: arvados.KeepMount{
585                         Replication:    1,
586                         StorageClasses: map[string]bool{"default": true},
587                         UUID:           "zzzzz-mount-00000000000000d",
588                         DeviceID:       "13-default",
589                 },
590                 KeepService: bal.srvs[13],
591         }}
592         // Pull to slot 9 because that's the only server with the
593         // desired class "special".
594         bal.try(c, tester{
595                 known:            0,
596                 desired:          map[string]int{"default": 2, "special": 1},
597                 current:          slots{0, 1},
598                 shouldPull:       slots{9},
599                 shouldPullMounts: []string{"zzzzz-mount-special20000009"}})
600         // If some storage classes are not satisfied, don't trash any
601         // excess replicas. (E.g., if someone desires repl=1 on
602         // class=durable, and we have two copies on class=volatile, we
603         // should wait for pull to succeed before trashing anything).
604         bal.try(c, tester{
605                 known:            0,
606                 desired:          map[string]int{"special": 1},
607                 current:          slots{0, 1},
608                 shouldPull:       slots{9},
609                 shouldPullMounts: []string{"zzzzz-mount-special20000009"}})
610         // Once storage classes are satisfied, trash excess replicas
611         // that appear earlier in probe order but aren't needed to
612         // satisfy the desired classes.
613         bal.try(c, tester{
614                 known:       0,
615                 desired:     map[string]int{"special": 1},
616                 current:     slots{0, 1, 9},
617                 shouldTrash: slots{0, 1}})
618         // Pull to slot 5, the best server with class "special2".
619         bal.try(c, tester{
620                 known:            0,
621                 desired:          map[string]int{"special2": 1},
622                 current:          slots{0, 1},
623                 shouldPull:       slots{5},
624                 shouldPullMounts: []string{"zzzzz-mount-special2000000d"}})
625         // Pull to slot 5 and 9 to get replication 2 in desired class
626         // "special2".
627         bal.try(c, tester{
628                 known:            0,
629                 desired:          map[string]int{"special2": 2},
630                 current:          slots{0, 1},
631                 shouldPull:       slots{5, 9},
632                 shouldPullMounts: []string{"zzzzz-mount-special20000009", "zzzzz-mount-special2000000d"}})
633         // Slot 0 has a replica in "default", slot 1 has a replica
634         // in "special"; we need another replica in "default", i.e.,
635         // on slot 2.
636         bal.try(c, tester{
637                 known:      1,
638                 desired:    map[string]int{"default": 2, "special": 1},
639                 current:    slots{0, 1},
640                 shouldPull: slots{2}})
641         // Pull to best probe position 0 (despite wrong storage class)
642         // if it's impossible to achieve desired replication in the
643         // desired class (only slots 1 and 3 have special2).
644         bal.try(c, tester{
645                 known:      1,
646                 desired:    map[string]int{"special2": 3},
647                 current:    slots{3},
648                 shouldPull: slots{0, 1}})
649         // Trash excess replica.
650         bal.try(c, tester{
651                 known:       3,
652                 desired:     map[string]int{"special": 1},
653                 current:     slots{0, 1},
654                 shouldTrash: slots{1}})
655         // Leave one copy on slot 1 because slot 0 (server 9) only
656         // gives us repl=1.
657         bal.try(c, tester{
658                 known:   3,
659                 desired: map[string]int{"special": 2},
660                 current: slots{0, 1}})
661 }
662
663 // Clear all servers' changesets, balance a single block, and verify
664 // the appropriate changes for that block have been added to the
665 // changesets.
666 func (bal *balancerSuite) try(c *check.C, t tester) {
667         bal.setupLookupTables()
668         blk := &BlockState{
669                 Replicas: bal.replList(t.known, t.current),
670                 Desired:  t.desired,
671         }
672         for i, t := range t.timestamps {
673                 blk.Replicas[i].Mtime = t
674         }
675         for _, srv := range bal.srvs {
676                 srv.ChangeSet = &ChangeSet{}
677         }
678         result := bal.balanceBlock(knownBlkid(t.known), blk)
679
680         var didPull, didTrash slots
681         var didPullMounts, didTrashMounts []string
682         for i, srv := range bal.srvs {
683                 var slot int
684                 for probeOrder, srvNum := range bal.knownRendezvous[t.known] {
685                         if srvNum == i {
686                                 slot = probeOrder
687                         }
688                 }
689                 for _, pull := range srv.Pulls {
690                         didPull = append(didPull, slot)
691                         didPullMounts = append(didPullMounts, pull.To.UUID)
692                         c.Check(pull.SizedDigest, check.Equals, knownBlkid(t.known))
693                 }
694                 for _, trash := range srv.Trashes {
695                         didTrash = append(didTrash, slot)
696                         didTrashMounts = append(didTrashMounts, trash.From.UUID)
697                         c.Check(trash.SizedDigest, check.Equals, knownBlkid(t.known))
698                 }
699         }
700
701         for _, list := range []slots{didPull, didTrash, t.shouldPull, t.shouldTrash} {
702                 sort.Sort(sort.IntSlice(list))
703         }
704         c.Check(didPull, check.DeepEquals, t.shouldPull)
705         c.Check(didTrash, check.DeepEquals, t.shouldTrash)
706         if t.shouldPullMounts != nil {
707                 sort.Strings(didPullMounts)
708                 c.Check(didPullMounts, check.DeepEquals, t.shouldPullMounts)
709         }
710         if t.shouldTrashMounts != nil {
711                 sort.Strings(didTrashMounts)
712                 c.Check(didTrashMounts, check.DeepEquals, t.shouldTrashMounts)
713         }
714         if t.expectBlockState != nil {
715                 c.Check(result.blockState, check.Equals, *t.expectBlockState)
716         }
717         if t.expectClassState != nil {
718                 c.Check(result.classState, check.DeepEquals, t.expectClassState)
719         }
720 }
721
722 // srvList returns the KeepServices, sorted in rendezvous order and
723 // then selected by idx. For example, srvList(3, slots{0, 1, 4})
724 // returns the first-, second-, and fifth-best servers for storing
725 // bal.knownBlkid(3).
726 func (bal *balancerSuite) srvList(knownBlockID int, order slots) (srvs []*KeepService) {
727         for _, i := range order {
728                 srvs = append(srvs, bal.srvs[bal.knownRendezvous[knownBlockID][i]])
729         }
730         return
731 }
732
733 // replList is like srvList but returns an "existing replicas" slice,
734 // suitable for a BlockState test fixture.
735 func (bal *balancerSuite) replList(knownBlockID int, order slots) (repls []Replica) {
736         nextMnt := map[*KeepService]int{}
737         mtime := time.Now().UnixNano() - (bal.signatureTTL+86400)*1e9
738         for _, srv := range bal.srvList(knownBlockID, order) {
739                 // round-robin repls onto each srv's mounts
740                 n := nextMnt[srv]
741                 nextMnt[srv] = (n + 1) % len(srv.mounts)
742
743                 repls = append(repls, Replica{srv.mounts[n], mtime})
744                 mtime++
745         }
746         return
747 }
748
749 // generate the same data hashes that are tested in
750 // sdk/go/keepclient/root_sorter_test.go
751 func knownBlkid(i int) arvados.SizedDigest {
752         return arvados.SizedDigest(fmt.Sprintf("%x+64", md5.Sum([]byte(fmt.Sprintf("%064x", i)))))
753 }