有些时候我们希望能使用一种简单一些的ID并且希望ID能够按照时间有序生成。
而twitter的snowflake解决了这种需求最初Twitter把存储系统从MySQL迁移到Cassandra因为Cassandra没有顺序ID生成机制为了满足Twitter每秒上万条消息的请求每条消息都必须分配一条唯一的id这些id还需要一些大致的顺序(方便客户端排序)并且在分布式系统中不同机器产生的id必须不同所以twitter开发了这样一套全局唯一ID生成服务。
Snowflake算法核心
- SnowFlake的结构如下(每部分用-分开): 把时间戳工作机器id序列号组合在一起。
*1位标识由于long基本类型在Java中是带符号的最高位是符号位正数是0负数是1所以id一般是正数最高位是0
*41位时间截(毫秒级)注意41位时间截不是存储当前时间的时间截而是存储时间截的差值(当前时间截 - 开始时间截) 后得到的值这里的的开始时间截一般是我们的id生成器开始使用的时间由我们程序来指定的(如下下面程序IdWorker类的startTime属性)。41位的时间截可以使用69年年T (1L <<41) / (1000L * 60 * 60 * 24 * 365) 69
10位的数据机器位可以部署在1024个节点包括10位workerId
12位序列毫秒内的计数12位的计数顺序号支持每个节点每毫秒(同一机器同一时间截)产生4096个ID序号
加起来刚好64位为一个Long型。
snowflake除了最高位bit标记为不可用以外其余三组bit占位均可浮动看具体的业务需求而定。默认情况下41bit的时间戳可以支持该算法使用到2082年10bit的工作机器id可以支持1023台机器序列号支持1毫秒产生4095个自增序列id。下文会具体分析。
- SnowFlake的优点是整体上按照时间自增排序并且整个分布式系统内不会产生ID碰撞(由机器ID作区分)并且效率较高经测试SnowFlake每秒能够产生26万ID左右。
Snowflake – 时间戳
这里时间戳的细度是毫秒级具体代码如下建议使用64位linux系统机器因为有vdsogettimeofday()在用户态就可以完成操作减少了进入内核态的损耗。
默认情况下有41个bit可以供使用那么一共有T(1llu <<41)毫秒供你使用分配年份 T / (3600 * 24 * 365 * 1000) 69.7年。如果你只给时间戳分配39个bit使用那么根据同样的算法最后年份 17.4年。
Snowflake – 工作机器id
严格意义上来说这个bit段的使用可以是进程级机器级的话你可以使用MAC地址来唯一标示工作机器工作进程级可以使用IPPath来区分工作进程。如果工作机器比较少可以使用配置文件来设置这个id是一个不错的选择如果机器过多配置文件的维护是一个灾难性的事情。
这里的解决方案是需要一个工作id分配的进程可以使用自己编写一个简单进程来记录分配id或者利用Mysql auto_increment机制也可以达到效果。
工作进程与工作id分配器只是在工作进程启动的时候交互一次然后工作进程可以自行将分配的id数据落文件下一次启动直接读取文件里的id使用。
PS这个工作机器id的bit段也可以进一步拆分比如用前5个bit标记进程id后5个bit标记线程id之类:D
Snowflake – 序列号
序列号就是一系列的自增id(多线程建议使用atomic)为了处理在同一毫秒内需要给多条消息分配id若同一毫秒把序列号用完了则“等待至下一毫秒”。
总体来说是一个很高效很方便的GUID产生算法一个int64_t字段就可以胜任不像现在主流128bit的GUID算法即使无法保证严格的id序列性但是对于特定的业务比如用做游戏服务器端的GUID产生方便。另外在多线程的环境下序列号使用atomic可以在代码实现上有效减少锁的密度。
【本文来自：美国大带宽服务器 http://www.558idc.com/mg.html提供，感恩】