blob: 63a02cd734614fd720d45fe79827e2bdc865da3b [file] [log] [blame]
khenaidoo59ce9dd2019-11-11 13:05:32 -05001// Copyright 2015 The etcd Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15// Package idutil implements utility functions for generating unique,
16// randomized ids.
17package idutil
18
19import (
20 "math"
21 "sync/atomic"
22 "time"
23)
24
25const (
26 tsLen = 5 * 8
27 cntLen = 8
28 suffixLen = tsLen + cntLen
29)
30
31// Generator generates unique identifiers based on counters, timestamps, and
32// a node member ID.
33//
34// The initial id is in this format:
35// High order 2 bytes are from memberID, next 5 bytes are from timestamp,
36// and low order one byte is a counter.
37// | prefix | suffix |
38// | 2 bytes | 5 bytes | 1 byte |
39// | memberID | timestamp | cnt |
40//
41// The timestamp 5 bytes is different when the machine is restart
42// after 1 ms and before 35 years.
43//
44// It increases suffix to generate the next id.
45// The count field may overflow to timestamp field, which is intentional.
46// It helps to extend the event window to 2^56. This doesn't break that
47// id generated after restart is unique because etcd throughput is <<
48// 256req/ms(250k reqs/second).
49type Generator struct {
50 // high order 2 bytes
51 prefix uint64
52 // low order 6 bytes
53 suffix uint64
54}
55
56func NewGenerator(memberID uint16, now time.Time) *Generator {
57 prefix := uint64(memberID) << suffixLen
58 unixMilli := uint64(now.UnixNano()) / uint64(time.Millisecond/time.Nanosecond)
59 suffix := lowbit(unixMilli, tsLen) << cntLen
60 return &Generator{
61 prefix: prefix,
62 suffix: suffix,
63 }
64}
65
66// Next generates a id that is unique.
67func (g *Generator) Next() uint64 {
68 suffix := atomic.AddUint64(&g.suffix, 1)
69 id := g.prefix | lowbit(suffix, suffixLen)
70 return id
71}
72
73func lowbit(x uint64, n uint) uint64 {
74 return x & (math.MaxUint64 >> (64 - n))
75}