vendor/github.com/coreos/etcd/pkg/idutil/id.go

   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"
  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 byte is memberID, next 5 bytes are from timestamp,
  36 // and low order 2 bytes are 0s.
  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         mu sync.Mutex
  51         // high order 2 bytes
  52         prefix uint64
  53         // low order 6 bytes
  54         suffix uint64
  55 }
  56
  57 func NewGenerator(memberID uint16, now time.Time) *Generator {
  58         prefix := uint64(memberID) << suffixLen
  59         unixMilli := uint64(now.UnixNano()) / uint64(time.Millisecond/time.Nanosecond)
  60         suffix := lowbit(unixMilli, tsLen) << cntLen
  61         return &Generator{
  62                 prefix: prefix,
  63                 suffix: suffix,
  64         }
  65 }
  66
  67 // Next generates a id that is unique.
  68 func (g *Generator) Next() uint64 {
  69         g.mu.Lock()
  70         defer g.mu.Unlock()
  71         g.suffix++
  72         id := g.prefix | lowbit(g.suffix, suffixLen)
  73         return id
  74 }
  75
  76 func lowbit(x uint64, n uint) uint64 {
  77         return x & (math.MaxUint64 >> (64 - n))
  78 }