分布式ID详解

分布式ID

在我们业务数据量不大的时候，单库单表完全可以支撑现有业务，数据再大一点搞个MySQL主从同步读写分离也能对付。但随着数据日渐增长，主从同步也扛不住了，就需要对数据库进行分库分表。在分库之后， 数据遍布在不同服务器上的数据库，数据库的自增主键已经没办法满足生成的主键唯一了，这个时候就需要生成分布式ID了。

在分布式系统中，分布式ID的使用场景主要包括高并发请求、跨服务的数据一致性和多节点的唯一标识符生成。例如，在电商平台中，为每个订单生成唯一的ID是非常重要的。一个高并发的电商系统可能有多个服务器同时处理订单请求，使用分布式ID可以避免ID冲突。类似地，在微服务架构中，各个服务可能需要生成唯一的标识符来标记请求或数据记录。分布式ID使得这些标识符在整个系统中保持唯一，从而避免数据混乱或冲突。

分布式ID生成一般都需要满足这些条件：

• 全局唯一：必须保证ID是全局性唯一的，这是基本要求；
• 高性能：高可用低延时，ID生成响应要块，否则反倒会成为业务瓶颈；
• 高可用：100%的可用性是骗人的，但是也要无限接近于100%的可用性；
• 趋势递增：如果要把ID存放在数据库的话，ID的有序性可以提升数据库写入速度。并且很多时候，我们还很有可能会直接通过ID来进行排序；
• 安全：分布式ID中不包含敏感信息；

有以下常见几种实现分布式ID方式：

处理上述这些方案外，利用系统当前时间也能实现。一般如果用这个方案，是将当前时间跟很多其他的业务字段拼接起来，作为一个ID，如果业务上你觉得可以接受，那么也是可以的。你可以将别的业务字段值跟当前时间拼接起来，组成一个全局唯一的编号。

UUID

UUID的全称是 “Universally Unique Identifier”，即通用唯一标识符。UUID是一种128位长的唯一标识符，通常表示为32个十六进制字符，分为5组，形式为xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx，其中每个x表示一个十六进制数字。

UUID的生成算法有不同版本，每个版本采用不同的方法来确保唯一性。

• UUIDv1通过结合当前时间戳和机器的MAC地址生成唯一标识符。生成过程涉及获取当前时间的100纳秒级别精度的时间戳，加上机器的MAC地址，以及一个序列号（用于处理同一时间生成多个UUID的情况）。时间戳和MAC地址确保了UUID在全球范围内的唯一性。此版本的UUID在时间上有序，但可能会暴露生成UUID的计算机信息，适用于需要时间排序的场景。
• UUIDv3基于指定的名称和命名空间生成UUID。生成过程中，将名称与命名空间拼接后，通过MD5哈希算法计算出一个128位的哈希值，然后将其格式化为UUID。这种方法确保了相同的名称和命名空间组合总是生成相同的UUID。UUIDv3适用于需要根据相同名称和命名空间生成一致UUID的场景，例如，生成固定格式的ID。
• UUIDv4使用随机数生成128位的UUID，生成过程包括生成122位的随机数，并在UUID中设置特定的版本号（4）和变体位。这种UUID生成方法完全依赖随机数来保证唯一性，具有很高的随机性，生成过程简单且效率高。UUIDv4适合需要高性能和随机性的场景，如生成临时标识符或分布式系统中的唯一ID。
• UUIDv5类似于UUIDv3，但使用SHA-1哈希算法代替MD5来生成UUID。生成过程中，将指定的名称和命名空间拼接后，通过SHA-1计算出一个160位的哈希值，然后将其格式化为UUID，设置版本号为5。这种方法比UUIDv3更安全，适合需要基于名称生成UUID的场景，同时提供了更强的哈希安全性。

在实际开发中，UUIDv4是最常用的UUID版本。UUIDv4生成的UUID通过随机数确保唯一性，不依赖于时间戳或机器信息。在Java中，可以使用java.util.UUID类来生成UUIDv4。

public class UUIDExample {
    public static void main(String[] args) {
        // 生成一个UUIDv4
        UUID uuid = UUID.randomUUID();
        System.out.println("生成的UUIDv4: " + uuid.toString());
    }
}

UUID一般不会作为主键使用，因为UUID太长了、占用空间大，作为主键性能太差了，且UUID不具有有序性，会导致B+树索引在写的时候有过多的随机写操作，总之就是无序的性能开销大。适合于随机生成个什么文件名、编号之类的。

Snowflake算法

Snowflake算法又称雪花算法，是一种由Twitter开发的分布式ID生成算法，用于生成唯一的64位ID。这种算法特别适合于分布式系统，能够在多个节点上高效地生成唯一ID。

算法思路是是把一个64位的long型的ID，1个bit是不用的，用其中的41bits作为毫秒数，用10bits作为工作机器ID，12bits作为序列号。

• 0-1bit：不用，为啥呢？因为二进制里第一个bit为如果是1，那么都是负数，但是我们生成的ID都是正数，所以第一个bit统一都是0；
• 1-41bit：表示的是时间戳，单位是毫秒。41bits可以表示的数字多达2^41 - 1，也就是可以标识2^41 - 1个毫秒值，换算成年就是表示69年的时间；
• 42-47bit：记录工作机器ID，代表的是这个服务最多可以部署在2^10台机器上，也就是1024台机器。但是10bits里5个bits代表机房ID，5个bits代表机器ID。意思就是最多代表2^5个机房（32 个机房），每个机房里可以代表 2^5 个机器（32 台机器）；
• 64-75bit：这个是用来记录同一个毫秒内产生的不同ID，12bits可以代表的最大正整数是2^12 - 1 = 4096 ，也就是说可以用这个12bits代表的数字来区分同一个毫秒内的4096个不同的ID；

雪花算法相对来说还是比较靠谱的，毫秒数在高位，自增序列在低位，整个ID都是趋势递增的。不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的，能达到百万计QPS。但是雪花算法强依赖时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。为了规避雪花算法的缺点，一些国内的大厂做了改进，像美团的Leaf，百度的uid-generator，都是基于雪花算法来实现的。所以你要真是搞分布式 ID生成，如果是高并发啥的，那么用这个应该性能比较好，一般每秒几万并发的场景，也足够用了。

以下是一个Snowflake算法的简化Java实现，实际开发中可能直接引用第三方库。

public class SnowflakeIdGenerator {
    private final long epoch = 1622548800000L; // 自定义Epoch时间
    private final long dataCenterIdBits = 5L;  // 数据中心ID位数
    private final long workerIdBits = 5L;      // 工作机器ID位数
    private final long sequenceBits = 12L;     // 序列号位数
    
    private final long maxDataCenterId = -1L ^ (-1L << dataCenterIdBits);
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);
    
    private long dataCenterId; // 数据中心ID
    private long workerId;     // 工作机器ID
    private long sequence = 0L; // 序列号
    private long lastTimestamp = -1L; // 上次生成ID的时间戳

    public SnowflakeIdGenerator(long dataCenterId, long workerId) {
        if (dataCenterId > maxDataCenterId || dataCenterId < 0) {
            throw new IllegalArgumentException("DataCenterId超出范围");
        }
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException("WorkerId超出范围");
        }
        this.dataCenterId = dataCenterId;
        this.workerId = workerId;
    }

    public synchronized long generateId() {
        long timestamp = System.currentTimeMillis();
        
        if (timestamp < lastTimestamp) {
            throw new RuntimeException("系统时间回退");
        }
        
        if (timestamp == lastTimestamp) {
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                timestamp = waitNextMillis(timestamp);
            }
        } else {
            sequence = 0L;
        }
        
        lastTimestamp = timestamp;
        return ((timestamp - epoch) << (dataCenterIdBits + workerIdBits + sequenceBits)) |
               (dataCenterId << (workerIdBits + sequenceBits)) |
               (workerId << sequenceBits) |
               sequence;
    }

    private long waitNextMillis(long lastTimestamp) {
        long timestamp = System.currentTimeMillis();
        while (timestamp <= lastTimestamp) {
            timestamp = System.currentTimeMillis();
        }
        return timestamp;
    }
}

数据库自增ID

在分布式系统中，使用数据库自增ID作为分布式ID，通常涉及在一个集中式的数据库系统中生成自增ID，然后将其分发到分布式系统的各个节点。

在数据库中创建一个自增ID的表。每次需要新的ID时，向这个表插入一条记录，然后获取即可。用数据库的自增ID功能，如MySQL的AUTO_INCREMENT，PostgreSQL的SERIAL等，用来保证ID的唯一性和递增性。

以下是一个简化的Java代码示例，演示如何从数据库中获取自增ID：

public class DistributedIdGenerator {

    private Connection connection;

    public DistributedIdGenerator(String dbUrl, String user, String password) throws Exception {
        connection = DriverManager.getConnection(dbUrl, user, password);
    }

    public long getNextId() throws Exception {
        Statement statement = connection.createStatement();
        // 假设存在一个名为'id_generator'的表，其中包含一个自增列'next_id'
        ResultSet resultSet = statement.executeQuery("SELECT next_id FROM id_generator FOR UPDATE");
        if (resultSet.next()) {
            long nextId = resultSet.getLong("next_id");
            // 更新ID
            statement.executeUpdate("UPDATE id_generator SET next_id = next_id + 1");
            return nextId;
        } else {
            throw new RuntimeException("无法获取新的ID");
        }
    }

    public static void main(String[] args) {
        try {
            DistributedIdGenerator idGenerator = new DistributedIdGenerator("jdbc:mysql://localhost:3306/mydb", "user", "password");
            long newId = idGenerator.getNextId();
            System.out.println("生成的ID: " + newId);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

往一个库的一个表里插入一条没什么业务含义的数据，获取一个数据库自增的一个ID，拿到这个ID之后再往对应的分库分表里去写入。缺点是高并发存在瓶颈，优点是简单方便。适用于并发不高，但是数据量太大导致的分库分表扩容，可能每秒最高并发最多就几百，那么就走单独的一个库和表生成自增主键即可。

Leaf算法

Leaf算法是一种用于生成分布式唯一ID的算法，由美团点评开发。 采用了基于Snowflake的设计思路，但将ID生成和ID管理分离。Leaf-Server负责分配ID段，Leaf-Worker负责在本地生成ID。

Leaf算法通过将ID生成和ID段管理分开，能够高效地生成ID。Leaf-Worker本地生成ID，减少了对中心服务器的依赖。通过分布式的Leaf-Server，Leaf算法支持高可用的ID生成。即使部分Leaf-Server出现故障，系统仍然可以继续生成ID。

Leaf算法的核心思想是将ID生成和ID管理分开，利用ID段来减少对中心服务器的压力。

1. Leaf-Server预分配一段ID给Leaf-Worker。ID段通常包括一个起始ID和一个结束ID，Leaf-Worker在该范围内生成ID。
2. Leaf-Worker从分配的ID段中生成ID，并维护一个指针或游标来跟踪当前使用的ID。每次生成ID时，Leaf-Worker都会从本地的ID段范围中获取新的ID。
3. 当Leaf-Worker用完当前ID段或需要更多ID时，它会向Leaf-Server请求一个新的ID段。Leaf-Server根据当前的负载和可用资源分配新的ID段。

以下是一个简化的Java代码示例，展示如何使用Leaf算法生成ID：

public class LeafWorker {
    private final long segmentStart;
    private final long segmentEnd;
    private final AtomicLong cursor;

    public LeafWorker(long segmentStart, long segmentEnd) {
        this.segmentStart = segmentStart;
        this.segmentEnd = segmentEnd;
        this.cursor = new AtomicLong(segmentStart);
    }

    public long getNextId() {
        long id = cursor.getAndIncrement();
        if (id > segmentEnd) {
            throw new RuntimeException("ID超出段范围");
        }
        return id;
    }
}

public class LeafServer {
    private long currentSegmentStart = 0;
    private long segmentSize = 1000; // 每次分配的ID段大小

    public synchronized LeafWorker requestSegment() {
        long start = currentSegmentStart;
        long end = start + segmentSize - 1;
        currentSegmentStart = end + 1;
        return new LeafWorker(start, end);
    }
}

public class Main {
    public static void main(String[] args) {
        LeafServer leafServer = new LeafServer();
        LeafWorker leafWorker = leafServer.requestSegment();
        
        for (int i = 0; i < 10; i++) {
            System.out.println("生成的ID: " + leafWorker.getNextId());
        }
    }
}

在需要高效生成唯一ID的分布式环境中，Leaf算法提供了高性能和高可用性。它适用于大规模应用和系统，其中ID生成的需求很高，且需要支持分布式架构。

Redis自增ID

Redis自增ID是基于对数据库自增的改进，原理就是利用Redis的INCR命令实现ID的原子性自增。不依赖于数据库，灵活方便，且性能优于数据库，但是如果系统中没有Redis，还需要引入新的组件，会增加系统复杂度。

Redis是内存数据库，INCR和INCRBY命令都是原子操作，执行速度非常快。Redis在单节点模式下可能成为单点故障。如果Redis服务出现故障，可能会影响ID生成。

以下是一个使用Java和Redis实现自增ID生成的示例代码：

public class RedisIdGenerator {
    private Jedis jedis;
    private String key;

    public RedisIdGenerator(String redisHost, int redisPort, String key) {
        this.jedis = new Jedis(redisHost, redisPort);
        this.key = key;
    }

    public long getNextId() {
        return jedis.incr(key);
    }

    public static void main(String[] args) {
        RedisIdGenerator idGenerator = new RedisIdGenerator("localhost", 6379, "unique_id");
        
        for (int i = 0; i < 10; i++) {
            System.out.println("生成的ID: " + idGenerator.getNextId());
        }
    }
}

Redis是内存数据库，具有极高的性能，Redis也能够满足实时系统需要快速生成唯一ID的情况。对于不需要复杂ID生成逻辑的应用场景，Redis自增ID是一种简单且高效的解决方案。例如，为日志条目生成唯一的ID，方便日志的管理和查询。