Twitter-Snowflake算法产生的背景相当简单,为了满足Twitter每秒上万条消息的请求,每条消息都必须分配一条唯一的id,这些id还需要一些大致的顺序(方便客户端排序),并且在分布式系统中不同机器产生的id必须不同。
Snowflake算法核心 把时间戳,工作机器id,序列号 组合在一起。
除了最高位bit标记为不可用以外,其余三组bit占位均可浮动,看具体的业务需求而定。默认情况下41bit的时间戳可以支持该算法使用到2082年,10bit的工作机器id可以支持1023台机器,序列号支持1毫秒产生4095个自增序列id 。下文会具体分析。
Snowflake – 时间戳 这里时间戳的细度是毫秒级,具体代码如下,建议使用64位linux系统机器,因为有vdso ,gettimeofday()在用户态就可以完成操作,减少了进入内核态的损耗。
1 2 3 4 5 6 uint64_t generateStamp(){ timeval tv; gettimeofday(&tv, 0 ); return (uint64_t )tv.tv_sec * 1000 + (uint64_t )tv.tv_usec / 1000 ; }
默认情况下有41个bit可以供使用,那么一共有T(1L << 41)毫秒供你使用分配,年份 = T / (3600 * 24 * 365 * 1000) = 69.7年。如果你只给时间戳分配39个bit使用,那么根据同样的算法最后年份 = 17.4年。
Snowflake – 工作机器id 严格意义上来说这个bit段的使用可以是进程级,机器级的话你可以使用MAC地址来唯一标示工作机器,工作进程级可以使用IP+Path来区分工作进程 。如果工作机器比较少,可以使用配置文件来设置这个id是一个不错的选择,如果机器过多配置文件的维护是一个灾难性的事情。
这里的解决方案是需要一个工作id分配的进程,可以使用自己编写一个简单进程来记录分配id,或者利用Mysql auto_increment机制也可以达到效果。
工作进程与工作id分配器只是在工作进程启动的时候交互一次,然后工作进程可以自行将分配的id数据落文件,下一次启动直接读取文件里的id使用。
PS:这个工作机器id的bit段也可以进一步拆分,比如用前5个bit标记进程id,后5个bit标记线程id之类:D
Snowflake – 序列号 序列号就是一系列的自增id(多线程建议使用atomic),为了处理在同一毫秒内需要给多条消息分配id,若同一毫秒把序列号用完了,则“等待至下一毫秒”。
1 2 3 4 5 6 7 8 uint64_t waitNextMs(uint64_t lastStamp){ uint64_t cur = 0 ; do { cur = generateStamp(); } while (cur <= lastStamp); return cur; }
总体来说,是一个很高效很方便的GUID产生算法,一个int64_t字段就可以胜任,不像现在主流128bit的GUID算法,即使无法保证严格的id序列性,但是对于特定的业务,比如用做游戏服务器端的GUID产生会很方便。另外,在多线程的环境下,序列号使用atomic可以在代码实现上有效减少锁的密度。
参考资料:https://github.com/twitter/snowflake
Snowflake - 算法实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 package com.qinjiangbo.util;import java.util.Random;public class TwitterSnowFlake { private final static long twepoch = 1468685273491L ; private static long workerId = 0L ; private static long datacenterId = 0L ; private static long sequence = 0L ; private static long workerIdBits = 5L ; private static long datacenterIdBits = 5L ; private static long maxWorkerId = -1L ^ (-1L << workerIdBits); private static long maxDataCenterId = -1L ^ (-1L << datacenterIdBits); private static long sequenceBits = 12L ; private static long workerIdShift = sequenceBits; private static long datacenterIdShift = workerIdBits + sequenceBits; private static long timestampShift = datacenterIdBits + workerIdBits + sequenceBits; private static long lastTimeStamp = -1L ; private static long sequenceMask = -1L ^ (-1L << sequenceBits); public TwitterSnowFlake () { Random random = new Random(); workerId = random.nextInt((int ) maxWorkerId); datacenterId = random.nextInt((int ) maxDataCenterId); } public TwitterSnowFlake (final long workerId, final long datacenterId) { if (workerId > maxWorkerId || workerId < 0 ) { throw new IllegalArgumentException("worker Id can't be greater than %d or less than 0" ); } if (datacenterId > maxDataCenterId || datacenterId < 0 ) { throw new IllegalArgumentException("datacenter Id can't be greater than %d or less than 0" ); } this .datacenterId = datacenterId; this .workerId = workerId; } private long getWorkerId () { return this .workerId; } private long getDatacenterId () { return this .datacenterId; } private long getTimeStamp () { return System.currentTimeMillis(); } public synchronized long nextId () { long timeStamp = timeGen(); if (timeStamp < lastTimeStamp) { try { throw new Exception(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds" , lastTimeStamp - timeStamp)); } catch (Exception e) { e.printStackTrace(); } } if (timeStamp == lastTimeStamp) { sequence = (sequence + 1 ) & sequenceMask; if (sequence == 0 ) { timeStamp = tilNextMills(); } }else { sequence = 0 ; } lastTimeStamp = timeStamp; long workId = ((timeStamp - twepoch) << timestampShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift) | sequence; return workId; } private long tilNextMills () { long timeStamp = timeGen(); do { timeStamp = timeGen(); } while (timeStamp <= lastTimeStamp); return timeStamp; } private long timeGen () { return System.currentTimeMillis(); } }