Twitter的分布式自增ID算法Snowflake - 我的博客 - ITeye技术网站

Twitter-Snowflake，64位自增ID算法详解

工作进程与工作id分配器只是在工作进程启动的时候交互一次，然后工作进程可以自行将分配的id数据落文件，下一次启动直接读取文件里的id使用。

总体来说，是一个很高效很方便的GUID产生算法，一个int64_t字段就可以胜任，不像现在主流128bit的GUID算法，即使无法保证严格的id序列性，但是对于特定的业务，比如用做游戏服务器端的GUID产生会很方便。另外，在多线程的环境下，序列号使用atomic可以在代码实现上有效减少锁的密度。
Twitter的分布式自增ID算法Snowflake - 我的博客 - ITeye技术网站

Twitter-Snowflake算法产生的背景相当简单，为了满足Twitter每秒上万条消息的请求，每条消息都必须分配一条唯一的id，这些id还需要一些大致的顺序（方便客户端排序），并且在分布式系统中不同机器产生的id必须不同。

Snowflake算法核心

把时间戳，工作机器id，序列号组合在一起。

 

除了最高位bit标记为不可用以外，其余三组bit占位均可浮动，看具体的业务需求而定。默认情况下41bit的时间戳可以支持该算法使用到2082年，10bit的工作机器id可以支持1023台机器，序列号支持1毫秒产生4095个自增序列id。

默认情况下有41个bit可以供使用，那么一共有T（1llu << 41）毫秒供你使用分配，年份 = T / (3600 * 24 * 365 * 1000) = 69.7年。如果你只给时间戳分配39个bit使用，那么根据同样的算法最后年份 = 17.4年。

严格意义上来说这个bit段的使用可以是进程级，机器级的话你可以使用MAC地址来唯一标示工作机器，工作进程级可以使用IP+Path来区分工作进程。如果工作机器比较少，可以使用配置文件来设置这个id是一个不错的选择，如果机器过多配置文件的维护是一个灾难性的事情。

序列号就是一系列的自增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; }

0---0000000000 0000000000 0000000000 0000000000 0 --- 00000 ---00000 ---0000000000 00

在上面的字符串中，第一位为未使用（实际上也可作为long的符号位），接下来的41位为毫秒级时间，然后5位datacenter标识位，5位机器ID（并不算标识符，实际是为线程标识），然后12位该毫秒内的当前毫秒内的计数，加起来刚好64位，为一个Long型。

1.     public synchronized long nextId() {  
2.         long timestamp = this.timeGen();  
3.         if (this.lastTimestamp == timestamp) {  
4.             this.sequence = (this.sequence + 1) & sequenceMask;  
5.             if (this.sequence == 0) {  
6.                 System.out.println("###########" + sequenceMask);  
7.                 timestamp = this.tilNextMillis(this.lastTimestamp);  
8.             }  
9.         } else {  
10.             this.sequence = 0;  
11.         }  
12.         if (timestamp < this.lastTimestamp) {  
13.             try {  
14.                 throw new Exception(String.format(  
15.                     "Clock moved backwards.  Refusing to generate id for %d milliseconds",  
16.                     this.lastTimestamp - timestamp));  
17.             } catch (Exception e) {  
18.                 e.printStackTrace();  
19.             }  
20.         }  
21.   
22.         this.lastTimestamp = timestamp;  
23.         long nextId = ((timestamp - twepoch << timestampLeftShift))  
24.                       | (this.workerId << workerIdShift) | (this.sequence);  
25.         //  System.out.println("timestamp:" + timestamp + ",timestampLeftShift:"  
26.         //       + timestampLeftShift + ",nextId:" + nextId + ",workerId:"  
27.         //       + workerId + ",sequence:" + sequence);  
28.         return nextId;  
29.     }  
30.   
31.     private long tilNextMillis(final long lastTimestamp) {  
32.         long timestamp = this.timeGen();  
33.         while (timestamp <= lastTimestamp) {  
34.             timestamp = this.timeGen();  
35.         }  
36.         return timestamp;  
37.     }  
38.   
39.     private long timeGen() {  
40.         return System.currentTimeMillis();  
41.     }  

http://highscalability.com/blog/2011/12/19/how-twitter-stores-250-million-tweets-a-day-using-mysql.html
Twitter的分布式自增ID算法Snowflake实现分析及其Java、Php和Python版
Read full article from Twitter的分布式自增ID算法Snowflake - 我的博客 - ITeye技术网站