From 61f4a861fb993f68240d884c3e9cc1e750d0753b Mon Sep 17 00:00:00 2001 From: Tom Clegg Date: Mon, 19 Mar 2018 13:19:41 -0400 Subject: [PATCH] 7931: Trash excess replicas when a server has more than one. Previously a given server was classified only as "having" or "not having" a replica, regardless of how many it reported. With this change, once there are already enough distinct replicas on other servers, excess replicas will be trashed -- even if they are on the same server as a replica that is being retained. Arvados-DCO-1.1-Signed-off-by: Tom Clegg --- services/keep-balance/balance.go | 54 +++++++++++++++++++++++---- services/keep-balance/balance_test.go | 45 +++++++++++++++++++++- 2 files changed, 89 insertions(+), 10 deletions(-) diff --git a/services/keep-balance/balance.go b/services/keep-balance/balance.go index 2d0324d53f..d87e2a29f9 100644 --- a/services/keep-balance/balance.go +++ b/services/keep-balance/balance.go @@ -405,14 +405,49 @@ var changeName = map[int]string{ // block, and makes the appropriate ChangeSet calls. func (bal *Balancer) balanceBlock(blkid arvados.SizedDigest, blk *BlockState) { debugf("balanceBlock: %v %+v", blkid, blk) + + // A slot is somewhere a replica could potentially be trashed + // from, pulled from, or pulled to. Each KeepService gets + // either one empty slot, or one or more non-empty slots. + type slot struct { + srv *KeepService // never nil + repl *Replica // nil if none found + } + + // First, we build an ordered list of all slots worth + // considering (including all slots where replicas have been + // found, as well as all of the optimal slots for this block). + // Then, when we consider each slot in that order, we will + // have all of the information we need to make a decision + // about that slot. + uuids := keepclient.NewRootSorter(bal.serviceRoots, string(blkid[:32])).GetSortedRoots() - hasRepl := make(map[string]Replica, len(bal.serviceRoots)) - for _, repl := range blk.Replicas { - hasRepl[repl.KeepService.UUID] = repl + rendezvousOrder := make(map[*KeepService]int, len(uuids)) + slots := make([]slot, len(uuids)) + for i, uuid := range uuids { + srv := bal.KeepServices[uuid] + rendezvousOrder[srv] = i + slots[i].srv = srv + } + for ri := range blk.Replicas { // TODO: when multiple copies are on one server, use // the oldest one that doesn't have a timestamp // collision with other replicas. + repl := &blk.Replicas[ri] + srv := repl.KeepService + slotIdx := rendezvousOrder[srv] + if slots[slotIdx].repl != nil { + // Additional replicas on a single server are + // considered non-optimal. Within this + // category, we don't try to optimize layout: + // we just say the optimal order is the order + // we encounter them. + slotIdx = len(slots) + slots = append(slots, slot{srv: srv}) + } + slots[slotIdx].repl = repl } + // number of replicas already found in positions better than // the position we're contemplating now. reportedBestRepl := 0 @@ -428,12 +463,11 @@ func (bal *Balancer) balanceBlock(blkid arvados.SizedDigest, blk *BlockState) { // requested on rendezvous positions M