分布式系统中的ID生成

原创
2015/12/01 22:07
阅读数 216

问题

在分布式系统中常遇到ID生成问题:

  • 场景1,在分库分表中需要保证某类ID唯一,这样使用主键自增的策略就不再合适

  • 场景2,需要某类ID需要具有同一特性来标识

诸如此类。

方案

有很多解决方案,比如

  1. 基于数据库主键自增策略(及其变种,如分片生成以提高效率、分库分表生成以解决单点问题等)

  2. UUID(简单但比较丑陋,生成的ID无规律,也有方案是基于UUID,但更简短

  3. 基于MongoDB的id策略

  4. DIY的ID(以不同用途的字符组装到一起,然后做编码转换以满足需要)

这里介绍一种方案4的实现,基本思想源于twitter的Snowflake方案,该实现可提供高性能、低延迟、高可用的ID生成。

每个ID是一个long类型的整数,结构如下:


0           41     51          64
+-----------+------+------------+

|timestamp  |node  |increment   |
+-----------+------+------------+

前42位是timestamp,这样可以使ID生成变得有序。以中间10位标识节点,这样可以有1024个节点。最后12位为了解决并发冲突问题,并发请求时以此12位作累加,这样在同一个前42位内最多可以生成2的12次方个ID。

通过以上方案,可以快速生成时间有序的,带节点标识的ID。基于这个思想,我们可以做各种变形以满足自身需要,比如可以调整这三部分的顺序和每一部分的位数以满足具体场景;可以开启多个进程,每个进程负责某些node节点的ID生成以避免单点;可以精简位数,并做编码转换以减少ID长度等等。

【问题】 该方案严重依赖于系统时间,如果系统时钟发生错误,生成的ID就可能有问题。

代码实现

按照以上描述的策略的基本代码实现可参看:

/**
 * 42位的时间前缀+10位的节点标识+12位的sequence避免并发的数字(12位不够用时强制得到新的时间前缀)
 * <p>
 * <b>对系统时间的依赖性非常强,需要关闭ntp的时间同步功能,或者当检测到ntp时间调整后,拒绝分配id。
 * 
 * @author sumory.wu
 * @date 2012-2-26 下午6:40:28
 */
public class IdWorker {
    private final static Logger logger = LoggerFactory.getLogger(IdWorker.class);

    private final long workerId;
    private final long snsEpoch = 1330328109047L;// 起始标记点,作为基准
    private long sequence = 0L;// 0,并发控制
    private final long workerIdBits = 10L;// 只允许workid的范围为:0-1023
    private final long maxWorkerId = -1L ^ -1L << this.workerIdBits;// 1023,1111111111,10位
    private final long sequenceBits = 12L;// sequence值控制在0-4095

    private final long workerIdShift = this.sequenceBits;// 12
    private final long timestampLeftShift = this.sequenceBits + this.workerIdBits;// 22
    private final long sequenceMask = -1L ^ -1L << this.sequenceBits;// 4095,111111111111,12位

    private long lastTimestamp = -1L;

    public IdWorker(long workerId) {
        super();
        if (workerId > this.maxWorkerId || workerId < 0) {// workid < 1024[10位:2的10次方]
            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() throws Exception {
        long timestamp = this.timeGen();
        if (this.lastTimestamp == timestamp) {// 如果上一个timestamp与新产生的相等,则sequence加一(0-4095循环),下次再使用时sequence是新值
            //System.out.println("lastTimeStamp:" + lastTimestamp);
            this.sequence = this.sequence + 1 & this.sequenceMask;
            if (this.sequence == 0) {
                timestamp = this.tilNextMillis(this.lastTimestamp);// 重新生成timestamp
            }
        }
        else {
            this.sequence = 0;
        }
        if (timestamp < this.lastTimestamp) {
            logger.error(String.format("Clock moved backwards.Refusing to generate id for %d milliseconds", (this.lastTimestamp - timestamp)));
            throw new Exception(String.format("Clock moved backwards.Refusing to generate id for %d milliseconds", (this.lastTimestamp - timestamp)));
        }

        this.lastTimestamp = timestamp;
        // 生成的timestamp
        return timestamp - this.snsEpoch << this.timestampLeftShift | this.workerId << this.workerIdShift | this.sequence;
    }

    /**
     * 保证返回的毫秒数在参数之后
     * 
     * @param lastTimestamp
     * @return
     */
    private long tilNextMillis(long lastTimestamp) {
        long timestamp = this.timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = this.timeGen();
        }
        return timestamp;
    }

    /**
     * 获得系统当前毫秒数
     * 
     * @return
     */
    private long timeGen() {
        return System.currentTimeMillis();
    }

    public static void main(String[] args) throws Exception {
        IdWorker iw1 = new IdWorker(1);
       
        for (int i = 0; i < 10; i++) {
            System.out.println(iw1.nextId());
        }
    }
}

实际应用

一个用于处理分布式系统中ID生成,唯一性字段值管理的通用模块UC

可以考虑用分布式锁来实现

http://roadrunners.iteye.com/blog/2225563 

展开阅读全文
打赏
0
15 收藏
分享
加载中
更多评论
打赏
0 评论
15 收藏
0
分享
返回顶部
顶部