冷饭新炒:理解Snowflake算法的实现原理

前提

Snowflake(雪花)是Twitter开源的高性能ID生成算法(服务)。

上图是SnowflakeGithub仓库,master分支中的REAEMDE文件中提示:初始版本于2010年发布,基于Apache Thrift,早于Finagle(这里的FinagleTwitter上用于RPC服务的构建模块)发布,而Twitter内部使用的Snowflake是一个完全重写的程序,在很大程度上依靠Twitter上的现有基础架构来运行。

2010年发布的初版Snowflake源码是使用Scala语言编写的,归档于scala_28分支。换言之,大家目前使用的Snowflake算法原版或者改良版已经是十年前(当前是2020年)的产物,不得不说这个算法确实比较厉害scala_28分支中有介绍该算法的动机和要求,这里简单摘录一下:

动机:

  • Cassandra中没有生成顺序ID的工具,Twitter由使用MySQL转向使用Cassandra的时候需要一种新的方式来生成ID(印证了架构不是设计出来,而是基于业务场景迭代出来)。

要求:

  • 高性能:每秒每个进程至少产生10KID,加上网络延迟响应速度要在2ms内。
  • 顺序性:具备按照时间的自增趋势,可以直接排序。
  • 紧凑性:保持生成的ID的长度在64 bit或更短。
  • 高可用:ID生成方案需要和存储服务一样高可用。

下面就Snowflake的源码分析一下他的实现原理。