forked from NVIDIA/aistore
-
Notifications
You must be signed in to change notification settings - Fork 0
/
sort.go
91 lines (77 loc) · 2.25 KB
/
sort.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// Package dsort provides APIs for distributed archive file shuffling.
/*
* Copyright (c) 2018-2023, NVIDIA CORPORATION. All rights reserved.
*/
package dsort
import (
"math/rand"
"sort"
"strconv"
"time"
"github.com/artashesbalabekyan/aistore/cmn/cos"
"github.com/artashesbalabekyan/aistore/ext/dsort/extract"
)
const (
sortKindEmpty = "" // default one - alphanumeric (sort decreasing)
SortKindAlphanumeric = "alphanumeric" // sort the records (decreasing or increasing)
SortKindNone = "none" // none, used for resharding
SortKindMD5 = "md5"
SortKindShuffle = "shuffle" // shuffle randomly, can be used with seed to get reproducible results
SortKindContent = "content" // sort by content of given file
)
const (
fmtInvalidAlgorithmKind = "invalid algorithm kind, expecting one of: %+v" // <--- supportedAlgorithms
)
var supportedAlgorithms = []string{sortKindEmpty, SortKindAlphanumeric, SortKindMD5, SortKindShuffle, SortKindContent, SortKindNone}
type (
alphaByKey struct {
*extract.Records
decreasing bool
formatType string
err error
}
)
// interface guard
var _ sort.Interface = (*alphaByKey)(nil)
func (s *alphaByKey) Less(i, j int) bool {
var (
less bool
err error
)
if s.decreasing {
less, err = s.Records.Less(j, i, s.formatType)
} else {
less, err = s.Records.Less(i, j, s.formatType)
}
if err != nil {
s.err = err
}
return less
}
// sortRecords sorts records by each Record.Key in the order determined by sort algorithm.
func sortRecords(r *extract.Records, algo *SortAlgorithm) (err error) {
var rnd *rand.Rand
if algo.Kind == SortKindNone {
return nil
} else if algo.Kind == SortKindShuffle {
seed := time.Now().Unix()
if algo.Seed != "" {
seed, err = strconv.ParseInt(algo.Seed, 10, 64)
// We assert error since we know that the seed should be validated
// during request spec validation.
cos.AssertNoErr(err)
}
rnd = rand.New(rand.NewSource(seed))
for i := 0; i < r.Len(); i++ { // https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
j := rnd.Intn(i + 1)
r.Swap(i, j)
}
} else {
keys := &alphaByKey{r, algo.Decreasing, algo.FormatType, nil}
sort.Sort(keys)
if keys.err != nil {
return keys.err
}
}
return nil
}