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

html5 • • 问答

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

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 条件周围添加同步块/方法。使用并发 api 而不使用任何类型的锁来解决这个问题的其他高效方法是什么？

如何摆脱 while 循环，以便我们可以在没有或更少线程争用的情况下获得下一个值？

约束：

下一个 db 序列将按递增顺序排列，不一定均匀分布。所以它可能是 1、11、31，其中 21 可能是其他节点询问的。请求的下一个值将始终是唯一的。还需要确保所有序列都被使用，一旦我们达到前一个范围的最大值，则只向 db 请求另一个起始序列，依此类推。

例子 ：

对于增量为 10 的 db next 序列 1,11,31，对于 30 个请求，输出的 next 序列应为 1-10、11-20、31-40。

回答

首先：我建议再考虑一次使用synchronized，因为：

  1. 看看这样的代码有多简单： 
     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;
 }
  2. java中的锁实际上非常智能并且具有非常好的性能。
  3. 您在代码中与 DB 交谈——仅此一项的性能成本可能比锁的性能成本高出几个数量级。

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

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时间
  • 更多类似问题

解决这些问题中的每一个都可能会使您的代码变得越来越复杂。

所以，恕我直言，这几乎是不值得的——锁可以正常工作并保持代码简单。

  • I don't get why anyone would upvote this. there are multiple threads that will call `newStateFromDb` without actually succeeding on this : `(stateHolder.compareAndSet(oldState, newState))`; which means this algorithm is broken. If any of the upvoters sees that I am wrong, please tag me in a comment below.
  • @Eugene You are correct. The question has to make it absolutely clear that implementations should not waste any sequence(and so the range) fetched from db. `Also need to make sure all the sequences are used and once we reach the max for previous range then only request to db for another starting sequence and so on` Though this from question is nearly clear, an example will be really helpful. So, assuming there are 2 application servers, then it should be guaranteed that all the values from `1,2, ...infinite` will be returned as `id`(they can be intermixed, but can't be mixed)
以上是如何在不使用同步（无锁序列计数器实现）的情况下修复竞争条件？的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>