分布式系统中ID的需求-白红宇

在过去单机系统中，生成唯一ID比较简单，可以使用MySQL的自增主键或者Oracle中sequence。在现在的大型高并发分布式系统中，以上策略就会有问题了，因为不同的数据库会部署到不同的机器上，一般都是多主实例，而且再加上高并发的话，就会有重复ID的情况了。在分布式系统中，ID有如下需求： 1.全局唯一性：不能出现重复的ID，最基本的要求。 2.数据递增:保证我的下一ID一定大于上一个ID 3.信息安全:防止恶意用户规矩id的规则来获取数据

ID生成的方案##

1.UUID

UUID是指在一台机器在同一时间中生成的数字在所有机器中都是唯一的。算法的核心思想是结合机器的网卡、当地时间、一个随即数来生成UUID。从理论上讲，如果一台机器每秒产生10000000个GUID，则可以保证（概率意义上）3240年不重复。 UUID由以下几部分的组合： 1.当前日期和时间; 2.时钟序列; 3.全局唯一的IEEE机器识别号，如果有网卡，从网卡MAC地址获得，没有网卡以其他方式获; 标准的UUID格式为：xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx (8-4-4-4-12)，以连字号分为五段形式的36个字符，示例：cbfc8eef-5c71-4f4d-bf4b-42f93128ba77 Java标准类库中已经提供了UUID的API。

#Java中生成uuid UUID.randomUUID() 优点： 1.本地生成ID，不需要进行远程调用，时延低 2.扩展性好，基本可以认为没有性能上限缺点： 1.无法保证趋势递增 2.uuid过长，往往用字符串表示，作为主键建立索引查询效率低，常见优化方案为“转化为两个uint64整数存储”或者“折半存储”（折半后不能保证唯一性） 3.信息不安全，基于MAC地址生成UUID的算法可能会造成MAC地址泄露，这个漏洞曾被用于寻找梅丽莎病毒的制作者位置。

2.Snowflake雪花算法

twitter在把存储系统从MySQL迁移到Cassandra的过程中由于Cassandra没有顺序ID生成机制，于是自己开发了一套全局唯一ID生成服务：Snowflake。 Snowflake的结构如下(每部分用-分开):

雪花ID生成的是一个64位的二进制正整数，然后转换成10进制的数。64位二进制数由如下部分组成： 1位标识符：始终是0，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0。 41位时间戳：41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截 )得到的值，这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的。 10位机器标识码：可以部署在1024个节点，如果机器分机房（IDC）部署，这10位可以由 5位机房ID + 5位机器ID 组成。 12位序列：毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号优点： 1.简单高效，生成速度快; 2.时间戳在高位，自增序列在低位，整个ID是趋势递增的，按照时间有序递增。 3.灵活度高，可以根据业务需求，调整bit位的划分，满足不同的需求。缺点： 1.依赖机器的时钟，如果服务器时钟回拨，会导致重复ID生成。 2.在分布式环境上，每个服务器的时钟不可能完全同步，有时会出现不是全局递增的情况。

snowflake Java实现 `public class SnowflakeIdWorker {

/** 开始时间截 (2015-01-01) */private final long twepoch = 1420041600000L;/** 机器id所占的位数 */private final long workerIdBits = 5L;/** 数据标识id所占的位数 */private final long datacenterIdBits = 5L;/** 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */private final long maxWorkerId = -1L ^ (-1L << workerIdBits);/** 支持的最大数据标识id，结果是31 */private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);/** 序列在id中占的位数 */private final long sequenceBits = 12L;/** 机器ID向左移12位 */private final long workerIdShift = sequenceBits;/** 数据标识id向左移17位(12+5) */private final long datacenterIdShift = sequenceBits + workerIdBits;/** 时间截向左移22位(5+5+12) */private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;/** 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095) */private final long sequenceMask = -1L ^ (-1L << sequenceBits);/** 工作机器ID(0~31) */private long workerId;/** 数据中心ID(0~31) */private long datacenterId;/** 毫秒内序列(0~4095) */private long sequence = 0L;/** 上次生成ID的时间截 */private long lastTimestamp = -1L;/** * 构造函数 * @param workerId 工作ID (0~31) * @param datacenterId 数据中心ID (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;}/** * 获得下一个ID (该方法是线程安全的) * @return SnowflakeId */public synchronized long nextId() {    long timestamp = timeGen();    //如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常    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;    }    //上次生成ID的时间截    lastTimestamp = timestamp;    //移位并通过或运算拼到一起组成64位的ID    return ((timestamp - twepoch) << timestampLeftShift) //            | (datacenterId << datacenterIdShift) //            | (workerId << workerIdShift) //            | sequence;}/** * 阻塞到下一个毫秒，直到获得新的时间戳 * @param lastTimestamp 上次生成ID的时间截 * @return 当前时间戳 */protected long tilNextMillis(long lastTimestamp) {    long timestamp = timeGen();    while (timestamp <= lastTimestamp) {        timestamp = timeGen();    }    return timestamp;}/** * 返回以毫秒为单位的当前时间 * @return 当前时间(毫秒) */protected long timeGen() {    return System.currentTimeMillis();}/** 测试 */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);    }}复制代码

3.Mysql自增机制

主要思路是采用数据库自增ID + replace_into实现唯一ID的获取。 create table t_global_id( id bigint(20) unsigned not null auto_increment, stub char(1) not null default '', primary key (id), unique key stub (stub) ) engine=MyISAM;

#每次业务可以使用以下SQL读写MySQL得到ID号 replace into t_golbal_id(stub) values('a'); select last_insert_id(); replace into跟insert功能类似，不同点在于：replace into首先尝试插入数据列表中，如果发现表中已经有此行数据（根据主键或唯一索引判断）则先删除，再插入。否则直接插入新数据。当然为了避免数据库的单点故障，最少需要两个数据库实例，通过区分auto_increment的起始值和步长来生成奇偶数的ID。如下： `Server1： auto-increment-increment = 2 auto-increment-offset = 1

Server2： auto-increment-increment = 2 auto-increment-offset = 2` 优点：简单，充分借助数据库的自增ID机制，可靠性高，生成有序的ID。缺点： I1.生成依赖数据库单机的读写性能。 2依赖数据库，当数据库异常时整个系统不可用。

4.Redis原子计数器

Redis实现了一个原子操作INCR和INCRBY实现递增的操作。当使用数据库性能不够时，可以采用Redis来代替，同时使用Redis集群来提高吞吐量。可以初始化每台Redis的初始值为1,2,3,4,5，然后步长为5。各个Redis生成的ID为： A：1，6，11，16，21 B：2，7，12，17，22 C：3，8，13，18，23 D：4，9，14，19，24 E：5，10，15，20，25 优点： 1.不依赖于数据库，灵活方便，且性能优于数据库。 2.数字ID天然排序，对分页或者需要排序的结果很有帮助。缺点： 1.如果系统中没有Redis，还需要引入新的组件，增加系统复杂度。 2.需要编码和配置的工作量比较大。这个都不是最大的问题。关于分布式全局唯一ID的生成，各个互联网公司有很多实现方案，比如美团点评的Leaf-snowflake，用zookeeper解决了各个服务器时钟回拨的问题，弱依赖zookeeper。以及Leaf-segment类似上面数据库批量ID获取的方案。