Доброго времени суток, уважаемый хабрачитатель.
В один прекрасный рабочий день начальство поставило задачу добавить в разрабатываемую нами систему возможность использовать несколько серверов для повышения производительности. Разворачивать кластер и осуществлять балансировку за счет специализированных средств возможности не было. Поэтому пришлось придумывать свою реализацию, используя алгоритм round-robin.
Исходя из архитектуры приложения было принято решение, что балансировку нужно осуществить проходя по списку серверов, которые задаются в конфигурации, и выдавать на новый запрос адрес следующего сервера.
Этот принцип лежит в основе алгоритма round-robin.
Проведя поиск в интернете, я нашел много вариантов реализации данного алгоритма, которые сводились к следующему коду:
Здесь objectList — это список доступных серверов.
В данной реализации мне не понравилось использование synchronized метода, поэтому мной была предложена следующая реализация:
Теперь непосредственно получившийся код (спасибо за совет relgames):
Для проверки работоспособности данной реализации под нагрузкой была написана небольшая программка.
Методика тестирования заключалась в том, что выполнялось 1 000 000 запросов на получения адреса сервера при разном количестве потоков (от 1 до 991) и измерялось среднее время получения адреса.
Результаты представлены в виде графика и их можно посмотреть тут.
Исходники для экспериментов тут.
Данные, на основе которых построены графики, тут.
Спасибо за внимание.
P.S. Предложенный вариант реализации работает одинаково стабильно как при работе в однопоточной системе, так и при работе в многопоточной системе, что хорошо видно на графике. Это и есть основное преимущество данной реализации.
UPD:
Старый график тут. Исследования тогда проводились на более медленном компе.
В один прекрасный рабочий день начальство поставило задачу добавить в разрабатываемую нами систему возможность использовать несколько серверов для повышения производительности. Разворачивать кластер и осуществлять балансировку за счет специализированных средств возможности не было. Поэтому пришлось придумывать свою реализацию, используя алгоритм round-robin.
Алгоритм
Исходя из архитектуры приложения было принято решение, что балансировку нужно осуществить проходя по списку серверов, которые задаются в конфигурации, и выдавать на новый запрос адрес следующего сервера.
Этот принцип лежит в основе алгоритма round-robin.
Реализация
Проведя поиск в интернете, я нашел много вариантов реализации данного алгоритма, которые сводились к следующему коду:
public synchronized Entity getNext_Iterator(){
if (!it.hasNext()) {
it = objectList.iterator();
}
return it.next();
}
Здесь objectList — это список доступных серверов.
В данной реализации мне не понравилось использование synchronized метода, поэтому мной была предложена следующая реализация:
- При инициализации создается список доступных серверов и сохраняется длина этого списка. Создается глобальный счетчик с типом данных AtomicInteger и начальным значением 0
- При запросе адреса сервера счетчик увеличивается на 1. Если получившееся значение превышает длину списка, то обнуляем счетчик. Значение этого счетчика используем, как индекс в списке.
Теперь непосредственно получившийся код (спасибо за совет 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;
}
}
Для проверки работоспособности данной реализации под нагрузкой была написана небольшая программка.
Методика тестирования заключалась в том, что выполнялось 1 000 000 запросов на получения адреса сервера при разном количестве потоков (от 1 до 991) и измерялось среднее время получения адреса.
Результаты представлены в виде графика и их можно посмотреть тут.
Исходники для экспериментов тут.
Данные, на основе которых построены графики, тут.
Спасибо за внимание.
P.S. Предложенный вариант реализации работает одинаково стабильно как при работе в однопоточной системе, так и при работе в многопоточной системе, что хорошо видно на графике. Это и есть основное преимущество данной реализации.
UPD:
Старый график тут. Исследования тогда проводились на более медленном компе.