Доброго времени суток, уважаемый хабрачитатель.
В один прекрасный рабочий день начальство поставило задачу добавить в разрабатываемую нами систему возможность использовать несколько серверов для повышения производительности. Разворачивать кластер и осуществлять балансировку за счет специализированных средств возможности не было. Поэтому пришлось придумывать свою реализацию, используя алгоритм 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:
Старый график тут. Исследования тогда проводились на более медленном компе.
