Implementing Java's round-robin thread-safe algorithm

Good day, dear habrachititel.
One fine day the bosses set the task to add the ability to use several servers to the system we are developing. There was no opportunity to expand the cluster and carry out balancing at the expense of specialized funds. Therefore, I had to invent my own implementation using the round-robin algorithm.

Algorithm

Based on the architecture of the application, it was decided that the balancing should be carried out passing through the list of servers that are specified in the configuration and issue the address of the next server to the new request.

This principle underlies the round-robin algorithm.

Implementation

Having conducted a search on the Internet, I found many options for implementing this algorithm, which boiled down to the following code:

public synchronized Entity getNext_Iterator(){ if (!it.hasNext()) { it = objectList.iterator(); } return it.next(); } 

')
Here objectList is a list of available servers.

In this implementation, I did not like the use of the synchronized method, so I proposed the following implementation:

1. During initialization, a list of available servers is created and the length of this list is saved. A global counter is created with the AtomicInteger data type and an initial value of 0
2. When a server address is requested, the counter is incremented by 1. If the resulting value exceeds the length of the list, then reset the counter. The value of this counter is used as an index in the list.

Now get the code directly (thanks for the advice relgames ):

  private final AtomicInteger position = new AtomicInteger(0); private volatile int listSize; ... public synchronized void init(List<Entity> objects) { ... listSize = objectList.size(); ... } } public Entity getNext() { return objectList.get(getNextPosition()); } public final int getNextPosition() { for (;;) { int current = position.get(); int next = current + 1; if(next >= listSize){ next = 0; } if (position.compareAndSet(current, next)) return current; } } 

To test the performance of this implementation under load, a small program was written.
The testing methodology consisted in the fact that 1,000,000 requests were made to get the server address with a different number of threads (from 1 to 991) and the average time to get the address was measured.

The results are presented in the form of a graph and can be viewed here .
Sources for experiments here .
The data on which the graphs are based is here .

Thanks for attention.

PS The proposed embodiment works equally stably as when working in a single-threaded system, and when working in a multi-threaded system, which is clearly seen on the graph. This is the main advantage of this implementation.

UPD:
Old schedule here . Studies were then conducted on a slower computer.