How to fix race conditions without using synchronized (Lock free sequence counter implementation)?

Question

Have a scenario where multiple threads have race condition on comparison code.

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;
}

Questions :

The obvious way to fix this would be add synchronized block/method around the if condition. What are other performant way to fix this using concurrent api without using any kind of locks ?

How to get rid of the while loop so we can get the next value with no or less thread contention ?

Constraints :

The next db sequences will be in increasing order not necessarily evenly distributed. So it could be 1, 11, 31 where 21 may be have asked by other node. The requested next value will always be unique. 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.

Example :

for db next sequences 1,11,31 with 10 increment, the output next sequence should be 1-10, 11-20, 31-40 for 30 requests.

Answer 1

First of all: I would recommend thinking one more time about using synchronized, because:

1. look at how simple such code is:

    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. locks in java actually are pretty intelligent and have pretty good performance.
3. you talk to DB in your code — the performance cost of that alone can be orders of magnitude higher than the performance cost of locks.

But in general, your race conditions happen because you update maxValue and currentValue independently.
You can combine these 2 values into a single immutable object and then work with the object atomically:

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;
  }
}

After fixing that you will probably have to solve the following problems next:

• how to prevent multiple parallel getFromDb(); (especially after taking into account that the method is idempotent)
• when one thread performs getFromDb();, how to prevent other threads from busy spinning inside while(true) loop and consuming all available cpu time
• more similar problems

Solving each of these problems will probably make your code more and more complicated.

So, IMHO it is almost never worth it — locks work fine and keep the code simple.