设计一款永不重复的高性能分布式发号器：如何根据设计实现多场景的发号器

如何根据设计实现多场景的发号器

项目结构

首先，我们的多场景发号器支持多种配置模式:嵌入发布模式、中心服务器发布模式、REST发布模式，因此我们对要实现的项目结构做个整体规划，如下图所示。

对应的项目结构如下：

/vesta-id-generator
/vesta-id-generator/vesta-client
/vesta-id-generator/vesta-doc
/vesta-id-generator/vesta-intf
/vesta-id-generator/vesta-rest
/vesta-id-generator/vesta-rest-netty
/vesta-id-generator/vesta-sample
/vesta-id-generator/vesta-server
/vesta-id-generator/vesta-service
/vesta-id-generator/vesta-theme
/vesta-id-generator/deploy-maven.sh
/vesta-id-generator/make-release.sh
/vesta-id-generator/pom.xml
/vesta-id-generator/LICENSE
/vesta-id-generator/README. md

对应的每个项目元素的职责和功能如下：

• vesta-id-generator：所有项目的父项目。
• vesta-id-generator/vesta-intf：发号器抽象出来的对外的接口。
• vesta-id-generator/vesta-service：实现发号器接口的核心项目。
• vesta-id-generator/vesta- server：把发号器服务通过Dubbo服务导出的项目。
• vesta-id-generator/vesta-rest：通过Spring Boot启动的REST模式的发号器服务器。
• vesta id-generator/vesta-rest-netty：通过Netty 启动的REST模式的发号器服务器。
• vesta-id-generator/vesta-client：导入发号器Dubbo服务的客户端项目。
• vesta id-generator/vesta-sample：嵌入式部署模式和Dubbo服务部署模式的使用示例。
• vesta id-generator/vesta-doc：包含架构设计文档、压测文档和使用向导等文档。
• vesta-id-generator/deploy-maven.sh：一键发布发号器依赖Jar包到Maven库。
• vesta-id-generator/make-release.sh：一键打包发号器。
• vesta-id-generator/pom.xml:发号器的Maven打包文件。
• vesta-id-generator/LICENSE：开源协议，本项目采用Apache License 2.0。
• vesta-id-generator/README.md：入门向导文件。

我们基于以下原则划分项目。

• 有的需求都堆砌在一起，需要根据功能职责对项目进行划分，因此，我们主要将项目有的需求都堆砌在一起，需要根据功能职责对项目进行划分，因此，我们主要将项目拆分成发号器服务的接口模块、实现模块，针对不同的发布模式的服务导出项目。
• 我们开发的是一个开源项目，希望该开源项目简单实用，使用者下载后根据项目结构即.可判断如何使用。因此，我们在根项目中增加了README文档，以及更丰富的doc项目下的文档，并且提供了一键打包和发布的脚本，还提供了演示使用发号器项目的示例项目。
• 我们分离了发号器的接口项目和实现项目，因为不同场景下的需求不一样，对于REST发布模式，不需要依赖发号器的接口和实现；对于Dubbo服务的客户端，只需要依赖发号器的接口即可；对于嵌入式发布模式，不但需要依赖发号器的接口，还需要依赖它的实现。

服务接口的定义

根据前面对需求的整理，我们对多场景发号器的接口实现如下：

public interface IdService {

    public long genId();

    public Id expId(long id) ;

    public long makeId (long time, long seq) ;

    public long makeId(long time,long seq, long machine) ;

    public long makeId (long genMethod, long time, long seq, long machine);

    public long makeId(long type, long genMethod, long time ,
        long seq, long machine) ;

    public long makeId (long version, long type, long genMethod,
        long time,long seq, long machine) ;

   public Date transTime (long time) ;
}

其中主要包含如下服务方法(按照重要程度排列)。

• genId):这是分布式发号器的主要API,用来产生唯一ID。
• expId(long id):这是产生唯一ID 的反向操作，可以对一个ID内包含的信息进行解读, 用人可读的形式来表达。
• makl...):用来伪造某-一时间的ID。
• trans Time(long time):该方法用于将整型时间翻译成格式化时间。

上面的接口定义简单、清晰、易懂，只定义了必要的功能。

服务接口的实现

在实现类的设计上，我们设计了两层结构:抽象类AbstractldServicelmpl 和实体类IdServicelmpl。抽象类AbstractldServicelmpl实现那些在任何场景下都不变的逻辑，而可变的逻辑被放到了实体类中实现;实体类IdServiceImpl则是最通用的实现方式。

实现类的类图如下图所示。

从图中可以看到，在抽象类里包含了如下4个属性：

protected long machineId;
protected long genMe thod;
protected long type;
protected long version;

这4个属性分别代表机器ID、生成方式、类型和版本。对于任意一个发号器部署实例，这些属性一旦固定下来将不会改变，因此，我们将这些属性和其处理逻辑放到了抽象的父类中。

现在我们来看看产生发号器的逻辑，主逻辑被封装在抽象父类AbstractldServicelmpl中，代码如下：

public long genId() (

    Id id- new Id() ;

    id.setMachine (machineId) ;
    id. setGenMethod (genMethod) ;
    id.setType (type) ;
    id. setVersion (version) ;

    populateId(id) ;

    long ret = idConverter . convert(id) ;

    //use trace because it cause low performance
    if (log. isTraceEnabled())

        log. trace (String. format("Id: %s => %d"，id, ret)) ;

    return ret:
}

我们清晰地看到，在该段代码中首先构造了一个ID元数据对象,然后调用了模板回调函数populateId,模板回调函数是一个抽象的方法：

protected abstract void populateId(Id id) ;

 这个抽象方法由子类来实现，子类根据不同的场景会有不同的实现，在这里我们只需要在父类中给子类进行处理的一个机会， 子类主要负责根据某一算法生成唯一 ID 的时间和序列号属性，父类则对自己管理的属性机器ID、生成方式、类型和版本进行赋值。

实现类IdServicelmpl通过代理模式代理到某个IdPopulator接口的一个实现来计算时间字段和序列号字段，具体代码如下：

public class IdServiceImpl extends AbstractIdService Impl{

    private static final String SYNC LOCK_ IMPL KEY二"vesta. sync. lock. impl. key" ;

    private static final String ATOMIC IMPL KEY = "vesta.atomic. impl. key";

    private IdPopulator idPopulator;

    public IdServiceImpl () {

        super () ;

        initPopulator() ;
    }

    public IdServiceImpl (String type) {

        super (type) ;

        initPopulator() ;

    public IdServiceImpl (IdType type) {

        super (type) ;

        initPopulator() ;
    }

    public void initPopulator ()

        if (CommonUtils. isPropKeyOn (SYNC LOCK IMPL KEY) ) {
            log.info ("The SyncIdPopulator is used.") ;
            idPopulator = new SyncIdPopulator () 
        } else if (CommonUtils. isPropKeyOn (ATOMIC IMPL KEY) )
            log.info ("The AtomicIdPopulator is used.") ;
            idPopulator = new AtomicIdpopulator() ;
        } else {
            log.info("The default LockIdPopulator is used.") ;
            idPopulator = new LockIdPopulator() ;
        }
    }

    protected void populateId(Id id) {
        idPopulator .populateId(id, this. idMeta);
    }
}

在IdPopulator的实现中需要计算构成唯一ID的格式中的另外两个变量：时间和序列号，它们的产生方式是变化多端和多种多样的，因此，我们把这两个变量和处理它们的逻辑封装在子类中，并且提供了多种实现方式。如在上面的架构设计中提到的，我们使用了传统的Synchronized锁、ReentrantLock 及CAS无锁技术来实现，其中，通过ReentrantLock 实现是默认的实现方式。可以通过传递JVM虚拟机参数来更换其他实现方式：如果JVM传递了vesta.sync.lock.impl.key参数，则使用Synchronized 锁的实现方式；如果JVM传递了vesta.atomic.impl.key参数，则使用CAS无锁的实现方式，否则使用默认的ReentrantLock 的实现方式。

其中，IdPopulator 是个简单的接口，如下所示：

public interface IdPopulator {
    void populateId(Id id, IdMeta idMeta) ;
}

IdServicelmpl通过IdPopulator来实现时间和序列号字段的计算，其中有3个实现类，包括：AtomicIdPopulator、LockIdPopulator 和SyncldPopulator,如下图所示。

默认的实现类是LockIdPopulator，定义的时间和序列号属性如下：

private long sequence;
private long lastTimestamp;

在下面的代码中使用了可重入锁来进行同步的修改，可重入锁比Synchronized锁的效率稍高，适合高并发的场景：

private Lock lock = new ReentrantLock();

完整的实现代码如下：

public class LockIdPopulator implements IdPopulator {

    private long sequence= 0;

    private long lastTimestamp =-1;

    private Lock lock=new ReentrantLock() ;

    public LockIdPopulator() {
        super () ;
    }

    public void populateId(Id id, IdMeta idMeta) {

        lock.lock();

        try {

            long timestamp = TimeUtils.genTime (IdType.parse (id.getType())) ;
            TimeUtils. validateTimest amp (lastTimestamp, timestamp) ;

            if (timestamp == lastTimestamp {
                sequence++;
                sequence &= idMeta. getseqBitsMask() ;
                if (sequence == 0) {
                    timestamp = TimeUtils. tillNextTimeUnit (lastTimes tamp,IdType . parse (id.getType())) ;
                }

            }else {
                lastTimestamp = timestamp;
                sequence = 0;
            }

           id. setSeq (sequence) ;
           id. setTime (t imestamp) ;

        } finally { 
            lock. unlock();
        }
    }
}

最后，我们还通过CAS底层基础设施实现了无锁版本，CAS 实现的无锁版本在高并发的场景下，能够高性能地处理唯一ID 的产生，但是，这里需要解决一个技术难题，就是如何安全地并发修改两个变量:时间字段和序列号字段。这里我们通过使用原子变量引用来实现，对时间和序列号两个字段的修改进行CAS保护，使其被高效、安全地修改。

首先，我们需要定义一个联合的数据结构：

class Variant {

    private long sequence = 0;
    private long lastTimestamp =-1:
}

然后，定义一个原子变量的引用，这个引用的CAS操作可以保证实现联合的数据结构Variant中的sequence和lastTimestamp中的任意一个被修改了， 都可以安全地得到更新：

private Atomi cReference<Variant> variant = new AtomicReference<Variant> (newVariant()) ;

具体的实现代码如下：

public class AtomicIdPopulator implements IdPopulator
    class Variant{

        private long sequence =0;
        private long lastTimestamp -1;
    }

    private AtomicReference<Variant> variant = new AtomicReference<Variant> (newVariant());

    public AtomicIdPopulator (){ 
        super () ;
    }

    public void populateId(Id id, IdMeta idMeta) {
        Variant varOld, varNew;
        long。timestamp, sequence;

        while (true) {

            //Save the old variant
            varold =variant.get() ;

            // populate the current variant
            timestamp = TimeUtils. genT ime (IdType. parse (id.getType())) ;
            TimeUtils. val idateTimes tamp (varOld.lastT imestamp, timestamp) ;

            sequence = varOld.sequence;

            if (timestamp == varOld. lastTimestamp){
                sequence++;
                sequence &= idMeta. getSeqBitsMask();
                if (sequence == 0)
                    timestamp = TimeUtils. til lNextTimeUnit (var0ld. lastTimes tamp,IdType.parse (id.getType()));
                }
            } else {
                sequence = 0;
            }

            // Assign the current variantby the atomic tools
            varNew = new Variant () ;
            varNew. sequence = sequence;
            varNew. lastTimestamp= t imestamp;

            if (variant. compareAndSet (var0ld, varNew)) {
                id.setSeq (sequence) ;
                id. setTime (timestamp) ;
                break;
            }
        }
    }
}

实现的逻辑如下：

(1)取得并保存原来的变量，这个变量包含原来的时间和序列号字段。

(2)基于原来的变量计算新的时间和序列号字段，计算逻辑和SyneldPopulator 、LockIdPopulator - -致。

(3)计算后，使用CAS操作更新原来的变量，在更新的过程中，需要传递保存的原来的变量。

(4)如果保存的原来的变量被其他线程改变了，就需要在这里重新拿到最新的变量，并再次计算和尝试更新。

ID元数据与长整型ID的互相转换

在主流程的ID元数据对象中设置了ID的各个属性后，可通过转换器类将ID的元数据对象转换成长整型的ID。

转换器类的设计如下图所示。

转换器负责将ID元数据对象转换成长整型的ID，或将长整型的ID转换成ID元数据对象，并且定义了清晰的转换接口，用于将来扩展，能够实现其他类型的转换。

将ID元数据对象转换成长整型的ID的代码实现如下：

public long convert(Id id) {
    return doConvert (id, IdMetaFactory. getIdMeta (idType)) ;
}

protected long doConvert(Id id, IdMeta idMeta) {
    long ret =0;

    ret l= id.getMachine() ;

    ret l= id.getSeq() << i dMeta .getSeqBitsStartPos) ;

    ret 1= id.getTime() << idMeta.getTimeBitsstartPos() ;

    ret l= id.getGenMethod() << idMeta.ge tGenMethodBitsStartPos();

    ret 1= id.getType() << idMeta.getTypeBitsStartPos;

    ret l= id.getVersion() << idMeta. getversionBitsstartPos() ;

    return ret;
}

如上面的代码实现所示，转换器根据ID元数据的信息对象获取每个属性所在ID的位数，然后通过左移来实现将各个属性拼接到一个长整型数字里。

另外，在前面的接口设计中，有时需要把- -个 长整型的ID解释成人可读的格式，可从中看到时间、序列号、版本、类型等属性。将长整型的ID转换成ID元数据对象的代码实现如下：

public Id convert (long id) {
    return doConvert (id, IdMetaFactory . getIdMeta (idType));
}

protected Id doConvert (1ong id, IdMeta idMeta) {
    Id ret = new Id() ;

    ret.setMachine(id & idMeta.getMachineBitsMask() ) ;

    ret.setSeq((id >>> idMeta.getSeqBitsstartPos()) & idMeta.getSegBitsMask());

    ret.setTime((id ! >>> idMeta.getTimeBitsstartPos()) &idMeta.getTimeBitsMask());

    ret.setGenMethod((id >>> idMeta . getGenMethodBitsstartPos()) &idMeta. ge tGenMethodB itsMask());

    ret.setType(id >>> idMeta . getTypeBitsStartPos()) &idMeta .getTypeBitsMask());

    ret.setversion((id >>> idMeta . getVersionBitsStartPos()) &idMeta. getversionBitsMask());

    return ret;
}

请注意，在上面的代码中使用的是无符号右移操作，因为产生的ID包含的每一位二进制位都代表特殊的含义，所以没有数学上的正负意义，最左边的一位二进制也不是用来表示符号的。

另外，我们看到在做无符号右移操作的时候使用了屏蔽字，这用于从ID数字中取出我们想要的某个属性的值，具体流程如下图所示。

举例说明，假设唯一ID的数字包含的生成方式属性为11则可以参考第2行的第3个方格。上图只是一一个示意图，每个属性的位数和设计不是一对应的。现在我们想取出生成方式属性的数值1111。

首先，程序会把ID数字整体右移，直到生成方式属性位于最右端：

id>>> idMeta.getTypeBitsStartPos())

得到的结果可参考上图中第3行的数据。

然后，与屏蔽字进行与操作，得到的结果为生成方式属性，参考图中第5行的数据：

id >>> idMeta.getTypeBitsStartPos()) &idMeta.getTypeBitsMask()

屏蔽字参考图中第4行的数据，实现代码如下：

public long getGenMethodBitsMask() {
    return -1L^ -1L << genMethodBits;
}

时间操作

在一个ID的生成中，最重要的部分就是时间和序列号的生成，其默认的LockIdPopulator类代码实现如下：

private Lock lock = new ReentrantLock() ;

public void populateId(Id id, IdMeta idMeta){
    lock.lock();
    try {
        long timestamp = TimeUtils. genTime (IdType .parse (id.getType()));
        TimeUtils. val idateTimestamp (lastTimestamp, timestamp ;

        if (timestamp 中= lastTimestamp {
            sequence++;
            sequence &= idMeta.getSeqBitsMask() ;
            if(sequence =F 0) {
                timestamp = TimeUtils. tillNextTimeUnit (lastTimestamp，IdType.parse (id.getType())) ;
            }

        }else{
            lastTimestamp = timestamp;
            sequence = 0;
        }

        id. setSeq (sequence);
        id .setTime (timestamp);

    } finally {
        lock.unlock() ;
    }
}

该段代码的主逻辑是，如果当前时间已经到了下一秒(或者毫秒)，则重置序列号，如果没有到下一秒(或者毫秒)，则对当前秒(或者毫秒)的序列号递增。对于这一段核心逻辑，我们使用了可重入锁进行了保护，因为我们要在并发的场景下维护下面这两个成员变量：

private long sequence;
private long lastTimestamp;

在主逻辑中有一个特殊的场景：假如我们还在同一秒，但是序列号已经用光了，怎么办?在这种情况下，我们只能等待下一秒， 这也就是为什么我们设计了最大峰值型和最小粒度型的设计方案。

在这种情况下，我们认为等待的时间不会太长，因为我们不想让线程处于等待状态，所以我们使用自旋锁来实现，这样减少了因线程切换而导致的性能损耗，参考下面的代码：

public static long tillNextTimeUnit (final long lastTimestamp, final IdType
idType) {

    if (log.isInfoEnabled()
    log. info(String.format("Ids are used out during 8d. Waiting till nextsecond/milisencond."，lastTimestamp));

    long timestamp = TimeUtils.genT ime (idType) ;
    while(timestamp <= lastTimestamp) {
        timestamp = TimeUtils.genTime (idType) ;
    }

    if (1og. isInfoEnabled())
        1og. info (String. format ("Next second/milisencond 8d is up.",timestamp)) ;

    return timestamp;

}

另外，在实现的过程中需要校验机器时间是否被调慢了，这是至关重要的，如果机器时间被回调了，服务就会产生重复的ID，这需要特别注意：

public static void validateTimestamp (1ong lastTimestamp, long timestamp) {
    if (timestamp < lastTimestamp) {
        if (1og. isErrorEnabled())
            log.error (String.format ("Clock moved backwards.Refusing to generate id for %dsecond/milisecond.", lastTimestamp 一timestamp));

            throw newIllegalStateException (String.format ("Clock moved backwards.Refusing to generate id for %dsecond/milisecond.", lastTimestamp - timestamp) ) ;

    }
}

在产生时间字段时，我们需要通过唯一ID 类型来确定产生的时间单位,并对时间进行编码，通过TimeUtils.EPOCH来对时间进行压缩：

public static long genTime (final IdType idType) {
    if (idType == IdType. MAX_PEAK)
        return (System. currentTimeMillis()一TimeUtils.EPOCH) / 1000;
    else if (idType == IdType .MIN_GRANULARITY)
        return (Sys tem. currentTimeMillis() - TimeUtils.EPOCH) ;

    return (System. currentTimeMillis() - TimeUtils.EPOCH) / 1000;
}

由于平台篇幅限制，今天就到这里了，有感兴趣的可以持续关注博主，以便更新后第一时间看到