[golang] 分布式ID生成算法Snowflake

king_wang · · 4220 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

大部分分布式系统中,对一些互斥资源通常需要一个集群唯一的ID,比如消息id,订单号等。而且很多业务需求往往要求这些ID必须具有先后顺序,以方便分页或者排序。这就要求ID具有两个特性:

  • 全局唯一
  • 随时间递增

Snowflake

Twitter-Snowflake算法很好的解决了这种需求,它可以非常高效的生成ID,其核心思想如下(图片来自网络):

snowflake-64bit.jpg
snowflake-64bit.jpg
  • 时间戳。时间戳段位共41位,单位毫秒,可以使用约70年。为了增加剩余可用期限,一般都会把起始日期尽量后移而不是直接使用1970-01-01。(ps:如果是使用1970,你的程序只能支持到2039年了)
  • 机器id。用于区分集群内不同机器,因为Snowflake生成ID是在每台机器上进行的。一般集群中每个节点都会有一个自己的id标示,如果实在没有也可以通过grpc,thrift等由master server生成。我们系统的nodeid是通过zookeeper来生成的。
  • 序列号。由于高并发的特性,即使时间戳精确到了毫秒,也有可能出现重复。序列号用于同一时间戳下生成多个id。12位的长度,可以达到每秒上限1000*(2^12)=400W,完全够用了。

Golang实现

实现代码如下:

/*
* Snowflake
*
* 1                                               42           52             64
* +-----------------------------------------------+------------+---------------+
* | timestamp(ms)                                 | workerid   | sequence      |
* +-----------------------------------------------+------------+---------------+
* | 0000000000 0000000000 0000000000 0000000000 0 | 0000000000 | 0000000000 00 |
* +-----------------------------------------------+------------+---------------+
*
* 1. 41位时间截(毫秒级),注意这是时间截的差值(当前时间截 - 开始时间截)。可以使用约70年: (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69
* 2. 10位数据机器位,可以部署在1024个节点
* 3. 12位序列,毫秒内的计数,同一机器,同一时间截并发4096个序号
*/

const (
   twepoch        = int64(1483228800000)             //开始时间截 (2017-01-01)
   workeridBits   = uint(10)                         //机器id所占的位数
   sequenceBits   = uint(12)                         //序列所占的位数
   workeridMax    = int64(-1 ^ (-1 << workeridBits)) //支持的最大机器id数量
   sequenceMask   = int64(-1 ^ (-1 << sequenceBits)) //
   workeridShift  = sequenceBits                     //机器id左移位数
   timestampShift = sequenceBits + workeridBits      //时间戳左移位数
)

// A Snowflake struct holds the basic information needed for a snowflake generator worker
type Snowflake struct {
   sync.Mutex
   timestamp int64
   workerid  int64
   sequence  int64
}

// NewNode returns a new snowflake worker that can be used to generate snowflake IDs
func NewSnowflake(workerid int64) (*Snowflake, error) {

   if workerid < 0 || workerid > workeridMax {
       return nil, errors.New("workerid must be between 0 and 1023")
   }

   return &Snowflake{
       timestamp: 0,
       workerid:  workerid,
       sequence:  0,
   }, nil
}

// Generate creates and returns a unique snowflake ID
func (s *Snowflake) Generate() int64 {

   s.Lock()

   now := time.Now().UnixNano() / 1000000

   if s.timestamp == now {
       s.sequence = (s.sequence + 1) & sequenceMask

       if s.sequence == 0 {
           for now <= s.timestamp {
               now = time.Now().UnixNano() / 1000000
           }
       }
   } else {
       s.sequence = 0
   }

   s.timestamp = now

   r := int64((now-twepoch)<<timestampShift | (s.workerid << workeridShift) | (s.sequence))

   s.Unlock()
   return r
}

参考资料:https://github.com/twitter/snowflake


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:king_wang

查看原文:[golang] 分布式ID生成算法Snowflake

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

4220 次点击  
加入收藏 微博
1 回复  |  直到 2017-10-20 03:27:57
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传