无锁循环ID生成器

背景

最近在做一个项目(HttpDNS),简单说其中一个流程,客户端通过DNS协议构造好UDP包发给Akamai DNS Server,每个包都会带一个ID,做过网络通讯开发的同学应该都知道它的用处,把req和resp做关联映射,防止串包。那么在DNS协议里面有个限制,ID的大小不能超过65535,不然会报错误“DNS message ID 65536 is out of range”,那么ID只能在0到65535之间循环发送。


方案

既然ID只能在0到65535之间循环发送,首先在生成ID时必然要保证ID不重复,不重复简单加一把锁就行了,在保证ID不重复的情况下也要有一定的性能保证,加锁必然不是最好的方案,如果能做到无锁自然是最好的。先看看concurrent库里面的AtomicInteger实现。

以下JDK1.7的代码:

   public final int getAndIncrement() {
      for (;;) {
          int current = get();
          int next = current + 1;
          if (compareAndSet(current, next))
              return current;
          }
   }
   public final boolean compareAndSet(int expect, int update) {
         return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
   }

Copy

在AtomicInteger实现中主要使用了cpu的Compare-and-swap指令,即原子操作。在getAndIncrement中会一直尝试操作,如果不成功当前线程会自旋直到操作成功为止。那么这种方式也可以来实现循环ID生成器,代码如下:

public class CycleAtomicIDGenerator{

    private final static long PARK_TIME = 1000L * 1000;

    private final AtomicInteger reqNum = new AtomicInteger(0);

    private int maxValue;

    public CycleAtomicIDGenerator(int maxValue) {
        this.maxValue = maxValue;
    }

    public int next() {
        for(;;) {
            int current = reqNum.get();
            int next    = (current + 1) & maxValue;
            if (reqNum.compareAndSet(current, next)) {
                return current;
            } else {
                LockSupport.parkNanos(PARK_TIME);
            }
        }

    }

}

Copy

以上代码核心是:int next = (current + 1) & maxValue,只要(current + 1) 超过maxValue计算结果会立马从0开始,从而实现循环。

上面代码中给还有一行LockSupport.parkNanos(PARK_TIME),此操作主要是在CAS失败后让线程休眠,减少多线程竞争导致的频繁cas失败,更进一步的导致cpu自旋,浪费cpu的运算能力(具体可查看下面第二篇参考文档)。

在实现循环方案中也可以这样做:int next = (current + 1) % maxValue即取模运算,不过位与( & )运算会比取莫运算速度快很多,我在本机的测试结果如下:

位与( & )(2个线程):

Thread[pool-1-thread-2,5,main]:1712ms
Thread[pool-1-thread-1,5,main]:1712ms

Copy

取模(%)(2个线程):

Thread[pool-1-thread-1,5,main]:2713ms
Thread[pool-1-thread-2,5,main]:2754ms

Copy

位与( & )(10个线程):

Thread[pool-1-thread-1,5,main]:5390ms
Thread[pool-1-thread-9,5,main]:5327ms
Thread[pool-1-thread-8,5,main]:5379ms
Thread[pool-1-thread-5,5,main]:5380ms
Thread[pool-1-thread-3,5,main]:5390ms
Thread[pool-1-thread-7,5,main]:5359ms
Thread[pool-1-thread-4,5,main]:5380ms
Thread[pool-1-thread-6,5,main]:5358ms
Thread[pool-1-thread-2,5,main]:5379ms
Thread[pool-1-thread-10,5,main]:5379ms

Copy

取模(%)(10个线程):

Thread[pool-1-thread-5,5,main]:8953ms
Thread[pool-1-thread-1,5,main]:8953ms
Thread[pool-1-thread-9,5,main]:8894ms
Thread[pool-1-thread-10,5,main]:8902ms
Thread[pool-1-thread-6,5,main]:8953ms
Thread[pool-1-thread-3,5,main]:8953ms
Thread[pool-1-thread-2,5,main]:8953ms
Thread[pool-1-thread-8,5,main]:8921ms
Thread[pool-1-thread-7,5,main]:8893ms
Thread[pool-1-thread-4,5,main]:8953ms

Copy

测试方法是开启多个线程,每个线程各自循环1亿次调用next方法获取ID。

评论区
Rick ©2018