1 // 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. 17 package idutil 18 19 import ( 20 "math" 21 "sync/atomic" 22 "time" 23 ) 24 25 const ( 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). 49 type Generator struct { 50 // high order 2 bytes 51 prefix uint64 52 // low order 6 bytes 53 suffix uint64 54 } 55 56 func 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. 67 func (g *Generator) Next() uint64 { 68 suffix := atomic.AddUint64(&g.suffix, 1) 69 id := g.prefix | lowbit(suffix, suffixLen) 70 return id 71 } 72 73 func lowbit(x uint64, n uint) uint64 { 74 return x & (math.MaxUint64 >> (64 - n)) 75 } 76