| 1 | package moves |
| 2 | |
| 3 | import ( |
| 4 | "math" |
| 5 | "time" |
| 6 | ) |
| 7 | |
| 8 | // The T11 cut budget (moves spec §7.3 T11, §7.4): pure arithmetic that |
| 9 | // prices a move's stop-to-open time from measured rates and decides how |
| 10 | // many probe attempts fit the operator's window. Ported from the model in |
| 11 | // internal/sim/hostlife/budget_test.go at 9c417aaa; the constants below |
| 12 | // that duplicate the model's (cutWindowDefault, probeAttemptsMax, |
| 13 | // probeSeconds, settleSeconds, admitSeconds, mirrorBarMiB) are twins of it |
| 14 | // and change together. All times are seconds, all sizes and rates MiB. |
| 15 | |
| 16 | const ( |
| 17 | CutWindowDefault = 120.0 // the operator's default cut window |
| 18 | OpenBudget = 5.0 // the target's open after the commit (§7.4) |
| 19 | ProbeAttemptsMax = 3 // §7.7: never more than three attempts |
| 20 | ProbeSeconds = 30.0 |
| 21 | SettleSeconds = 20.0 |
| 22 | AdmitSeconds = 2.0 // the admitting CAS, the purge and generation.json |
| 23 | MirrorBarMiB = 16.0 // §7.3: the final mirror round is at most this much |
| 24 | ArchiveSeconds = 2.0 // the archive phase's floor (ruling T7-budget) |
| 25 | ) |
| 26 | |
| 27 | // CutEstimate is a cut priced phase by phase. |
| 28 | type CutEstimate struct { |
| 29 | Stop, Checkpoint, Mirror, Archive, Render, Open float64 |
| 30 | RestoreStaged, SnapshotBuild, Anchor, Verify float64 // target-side build, whole database |
| 31 | RestoreAttempt, Admit, FreshUpload float64 // per probe attempt |
| 32 | Probe, Settle float64 // one attempt |
| 33 | } |
| 34 | |
| 35 | // Rates are the measured rates T11 reads, in MiB/s: the cross-region copy |
| 36 | // path, regional S3 (reads and writes from a box in the bucket's region) |
| 37 | // and the box's disk. MirrorBar is the final mirror round's size bar in |
| 38 | // MiB; zero means MirrorBarMiB. It is the one knob Task 11 turns |
| 39 | // (CARLOS_MOVE_READY_DELTA_BYTES, ruling F28(e)). FsyncRate is the target |
| 40 | // disk's per-file sync rate in files per second (ruling T7-budget): the |
| 41 | // landing's extract syncs every file, so the archive's entry count prices |
| 42 | // the Archive phase. |
| 43 | type Rates struct { |
| 44 | Cross, S3, Disk float64 |
| 45 | MirrorBar float64 |
| 46 | FsyncRate float64 |
| 47 | } |
| 48 | |
| 49 | // ExampleRates are the rates the spec's worked example uses (§7.3 T11): |
| 50 | // 10 MiB/s across regions, 250 MiB/s to regional S3, 500 MiB/s on disk, |
| 51 | // and (not in the spec's example, which has no files) 1600 files a second |
| 52 | // synced, about what Task 7 measured for its 16-worker pool. Tests and |
| 53 | // documentation only: T11 reads measured rates. |
| 54 | var ExampleRates = Rates{Cross: 10, S3: 250, Disk: 500, FsyncRate: 1600} |
| 55 | |
| 56 | // Estimate prices a cut for a database of dbMiB at the given rates. The |
| 57 | // final mirror is within the bar across regions. On the target every |
| 58 | // build pass moves the whole database once across S3 and once across the |
| 59 | // disk, bar the verification, which reads the disk alone. Each probe |
| 60 | // attempt restores the prepared generation again and pays the admission; |
| 61 | // a retried probe also uploads the whole database as a fresh generation. |
| 62 | // The archive phase is at least ArchiveSeconds, and longer when the |
| 63 | // archive's entries take longer than that to sync on the target at |
| 64 | // r.FsyncRate (ruling T7-budget): max(2, entries/FsyncRate). |
| 65 | // |
| 66 | // An input that is not a usable measurement (a rate that is not a positive |
| 67 | // finite number, a negative, NaN or infinite database size or bar, a |
| 68 | // negative entry count, or entries with no usable fsync rate) prices the cut |
| 69 | // at infinity, so it is refused: a negative rate must never price a phase |
| 70 | // below zero and let a move in. With no entries the fsync rate is not |
| 71 | // needed, but a negative, NaN or infinite one is still refused. |
| 72 | func Estimate(dbMiB float64, entries int, r Rates) CutEstimate { |
| 73 | if !usable(r.Cross) || !usable(r.S3) || !usable(r.Disk) || |
| 74 | !finite(dbMiB) || dbMiB < 0 || !finite(r.MirrorBar) || r.MirrorBar < 0 || |
| 75 | entries < 0 || !finite(r.FsyncRate) || r.FsyncRate < 0 || (entries > 0 && !usable(r.FsyncRate)) { |
| 76 | inf := math.Inf(1) |
| 77 | return CutEstimate{Stop: inf, Checkpoint: inf, Mirror: inf, Archive: inf, Render: inf, Open: inf} |
| 78 | } |
| 79 | bar := r.MirrorBar |
| 80 | if bar == 0 { |
| 81 | bar = MirrorBarMiB |
| 82 | } |
| 83 | archive := ArchiveSeconds |
| 84 | if entries > 0 { |
| 85 | archive = math.Max(ArchiveSeconds, float64(entries)/r.FsyncRate) |
| 86 | } |
| 87 | return CutEstimate{ |
| 88 | Stop: 2, Checkpoint: 1, Archive: archive, Render: 1, Open: OpenBudget, |
| 89 | Mirror: bar / r.Cross, |
| 90 | RestoreStaged: dbMiB/r.S3 + dbMiB/r.Disk, |
| 91 | SnapshotBuild: dbMiB/r.Disk + dbMiB/r.S3, |
| 92 | Anchor: dbMiB/r.Disk + dbMiB/r.S3, |
| 93 | Verify: dbMiB / r.Disk, |
| 94 | RestoreAttempt: dbMiB/r.S3 + dbMiB/r.Disk, |
| 95 | Admit: AdmitSeconds, |
| 96 | FreshUpload: dbMiB/r.Disk + dbMiB/r.S3, |
| 97 | Probe: ProbeSeconds, Settle: SettleSeconds, |
| 98 | } |
| 99 | } |
| 100 | |
| 101 | // Fixed is the cost of every phase outside the probe attempts. |
| 102 | func (e CutEstimate) Fixed() float64 { |
| 103 | return e.Stop + e.Checkpoint + e.Mirror + e.Archive + e.RestoreStaged + e.SnapshotBuild + e.Anchor + e.Verify + e.Render + e.Open |
| 104 | } |
| 105 | |
| 106 | // Attempt prices the i-th probe attempt (from 1): the restore of the |
| 107 | // prepared generation and the admission overhead, the probe and its |
| 108 | // settle; from the second attempt on, the fresh generation's first upload |
| 109 | // as well. |
| 110 | func (e CutEstimate) Attempt(i int) float64 { |
| 111 | c := e.RestoreAttempt + e.Admit + e.Probe + e.Settle |
| 112 | if i > 1 { |
| 113 | c += e.FreshUpload |
| 114 | } |
| 115 | return c |
| 116 | } |
| 117 | |
| 118 | // AttemptsAdmitted is T11: the attempts permitted are those whose summed |
| 119 | // costs fit the window after the fixed costs, at most ProbeAttemptsMax. |
| 120 | // The instance is eligible when that is at least one, and the probe loop |
| 121 | // runs at most that many. |
| 122 | func (e CutEstimate) AttemptsAdmitted(window float64) int { |
| 123 | left := window - e.Fixed() |
| 124 | n := 0 |
| 125 | for n < ProbeAttemptsMax && left >= e.Attempt(n+1) { |
| 126 | left -= e.Attempt(n + 1) |
| 127 | n++ |
| 128 | } |
| 129 | return n |
| 130 | } |
| 131 | |
| 132 | // Total prices the cut with n attempts. |
| 133 | func (e CutEstimate) Total(n int) float64 { |
| 134 | t := e.Fixed() |
| 135 | for i := 1; i <= n; i++ { |
| 136 | t += e.Attempt(i) |
| 137 | } |
| 138 | return t |
| 139 | } |
| 140 | |
| 141 | // CutDeadline is §7.4's one absolute deadline: cut_at + cut_budget - |
| 142 | // open_budget. Every phase before the commit checks it; the commit CAS is |
| 143 | // conditional on it. |
| 144 | func CutDeadline(cutAt time.Time, windowSeconds float64) time.Time { |
| 145 | return cutAt.Add(time.Duration((windowSeconds - OpenBudget) * float64(time.Second))) |
| 146 | } |
| 147 | |
| 148 | func finite(x float64) bool { return !math.IsNaN(x) && !math.IsInf(x, 0) } |
| 149 | |
| 150 | // usable is a rate that can be divided by: positive and finite. |
| 151 | func usable(rate float64) bool { return finite(rate) && rate > 0 } |
| 152 | |
amadan