分布式高性能ID生成算法——SnowflakeID。WikipediaSnowflakeIDformatUntitledSource:https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake[2]雪花算法（SnowflakeID）是当今广泛使用的分布式总订单ID生成算法，一种2010年推特官方博客上的文章，宣告了雪花算法的诞生，并简要介绍了当时推特对分布式ID生产算法需求的背景（context）、选择方案和最终解决方案。理解了生成时的需求，就理解了一半的算法。推荐阅读。问题背景。Twitter的数据库经历了从小到大，从单机到分布式的成长过程。然而，无论是在分布式数据库Cassandra[3]中，还是在使用gizzard[4]方案进行水平扩展的多机MySQL中，当时都没有满足Twitter需求的全局ID生成方案。那么推特当时对全球ID的要求是什么？每秒生成数以万计的ID。这限制了依赖多机通信生成ID的使用。毕竟一次网络通信延迟永远是1ms+，自然很难达到超过1k的qps。所有的ID都满足一个大致可排序的关系。也就是说，任何两个id都是可比较的，毕竟feed流中所有推文的排序都取决于这个id。长度不能超过64位。Twitter之前曾经历过随着系统规模的增加而增加ID位数的痛苦过程。这一次，它希望一步到位，同时时间也不会太长。选修的。基于MySQL的自增id，类似于flickr[5]的方案。但如果没有多机同步，就很难提供全序保证。一些现成的UUID算法，但是生成的ID都是128位的。基于Zookeeper的全局自增id。自然，由于Zab等可以保证全序的共识算法，无法满足Twitter的性能要求。最后的提议。通过结合时间戳、进程号和自增序列号，Twitter找到了一种分布式高性能总订单ID生成算法。基本思想是大致保证机器间的时钟同步，使用机器时钟产生的时间戳作为自增ID。如果两个进程生成相同的时间戳，则它们的大小进一步由进程号确定。由于一般的时间戳都是精确到毫秒的，为了满足QPS要求，会预留几个bits给自增id，这样1ms内会产生10+个id。最终格式如上图所示。1位符号位固定为0，保证ID在有符号数系中也是正数。41位时间戳，单位ms。时间戳本身是一个相对值，它的起点可以自己设置。10位的进程号最终可以支持1024个进程的单机或集群，但一般来说，每台机器都有一个进程。12位自增序列号，每毫秒最多可生成4k+个ID。在实际使用中，三个字段的位数可以在保证总位数的情况下根据需要进行调整。例如，如果确定进程数不超过100，则可以将相应字段缩短为7比特。条目编号可以由全局编号发行者初始分配，例如Zookeeper。在后续运行或重新启动时无需更改它。开源代码在这里[6]，其优点如下：高性能（Performance）。单进程10k+QPS，平均延迟2ms。无需沟通（不协调）。生成ID的进程集可以分布在多个数据中心的多台机器上，生成数据时无需相互通信（NTP时间戳同步除外）。大致按时间顺序。时间戳可以从ID中解析出来。可以直接排序（DirectlySortable）。不解析直接排序。袖珍的。64位而不是128位。高度可用。将进程分布在多个数据中心的多台机器上，只要一台机器还活着，它仍然可以提供服务。一些问题。雪花算法隐含地依赖于机器时钟，尽管不是严格的。但是用户需要保证所有生成ID的机器都通过NTP保持大致的时间同步。雪花算法可以处理NTP时钟同步带来的时钟回退问题。但是解决方法很粗暴，就是如果发现时钟回滚了，就死等，直到时钟超过了上次生成ID对应的时间点。正因为如此，需要保持所有机器时钟的大致同步。参考资料[1]有任何想法欢迎提issue：https://github.com/DistSysCorp/ArticleListWeekly/issues[2]宣布Snowflake：https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake[3]Cassandra：开源NoSQL数据库：http://cassandra.apache.org/[4]gizzard：http://github.com/twitter/gizzard[5]TicketServers：分布式唯一主键便宜：https://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/[6]snowflake2010：https://github.com/推特存档/snowflake/tree/snowflake-2010
