lib/controller/federation/list.go

   1 // Copyright (C) The Arvados Authors. All rights reserved.
   2 //
   3 // SPDX-License-Identifier: AGPL-3.0
   4
   5 package federation
   6
   7 import (
   8         "context"
   9         "fmt"
  10         "net/http"
  11         "sort"
  12         "sync"
  13         "sync/atomic"
  14
  15         "git.curoverse.com/arvados.git/sdk/go/arvados"
  16         "git.curoverse.com/arvados.git/sdk/go/httpserver"
  17 )
  18
  19 //go:generate go run generate.go
  20
  21 // CollectionList is used as a template to auto-generate List()
  22 // methods for other types; see generate.go.
  23
  24 func (conn *Conn) CollectionList(ctx context.Context, options arvados.ListOptions) (arvados.CollectionList, error) {
  25         var mtx sync.Mutex
  26         var merged arvados.CollectionList
  27         var needSort atomic.Value
  28         needSort.Store(false)
  29         err := conn.splitListRequest(ctx, options, func(ctx context.Context, _ string, backend arvados.API, options arvados.ListOptions) ([]string, error) {
  30                 cl, err := backend.CollectionList(ctx, options)
  31                 if err != nil {
  32                         return nil, err
  33                 }
  34                 mtx.Lock()
  35                 defer mtx.Unlock()
  36                 if len(merged.Items) == 0 {
  37                         merged = cl
  38                 } else if len(cl.Items) > 0 {
  39                         merged.Items = append(merged.Items, cl.Items...)
  40                         needSort.Store(true)
  41                 }
  42                 uuids := make([]string, 0, len(cl.Items))
  43                 for _, item := range cl.Items {
  44                         uuids = append(uuids, item.UUID)
  45                 }
  46                 return uuids, nil
  47         })
  48         if needSort.Load().(bool) {
  49                 // Apply the default/implied order, "modified_at desc"
  50                 sort.Slice(merged.Items, func(i, j int) bool {
  51                         mi, mj := merged.Items[i].ModifiedAt, merged.Items[j].ModifiedAt
  52                         if mi == nil || mj == nil {
  53                                 return false
  54                         } else {
  55                                 return mj.Before(*mi)
  56                         }
  57                 })
  58         }
  59         return merged, err
  60 }
  61
  62 // Call fn on one or more local/remote backends if opts indicates a
  63 // federation-wide list query, i.e.:
  64 //
  65 // * There is at least one filter of the form
  66 //   ["uuid","in",[a,b,c,...]] or ["uuid","=",a]
  67 //
  68 // * One or more of the supplied UUIDs (a,b,c,...) has a non-local
  69 //   prefix.
  70 //
  71 // * There are no other filters
  72 //
  73 // (If opts doesn't indicate a federation-wide list query, fn is just
  74 // called once with the local backend.)
  75 //
  76 // fn is called more than once only if the query meets the following
  77 // restrictions:
  78 //
  79 // * Count=="none"
  80 //
  81 // * Limit<0
  82 //
  83 // * len(Order)==0
  84 //
  85 // * Each filter must be either "uuid = ..." or "uuid in [...]".
  86 //
  87 // * The maximum possible response size (total number of objects that
  88 //   could potentially be matched by all of the specified filters)
  89 //   exceeds the local cluster's response page size limit.
  90 //
  91 // If the query involves multiple backends but doesn't meet these
  92 // restrictions, an error is returned without calling fn.
  93 //
  94 // Thus, the caller can assume that either:
  95 //
  96 // * splitListRequest() returns an error, or
  97 //
  98 // * fn is called exactly once, or
  99 //
 100 // * fn is called more than once, with options that satisfy the above
 101 //   restrictions.
 102 //
 103 // Each call to fn indicates a single (local or remote) backend and a
 104 // corresponding options argument suitable for sending to that
 105 // backend.
 106 func (conn *Conn) splitListRequest(ctx context.Context, opts arvados.ListOptions, fn func(context.Context, string, arvados.API, arvados.ListOptions) ([]string, error)) error {
 107         cannotSplit := false
 108         var matchAllFilters map[string]bool
 109         for _, f := range opts.Filters {
 110                 matchThisFilter := map[string]bool{}
 111                 if f.Attr != "uuid" {
 112                         cannotSplit = true
 113                         continue
 114                 }
 115                 if f.Operator == "=" {
 116                         if uuid, ok := f.Operand.(string); ok {
 117                                 matchThisFilter[uuid] = true
 118                         } else {
 119                                 return httpErrorf(http.StatusBadRequest, "invalid operand type %T for filter %q", f.Operand, f)
 120                         }
 121                 } else if f.Operator == "in" {
 122                         if operand, ok := f.Operand.([]interface{}); ok {
 123                                 // skip any elements that aren't
 124                                 // strings (thus can't match a UUID,
 125                                 // thus can't affect the response).
 126                                 for _, v := range operand {
 127                                         if uuid, ok := v.(string); ok {
 128                                                 matchThisFilter[uuid] = true
 129                                         }
 130                                 }
 131                         } else if strings, ok := f.Operand.([]string); ok {
 132                                 for _, uuid := range strings {
 133                                         matchThisFilter[uuid] = true
 134                                 }
 135                         } else {
 136                                 return httpErrorf(http.StatusBadRequest, "invalid operand type %T in filter %q", f.Operand, f)
 137                         }
 138                 } else {
 139                         cannotSplit = true
 140                         continue
 141                 }
 142
 143                 if matchAllFilters == nil {
 144                         matchAllFilters = matchThisFilter
 145                 } else {
 146                         // Reduce matchAllFilters to the intersection
 147                         // of matchAllFilters ∩ matchThisFilter.
 148                         for uuid := range matchAllFilters {
 149                                 if !matchThisFilter[uuid] {
 150                                         delete(matchAllFilters, uuid)
 151                                 }
 152                         }
 153                 }
 154         }
 155
 156         if matchAllFilters == nil {
 157                 // Not filtering by UUID at all; just query the local
 158                 // cluster.
 159                 _, err := fn(ctx, conn.cluster.ClusterID, conn.local, opts)
 160                 return err
 161         }
 162
 163         // Collate UUIDs in matchAllFilters by remote cluster ID --
 164         // e.g., todoByRemote["aaaaa"]["aaaaa-4zz18-000000000000000"]
 165         // will be true -- and count the total number of UUIDs we're
 166         // filtering on, so we can compare it to our max page size
 167         // limit.
 168         nUUIDs := 0
 169         todoByRemote := map[string]map[string]bool{}
 170         for uuid := range matchAllFilters {
 171                 if len(uuid) != 27 {
 172                         // Cannot match anything, just drop it
 173                 } else {
 174                         if todoByRemote[uuid[:5]] == nil {
 175                                 todoByRemote[uuid[:5]] = map[string]bool{}
 176                         }
 177                         todoByRemote[uuid[:5]][uuid] = true
 178                         nUUIDs++
 179                 }
 180         }
 181
 182         if len(todoByRemote) > 1 {
 183                 if cannotSplit {
 184                         return httpErrorf(http.StatusBadRequest, "cannot execute federated list query: each filter must be either 'uuid = ...' or 'uuid in [...]'")
 185                 }
 186                 if opts.Count != "none" {
 187                         return httpErrorf(http.StatusBadRequest, "cannot execute federated list query unless count==\"none\"")
 188                 }
 189                 if opts.Limit >= 0 || opts.Offset != 0 || len(opts.Order) > 0 {
 190                         return httpErrorf(http.StatusBadRequest, "cannot execute federated list query with limit, offset, or order parameter")
 191                 }
 192                 if max := conn.cluster.API.MaxItemsPerResponse; nUUIDs > max {
 193                         return httpErrorf(http.StatusBadRequest, "cannot execute federated list query because number of UUIDs (%d) exceeds page size limit %d", nUUIDs, max)
 194                 }
 195                 selectingUUID := false
 196                 for _, attr := range opts.Select {
 197                         if attr == "uuid" {
 198                                 selectingUUID = true
 199                         }
 200                 }
 201                 if opts.Select != nil && !selectingUUID {
 202                         return httpErrorf(http.StatusBadRequest, "cannot execute federated list query with a select parameter that does not include uuid")
 203                 }
 204         }
 205
 206         ctx, cancel := context.WithCancel(ctx)
 207         defer cancel()
 208         errs := make(chan error, len(todoByRemote))
 209         for clusterID, todo := range todoByRemote {
 210                 go func(clusterID string, todo map[string]bool) {
 211                         // This goroutine sends exactly one value to
 212                         // errs.
 213                         batch := make([]string, 0, len(todo))
 214                         for uuid := range todo {
 215                                 batch = append(batch, uuid)
 216                         }
 217
 218                         var backend arvados.API
 219                         if clusterID == conn.cluster.ClusterID {
 220                                 backend = conn.local
 221                         } else if backend = conn.remotes[clusterID]; backend == nil {
 222                                 errs <- httpErrorf(http.StatusNotFound, "cannot execute federated list query: no proxy available for cluster %q", clusterID)
 223                                 return
 224                         }
 225                         remoteOpts := opts
 226                         for len(todo) > 0 {
 227                                 if len(batch) > len(todo) {
 228                                         // Reduce batch to just the todo's
 229                                         batch = batch[:0]
 230                                         for uuid := range todo {
 231                                                 batch = append(batch, uuid)
 232                                         }
 233                                 }
 234                                 remoteOpts.Filters = []arvados.Filter{{"uuid", "in", batch}}
 235
 236                                 done, err := fn(ctx, clusterID, backend, remoteOpts)
 237                                 if err != nil {
 238                                         errs <- err
 239                                         return
 240                                 }
 241                                 progress := false
 242                                 for _, uuid := range done {
 243                                         if _, ok := todo[uuid]; ok {
 244                                                 progress = true
 245                                                 delete(todo, uuid)
 246                                         }
 247                                 }
 248                                 if !progress {
 249                                         errs <- httpErrorf(http.StatusBadGateway, "cannot make progress in federated list query: cluster %q returned none of the requested UUIDs", clusterID)
 250                                         return
 251                                 }
 252                         }
 253                         errs <- nil
 254                 }(clusterID, todo)
 255         }
 256
 257         // Wait for all goroutines to return, then return the first
 258         // non-nil error, if any.
 259         var firstErr error
 260         for range todoByRemote {
 261                 if err := <-errs; err != nil && firstErr == nil {
 262                         firstErr = err
 263                         // Signal to any remaining fn() calls that
 264                         // further effort is futile.
 265                         cancel()
 266                 }
 267         }
 268         return firstErr
 269 }
 270
 271 func httpErrorf(code int, format string, args ...interface{}) error {
 272         return httpserver.ErrorWithStatus(fmt.Errorf(format, args...), code)
 273 }