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