Last active
July 11, 2024 09:38
-
-
Save cloudhuang/3c0c582115adecd9555f61b4e520d6ae to your computer and use it in GitHub Desktop.
Generating unique IDs in a distributed environment at high scale
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.net.NetworkInterface; | |
import java.security.SecureRandom; | |
import java.time.Instant; | |
import java.util.Enumeration; | |
/** | |
* Distributed Sequence Generator. | |
* Inspired by Twitter snowflake: https://github.com/twitter/snowflake/tree/snowflake-2010 | |
* | |
* This class should be used as a Singleton. | |
* Make sure that you create and reuse a Single instance of SequenceGenerator per node in your distributed system cluster. | |
*/ | |
public class SequenceGenerator { | |
private static final int UNUSED_BITS = 1; // Sign bit, Unused (always set to 0) | |
private static final int EPOCH_BITS = 41; | |
private static final int NODE_ID_BITS = 10; | |
private static final int SEQUENCE_BITS = 12; | |
private static final int maxNodeId = (int)(Math.pow(2, NODE_ID_BITS) - 1); | |
private static final int maxSequence = (int)(Math.pow(2, SEQUENCE_BITS) - 1); | |
// Custom Epoch (January 1, 2015 Midnight UTC = 2015-01-01T00:00:00Z) | |
private static final long CUSTOM_EPOCH = 1420070400000L; | |
private final int nodeId; | |
private volatile long lastTimestamp = -1L; | |
private volatile long sequence = 0L; | |
// Create SequenceGenerator with a nodeId | |
public SequenceGenerator(int nodeId) { | |
if(nodeId < 0 || nodeId > maxNodeId) { | |
throw new IllegalArgumentException(String.format("NodeId must be between %d and %d", 0, maxNodeId)); | |
} | |
this.nodeId = nodeId; | |
} | |
// Let SequenceGenerator generate a nodeId | |
public SequenceGenerator() { | |
this.nodeId = createNodeId(); | |
} | |
public synchronized long nextId() { | |
long currentTimestamp = timestamp(); | |
if(currentTimestamp < lastTimestamp) { | |
throw new IllegalStateException("Invalid System Clock!"); | |
} | |
if (currentTimestamp == lastTimestamp) { | |
sequence = (sequence + 1) & maxSequence; | |
if(sequence == 0) { | |
// Sequence Exhausted, wait till next millisecond. | |
currentTimestamp = waitNextMillis(currentTimestamp); | |
} | |
} else { | |
// reset sequence to start with zero for the next millisecond | |
sequence = 0; | |
} | |
lastTimestamp = currentTimestamp; | |
long id = currentTimestamp << (NODE_ID_BITS + SEQUENCE_BITS); | |
id |= (nodeId << SEQUENCE_BITS); | |
id |= sequence; | |
return id; | |
} | |
// Get current timestamp in milliseconds, adjust for the custom epoch. | |
private static long timestamp() { | |
return Instant.now().toEpochMilli() - CUSTOM_EPOCH; | |
} | |
// Block and wait till next millisecond | |
private long waitNextMillis(long currentTimestamp) { | |
while (currentTimestamp == lastTimestamp) { | |
currentTimestamp = timestamp(); | |
} | |
return currentTimestamp; | |
} | |
private int createNodeId() { | |
int nodeId; | |
try { | |
StringBuilder sb = new StringBuilder(); | |
Enumeration<NetworkInterface> networkInterfaces = NetworkInterface.getNetworkInterfaces(); | |
while (networkInterfaces.hasMoreElements()) { | |
NetworkInterface networkInterface = networkInterfaces.nextElement(); | |
byte[] mac = networkInterface.getHardwareAddress(); | |
if (mac != null) { | |
for(int i = 0; i < mac.length; i++) { | |
sb.append(String.format("%02X", mac[i])); | |
} | |
} | |
} | |
nodeId = sb.toString().hashCode(); | |
} catch (Exception ex) { | |
nodeId = (new SecureRandom().nextInt()); | |
} | |
nodeId = nodeId & maxNodeId; | |
return nodeId; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment