java - 如何在不使用同步(无锁序列计数器实现)的情况下修复竞争条件？

Question

有一个场景，其中多个线程在比较代码上有竞争条件。

private int volatile maxValue;
private AtomicInteger currentValue;

public void constructor() {
   this.current = new AtomicInteger(getNewValue());
}

public getNextValue() {
  while(true) {
     int latestValue = this.currentValue.get();
     int nextValue = latestValue + 1;
     if(latestValue == maxValue) {//Race condition 1 
       latestValue = getNewValue();
     }
    if(currentValue.compareAndSet(latestValue, nextValue) {//Race condition 2
      return latestValue;
    }
  }
}

private int getNewValue() {
    int newValue = getFromDb(); //not idempotent
    maxValue = newValue + 10;
    return newValue;
}

问题:
解决此问题的明显方法是在 if 条件周围添加同步块(synchronized block)/方法。在不使用任何类型的锁的情况下，使用并发 api 解决此问题的其他高性能方法是什么？
如何摆脱 while 循环，以便我们可以在没有或更少线程争用的情况下获得下一个值？
约束:
下一个 db 序列将按递增顺序排列，不一定均匀分布。因此它可能是 1、11、31，其中 21 可能已被其他节点询问。请求的下一个值将始终是唯一的。还需要确保所有序列都被使用，一旦我们达到先前范围的最大值，然后只向 db 请求另一个起始序列，依此类推。
示例:
对于增量为 10 的 db next 序列 1、11、31，对于 30 个请求，输出的下一个序列应该是 1-10、11-20、31-40。

Answer 1

首先:我建议再考虑一下使用synchronized。 ， 因为:

看看这样的代码有多简单:

 private int maxValue;
 private int currentValue;

 public constructor() {
   requestNextValue();
 }

 public synchronized int getNextValue() {
   currentValue += 1;
   if (currentValue == maxValue) {
     requestNextValue();
   }
   return currentValue;
 }

 private void requestNextValue() {
   currentValue = getFromDb(); //not idempotent
   maxValue = currentValue + 10;
 }

Java中的锁实际上是pretty intelligent并拥有 pretty good performance .

您在代码中与 DB 对话——仅此一项的性能成本就可能比锁的性能成本高几个数量级。

但总的来说，您的竞争条件发生是因为您更新了 maxValue和 currentValue独立。
您可以将这两个值组合成一个不可变对象(immutable对象)，然后以原子方式使用该对象:

private final AtomicReference<State> stateHolder = new AtomicReference<>(newStateFromDb());

public int getNextValue() {
  while (true) {
    State oldState = stateHolder.get();
    State newState = (oldState.currentValue == oldState.maxValue)
        ? newStateFromDb()
        : new State(oldState.currentValue + 1, oldState.maxValue);
    if (stateHolder.compareAndSet(oldState, newState)) {
      return newState.currentValue;
    }
  }
}

private static State newStateFromDb() {
  int newValue = getFromDb(); // not idempotent
  return new State(newValue, newValue + 10);
}


private static class State {

  final int currentValue;
  final int maxValue;

  State(int currentValue, int maxValue) {
    this.currentValue = currentValue;
    this.maxValue = maxValue;
  }
}

修复该问题后，您接下来可能必须解决以下问题:

如何防止多个并行getFromDb(); (特别是考虑到方法是幂等的)

当一个线程执行getFromDb(); ，如何防止其他线程在里面忙转while(true)循环并消耗所有可用的 cpu 时间

更多类似问题

解决这些问题中的每一个都可能会使您的代码越来越复杂。
所以，恕我直言，这几乎是不值得的——锁可以正常工作并保持代码简单。