Twitter Snowflake 算法（解决分布式ID生成问题）

什么是分布式id? 它具备那些特点：

唯一性，必须垮表，垮系统唯一；
高性能，生成速度快，生成时尽量全部是数学运算，没有第三方依赖；
高可靠性，保证持续可用，不停机，不然就会影响第三方系统的运行；
具备递增和业务存储性，可以根据业务需要存储某些关键数据，后续可以根据 id 还原这些数据；

要实现分布式id的生成，目前比较常用的就是 snowflake 算法，以及基于此算法的改进，比如美团的Leaf和百度的uid-generator。
一般我们会选择 int64 版本的 snowflake 算法，该id的内部构成如下图：

64位bit，被划分为四部分，不含开头的第一个bit，因为这个bit是符号位；
用41位来存储收到请求时的时间戳，单位为毫秒；由于毫秒时间戳表示的是从1970年以来的毫秒数，41bit大概能够表示70年；不过我们在实现时，会取系统上线前的某个时间做为起始时间戳，这样我们的分布式id系统就会运行的更长久一些。
然后用10位来表示机器实例id（这里也可以做拆分，比如5位表示数据中心，5位表示机器实例，如果没有那么多机器实例，也可以用某些位来表示业务数据，总之就是可以根据自己业务来调整位数的表达）；
最后是12位的循环自增id（到达1111,1111,1111后会归0）。

这样的机制可以支持我们在同一台机器上，同一毫秒内产生2 ^ 12 = 4096条消息。一秒共409.6万条唯一id。从并发性来讲，再配合多台机器已经可以满足大多数高并发系统的要求了。

那么要实现 snowflake 算法要解决那些问题？

如何将各个部分的bit数据，最终组合成一个唯一的 int64 数据呢？最简单的实现就是采用 << 和 | 操作；将需要位于高位的数据左移N位，然后再和低位的数据进行或运算就可以完成数据的组装。
如何解决时钟回拨问题？什么是时钟回拨，就是某个机器由于某些原因时钟跑的过快，后来被中央时间校准器发现，时间被校准到之前的时间。由于该算法生成id非常依赖时间戳，如果在高并发状态下发生时钟回拨，在某台机器上几乎必然会生成和之前相同的id，这就完全违背了分布式id的第一原则：唯一性，会造成依赖该分布式id的系统出问题。目前解决时钟回拨问题有如下几种方案：
a) 抛出异常给依赖方，让依赖方自行决定如何解决；
b) 阻塞并等待，等待新的时间戳大于最近生成id的时间戳，这种方案被很多简单实现所采用；
c) 每次新生成id时，记录最大的时间戳到redis，如果发现当前时间戳小于最大时间戳，就将当前时间戳更新为最大时间戳继续生成id；

分布式id，如何还原各位置的数据？比如想知道时间戳是多少？

//以上面64bit版本的 snowflake算法为例，    
时间戳 = id >> 22 或者 (id >> 22) + 起始时间戳(非1970年)；     
//想知道机器id怎么办？ 先将分布式id右移12位     
k := id >> 12     
//然后切去高41位，所得的值就是机器 id 的值，这里涉及的一个计算机知识就是，    
//n位bit表示的最大数字 = 2^n - 1，此时各个bit位的值都是1     
workerId := (int64(1 << 10) - 1) & k

有了分布式id，我们能够做那些事情？

直接代替表中的自增id，可以方便的做分表分库，可以根据id回溯信息；
生成id的速度变得更快，更能适配高并发环境下的业务构建；
唯一id的存储成本更小，索引效率更高，彻底放弃字符串 uuid 这种效率和经济性都不高的方案。