原生实现

本文承接sharding-jdbc源码之分布式ID,在这篇文章中详细介绍了sharding-jdbc的分布式ID是如何实现的;很遗憾的是sharding-jdbc只是基于snowflake算法实现了如何生成分布式ID,并没有解决snowflake算法的缺点:

  1. 时钟回拨问题;
  2. 趋势递增,而不是绝对递增;
  3. 不能在一台服务器上部署多个分布式ID服务;

第2点算不上缺点,毕竟如果绝对递增的话,需要牺牲不少的性能;第3点也算不上缺点,即使一台足够大内存的服务器,在部署一个分布式ID服务后,还有很多可用的内存,可以用来部署其他的服务,不一定非得在一台服务器上部署一个服务的多个实例;可以参考elasticsearch的主分片和副本的划分规则:某个主分片的副本是不允许和主分片在同一台节点上--因为这样意思不大,如果这个分片只拥有一个副本,且这个节点宕机后,服务状态就是"RED";

所以这篇文章的主要目的是解决第1个缺点:时钟回拨问题;先来看一下sharding-jdbc的DefaultKeyGenerator.javagenerateKey()方法的源码:

@Override 
public synchronized Number generateKey() { 
    long currentMillis = timeService.getCurrentMillis(); 
    Preconditions.checkState(lastTime <= currentMillis, "Clock is moving backwards, last time is %d milliseconds, current time is %d milliseconds", lastTime, currentMillis); 
    if (lastTime == currentMillis) { 
        if (0L == (sequence = ++sequence & SEQUENCE_MASK)) { 
            currentMillis = waitUntilNextTime(currentMillis); 
        } 
    } else { 
        sequence = 0; 
    } 
    lastTime = currentMillis; 
    if (log.isDebugEnabled()) { 
        log.debug("{}-{}-{}", new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS").format(new Date(lastTime)), workerId, sequence); 
    } 
    return ((currentMillis - EPOCH) << TIMESTAMP_LEFT_SHIFT_BITS) | (workerId << WORKER_ID_LEFT_SHIFT_BITS) | sequence; 
} 

说明:从这段代码可知,sharding-jdbc并没有尝试去解决snowflake算法时钟回拨的问题,只是简单判断如果lastTime <= currentMillis不满足就抛出异常:Preconditions.checkState(lastTime <= currentMillis, "Clock is moving backwards, last time is %d milliseconds, current time is %d milliseconds", lastTime, currentMillis);

改进思路

snowflake算法一个很大的优点就是不需要依赖任何第三方组件,笔者想继续保留这个优点:毕竟多一个依赖的组件,多一个风险,并增加了系统的复杂性。

snowflake算法给workerId预留了10位,即workId的取值范围为[0, 1023],事实上实际生产环境不大可能需要部署1024个分布式ID服务,所以:将workerId取值范围缩小为[0, 511],[512, 1023]这个范围的workerId当做备用workerId。workId为0的备用workerId是512,workId为1的备用workerId是513,以此类推……

说明:如果你的业务真的需要512个以上分布式ID服务才能满足需求,那么不需要继续往下看了,这个方案不适合你^^;

改进实现

generateKey()方法的改进如下:

// 修改处: workerId原则上上限为1024, 但是为了每台sequence服务预留一个workerId, 所以实际上workerId上限为512 
private static final long WORKER_ID_MAX_VALUE = 1L << WORKER_ID_BITS >> 1; 

/**

  • 保留workerId和lastTime, 以及备用workerId和其对应的lastTime
    */
    private static Map<Long, Long> workerIdLastTimeMap = new ConcurrentHashMap<>();

/**

  • Generate key. 考虑时钟回拨, 与sharding-jdbc源码的区别就在这里</br>

  • 缺陷: 如果连续两次时钟回拨, 可能还是会有问题, 但是这种概率极低极低

  • @return key type is @{@link Long}.

  • @Author 阿飞
    */
    @Override
    public synchronized Number generateKey() {
    long currentMillis = System.currentTimeMillis();

    // 当发生时钟回拨时
    if (lastTime > currentMillis){
    // 如果时钟回拨在可接受范围内, 等待即可
    if (lastTime - currentMillis < MAX_BACKWARD_MS){
    try {
    Thread.sleep(lastTime - currentMillis);
    } catch (InterruptedException e) {
    e.printStackTrace();
    }
    }else {
    // 如果时钟回拨太多, 那么换备用workerId尝试

     <span class="token comment"><span class="hljs-comment">// 当前workerId和备用workerId的值的差值为512</span></span> 
         <span class="token keyword"><span class="hljs-keyword">long</span></span> interval <span class="token operator">=</span> <span class="token number"><span class="hljs-number">512L</span></span><span class="token punctuation">;</span> 
         <span class="token comment"><span class="hljs-comment">// 发生时钟回拨时, 计算备用workerId[如果当前workerId小于512,</span></span> 
         <span class="token comment"><span class="hljs-comment">// 那么备用workerId=workerId+512; 否则备用workerId=workerId-512, 两个workerId轮换用]</span></span> 
         <span class="token keyword"><span class="hljs-keyword">if</span></span> <span class="token punctuation">(</span><span class="token class-name">MyKeyGenerator</span><span class="token punctuation">.</span>workerId <span class="token operator">&gt;=</span> interval<span class="token punctuation">)</span> <span class="token punctuation">{</span> 
             <span class="token class-name">MyKeyGenerator</span><span class="token punctuation">.</span>workerId <span class="token operator">=</span> <span class="token class-name">MyKeyGenerator</span><span class="token punctuation">.</span>workerId <span class="token operator">-</span> interval<span class="token punctuation">;</span> 
         <span class="token punctuation">}</span> <span class="token keyword"><span class="hljs-keyword">else</span></span> <span class="token punctuation">{</span> 
             <span class="token class-name">MyKeyGenerator</span><span class="token punctuation">.</span>workerId <span class="token operator">=</span> <span class="token class-name">MyKeyGenerator</span><span class="token punctuation">.</span>workerId <span class="token operator">+</span> interval<span class="token punctuation">;</span> 
         <span class="token punctuation">}</span> 
     
         <span class="token comment"><span class="hljs-comment">// 取得备用workerId的lastTime</span></span> 
         <span class="token class-name">Long</span> tempTime <span class="token operator">=</span> workerIdLastTimeMap<span class="token punctuation">.</span><span class="token function">get</span><span class="token punctuation">(</span><span class="token class-name">MyKeyGenerator</span><span class="token punctuation">.</span>workerId<span class="token punctuation">)</span><span class="token punctuation">;</span> 
         lastTime <span class="token operator">=</span> tempTime<span class="token operator">==</span><span class="token keyword"><span class="hljs-keyword">null</span></span><span class="token operator">?</span><span class="token number"><span class="hljs-number">0L</span></span><span class="token operator">:</span>tempTime<span class="token punctuation">;</span> 
         <span class="token comment"><span class="hljs-comment">// 如果在备用workerId也处于过去的时钟, 那么抛出异常</span></span> 
         <span class="token comment"><span class="hljs-comment">// [这里也可以增加时钟回拨是否超过MAX_BACKWARD_MS的判断]</span></span> 
         <span class="token class-name">Preconditions</span><span class="token punctuation">.</span><span class="token function">checkState</span><span class="token punctuation">(</span>lastTime <span class="token operator">&lt;=</span> currentMillis<span class="token punctuation">,</span> <span class="token string"><span class="hljs-string">"Clock is moving backwards, last time is %d milliseconds, current time is %d milliseconds"</span></span><span class="token punctuation">,</span> lastTime<span class="token punctuation">,</span> currentMillis<span class="token punctuation">)</span><span class="token punctuation">;</span> 
         <span class="token comment"><span class="hljs-comment">// 备用workerId上也处于时钟回拨范围内的逻辑还可以优化: 比如摘掉当前节点. 运维通过监控发现问题并修复时钟回拨</span></span> 
     <span class="token punctuation">}</span> 
    

    }

    // 如果和最后一次请求处于同一毫秒, 那么sequence+1
    if (lastTime currentMillis) {
    if (0L (sequence = ++sequence & SEQUENCE_MASK)) {
    currentMillis = waitUntilNextTime(currentMillis);
    }
    } else {
    // 如果是一个更近的时间戳, 那么sequence归零
    sequence = 0;
    }

    lastTime = currentMillis;
    // 更新map中保存的workerId对应的lastTime
    workerIdLastTimeMap.put(MyKeyGenerator.workerId, lastTime);

    if (log.isDebugEnabled()) {
    log.debug("{}-{}-{}", new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS").format(new Date(lastTime)), workerId, sequence);
    }
    System.out.println(new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS").format(new Date(lastTime))
    +" -- "+workerId+" -- "+sequence+" -- "+workerIdLastTimeMap);
    return ((currentMillis - EPOCH) << TIMESTAMP_LEFT_SHIFT_BITS) | (workerId << WORKER_ID_LEFT_SHIFT_BITS) | sequence;
    }

改进验证

Powered By 阿飞Javaer.png

第一个红色箭头的地方通过修改本地时间,通过启动了备用workerId从而避免了时钟回拨60s(window系统直接修改系统时间模拟)引起的问题;第二个红色箭头在60s内再次模拟时钟回拨,就会有问题,因为无论是workerId还是备用workerId都会有冲突;如果第二红色箭头是60s后模拟时钟回拨,依然可以避免问题,原因嘛,你懂得;

再次优化

每个workerId可以配置任意个备用workerId,由使用者去平衡sequence服务的性能及高可用,终极版代码如下:

public final class MyKeyGenerator implements KeyGenerator { 
<span class="token keyword"><span class="hljs-keyword">private</span></span> <span class="token keyword"><span class="hljs-keyword">static</span></span> <span class="token keyword"><span class="hljs-keyword">final</span></span> <span class="token keyword"><span class="hljs-keyword">long</span></span> EPOCH<span class="token punctuation">;</span> 
 
<span class="token keyword"><span class="hljs-keyword">private</span></span> <span class="token keyword"><span class="hljs-keyword">static</span></span> <span class="token keyword"><span class="hljs-keyword">final</span></span> <span class="token keyword"><span class="hljs-keyword">long</span></span> SEQUENCE_BITS <span class="token operator">=</span> <span class="token number"><span class="hljs-number">12L</span></span><span class="token punctuation">;</span> 
 
<span class="token keyword"><span class="hljs-keyword">private</span></span> <span class="token keyword"><span class="hljs-keyword">static</span></span> <span class="token keyword"><span class="hljs-keyword">final</span></span> <span class="token keyword"><span class="hljs-keyword">long</span></span> WORKER_ID_BITS <span class="token operator">=</span> <span class="token number"><span class="hljs-number">10L</span></span><span class="token punctuation">;</span> 
 
<span class="token keyword"><span class="hljs-keyword">private</span></span> <span class="token keyword"><span class="hljs-keyword">static</span></span> <span class="token keyword"><span class="hljs-keyword">final</span></span> <span class="token keyword"><span class="hljs-keyword">long</span></span> SEQUENCE_MASK <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token number"><span class="hljs-number">1</span></span> <span class="token operator">&lt;&lt;</span> SEQUENCE_BITS<span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token number"><span class="hljs-number">1</span></span><span class="token punctuation">;</span> 
 
<span class="token keyword"><span class="hljs-keyword">private</span></span> <span class="token keyword"><span class="hljs-keyword">static</span></span> <span class="token keyword"><span class="hljs-keyword">final</span></span> <span class="token keyword"><span class="hljs-keyword">long</span></span> WORKER_ID_LEFT_SHIFT_BITS <span class="token operator">=</span> SEQUENCE_BITS<span class="token punctuation">;</span> 
 
<span class="token keyword"><span class="hljs-keyword">private</span></span> <span class="token keyword"><span class="hljs-keyword">static</span></span> <span class="token keyword"><span class="hljs-keyword">final</span></span> <span class="token keyword"><span class="hljs-keyword">long</span></span> TIMESTAMP_LEFT_SHIFT_BITS <span class="token operator">=</span> WORKER_ID_LEFT_SHIFT_BITS <span class="token operator">+</span> WORKER_ID_BITS<span class="token punctuation">;</span> 
 
<span class="token comment"><span class="hljs-comment">/** 
 * 每台workerId服务器有3个备份workerId, 备份workerId数量越多, 可靠性越高, 但是可部署的sequence ID服务越少 
 */</span></span> 
<span class="token keyword"><span class="hljs-keyword">private</span></span> <span class="token keyword"><span class="hljs-keyword">static</span></span> <span class="token keyword"><span class="hljs-keyword">final</span></span> <span class="token keyword"><span class="hljs-keyword">long</span></span> BACKUP_COUNT <span class="token operator">=</span> <span class="token number"><span class="hljs-number">3</span></span><span class="token punctuation">;</span> 
 
<span class="token comment"><span class="hljs-comment">/** 
 * 实际的最大workerId的值&lt;br/&gt; 
 * workerId原则上上限为1024, 但是需要为每台sequence服务预留BACKUP_AMOUNT个workerId, 
 */</span></span> 
<span class="token keyword"><span class="hljs-keyword">private</span></span> <span class="token keyword"><span class="hljs-keyword">static</span></span> <span class="token keyword"><span class="hljs-keyword">final</span></span> <span class="token keyword"><span class="hljs-keyword">long</span></span> WORKER_ID_MAX_VALUE <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token number"><span class="hljs-number">1L</span></span> <span class="token operator">&lt;&lt;</span> WORKER_ID_BITS<span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token punctuation">(</span>BACKUP_COUNT <span class="token operator">+</span> <span class="token number"><span class="hljs-number">1</span></span><span class="token punctuation">)</span><span class="token punctuation">;</span> 
 
<span class="token comment"><span class="hljs-comment">/** 
 * 目前用户生成ID的workerId 
 */</span></span> 
<span class="token keyword"><span class="hljs-keyword">private</span></span> <span class="token keyword"><span class="hljs-keyword">static</span></span> <span class="token keyword"><span class="hljs-keyword">long</span></span> workerId<span class="token punctuation">;</span> 
 
<span class="token keyword"><span class="hljs-keyword">static</span></span> <span class="token punctuation">{</span> 
    <span class="token class-name">Calendar</span> calendar <span class="token operator">=</span> <span class="token class-name">Calendar</span><span class="token punctuation">.</span><span class="token function">getInstance</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> 
    calendar<span class="token punctuation">.</span><span class="token function">set</span><span class="token punctuation">(</span><span class="token number"><span class="hljs-number">2018</span></span><span class="token punctuation">,</span> <span class="token class-name">Calendar</span><span class="token punctuation">.</span>NOVEMBER<span class="token punctuation">,</span> <span class="token number"><span class="hljs-number">1</span></span><span class="token punctuation">)</span><span class="token punctuation">;</span> 
    calendar<span class="token punctuation">.</span><span class="token function">set</span><span class="token punctuation">(</span><span class="token class-name">Calendar</span><span class="token punctuation">.</span>HOUR_OF_DAY<span class="token punctuation">,</span> <span class="token number"><span class="hljs-number">0</span></span><span class="token punctuation">)</span><span class="token punctuation">;</span> 
    calendar<span class="token punctuation">.</span><span class="token function">set</span><span class="token punctuation">(</span><span class="token class-name">Calendar</span><span class="token punctuation">.</span>MINUTE<span class="token punctuation">,</span> <span class="token number"><span class="hljs-number">0</span></span><span class="token punctuation">)</span><span class="token punctuation">;</span> 
    calendar<span class="token punctuation">.</span><span class="token function">set</span><span class="token punctuation">(</span><span class="token class-name">Calendar</span><span class="token punctuation">.</span>SECOND<span class="token punctuation">,</span> <span class="token number"><span class="hljs-number">0</span></span><span class="token punctuation">)</span><span class="token punctuation">;</span> 
    calendar<span class="token punctuation">.</span><span class="token function">set</span><span class="token punctuation">(</span><span class="token class-name">Calendar</span><span class="token punctuation">.</span>MILLISECOND<span class="token punctuation">,</span> <span class="token number"><span class="hljs-number">0</span></span><span class="token punctuation">)</span><span class="token punctuation">;</span> 
    <span class="token comment"><span class="hljs-comment">// EPOCH是服务器第一次上线时间点, 设置后不允许修改</span></span> 
    EPOCH <span class="token operator">=</span> calendar<span class="token punctuation">.</span><span class="token function">getTimeInMillis</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> 
<span class="token punctuation">}</span> 
 
<span class="token keyword"><span class="hljs-keyword">private</span></span> <span class="token keyword"><span class="hljs-keyword">long</span></span> sequence<span class="token punctuation">;</span> 
 
<span class="token keyword"><span class="hljs-keyword">private</span></span> <span class="token keyword"><span class="hljs-keyword">long</span></span> lastTime<span class="token punctuation">;</span> 
 
<span class="token comment"><span class="hljs-comment">/** 
 * 保留workerId和lastTime, 以及备用workerId和其对应的lastTime 
 */</span></span> 
<span class="token keyword"><span class="hljs-keyword">private</span></span> <span class="token keyword"><span class="hljs-keyword">static</span></span> <span class="token class-name">Map</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">Long</span><span class="token punctuation">,</span> <span class="token class-name">Long</span><span class="token punctuation">&gt;</span></span> workerIdLastTimeMap <span class="token operator">=</span> <span class="token keyword"><span class="hljs-keyword">new</span></span> <span class="token class-name">ConcurrentHashMap</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token punctuation">&gt;</span></span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> 
 
<span class="token keyword"><span class="hljs-keyword">static</span></span> <span class="token punctuation">{</span> 
    <span class="token comment"><span class="hljs-comment">// 初始化workerId和其所有备份workerId与lastTime</span></span> 
    <span class="token comment"><span class="hljs-comment">// 假设workerId为0且BACKUP_AMOUNT为4, 那么map的值为: {0:0L, 256:0L, 512:0L, 768:0L}</span></span> 
    <span class="token comment"><span class="hljs-comment">// 假设workerId为2且BACKUP_AMOUNT为4, 那么map的值为: {2:0L, 258:0L, 514:0L, 770:0L}</span></span> 
    <span class="token keyword"><span class="hljs-keyword">for</span></span> <span class="token punctuation">(</span><span class="token keyword"><span class="hljs-keyword">int</span></span> i <span class="token operator">=</span> <span class="token number"><span class="hljs-number">0</span></span><span class="token punctuation">;</span> i<span class="token operator">&lt;=</span> BACKUP_COUNT<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span> 
        workerIdLastTimeMap<span class="token punctuation">.</span><span class="token function">put</span><span class="token punctuation">(</span>workerId <span class="token operator">+</span> <span class="token punctuation">(</span>i <span class="token operator">*</span> WORKER_ID_MAX_VALUE<span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token number"><span class="hljs-number">0L</span></span><span class="token punctuation">)</span><span class="token punctuation">;</span> 
    <span class="token punctuation">}</span> 
    <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string"><span class="hljs-string">"workerIdLastTimeMap:"</span></span> <span class="token operator">+</span> workerIdLastTimeMap<span class="token punctuation">)</span><span class="token punctuation">;</span> 
<span class="token punctuation">}</span> 
 
<span class="token comment"><span class="hljs-comment">/** 
 * 最大容忍时间, 单位毫秒, 即如果时钟只是回拨了该变量指定的时间, 那么等待相应的时间即可; 
 * 考虑到sequence服务的高性能, 这个值不易过大 
 */</span></span> 
<span class="token keyword"><span class="hljs-keyword">private</span></span> <span class="token keyword"><span class="hljs-keyword">static</span></span> <span class="token keyword"><span class="hljs-keyword">final</span></span> <span class="token keyword"><span class="hljs-keyword">long</span></span> MAX_BACKWARD_MS <span class="token operator">=</span> <span class="token number"><span class="hljs-number">3</span></span><span class="token punctuation">;</span> 
 
<span class="token comment"><span class="hljs-comment">/** 
 * Set work process id. 
 * <span class="hljs-doctag">@param</span> workerId work process id 
 */</span></span> 
<span class="token keyword"><span class="hljs-function"><span class="hljs-keyword">public</span></span></span><span class="hljs-function"> </span><span class="token keyword"><span class="hljs-function"><span class="hljs-keyword">static</span></span></span><span class="hljs-function"> </span><span class="token keyword"><span class="hljs-function"><span class="hljs-keyword">void</span></span></span><span class="hljs-function"> </span><span class="token function"><span class="hljs-function"><span class="hljs-title">setWorkerId</span></span></span><span class="token punctuation"><span class="hljs-function"><span class="hljs-params">(</span></span></span><span class="token keyword"><span class="hljs-function"><span class="hljs-params"><span class="hljs-keyword">final</span></span></span></span><span class="hljs-function"><span class="hljs-params"> </span></span><span class="token keyword"><span class="hljs-function"><span class="hljs-params"><span class="hljs-keyword">long</span></span></span></span><span class="hljs-function"><span class="hljs-params"> workerId</span></span><span class="token punctuation"><span class="hljs-function"><span class="hljs-params">)</span></span></span><span class="hljs-function"> </span><span class="token punctuation">{</span> 
    <span class="token class-name">Preconditions</span><span class="token punctuation">.</span><span class="token function">checkArgument</span><span class="token punctuation">(</span>workerId <span class="token operator">&gt;=</span> <span class="token number"><span class="hljs-number">0L</span></span> <span class="token operator">&amp;&amp;</span> workerId <span class="token operator">&lt;</span> WORKER_ID_MAX_VALUE<span class="token punctuation">)</span><span class="token punctuation">;</span> 
    <span class="token class-name">MyKeyGenerator</span><span class="token punctuation">.</span>workerId <span class="token operator">=</span> workerId<span class="token punctuation">;</span> 
<span class="token punctuation">}</span> 
 
<span class="token comment"><span class="hljs-comment">/** 
 * Generate key. 考虑时钟回拨, 与sharding-jdbc源码的区别就在这里&lt;/br&gt; 
 * 缺陷: 如果连续两次时钟回拨, 可能还是会有问题, 但是这种概率极低极低 
 * <span class="hljs-doctag">@return</span> key type is @{<span class="hljs-doctag">@link</span> Long}. 
 * <span class="hljs-doctag">@Author</span> 阿飞 
 */</span></span> 
<span class="token annotation punctuation"><span class="hljs-meta">@Override</span></span> 
<span class="token keyword"><span class="hljs-function"><span class="hljs-keyword">public</span></span></span><span class="hljs-function"> </span><span class="token keyword"><span class="hljs-function"><span class="hljs-keyword">synchronized</span></span></span><span class="hljs-function"> </span><span class="token class-name"><span class="hljs-function">Number</span></span><span class="hljs-function"> </span><span class="token function"><span class="hljs-function"><span class="hljs-title">generateKey</span></span></span><span class="token punctuation"><span class="hljs-function"><span class="hljs-params">(</span></span></span><span class="token punctuation"><span class="hljs-function"><span class="hljs-params">)</span></span></span><span class="hljs-function"> </span><span class="token punctuation">{</span> 
    <span class="token keyword"><span class="hljs-keyword">long</span></span> currentMillis <span class="token operator">=</span> <span class="token class-name">System</span><span class="token punctuation">.</span><span class="token function">currentTimeMillis</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> 
 
    <span class="token comment"><span class="hljs-comment">// 当发生时钟回拨时</span></span> 
    <span class="token keyword"><span class="hljs-keyword">if</span></span> <span class="token punctuation">(</span>lastTime <span class="token operator">&gt;</span> currentMillis<span class="token punctuation">)</span><span class="token punctuation">{</span> 
        <span class="token comment"><span class="hljs-comment">// 如果时钟回拨在可接受范围内, 等待即可</span></span> 
        <span class="token keyword"><span class="hljs-keyword">if</span></span> <span class="token punctuation">(</span>lastTime <span class="token operator">-</span> currentMillis <span class="token operator">&lt;</span> MAX_BACKWARD_MS<span class="token punctuation">)</span><span class="token punctuation">{</span> 
            <span class="token keyword"><span class="hljs-keyword">try</span></span> <span class="token punctuation">{</span> 
                <span class="token class-name">Thread</span><span class="token punctuation">.</span><span class="token function">sleep</span><span class="token punctuation">(</span>lastTime <span class="token operator">-</span> currentMillis<span class="token punctuation">)</span><span class="token punctuation">;</span> 
            <span class="token punctuation">}</span> <span class="token keyword"><span class="hljs-keyword">catch</span></span> <span class="token punctuation">(</span><span class="token class-name">InterruptedException</span> e<span class="token punctuation">)</span> <span class="token punctuation">{</span> 
                e<span class="token punctuation">.</span><span class="token function">printStackTrace</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> 
            <span class="token punctuation">}</span> 
        <span class="token punctuation">}</span><span class="token keyword"><span class="hljs-keyword">else</span></span> <span class="token punctuation">{</span> 
            <span class="token function">tryGenerateKeyOnBackup</span><span class="token punctuation">(</span>currentMillis<span class="token punctuation">)</span><span class="token punctuation">;</span> 
        <span class="token punctuation">}</span> 
    <span class="token punctuation">}</span> 
 
    <span class="token comment"><span class="hljs-comment">// 如果和最后一次请求处于同一毫秒, 那么sequence+1</span></span> 
    <span class="token keyword"><span class="hljs-keyword">if</span></span> <span class="token punctuation">(</span>lastTime <span class="token operator">==</span> currentMillis<span class="token punctuation">)</span> <span class="token punctuation">{</span> 
        <span class="token keyword"><span class="hljs-keyword">if</span></span> <span class="token punctuation">(</span><span class="token number"><span class="hljs-number">0L</span></span> <span class="token operator">==</span> <span class="token punctuation">(</span>sequence <span class="token operator">=</span> <span class="token operator">++</span>sequence <span class="token operator">&amp;</span> SEQUENCE_MASK<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> 
            currentMillis <span class="token operator">=</span> <span class="token function">waitUntilNextTime</span><span class="token punctuation">(</span>currentMillis<span class="token punctuation">)</span><span class="token punctuation">;</span> 
        <span class="token punctuation">}</span> 
    <span class="token punctuation">}</span> <span class="token keyword"><span class="hljs-keyword">else</span></span> <span class="token punctuation">{</span> 
        <span class="token comment"><span class="hljs-comment">// 如果是一个更近的时间戳, 那么sequence归零</span></span> 
        sequence <span class="token operator">=</span> <span class="token number"><span class="hljs-number">0</span></span><span class="token punctuation">;</span> 
    <span class="token punctuation">}</span> 
 
    lastTime <span class="token operator">=</span> currentMillis<span class="token punctuation">;</span> 
    <span class="token comment"><span class="hljs-comment">// 更新map中保存的workerId对应的lastTime</span></span> 
    workerIdLastTimeMap<span class="token punctuation">.</span><span class="token function">put</span><span class="token punctuation">(</span><span class="token class-name">MyKeyGenerator</span><span class="token punctuation">.</span>workerId<span class="token punctuation">,</span> lastTime<span class="token punctuation">)</span><span class="token punctuation">;</span> 
 
    <span class="token keyword"><span class="hljs-keyword">if</span></span> <span class="token punctuation">(</span>log<span class="token punctuation">.</span><span class="token function">isDebugEnabled</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> 
        log<span class="token punctuation">.</span><span class="token function">debug</span><span class="token punctuation">(</span><span class="token string"><span class="hljs-string">"{}-{}-{}"</span></span><span class="token punctuation">,</span> <span class="token keyword"><span class="hljs-keyword">new</span></span> <span class="token class-name">SimpleDateFormat</span><span class="token punctuation">(</span><span class="token string"><span class="hljs-string">"yyyy-MM-dd HH:mm:ss.SSS"</span></span><span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">format</span><span class="token punctuation">(</span><span class="token keyword"><span class="hljs-keyword">new</span></span> <span class="token class-name">Date</span><span class="token punctuation">(</span>lastTime<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">,</span> workerId<span class="token punctuation">,</span> sequence<span class="token punctuation">)</span><span class="token punctuation">;</span> 
    <span class="token punctuation">}</span> 
 
    <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token keyword"><span class="hljs-keyword">new</span></span> <span class="token class-name">SimpleDateFormat</span><span class="token punctuation">(</span><span class="token string"><span class="hljs-string">"yyyy-MM-dd HH:mm:ss.SSS"</span></span><span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">format</span><span class="token punctuation">(</span><span class="token keyword"><span class="hljs-keyword">new</span></span> <span class="token class-name">Date</span><span class="token punctuation">(</span>lastTime<span class="token punctuation">)</span><span class="token punctuation">)</span> 
            <span class="token operator">+</span><span class="token string"><span class="hljs-string">" -- "</span></span><span class="token operator">+</span>workerId<span class="token operator">+</span><span class="token string"><span class="hljs-string">" -- "</span></span><span class="token operator">+</span>sequence<span class="token operator">+</span><span class="token string"><span class="hljs-string">" -- "</span></span><span class="token operator">+</span>workerIdLastTimeMap<span class="token punctuation">)</span><span class="token punctuation">;</span> 
    <span class="token keyword"><span class="hljs-keyword">return</span></span> <span class="token punctuation">(</span><span class="token punctuation">(</span>currentMillis <span class="token operator">-</span> EPOCH<span class="token punctuation">)</span> <span class="token operator">&lt;&lt;</span> TIMESTAMP_LEFT_SHIFT_BITS<span class="token punctuation">)</span> <span class="token operator">|</span> <span class="token punctuation">(</span>workerId <span class="token operator">&lt;&lt;</span> WORKER_ID_LEFT_SHIFT_BITS<span class="token punctuation">)</span> <span class="token operator">|</span> sequence<span class="token punctuation">;</span> 
<span class="token punctuation">}</span> 
 
<span class="token comment"><span class="hljs-comment">/** 
 * 尝试在workerId的备份workerId上生成 
 * <span class="hljs-doctag">@param</span> currentMillis 当前时间 
 */</span></span> 
<span class="token keyword"><span class="hljs-function"><span class="hljs-keyword">private</span></span></span><span class="hljs-function"> </span><span class="token keyword"><span class="hljs-function"><span class="hljs-keyword">long</span></span></span><span class="hljs-function"> </span><span class="token function"><span class="hljs-function"><span class="hljs-title">tryGenerateKeyOnBackup</span></span></span><span class="token punctuation"><span class="hljs-function"><span class="hljs-params">(</span></span></span><span class="token keyword"><span class="hljs-function"><span class="hljs-params"><span class="hljs-keyword">long</span></span></span></span><span class="hljs-function"><span class="hljs-params"> currentMillis</span></span><span class="token punctuation"><span class="hljs-function"><span class="hljs-params">)</span></span></span><span class="token punctuation">{</span> 
    <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string"><span class="hljs-string">"try GenerateKey OnBackup, map:"</span></span> <span class="token operator">+</span> workerIdLastTimeMap<span class="token punctuation">)</span><span class="token punctuation">;</span> 
 
    <span class="token comment"><span class="hljs-comment">// 遍历所有workerId(包括备用workerId, 查看哪些workerId可用)</span></span> 
    <span class="token keyword"><span class="hljs-keyword">for</span></span> <span class="token punctuation">(</span><span class="token class-name">Map</span><span class="token punctuation">.</span><span class="token class-name">Entry</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">Long</span><span class="token punctuation">,</span> <span class="token class-name">Long</span><span class="token punctuation">&gt;</span></span> entry<span class="token operator">:</span>workerIdLastTimeMap<span class="token punctuation">.</span><span class="token function">entrySet</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">{</span> 
        <span class="token class-name">MyKeyGenerator</span><span class="token punctuation">.</span>workerId <span class="token operator">=</span> entry<span class="token punctuation">.</span><span class="token function">getKey</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> 
        <span class="token comment"><span class="hljs-comment">// 取得备用workerId的lastTime</span></span> 
        <span class="token class-name">Long</span> tempLastTime <span class="token operator">=</span> entry<span class="token punctuation">.</span><span class="token function">getValue</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> 
        lastTime <span class="token operator">=</span> tempLastTime<span class="token operator">==</span><span class="token keyword"><span class="hljs-keyword">null</span></span><span class="token operator">?</span><span class="token number"><span class="hljs-number">0L</span></span><span class="token operator">:</span>tempLastTime<span class="token punctuation">;</span> 
 
        <span class="token comment"><span class="hljs-comment">// 如果找到了合适的workerId</span></span> 
        <span class="token keyword"><span class="hljs-keyword">if</span></span> <span class="token punctuation">(</span>lastTime<span class="token operator">&lt;=</span>currentMillis<span class="token punctuation">)</span><span class="token punctuation">{</span> 
            <span class="token keyword"><span class="hljs-keyword">return</span></span> lastTime<span class="token punctuation">;</span> 
        <span class="token punctuation">}</span> 
    <span class="token punctuation">}</span> 
 
    <span class="token comment"><span class="hljs-comment">// 如果所有workerId以及备用workerId都处于时钟回拨, 那么抛出异常</span></span> 
    <span class="token keyword"><span class="hljs-keyword">throw</span></span> <span class="token keyword"><span class="hljs-keyword">new</span></span> <span class="token class-name">IllegalStateException</span><span class="token punctuation">(</span><span class="token string"><span class="hljs-string">"Clock is moving backwards, current time is "</span></span> 
            <span class="token operator">+</span>currentMillis<span class="token operator">+</span><span class="token string"><span class="hljs-string">" milliseconds, workerId map = "</span></span> <span class="token operator">+</span> workerIdLastTimeMap<span class="token punctuation">)</span><span class="token punctuation">;</span> 
<span class="token punctuation">}</span> 
 
<span class="token keyword"><span class="hljs-function"><span class="hljs-keyword">private</span></span></span><span class="hljs-function"> </span><span class="token keyword"><span class="hljs-function"><span class="hljs-keyword">long</span></span></span><span class="hljs-function"> </span><span class="token function"><span class="hljs-function"><span class="hljs-title">waitUntilNextTime</span></span></span><span class="token punctuation"><span class="hljs-function"><span class="hljs-params">(</span></span></span><span class="token keyword"><span class="hljs-function"><span class="hljs-params"><span class="hljs-keyword">final</span></span></span></span><span class="hljs-function"><span class="hljs-params"> </span></span><span class="token keyword"><span class="hljs-function"><span class="hljs-params"><span class="hljs-keyword">long</span></span></span></span><span class="hljs-function"><span class="hljs-params"> lastTime</span></span><span class="token punctuation"><span class="hljs-function"><span class="hljs-params">)</span></span></span><span class="hljs-function"> </span><span class="token punctuation">{</span> 
    <span class="token keyword"><span class="hljs-keyword">long</span></span> time <span class="token operator">=</span> <span class="token class-name">System</span><span class="token punctuation">.</span><span class="token function">currentTimeMillis</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> 
    <span class="token keyword"><span class="hljs-keyword">while</span></span> <span class="token punctuation">(</span>time <span class="token operator">&lt;=</span> lastTime<span class="token punctuation">)</span> <span class="token punctuation">{</span> 
        time <span class="token operator">=</span> <span class="token class-name">System</span><span class="token punctuation">.</span><span class="token function">currentTimeMillis</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> 
    <span class="token punctuation">}</span> 
    <span class="token keyword"><span class="hljs-keyword">return</span></span> time<span class="token punctuation">;</span> 
<span class="token punctuation">}</span> 

}

核心优化代码在方法tryGenerateKeyOnBackup()中,BACKUP_COUNT即备份workerId数越多,sequence服务避免时钟回拨影响的能力越强,但是可部署的sequence服务越少,设置BACKUP_COUNT为3,最多可以部署1024/(3+1)即256个sequence服务,完全够用,抗时钟回拨影响的能力也得到非常大的保障。

改进总结

这种改进方案最大优点就是没有引入任何第三方中间件(例如redis,zookeeper等),但是避免时钟回拨能力得到极大的提高,而且时钟回拨本来就是极小概率。阿飞Javaer认为这种方案能够达到绝大部分sequence服务的需求了;

原文地址:https://www.jianshu.com/p/98c202f64652?utm_campaign=haruki&utm_content=note&utm_medium=reader_share&utm_source=weixin

发布评论
IT序号网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

Leaf:美团分布式ID生成服务开源知识解答
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。