buildbucket/appengine/internal/buildid/buildid.go

// 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 in descending order.
func NewBuildIDs(ctx context.Context, t time.Time, n int) []int64 {
	// Build ID format [idTimeSegment] [random number] [buildIDVersion]
	// Generate n build IDs by getting a random number R, then using the n
	// integers in the range (R-n, R] as the random component while fixing
	// the time and version components (see package-level comment). Ensure
	// R is in [n-1, 2^16) so that the range (R-n, R] only contains
	// non-negative integers.
	r := mathrand.Intn(ctx, 65536-(n-1)) + (n - 1)
	base := idTimeSegment(t) | (int64(r) << 4) | buildIDVersion
	ids := make([]int64, n)
	for i := range ids {
		// Returned build IDs are in descending order:
		// [time] [R] [version]
		// [time] [R-1] [version]
		// [time] [R-2] [version]
		// ...
		// [time] [R-(n-1)] [version]
		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
}