blob: 90cd955ebaf2c9b988c90d04a616ddc56445a780 [file] [log] [blame]
// Copyright 2020 The LUCI Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// Package buildid provides the build id computation related functions.
//
// Build key:
// Build keys are autogenerated, monotonically decreasing integers.
// That is, when sorted by key, new builds are first.
// Build has no parent.
//
// Build id is a 64 bits integer.
// - 1 highest order bit is set to 0 to keep value positive.
// - 43 bits are 43 lower bits of bitwise-inverted time since
// beginningOfTheWorld at 1ms resolution.
// It is good for 2**43 / 365.3 / 24 / 60 / 60 / 1000 = 278 years
// or 2010 + 278 = year 2288.
// - 16 bits are set to a random value. Assuming an instance is internally
// consistent with itself, it can ensure to not reuse the same 16 bits in two
// consecutive requests and/or throttle itself to one request per
// millisecond. Using random value reduces to 2**-15 the probability of
// collision on exact same timestamp at 1ms resolution, so a maximum
// theoretical rate of 65536000 requests/sec but an effective rate in the
// range of ~64k qps without much transaction conflicts. We should be fine.
// - 4 bits are 0. This is to represent the 'version' of the entity
// schema.
//
// The idea is taken from Swarming TaskRequest entity:
// https://source.chromium.org/chromium/_/chromium/infra/luci/luci-py/+/a4a91d5e1e14b8b866b68b68bc1055b0b8ffef3b:appengine/swarming/server/task_request.py;l=1380-1404
package buildid
import (
"context"
"time"
"go.chromium.org/luci/common/data/rand/mathrand"
)
const (
timeResolution = time.Millisecond
// buildIDMax is the maximum theoretical build ID.
// Based on time = beginningOfTheWorld, and max values for random and version bits.
buildIDMax = int64(0x7FFFFFFFFFFFFFFF)
// buildIDTimeSuffixLen is the number of bits following the time in a build ID.
buildIDTimeSuffixLen = 20
// buildIDVersion is the version number of the build ID scheme.
// Must not exceed 15 in the current build ID scheme since it's stored in four bits.
buildIDVersion = 1
)
var (
// beginningOfTheWorld is the earliest valid time encoded by build IDs.
beginningOfTheWorld = time.Date(2010, 01, 01, 0, 0, 0, 0, time.UTC)
)
// NewBuildIDs generates the given number of build IDs.
func NewBuildIDs(ctx context.Context, t time.Time, n int) []int64 {
// Random component is in [n-1, 2^16).
base := idTimeSegment(t) | (int64(mathrand.Intn(ctx, 2^16-(n-1))+(n-1)) << 4) | buildIDVersion
ids := make([]int64, n)
for i := range ids {
ids[i] = base - int64(i*(1<<4))
}
return ids
}
// MayContainBuilds returns true if the time range can possibly contain builds.
// Zero low/high value means no boundary for low/high.
func MayContainBuilds(low, high time.Time) bool {
switch {
case !high.IsZero() && (high.Before(beginningOfTheWorld) || high.Equal(beginningOfTheWorld)):
return false
case !low.IsZero() && !high.IsZero() && high.Before(low):
return false
default:
return true
}
}
// IDRange converts a creation time range to the build id range.
// Low/high bounds are inclusive/exclusive respectively
// for both time and id ranges.
func IDRange(low, high time.Time) (int64, int64) {
// Convert the inclusive low time bound to the exclusive high id bound.
idHigh := idTimeSegment(low.Add(-timeResolution))
// Convert the exclusive high time bound to the inclusive low id bound.
idLow := idTimeSegment(high.Add(-timeResolution))
return idLow, idHigh
}
// idTimeSegment constructs the build id bits: "0N{43}0{20}",
// where N is the bits converted from time.
// If time equals to beginningOfTheWorld, the id is 0x7FFFFFFFFFF00000.
// If the returned id is 0, it means its time is less than beginningOfTheWorld.
func idTimeSegment(t time.Time) int64 {
delta := t.Sub(beginningOfTheWorld).Milliseconds()
if delta < 0 {
return 0
}
// Use bitwise negation to make sure build id is monotonically decreasing.
// Thus the larger of the time, the smaller of the id.
return (^delta & ((int64(1) << 43) - 1)) << buildIDTimeSuffixLen
}