1. Snowflake(雪花算法)

Snowflake 是 Twitter 开源的分布式 ID 生成算法。Snowflake 由 64 bit 的二进制数字组成，这 64bit 的二进制被分成了几部分，每一部分存储的数据都有特定的含义。

第1位占用1bit，其值始终是0，可看做是符号位不使用。（为了保持 ID 的自增特性，若使用了最高位，int64_t 会表示为负数。）
第2位开始的41位是时间戳，41-bit位可表示2^41个数，每个数代表毫秒，那么雪花算法可用的时间年限是(1L<<41)/(1000L360024*365)= 69 年的时间。
中间的10-bit位可表示机器数，即2^10 = 1024台机器。但是一般情况下我们不会部署这么台机器。如果我们对IDC（互联网数据中心）有需求，还可以将 10-bit 分 5-bit 给 IDC，分5-bit给工作机器。这样就可以表示32个IDC，每个IDC下可以有32台机器，具体的划分可以根据自身需求定义。
最后12-bit位是自增序列，可表示2^12 = 4096个数。

这样的划分之后相当于在一毫秒一个数据中心的一台机器上可产生4096个有序的不重复的ID。但是我们 IDC 和机器数肯定不止一个，所以毫秒内能生成的有序ID数是翻倍的。

1.1 生成逻辑

我们需要生成一个 id 的时候，首先我们需要获取当前的时间戳，判断是否和上一次的时间戳一致，如果说和上一次的时间戳一致，那么我们应该增加序列号，然后通过移位操作构造对应的一个 64 bits 的 id 号返回。

如果说当前的时间戳与上一次的不同，那么我们直接修改时间戳，然后序列号取零，进行拼接即可。

1.2 优缺点

雪花算法提供了一个很好的设计思想，雪花算法生成的ID是趋势递增，不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的，而且可以根据自身业务特性分配bit位，非常灵活。

但是雪花算法强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。如果恰巧回退前生成过一些ID，而时间回退后，生成的ID就有可能重复。官方对于此并没有给出解决方案，而是简单的抛错处理，这样会造成在时间被追回之前的这段时间服务不可用。

1.3 工作机器id重复怎么办？

现在容器可能hostname 都是默认的 localhost，可以用随机数。
也可以放在redis里集中管理，各个机器从redis里去拿。当分配的 id 存在于活动节点队列则跳过取下一个可用空间，达到复用原地址空间的目的。

1.4 时钟回拨问题怎么解决？

等待策略：当回拨时间小于15ms，就等时间追上来之后继续生成。
在时钟回拨后会将生成的ID时间戳停留在最后一次时间戳上，等待系统时间追上后即可以避过时钟回拨问题。
当时间大于15ms时间，我们通过更换workid（workid需要redis集中式管理）。
当发现时间回拨太多的时候，我们就再去队列取一个来当新的workid使用把刚刚那个使用回拨的情况的workid存到队列里面。
队列我们每次都是从头取，从尾部进行插入，这样避免刚刚a机器使用又被b机器获取的可能性。

调整出一些扩展位，例如实现多时钟。

timeNow := 当前系统时间
if last_time >= timeNow:  // 时钟回拨
	clock_id = (clock_id + 1) & (1<<4-1)
last_time = timeNow
seq := 下一个序列号
return encode(timeNow, machineID, seq, clock_id)

2. Golang 实现

2.1 snowflake

https://github.com/bwmarrin/snowflake

使用单调时钟计算可防止单机时钟漂移。

package main

import (
	"fmt"

	"github.com/bwmarrin/snowflake"
)

func main() {

	// Create a new Node with a Node number of 1
	node, err := snowflake.NewNode(1)
	if err != nil {
		fmt.Println(err)
		return
	}

	// Generate a snowflake ID.
	id := node.Generate()

	// Print out the ID in a few different ways.
	fmt.Printf("Int64  ID: %d\n", id)
	fmt.Printf("String ID: %s\n", id)
	fmt.Printf("Base2  ID: %s\n", id.Base2())
	fmt.Printf("Base64 ID: %s\n", id.Base64())

	// Print out the ID's timestamp
	fmt.Printf("ID Time  : %d\n", id.Time())

	// Print out the ID's node number
	fmt.Printf("ID Node  : %d\n", id.Node())

	// Print out the ID's sequence number
	fmt.Printf("ID Step  : %d\n", id.Step())

	// Generate and print, all in one.
	fmt.Printf("ID       : %d\n", node.Generate().Int64())
}


/*
Int64  ID: 1808480519873105920
String ID: 1808480519873105920
Base2  ID: 1100100011001000000110111001101111010010000000001000000000000
Base64 ID: MTgwODQ4MDUxOTg3MzEwNTkyMA==
ID Time  : 1720010330538
ID Node  : 1
ID Step  : 0
ID       : 1808480519873105921
*/

Levon's Blog

分布式ID的snowflake算法