Twitter的分布式自增ID算法Snowflake

Snowflake Twitter 自增ID

摘要

Twitter把存储系统从MySQL迁移到Cassandra的过程中，由于Cassandra没有顺序ID生成机制，因此自己开发了一套全局唯一ID生成服务：Snowflake。

正文

Twitter早期使用MySQL存储数据，随着用户的增长，单一MySQL实例无法支持海量数据，Twitter开始把存储系统从MySQL迁移到Cassandra，但是Cassandra没有内置的顺序ID生成机制，因此Twitter开发了一套分布式系统全局唯一ID生成服务：Snowflake。

对于Twitter而言，必须满足每秒上万条消息的请求，并且每条消息能够分配一个全局唯一的ID，因此，ID生成服务要求必须满足高性能（>10K ids/s）、低延迟（<2ms）、高可用的特性，同时生成的ID还可以进行大致的排序，以方便客户端的排序。

Snowflake满足了以上的需求。Snowflake生成的每一个ID都是64位的整型数，它的核心算法也比较简单高效，结构如下：

• 41位的时间序列，精确到毫秒级，41位的长度可以使用69年。时间位还有一个很重要的作用是可以根据时间进行排序。

• 10位的机器标识，10位的长度最多支持部署1024个节点。

• 12位的计数序列号，序列号即一系列的自增id，可以支持同一节点同一毫秒生成多个ID序号，12位的计数序列号支持每个节点每毫秒产生4096个ID序号。

• 最高位是符号位，始终为0，不可用。

Snowflake是一个高效方便的GUID生成算法，可用性强，速度快并且可以根据时间排序。但是，就目前来看部署Snowflake需要引入ZooKeeper和Snowflake专用服务器，Twitter也声明希望可以让Snowflake运行在Twitter以外更多的环境中，如果可以实现，Snowflake的使用就会更方便。

Snowflake是用Scala实现的，如果想要了解更多细节，请移步至Snowflake项目。