An overview of the

In distributed systems, there are some scenarios where globally unique ids are required. In this case, 36-bit UUID can be used to prevent ID collisions. However, UUID has some disadvantages.

Sometimes we want to use a simpler ID, and we want the ids to be generated in chronological order.

Twitter’s Snowflake addressed this need by initially migrating its storage system from MySQL to Cassandra, which has no sequential ID generation mechanism, so it developed a globally unique ID generation service.

 

structure

The structure of snowflake is as follows (each part is separated by -):

0-0000000000 0000000000 0000000000 0000000000 0-00000-00000-000000000000

The first bit is unused, followed by 41 bits of millisecond time (a 41-bit length of 69 years), followed by a 5-bit datacenterId and a 5-bit workerId(a 10-bit length that supports up to 1024 nodes), The last 12 bits are counts in milliseconds (12-bit count sequence numbers support 4096 ID numbers per millisecond per node)

That adds up to just 64 bits, which is a Long. (Maximum length 19 after conversion to string)

Snowflake generates ids that are incrementally sorted by time as a whole, don’t cause ID collisions (as distinguished by Datacenter and workerId) across the distributed system, and are efficient. In testing, Snowflake generates 260,000 ids per second.

 

The source code

(JAVA version of the source code)

/** * Twitter_Snowflake<br> * The structure of SnowFlake is as follows (each part is separated by -):<br> * 0-0000000000 0000000000 0000000000 0000000000 0-00000 - 0000000-000000000000 <br> * 1 bit identifier, because the basic type of long is signed in Java, the highest bit is the sign bit, the positive number is 0, the negative number is 1, so the id is generally positive, the highest bit is 0<br> * 41 bit truncation (milliseconds), notice, The 41-bit cut-off is not the current cut-off, but the difference between the current cut-off and the start cut-off *. The start cut-off is usually the time our ID generator started using. Specified by our program (as shown in the startTime property of the IdWorker class). The 41-bit time segment can be used for 69 years. The year T = (1L << 41)/(1000L * 60 * 60 * 24 * 365) = 69< BR > * the 10-bit data machine bit can be deployed on 1024 nodes. Includes 5-bit datacenterId and 5-bit workerId< BR > * 12-bit sequence, count in milliseconds, 12-bit count sequence number support each node every millisecond (same machine, same time intercept) 4096 ID sequence number < BR > * add up to just 64 bits, a Long. < BR > * The advantage of SnowFlake is that the whole system is sorted by time increment, there is no ID collision across the distributed system (distinguished by data center ids and machine ids), and it is very efficient. SnowFlake can generate around 260,000 ids per second in tests. */ public class SnowflakeIdWorker { // ==============================Fields=========================================== /** Start time (2015-01-01) */ private final Long twepoch = 1420041600000L; Private final Long workerIdBits = 5L; */ private final Long datacenterIdBits = 5L; Private final Long maxWorkerId = -1l ^ (-1l << workerIdBits); private final Long maxWorkerId = -1l ^ (-1l << workerIdBits); Private final Long maxDatacenterId = -1L ^ (-1L << datacenterIdBits); private Final Long maxDatacenterId = -1L ^ (-1L << datacenterIdBits); */ private final Long sequenceBits = 12L; */ private final Long workerIdShift = sequenceBits; Private final Long datacenterIdShift = sequenceBits + workerIdBits; private final Long datacenterIdShift = sequenceBits + workerIdBits; */ Private final Long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits; Private final Long sequenceMask = -1l ^ (-1L << sequenceBits); private final Long sequenceMask = -1l ^ (-1l << sequenceBits); /** private long workerId; /** datacenterId (0~31) */ private long datacenterId; Private long sequence = 0L; private long sequence = 0L; */ private long lastTimestamp = -1l; / / = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Constructors = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = / constructor * * * * @ param workerId work ID (0~31) * @param datacenterId datacenterId (0~31) */ public SnowflakeIdWorker(long workerId, long datacenterId) { if (workerId > maxWorkerId || workerId < 0) { throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId)); } if (datacenterId > maxDatacenterId || datacenterId < 0) { throw new IllegalArgumentException(String.format("datacenter  Id can't be greater than %d or less than 0", maxDatacenterId)); } this.workerId = workerId; this.datacenterId = datacenterId; } / / = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = the Methods = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = / * * * get the next ID (this method is thread-safe) * @ the return  SnowflakeId */ public synchronized long nextId() { long timestamp = timeGen(); // If the current time is less than the last ID generated timestamp, If (timestamp < lastTimestamp) {throw new RuntimeException(string. format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp)); If (lastTimestamp == timestamp) {sequence = (sequence + 1) &sequencemask; If (sequence == 0) {timestamp = tilNextMillis(lastTimestamp); Else {sequence = 0L; } // The last time the ID was generated lastTimestamp = timestamp; / / shift and through or operations up to 64 - bit ID return ((timestamp - twepoch) < < timestampLeftShift) / / | (datacenterId < < datacenterIdShift) / / | (workerId << workerIdShift) // | sequence; } /** * blocks until the next millisecond, * @return current timestamp */ protected long tilNextMillis(long lastTimestamp) {long timestamp = timeGen(); while (timestamp <= lastTimestamp) { timestamp = timeGen(); } return timestamp; } /** * returns the current time in milliseconds * @return current time (milliseconds) */ protected long timeGen() {return system.currentTimemillis (); } / / = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Test = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = / Test * * * / public static void main(String[] args) { SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0); for (int i = 0; i < 1000; i++) { long id = idWorker.nextId(); System.out.println(Long.toBinaryString(id)); System.out.println(id); }}}Copy the code

 

 

reference

Github.com/twitter/sno…