Leaf——美团点评分布式ID生成系统

前言

在复杂分布式系统中，往往需要对大量的数据和消息进行唯一标识。如在美团点评的金融、支付、餐饮、酒店、猫眼电影等产品的系统中，数据日渐增长，对数据分库分表后需要有一个唯一ID来标识一条数据或消息，数据库的自增ID显然不能满足需求；特别一点的如订单、骑手、优惠券也都需要有唯一ID做标识。此时一个能够生成全局唯一ID的系统是非常必要的。概括下来，那业务系统对ID号的要求有哪些呢？

1. 全局唯一性：不能出现重复的ID号，既然是唯一标识，这是最基本的要求。
2. 趋势递增：在MySQL InnoDB引擎中使用的是聚集索引，由于多数RDBMS使用B-tree的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能。
3. 单调递增：保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序等特殊需求。
4. 信息安全：如果ID是连续的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定URL即可；如果是订单号就更危险了，竞对可以直接知道我们一天的单量。所以在一些应用场景下，会需要ID无规则、不规则。

上述123对应三类不同的场景，3和4需求还是互斥的，无法使用同一个方案满足。

同时除了对ID号码自身的要求，业务还对ID号生成系统的可用性要求极高，想象一下，如果ID生成系统瘫痪，整个美团点评支付、优惠券发券、骑手派单等关键动作都无法执行，这就会带来一场灾难。

由此总结下一个ID生成系统应该做到如下几点：

1. 平均延迟和TP999延迟都要尽可能低；
2. 可用性5个9；
3. 高QPS。

在实际的应用中，我们经常会遇到id生成问题。其中最基本的就是要保证id的唯一性。常见解决方案如下。

1. 微软公司通用唯一识别码（UUID）
2. Twitter公司雪花算法（SnowFlake）
3. 基于数据库的id自增

其中，使用数据库进行id自增是在单机应用中使用最普遍的id生成方式，它能够完全保证id的不重复。但id的自增并不是在任何数据库都支持，这就给数据库迁移造成了麻烦。并且，数据库的解决方案在分布式环境下的只能保证单个数据库作为生产数据库，存在单点故障的危险。

而微软的UUID显然是一种极佳的解决方案，它由当前日期时间、时钟序列、全局唯一的机器标识号来生成一段无序的字符串id。 它的确实现了ID的唯一性但肉眼可辨识度比较差。虽然满足了我们的基本要求，但实际很多的生产中我们还有id根据时间进行递增的进阶要求。这显然是无法实现的。

所以，下面我们就讲讲Twitter公司的雪花算法是如何进行id生成的。

雪花算法的优缺点是：

优点：

• 毫秒数在高位，自增序列在低位，整个ID都是趋势递增的。
• 不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的。
• 可以根据自身业务特性分配bit位，非常灵活。

缺点：

• 强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。

应用举例Mongdb objectID

MongoDB官方文档 ObjectID可以算作是和snowflake类似方法，通过“时间+机器码+pid+inc”共12个字节，通过4+3+2+3的方式最终标识成一个24长度的十六进制字符。

雪花的结构

首先，我们从它的设计入手，自己想一下，如果让我们设计一个id，如何保证既能唯一又能按照时间递增？

首先，既然要按照时间递增，那么这个id一定是个数，而不是字符串。并且在id中时间要作为第一影响因素，越晚生成的id，数字越大。那么整个数字id的前几位一定是时间戳。这就实现了按照时间递增。

那么同时间的并发生成如何保证唯一性呢？我们还会想到在分布式情况下要在多台机器上生成id，那么直接再加上这台机器的id就好了。

Ok，继续思考，时间相同，在同一台机器上生成的多个id如何保证唯一性，这时候就会想，也许可以再在后面加一串随机数或者序列之类的。

想到这，就有了下面的雪花算法的结构图。

可以看出，雪花算法生成的id既保证了唯一性，又因为是long存储，所以能够按照时间进行排序。至于69年的限制可以忽略不计。

/**
* 雪花算法--分布式系统ID
* @author huzhiyong
*
*/
public class IdWorker {
private long workerId;
private long datacenterId;
private long sequence;

public IdWorker(long workerId, long datacenterId, long sequence) {  
    // sanity check for workerId  
    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));  
    }  
    System.out.printf(  
            "worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d",  
            timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId);  
    this.workerId = workerId;  
    this.datacenterId = datacenterId;  
    this.sequence = sequence;  
}

private long twepoch = 1288834974657L;  
private long workerIdBits = 5L;  
private long datacenterIdBits = 5L;  
private long maxWorkerId = -1L ^ (-1L << workerIdBits);  
private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);  
private long sequenceBits = 12L;  
private long workerIdShift = sequenceBits;  
private long datacenterIdShift = sequenceBits + workerIdBits;  
private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;  
private long sequenceMask = -1L ^ (-1L << sequenceBits);  
private long lastTimestamp = -1L;

public long getWorkerId() {  
    return workerId;  
}

public long getDatacenterId() {  
    return datacenterId;  
}

public long getTimestamp() {  
    return System.currentTimeMillis();  
}

public synchronized long nextId() {  
    long timestamp = timeGen();  
    if (timestamp < lastTimestamp) {  
        System.err.printf("clock is moving backwards. Rejecting requests until %d.", 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 = 0;  
    }  
    lastTimestamp = timestamp;  
    return ((timestamp - twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift)  
            | (workerId << workerIdShift) | sequence;  
}

private long tilNextMillis(long lastTimestamp) {  
    long timestamp = timeGen();  
    while (timestamp <= lastTimestamp) {  
        timestamp = timeGen();  
    }  
    return timestamp;  
}

private long timeGen() {  
    return System.currentTimeMillis();  
}

// ---------------测试---------------  
public static void main(String\[\] args) {  
    IdWorker worker = new IdWorker(1, 1, 1);  
    for (int i = 0; i < 30; i++) {  
        System.out.println(worker.nextId());  
    }  
}  

}