设计一款永不重复的高性能分布式发号器：如何根据设计实现多场景的发号器
如何根据设计实现多场景的发号器
项目结构
首先，我们的多场景发号器支持多种配置模式:嵌入发布模式、中心服务器发布模式、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;
}
由于平台篇幅限制，今天就到这里了，有感兴趣的可以持续关注博主，以便更新后第一时间看到
美团公司氛围 1908人发布