1.3 How to Implement Distributed IDs

This is a historical learning note and may contain outdated or incomplete understanding.

1. What Is a Distributed ID?

A unique ID in a distributed environment (multiple machines).

Characteristics of distributed IDs:

Globally unique
- It is an ID, so of course uniqueness must be guaranteed.
Roughly increasing
- Increasing IDs are used to fit the characteristics of the clustered index in the MySQL InnoDB storage engine.
- Roughly increasing rather than strictly sequential is intended to prevent people from guessing the ID-generation strategy and attacking it. A timestamp can be added.
High concurrency
- Taobao Double 11: 1 billion / 24 hours / 60 minutes / 60 seconds = 12,000/s.
High availability
- Other services call the ID-generation service. If the ID-generation service goes down, the entire business becomes unavailable.

2. How to Implement Distributed IDs

2.1. Database Auto-Increment

If it is a primary-key ID, an auto-increment strategy can be used, such as MySQL’s auto_increment; otherwise, a custom sequence can be used.
Build a cluster with master-master synchronization (master-slave is only used for read/write separation and is rarely used here).
- master1 starts auto-incrementing from 0 with a step of 2, while master2 starts from 1 with a step of 2. However, when machines are added, IDs need to be reassigned, which is troublesome.

2.1.1. Problems

It does not meet the high-concurrency requirement, and building a database cluster only to generate IDs wastes resources.

2.2. UUID

Generate a UUID by combining the machine’s network card, local time, and a random number.

UUID1: time
- Obtained by calculating the current timestamp, a random number, and the machine’s MAC address.
- Uniqueness: because the MAC address is used in the algorithm, this version of UUID can guarantee uniqueness globally.
- Disadvantage: using a MAC address introduces security issues.
- This is generally used.
UUID2: DCE Security
- The same as the time-based UUID algorithm, but the first four positions of the timestamp are replaced with the POSIX UID or GID.
- Used less often.
UUID3: MD5
- A name-based UUID is obtained by calculating the MD5 hash of a name and namespace.
- Uniqueness: UUIDs generated from different names in the same namespace are unique; UUIDs in different namespaces are unique.
- Disadvantage: repeatedly generating a UUID from the same name in the same namespace produces the same UUID.
UUID4: random number
- Pseudorandom number; duplicates are possible.
UUID5: SHA1
- The same as UUID3, except the algorithm is changed to SHA1.

2.2.1. Problems

It does not meet the roughly-increasing requirement.

2.3. Redis-Generated IDs

Redis commands are single-threaded, and Redis provides the atomic incr command.
Redis Cluster solution: suppose there are 3 masters and 3 replicas. master1 can create a key id1 starting from 0 with a step of 3; master2 can create a key id2 starting from 1 with a step of 3; master3 can create a key id3 starting from 2 with a step of 3. However, when machines are added, IDs need to be reassigned, which is troublesome.

2.3.1. Problems

It does not meet the high-availability requirement and depends entirely on Redis.

2.4. snowflakeId

2.4.1. Principle

Use the timestamp to guarantee ID uniqueness.

2.4.2. Implementation

package com.zsk.template.util;

import org.apache.commons.lang3.StringUtils;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.springframework.stereotype.Component;

import java.lang.management.ManagementFactory;
import java.net.InetAddress;
import java.net.NetworkInterface;

/**
 * Twitter_Snowflake ID generator
 *
 * Twitter_Snowflake<br>
 * The SnowFlake structure is as follows (each part is separated by -):<br>
 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>
 * 1-bit identifier. Because Java's long primitive type is signed, the highest bit is the sign bit:
 * positive numbers use 0 and negative numbers use 1. IDs are generally positive, so the highest bit is 0.<br>
 * 41-bit timestamp (millisecond level). Note that the 41-bit timestamp does not store the current timestamp,
 * but the timestamp difference (current timestamp - starting timestamp).
 * The starting timestamp is generally the time when our ID generator begins to be used and is specified by
 * our program (the startTime property of the IdWorker class in the program below).
 * A 41-bit timestamp can be used for 69 years:
 * T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>
 * 10-bit data-machine field, supporting deployment on 1024 nodes, including a 5-bit datacenterId
 * and a 5-bit workerId.<br>
 * 12-bit sequence: a counter within a millisecond. A 12-bit sequence supports each node generating
 * 4096 ID sequence numbers per millisecond (same machine, same timestamp).<br>
 * Together these are exactly 64 bits, forming a Long value.<br>
 * The advantage of SnowFlake is that IDs are generally sorted increasingly by time, and ID collisions
 * will not occur in the whole distributed system (distinguished by data-center ID and machine ID).
 * It is also efficient. Tests show that SnowFlake can generate about 260,000 IDs per second.
 */
//@Component
public class SnowflakeId {

    private static final Logger logger  = LoggerFactory.getLogger(SnowflakeId.class);

    // ==============================Fields===========================================
    /** Starting timestamp (2015-01-01) */
    private final long twepoch = 1420041600000L;

    /** Number of bits occupied by the machine ID */
    private final long workerIdBits = 5L;

    /** Number of bits occupied by the data identifier ID */
    private final long datacenterIdBits = 5L;

    /** Maximum supported machine ID, result is 31 (this shift algorithm can quickly calculate
     * the maximum decimal number representable by a given number of binary bits) */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);

    /** Maximum supported data identifier ID, result is 31 */
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

    /** Number of bits occupied by the sequence in the ID */
    private final long sequenceBits = 12L;

    /** Shift machine ID left by 12 bits */
    private final long workerIdShift = sequenceBits;

    /** Shift data identifier ID left by 17 bits (12+5) */
    private final long datacenterIdShift = sequenceBits + workerIdBits;

    /** Shift timestamp left by 22 bits (5+5+12) */
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

    /** Mask for generating the sequence, 4095 here (0b111111111111=0xfff=4095) */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

    /** Worker machine ID (0~31) */
    private long workerId;

    /** Data-center ID (0~31) */
    private long datacenterId;

    /** Sequence within a millisecond (0~4095) */
    private long sequence = 0L;

    /** Timestamp of the last generated ID */
    private long lastTimestamp = -1L;

    // ==============================Constructors=====================================

    public SnowflakeId() {
        this.datacenterId = getDatacenterId(maxDatacenterId);
        this.workerId = getMaxWorkerId(datacenterId, maxWorkerId);
    }

    /**
     * Constructor
     * @param workerId worker ID (0~31)
     * @param datacenterId data-center ID (0~31)
     */
    public SnowflakeId(long workerId, long datacenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(
                    String.format("worker EsId can't be greater than %d or less than 0", maxWorkerId));
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException(
                    String.format("datacenter EsId can't be greater than %d or less than 0", maxDatacenterId));
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
        logger.debug("SnowflakeId: datacenterId:[{}], workerId:[{}]", datacenterId, workerId);
    }

    // ==============================Methods==========================================
    /**
     * Get the next ID (this method is thread-safe)
     * @return SnowflakeId
     */
    public synchronized long nextId() {
        long timestamp = timeGen();

        // If the current time is earlier than the timestamp of the last generated ID,
        // the system clock has moved backward and an exception should be thrown.
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(String.format(
                    "Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }

        // Changing this line to the one below may result in all values being even.
        // Reference: https://blog.csdn.net/wangzhanzheng/article/details/84937021
        //      sequence = (sequence + 1) & sequenceMask;

        // If IDs are generated at the same time, use the sequence within the millisecond.
        if (lastTimestamp == timestamp) {
            // Use bit operations to determine whether it is >4095, i.e. whether it overflows.
            sequence = (sequence + 1) & sequenceMask;
            // Sequence overflow within the millisecond.
            if (sequence == 0) {
                // Block until the next millisecond and obtain a new timestamp.
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            // Timestamp changed; reset the sequence within the millisecond.
            sequence = 0L;
        }

        // Timestamp of the last generated ID.
        lastTimestamp = timestamp;

        // Shift and combine with OR operations to form a 64-bit ID.
        return ((timestamp - twepoch) << timestampLeftShift) // Timestamp part. Note: twepoch must never be modified.
                | (datacenterId << datacenterIdShift) // Data center.
                | (workerId << workerIdShift) // Machine.
                | sequence; // Sequence number within the millisecond.
    }

    /**
     * <p>
     * Data identifier ID part
     * </p>
     */
    protected static long getDatacenterId(long maxDatacenterId) {
        long id = 0L;
        try {
            InetAddress ip = InetAddress.getLocalHost();
            NetworkInterface network = NetworkInterface.getByInetAddress(ip);
            if (network == null) {
                id = 1L;
            } else {
                byte[] mac = network.getHardwareAddress();
                if (null != mac) {
                    id = ((0x000000FF & (long) mac[mac.length - 1]) | (0x0000FF00 & (((long) mac[mac.length - 2]) << 8))) >> 6;
                    id = id % (maxDatacenterId + 1);
                }
            }
        } catch (Exception e) {
            logger.warn(" getDatacenterId: " + e.getMessage());
        }
        return id;
    }

    /**
     * <p>
     * Get maxWorkerId
     * </p>
     */
    protected static long getMaxWorkerId(long datacenterId, long maxWorkerId) {
        StringBuilder mpid = new StringBuilder();
        mpid.append(datacenterId);
        String name = ManagementFactory.getRuntimeMXBean().getName();
        if (StringUtils.isNotEmpty(name)) {
            /*
             * GET jvmPid
             */
            mpid.append(name.split("@")[0]);
        }
        /*
         * Use the hashcode of MAC + PID to obtain the lower 16 bits.
         */
        return (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1);
    }

    /**
     * Block until the next millisecond, until a new timestamp is obtained.
     * @param lastTimestamp timestamp of the last generated ID
     * @return current timestamp
     */
    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    /**
     * Return the current time in milliseconds.
     * @return current time (milliseconds)
     */
    protected long timeGen() {
        return System.currentTimeMillis();
    }
}

2.4.3. Deployment

2.4.3.1. Cluster Mode

2.4.3.2. How to Manage datacenterId and workerId in Cluster Mode

ZooKeeper or a configuration file.

2.4.4. Problems

2.4.4.1. Clock Rollback

It does not meet high-availability requirements, because a clock rollback directly throws an exception.

2.4.4.1.1. Solutions

In cluster mode, first deploy an NTP time-synchronization server, then have all nodes synchronize their global clocks with this server.
Set a maximum tolerance time. If the clock moves backward, sleep for a while and retry (actually only about 10 ms).
Redundancy strategy
- The machine field has 10 bits and can be divided into two batches. The first batch is 0-512, and the second batch is 512-1023. If machine 0 experiences clock rollback, it can degrade to calling machine 512.

2.4.5. Examples

2.4.5.1. Meituan Leaf

Leaf/README_CN.md at master · Meituan-Dianping/Leaf · GitHub

Leaf: Meituan Open-Sources Its Distributed ID Generation Service - Meituan Tech

2.4.5.2. Baidu uid-generator

Baidu’s Open-Source Distributed ID Generator Is Very Powerful! - SegmentFault

GitHub - baidu/uid-generator: UniqueID generator