5分钟了解分布式ID生成方案

中大型的互联网应用中,分布式ID生成是基础的必须存在的基础应用. 然而想要成功实施还是很困难的.

UUID

UUID是指在一台机器上生成的数字,它保证对在同一时空中的所有机器都是唯一的。通常平台会提供生成的API。按照开放软件基金会(OSF)制定的标准计算,用到了以太网卡地址、纳秒级时间、芯片ID码和许多可能的数字.

UUID由以下几部分的组合:

  • 当前日期和时间,UUID的第一个部分与时间有关,如果你在生成一个UUID之后,过几秒又生成一个UUID,则第一个部分不同,其余相同。
  • 时钟序列。
  • 全局唯一的IEEE机器识别号,如果有网卡,从网卡MAC地址获得,没有网卡以其他方式获得。

有 4 种不同的基本 UUID 类型:基于时间的 UUID、DCE 安全 UUID、基于名称的 UUID 和随机生成的 UUID。

Java使用UUID非常方便

UUID uuid = UUID.randomUUID();

格式是35b3dda6-f481-410a-b393-9adc91703c68

优点:使用方便,无状态
缺点:太长,32位,不适合做数据库主键索引

SnowFlake

Twitter的SnowFlake是一个非常优秀的id生成方案,实现也非常简单,8Byte 是一个Long,8Byte等于64bit,核心代码就是毫秒级时间41位+机器ID 10位+毫秒内序列12位。当然可以调整机器位数和毫秒内序列位数比例,实际上从这个项目衍生出来很多实现方式。该项目地址为:https://github.com/twitter/snowflake是用Scala实现的。

优点:

  • 比UUID短,一般9-17位左右;
  • 性能非常出色,每秒几十万;

如果能用snowFlaker的方式,绝对不用UUID。

Flickr

采用mysql自增长id实现,实现也非常简单,至少使用两个节点容灾,

设置节点一

auto_increment_increment=2;
auto_increment_offset=1;

设置节点二

auto_increment_increment=2;
auto_increment_offset=2;

需要注意的是这两个配置最好放在配置文件中,否则mysql服务重启将丢失设置;如果直接通过set来设置,已经建立的连接不会改变变量的值,特别是使用连接池的时候。

分表在两个库里面建表
1
2
3
4
5
6
CREATE TABLE `tickets1` (
`id` bigint(20) unsigned NOT NULL auto_increment,
`stub` char(1) NOT NULL default '',
PRIMARY KEY (`id`),
UNIQUE KEY `stub` (`stub`)
) ENGINE=MyISAM

注意建的是MyISAM表,MyISAM是表级锁,能保证所有replace的原子性。

不断的通过replace促使id自增,这样表中只有一条记录。

REPLACE INTO tickets1 (stub) VALUES ('a')REPLACE INTO tickets1 (stub) VALUES ('a')

在同一个连接内,通过last insert id获取自增的id值。

对MyISAM性能影响比较大的参数是key_buffer_size,可以适当调整。

优点:

  • 对于数据量不是特别大的应用,长度最小,从零开始。
  • 如果已经有应用是基于sequence或者mysql的自增id,采用此方案非常容易迁移,兼容性好。
  • 这种方案是没有绝对顺序的,只能有一个近似顺序。有可能一个实例跑的更快。

总结

  1. Id首先要保证的是全局唯一,可以不必保证精确的顺序性,保证顺序意义不大,试想,就算这里保证了,由于现在的系统都是分布式的,先拿到的也不一定会先执行完。

  2. 只要有大概的顺序对于调试、简单识别而言已经非常不错。

  3. 如果在高并发,大数据量的情况下,建议采用SnowFake方案,性能非常突出,而对于需要兼容老业务的应用,特别是拿到id要进行拼装以表示某种意义,并发又不那么高,可以使用flickr的方案,两台物理机也能轻松到达1.8万tps,响应时间在毫秒级。

  4. Id的长度也是一个非常重要的指标,如果在并发量比较大的情况下,可以计算一下,传输的数据量非常可观。

SnowFlake Java版实现

package com.meililinc.mls.datastruct;

public class SnowFlakeIdWorker {

    private final long workerId;
    private final static long twepoch = 1390838400000L;
    private Long sequence = 0L;
    private final static long workerIdBits = 4L;
    public final static long maxWorkerId = -1L ^ -1L << workerIdBits;
    private final static long sequenceBits = 10L;
    private final static long workerIdShift = sequenceBits;
    private final static long timestampLeftShift = sequenceBits + workerIdBits;
    public final static long sequenceMask = -1L ^ -1L << sequenceBits;
    private long lastTimestamp = -1L;

    public SnowFlakeIdWorker(final long workerId) {
        super();
        if (workerId > this.maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format(
                    "worker Id can't be greater than %d or less than 0",
                    this.maxWorkerId));
        }
        this.workerId = workerId;
    }

    public synchronized long nextId() {
        long timestamp = this.timeGen();
        if (this.lastTimestamp == timestamp) {
            this.sequence = (this.sequence + 1) & this.sequenceMask;
            if (this.sequence == 0) {
                System.out.println("###########" + sequenceMask);
                timestamp = this.tilNextMillis(this.lastTimestamp);
            }
        } else {
            this.sequence = 0L;
        }
        if (timestamp < this.lastTimestamp) {
            try {
                throw new Exception(
                        String.format(
                                "Clock moved backwards.  Refusing to generate id for %d milliseconds",
                                this.lastTimestamp - timestamp));
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        this.lastTimestamp = timestamp;
        long nextId = ((timestamp - twepoch << timestampLeftShift))
                | (this.workerId << this.workerIdShift) | (this.sequence);
        return nextId;
    }

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

    private long timeGen() {
        return System.currentTimeMillis();
    }
}
文章目录
  1. 1. UUID
  2. 2. SnowFlake
  3. 3. Flickr
  4. 4. 总结
  5. 5. SnowFlake Java版实现
|